<<

. 19
( 19 .)



MD5 with the time of day as the seed, for example,
Page 72
! N




formation that moves across a network that could be included as they occur. Re-seeding also frustrates
attackers
intercepted by a dedicated attacker. Mouse move- trying to find the seed state using a brute
ments on X-terminals, for example, may be avail- force attack. Since the seed will be change, say, ev-
able to anyone listening on the wire. ery thirty seconds, the seed state becomes a moving
target and makes the brute force attack infeasible.
Now we get to the issue of quantity. A developer The idea is to take the existing seed and mix it to-
cannot assume that all of the bits collected are truly gether with the new information as it becomes avail-
able.
random, so a useful rule of thumb is to assume that
for every byte of data collected at random, there is
Example
one bit of entropy. This may either be a bit conser-
vative, or a bit generous, depending on the source. A brief example is in order. The diagram in Figure 1
To illustrate this rule of thumb, take the example of illustrates how functions in BSAFE would be used to
user keystrokes, which many consider to be a go& generate random keying material.
source of randomness. Assuming ASCII keystrokes,
bit 7 will always be zero. Many of the letters can be
predicted: they will probably all be lowercase, and
will often alternate between left and right hand.
Analysis has shown that there is only one bit per
byte of entropy per keystroke.
B-GenerateRandomBytes
To guard against this kind of analysis, the idea is to
collect one byte of seed for each bit required. This
information will be fed into the PRNG to produce
the first random output.

Asanexample,iftheseedwillbeusedtoproducea
random symmetric encryption key, the number of
random bytes in the seed should at least equal the
number of effective bits in the key. In the case of
DES, this would be 56 random bits culled from a The first step is to supply the pool of random seed
seed pool of 56 bytes. Any less and the number of bytes. Let™s assume that the application needs a
possible starting keys is reduced from 2% to some- random 80-bit RC2 key. Using the rule of thumb
thing smaller, reducing the amount of effort required that one byte of data yields one bit of randomn˜, a
minimum of 80 bytes will be needed for the pool.
by an attacker in searching the seed space by brute
force. Attacks like this have recently been widely This pool would be gathered from the sources listed
publicized on the Internet and in the press. For in Table 1. The B-RandomUpdate function in
public-key algorithms, the goal is to make search- BSAFE takes the seed pool and runs it through the
MD5 message digest algorithm to create the state.
ingfortheseedatleastasdifhcultasthehardmath-
ematical problem at their core. This will discour-
age attackers from searching for seeds instead of at- The state is then used by the function
tacking problems like factoring composite numbers B-GenerateRandomBytes, which runs it through
and calculating discreet Iogarithms. A seed of 128 MD5 to produce the key. This is the key that would
be used for RC2. As an added measure, BSAFE au-
bits (taken from a seed pool of 128 bytes) should be
more than enough for the modulus sizes being used tomatically advances the state after random bytes are
generated.
today.

Notice the arrow labeled “Update” within
One last thing that should be mentioned is updat-
ing the seed, or ?-e-seeding.” It makes sense to al- B-RandomUpdate. This is where reseeding is done.
low an application to add seed bits as they become By calling B-RandomUpdate again, the state can ti
available. User events often provide additional mixed with more seed information. Random infor-
sources of randomness, but obviously have not taken mation like key timing and mouse movement can be
place when an application starts. These should be used here, along with changes in the system statis-
Page 73


Further Reading
tics, clock, and various files. Now the next RC2 key
generatedwillbebasedonnewseedmaterialaswell For more information on random numbers and ayp-
as the old. tography, take a look at the following:

Conclusion Donald FasTlake, Steve Crwker, J& !3chiUer, “Random-
Done properly, random number generation in soft- ness Recommendations for Security,” IETF RFC 1750,
ware can provide the security necessary for most 1994
cryptographic systems. Using a good PRNG and Ian Goldberg and David Wagner, “Randomness ardthe
choosing good seed material are the two critical Netscape Bmwseq,“Dr Lhbb˜Joutnal, Jam˜a˜y 19%
Donald E. Knuth, 7&e A# of Computw Programming:
points.
Seminumerfcal A&oritbms, Addison-Wesley, Reading,
Developers may wish to create a set of routines to MA, 1981
Cdin Plumb, ˜Th˜ly Random Numbs,” Lh: II&b™s Jour-
pull random and unique information from the oper-
ating system, which can then be used in any applica- nal, November 1994
RSA Data Security, Inc., BSAFE C&r™s Manual, Ver-
tions requiring ciyptogmphy. It may be desirable to
save encrypted seed state for use in subsequent ses- sion 3.0,1996
Bruce Schneier, Applied Cgpograpby, John Wiley &
sions.
Sons, Inc., New York, 1995
Over time, as the need for cryptogmphy in sofbvare
“._.“.” .-.--_.-. “.” . .” . .” . _. . . ._. . . . . -- --.-___.“““.” . .” . ,. . _, ,I
increases, hardware and operating system vendors
i----™For more information on this and other recent
may provide more tools and hooks for random infor-
mation. In the meantime, however, the techniques
described can be used. developments in qptogmphy. contact RSA L&c-
ratori˜atoneofthe˜bekYw.

RSA-
100 Marine Parkway, Suite 540
Redwood City, CA 94065 USA
4151595703
415/595a26 (fax)
txl-.m
bt@˜wwummwkhom/tsalabs/

<<

. 19
( 19 .)