<<

. 2
( 2)



is a close second. I would be very interested in seeing cryptanalytic results against
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.

<<

. 2
( 2)