Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:17 ADT
bram (bram@gawth.com)
Sun, 12 Jul 1998 16:18:49 -0700 (PDT)
On Sat, 11 Jul 1998, Bill Frantz wrote:
> To toss my had into the current discussion of randomness, and to get a
> public vetting, let me describe a recent secure random generator I
> implemented.
Hmmm, another PRNG, once again highlighting how there's a need for more
academic work on the subject so people can stop coming up with ad hoc
ones.
> Assumptions and ground rules:
>
> (1) If we can get 160 bits of entropy, and keep it secret, we can maintain
> security on the DSA and DES keys we generate for the life of the
> application (20 years).
Assuming no breach of the cryptographic algorithms used, an accurate and
important observation.
> (2) Since we probably can't keep a secret for 20 years, we continuously
> stir new entropy into the generator.
Very important. Only seeding a PRNG once is a very easy mistake to make.
> Entropy is mixed using MD5. (The collision weakness reported should not
> effect its use as a mixing function.)
Although one might still want to not use it just on general principle.
> The entropy pool consists of an array of 16 MD5 hashes.
Why 16? You said earlier that you think 160 bits of entropy is enough, so
it's questionable what having a larger pool buys you. I think having a 160
bit pool and using a technique based on sha1 or ripemd160 can make a
perfectly good PRNG.
> Each time new entropy is added to the pool, we replace the next hash (in
> a circular manner) with MD5(entire pool || new entropy || current value
> of the CPU cycle counter).
In general, you want to hash any new entropy coming in before
incorporating it, to thwart malicious attackers who have the ability to
feed arbitrary bit strings into your PRNG.
Also, it's important to maintain a pool of entropy outside your the core
of your PRNG for putting new entropy into and only incorporate it when
it's entropy count gets high enough, to prevent continuation attacks.
Consider the case where an attacker finds out your internal state and can
see all output from the PRNG and all entropy is being added in one bit
chunks. If the attacker gets to see at least some output after each new
piece of entropy is added, he on average only needs to make one guess as
to what the added bitstring was before being able to confirm it based on
output. If, on the other hand, the strings containing entropy were
combined together and only used once their combined entropy hit 160 bits,
the attacker would be totally lost.
Finally, and least importantly, are you xoring at the beginning or the end
of the pool? Doing it at the beginning results in better compounding.
> When we generate a random number, we compute enough MD5(entire pool || 8
> byte sequence counter) to meet fill the requested size. The 8 byte
> sequence counter is incremented for each new calculation.
Unfortunately that can result in hashing a large number of similar
bitstrings, making those available is an attack most hash functions aren't
really meant to withstand.
> We currently use two sources of entropy:
Actually, you use 3. You already mentioned use of the cycle counter, which
while strictly speaking is deterministic it can be very difficult for an
attacker to keep track of exactly what it's at.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:17 ADT