my generators that combine LFSRs and FCSRs; this seems to be a very fruitful area

of stream-cipher research to mine for actual designs. Or, you can use a block cipher

in OFB or CFB to get a stream cipher.

Table 17.3 gives some timing measurements for some algorithms. These are

meant for comparison purposes only.

17.13 GENERATING MULTIPLE STREAMS FROM A SINGLE

PSEUDO-RANDOM-SEQUENCE GENERATOR

If you need to encrypt multiple channels of communications in a single box-

a multiplexer, for example-the easy solution is to use a different pseudo-random-

sequence generator for each stream. This has two problems: It requires more hard-

ware, and all the different generators have to be synchronized. It would be simpler

to use a single generator.

Table 17.3

Encryption Speeds of Some

Stream Ciphers on a 33MHz 486SX

Algorithm Encryption Speed (Kilobytes/Second)

A5 5

PIKE 62

RC4 164

SEAL 381

Page 420

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17.14 Real Random-Sequence Generators

One solution is to clock the generator multiple times. If you want three indepen-

dent streams, clock the generator three times and send 1 bit into each stream. This

technique works, but you may have trouble clocking the generator as fast as you

would like. For example, if you can only clock the generator three times as fast as

the data stream, you can only create three streams. Another way is to use the same

sequence for each channel-perhaps with a variable time delay. This is insecure.

A really clever idea [ 14891, patented by the NSA, is shown in Figure 17.11. Dump

the output of your favorite generator into an m-bit simple shift register. At each

clock pulse, shift the register one to the right. Then, for each output stream, AND

the register with a different m-bit control vector viewed as a unique identifier for

the desired output stream, then XOR all the bits together to get the output bit for

that stream. If you want several output streams in parallel, you need a separate con-

trol vector and an XOR/AND logic array for each output stream.

There are some things to watch out for. If any of the streams are linear combina-

tions of other streams, then the system can be broken. But if you are clever, this is

an easy and secure way to solve the problem.

17.14 REAL RANDOM-SEQUENCE GENERATORS

Sometimes cryptographically secure pseudo-random numbers are not good enough.

Many times in cryptography, you want real random numbers. Key generation is a

prime example. It™s fine to generate random cryptographic keys based on a pseudo-

rlGenerator

... I

m-Bit

Control Control Control

output

Vector 1 Vector 2 Vector n

I Stream 1 Stream 2 Stream n

Figure 17.12 Multiple-bit generator.

Page 421

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17 Other Stream Ciphers

CHAPTER

random sequence generator, but if an adversary gets a copy of that generator and the

master key, the adversary can create the same keys and break your cryptosystem, no

matter how secure your algorithms are. A random-sequence generator™s sequences

cannot be reproduced. No one, not even you, can reproduce the bit sequence out of

those generators.

There is a large philosophical debate over whether any of these techniques actu-

ally produces real random bits. I am not going to address that debate. The point here

is to produce bits that have the same statistical properties as random bits and are not

reproducible.

The important thing about any real random-sequence generator is that it be

tested. There is a wealth of literature on this topic. Tests of randomness can be

found in [863,99]. Maurer showed that all these tests can be derived from trying to

compress the sequence [ 103 1,1032]. If you can compress a random sequence, then it

is not truly random.

Anyhow, what we have here is a whole lot of black magic. The primary point is to

generate a sequence of bits that your adversary is unlikely to guess. It doesn™t sound

like much, but it™s harder than you think. I can™t prove that any of these techniques

generates random bits. These techniques produce a sequence of bits that cannot be

easily reproduced. For some details, see [ 1375,1376,511].

RAND Tables

Back in 1955, when computers were still new, the Rand Corporation published a

book that contained a million random digits [1289]. Their method is described in

the book:

The random digits in the book were produced by rerandomization of a basic table

generated by an electronic roulette wheel. Briefly, a random frequency pulse

source, providing on the average about 100,000 pulses per second, was gated about

once per second by a constant frequency pulse. Pulse standardization circuits

passed the pulses through a 5place binary counter. In principle the machine was

a 32-place roulette wheel which made, on the average, about 3000 revolutions per

trial and produced one number per second. A binary-to-decimal converter was

used which converted 20 of the 32 numbers (the other twelve were discarded] and

retained only the final digit of two-digit numbers; this final digit was fed into an

IBM punch to produce finally a punched card table of random digits.

The book goes on to discuss the results of various randomness tests on the data.

It also suggests how to use the book to find a random number:

The lines of the digit table are numbered from 00000 to 19999. In any use of the

table, one should first find a random starting position. A common procedure for

doing this is to open the book to an unselected page of the digit table and blindly

choose a five-digit number; this number with the first digit reduced modulo 2 deter-

mines the starting line; the two digits to the right of the initially selected five-digit

number are reduced modulo 50 to determine the starting column in the starting

line. To guard against the tendency of books to open repeatedly at the same page

and the natural tendency of a person to choose a number toward the center of the

Page 422

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17.14 Real Random-Sequence Generators

page: every five-digit number used to determine a starting position should be

marked and not used a secondtime for this purpose.

The meat of the book is the “Table of Random Digits.” It lists them in 5digit

groups-“10097 32533 76520 13586. . .“- 50 on a line and 50 lines on a page. The

table goes on for 400 pages and, except for a particularly racy section on page 283

which reads “69696,” makes for a boring read. The book also includes a table of

100,000 normal deviates.

The interesting thing about the RAND book is not its million random digits, but

that they were created before the computer revolution. Many cryptographic algo-

rithms use arbitrary constants-so-called “magic numbers.” Choosing magic num-

bers from the RAND tables ensures that they haven™t been specially chosen for

some nefarious reason. Khafre does this, for example.

Using Random Noise

The best way to collect a large number of random bits is to tap the natural ran-

domness of the real world. Often this method requires specialized hardware, but you

can play tricks with computers.

Find an event that happens regularly but randomly: atmospheric noise peaking at

a certain threshold, a toddler falling while learning to walk, or some such. Measure

the time interval between one event and the next event. Record it. Measure the time

interval between the second event and the third event. Record it as well. If the first

time interval is greater than the second, output 1 as the bit. If the second time inter-

val is greater than the first, output 0 as the event. Do it again for the next event.

Throw a dart at the New York Stock Exchange closing prices in your local news-

paper. Compare the closing price of the stock you hit with the closing price of the

stock directly above it. If the one you hit is more, output 0; if it less, output 1.

Hook a Geiger counter up to your computer, count emissions over a fixed time

interval, and keep the least significant bit. Or measure the time between successive

ticks. (Since the radioactive source is decaying, the average time between successive

ticks is continuously getting longer. You want to choose a source with the half life

long enough to make this negligible-like plutonium. Or, if you™re worried about

your health, you can apply appropriate statistical corrections.)

G. B. Agnew proposed a real random-bit generator, suitable for integration into a

VLSI device [21]. It is a metal insulator semiconduction capacitor (MISC). Two of

them are placed in close proximity, and the random bit is a function of the differ-

ence in charge between the two. Another random-number generator generates a ran-

dom-bit stream based on the frequency instability in a free-running oscillator [535].

A commercial chip from AT&T generates random numbers from the same phe-

nomenon [67]. M. Gude built a random-number generator that collected random

bits from physical phenomena, such as radioactive decay [668,669]. Manfield

Richter developed a random-number generator based on thermal noise from a semi-

conductor diode [ 13091.

Supposedly the time intervals between successive 2e4 light emissions from a

trapped mercury atom are random. Use that. Better yet, find a semiconductor com-

pany that makes random-number-generation chips; they are out there.

Page 423

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17 Other Stream Ciphers

CHAPTER

There is also a random-number generator that uses the computer™s disk drive

[439]. It measures the time required to read a disk block and uses the variation in

that time as a random number source. It filters the timing data to remove structure

that comes from quantization, then applies a fast Fourier transform to vectors of the

numbers. This removes bias and correlation. Finally, it uses the spectral angles for

frequencies in (0, ˜rr),normalized to the unit interval, as the random bits. A large part

of the variation in disk rotation speed is caused by air turbulence, so there is ran-

domness in the system. There are caveats, though. If you keep too many bits of the

output, you are using the fast Fourier transform as a random-number generator and

risk predictability. And it™s best to read the same disk block over and over, so that

your filtering doesn™t have to remove structure that comes from the disk-scheduler.

An implementation of this system was able to collect about 100 bits per minute

[439].

Using the Computer™s Clock

If you want a single random bit (or even a few), take the least significant bit from

any clock register. This might not be terribly random in a UNIX system because of

various potential synchronizations, but it works on some personal computers.

Beware of getting too many bits this way. Executing the same subroutine several

times in succession could easily skew bits generated in this manner. For example, if

each bit generation subroutine takes an even number of clock ticks to execute, you

will get an endless stream of the same bit out of the generator. If each subroutine

takes an odd number of clock ticks to execute, you will get an endless stream of

alternating bits out of the generator. Even if the resonance isn™t this obvious, the

resultant bit stream will be far from random.

One random-number generator works this way [918]:

Our truly random number generator . . . works by setting an alarm and then

incrementing a counter register rapidly in the CPU until an interrupt occurs. The

contents of the register are then XORed with the contents of an output buffer byte

(truncating the register™s data to 8 bits). After each byte of the output buffer is

filled, the buffer is further processed by doing a right, circular shift of each char-

acter by 2 bits. This has the effect of moving the most active (and random) least

significant bits into the most significant positions. The entire process is then

repeated 3 times. Finally each character of the buffer has been touched by the two

That is 4n interrupts

most random bits of the counter register after interrupts.

have occurred where n is the number of desired random bytes.

This method is very sensitive to the randomness of system interrupts and the

granularity of the clock. The output looked pretty good when tested on real UNIX

machines.

Measuring Keyboard Latency

People™s typing patterns are both random and nonrandom. They are nonrandom

enough that they can be used as a means of identification, but they are random

enough that they can be used to generate random bits. Measure the time between

Page 424

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17.14 Real Random-Sequence Generators

successive keystrokes, then take the least significant bits of those measurements.

These bits are going to be pretty random. This technique may not work on a UNIX

terminal, since the keystrokes pass through filters and other mechanisms before

they get to your program, but it will work on most personal computers.

Ideally, you only want to collect one random bit per keystroke. Collecting more

may skew the results, depending on how good a typist is sitting at the keyboard.

This technique is limited, though. While it™s easy to have someone type 100 words

or so when it is time to generate a key, it isn™t reasonable to ask the typist to type a

lOO,OOO-wordessay to generate a keystream for a one-time pad.

Biases and Correlations

A major problem with all these systems is that there could be nonrandomness in

the generated sequence. The underlying physical processes might be random, but

many kinds of measuring instruments are between the digital part of the computer

and the physical process. Those instruments could easily introduce problems.

A way to eliminate bias, or skew, is to XOR several bits together. If a random bit

is biased toward 0 by a factor e, then the probability of 0 can be written as:

P(0) = 5 + e

XORing two of these bits together yields:

P(0) = (S + e)” + (5 - e)” = .5 + 2e2

By the same calculation, XORing 4 bits together yields:

P(0) = .5 + 8e4

XORing m bits will exponentially converge to an equal probability of 0 and 1. If you

know the maximum bias you are willing to accept for your application, you can cal-

culate how many bits you need to XOR together to get random bits below that bias.

An even better method is to look at the bits in pairs. If the 2 bits are the same, dis-

card them and look at the next pair. If the 2 bits are different, take the first bit as the

output of the generator. This eliminates bias completely. Other techniques for reduc-

ing bias use transition mappings, compression, and fast Fourier transforms [511].

The potential problem with both methods is that if there is a correlation between

adjacent bits, then these methods will increase the bias. One way to correct this is

to use multiple random sources. Take four different random sources and XOR the

bits together; or take two random sources, and look at those bits in pairs.

For example, take a radioactive source and hook a Geiger counter to your com-

puter. Take a pair of noisy diodes and record as an event every time the noise

exceeds a certain peak. Measure atmospheric noise. Get a random bit from each and

XOR them together to produce the random bit. The possibilities are endless.

The mere fact that a random-number generator has a bias does not necessarily

mean that it is unusable. It just means that it is less secure. For example, consider

the problem of Alice generating a triple-DES 168-bit key. All she has is a random-bit

generator with a bias toward 0: It produces 55 percent OSand 45 percent 1s. This

means that there are only 0.99277 bits of entropy per key bit, as opposed to 1 bit of

Page 425

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17 Other Stream Ciphers

CHAPTER

entropy if the generator were perfect. Mallory, trying to break the key, can optimize

his brute-force search to try the most probable key first (000 . . . 0), and work toward

the least probable key (111 . . . 1). Because of the bias, Mallory can expect to find the

key in 21°9 attempts. If there were no bias, Mallory would expect to make 2111

attempts. The resultant key is less secure, but not appreciably so.

Distilling Randomness

In general, the best way to generate random numbers is to find a whole lot of

seemingly random events and distill randomness from them. This randomness can

then be stored in a pool or reservoir that applications can draw on as needed. One-

way hash functions are ready-made for the job; they™re fast, so you can shovel quite

a bit through them without worrying too much about performance or the actual ran-

domness of each observation. Hash almost anything you can find that has at least

some randomness. Try:

- A copy of every keystroke

- Mouse commands

- The sector number, time of day, and seek latency for every disk oper-

ation

- Actual mouse position

- Number of current scanline of monitor

- Contents of the actually displayed image

- Contents of FATS, kernel tables, and so on

- Access/modify times of /dev/tty

- CPU load

- Arrival times of network packets

- Input from a microphone

- /dev/audio without a microphone attached

If your system uses separate crystal oscillators for its CPU and time-of-day clocks,

try reading the time of day in a tight loop. On some (but not all) systems this will

reflect the random phase jitter between the two oscillators.

Since much of the randomness in these events is in their timing, use the most

finely grained time-of-day clock you can find. A standard PC uses an Intel 8254

clock chip (or equivalent) driven at 1.1931818 megahertz, so reading the counter

register directly gives you 83%nanosecond resolution. To avoid skewing the results,

avoid taking your event samples on a timer interrupt.

Here is the process in C with MD5 (see Section 18.5) as the hash function:

char Randpool[lGl;

/* Call early and call often on a wide variety of random or semi

* random system events to churn the randomness pool.

Page 426

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

* The exact format and length of randevent doesn't matter as long as

* its contents are at least somewhat unpredictable.

*/

void churnrandcchar *randevent,unsigned int randlen)

MD5-CTX md5;

MD5Init(&md5);

MD5Update(&md5,Randpool,sizeof(Randpool)I;

MD5Update(&md5,randevent,randlen);

MD5Final(Randpool,&md5);

After calling churnrand enough to build up sufficient randomness in Randpool,

you can now generate random bits from it. MD5 again comes in handy, this time as

a counter-mode pseudo-random byte-stream generator.

long Randcnt;

void genrandcchar *buf,unsigned int buflen)

MDS-CTX md5;

char tmpL161;

unsigned int n;

whilecbuflen != 0) 1

/* Hash the pool with a counter */

MD5Init(&md5);

MD5lJpdate(&md5,Randpool,sizeof(Randpool));

char *)&Randcnt,sizeof(Randcnt));

MD5Update(&md5,(unsigned

MD5Final(tmp,&md5);

Randcnt++; /* Increment counter */

/* Copy 16 bytes or requested amount, whichever is less,

* to the user's buffer */

n = (buflen < 16) ? buflen : 16;

memcpy(buf,tmp,n);

buf += n;

buflen -= n;

The hash function is crucial here for several reasons. First, it provides an easy way

to generate an arbitrary amount of pseudo-random data without having to call

churnrand each time. In effect, the system degrades gracefully from perfect to prac-

tical randomness when the demand exceeds the supply. In this case it becomes the-

oretically possible to use the result from one genrand() call to determine a previous

or subsequent result. But this requires inverting MD5, which is computationally

infeasible.

This is important since the routine doesn™t know what each caller will do with

the random data it returns. One call might generate a random number for a protocol

that is sent in the clear, perhaps in response to a direct request by an attacker. The

very next call might generate a secret key for an unrelated session that the attacker

Page 427

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

17 Other Stream Ciphers

CHAPTER

wishes to penetrate. Obviously, it is very important that an attacker not be able to

deduce the secret key from the nonce.

One problem remains. There must be sufficient randomness in the Randpool[]

array before the first call to genrand(). If the system has been running for a while

with a local user typing on the keyboard, no problem. But what about a standalone

system that reboots automatically without seeing any keyboard or mouse input?

This is a tough one. A partial solution would require the operator to type for a

while after the very first reboot, and to create a seed file on disk before shutting

down to carry the randomness in Randseed[] across reboots. But do not save the

Randseed[] array directly. An attacker who steals this file could determine all of the

results from genrand() after the last call to churnrand prior to the file being created.

The fix to this problem is to hash the Randseed[] array before storing it, perhaps

by just calling genrand(). When the system reboots, you read in the seed file, pass it

to churnrando, then promptly destroy it. Unfortunately, this does not deal with the

threat of someone stealing the seed file between reboots and using it to guess future

values of the genrand() function. I see no solution to this problem other than to wait

until enough external random events have taken place after a reboot before allowing

genrand() to produce results.