From: mjr@TIS.COM
Date: Tue, 14 Sep 93 20:00:08 PDT
To: cypherpunks@toad.com
Subject: Re:  Testing randomness of PGP-generated IDEA keys
Message-ID: <13737.9309150258@otter.TIS.COM>
MIME-Version: 1.0
Content-Type: text/plain


>Hi, you may remember a few weeks back I was going to take a look at
>the randomness of PGP random number generation.... well, I finally
>got round to it. Since the MD5 of the file being encrypted is used
>as part of the random number generation process to prevent anyone 
>copying the randseed.bin file and generating all future keys from it, [...]

	I found myself embroiled in a similar exploration of random
number generation as part of some other work, and it took me a while
to realize that running statistics on the output of the PRNG is
almost useless, if you're using a cryptosystem or cryptographic hash
as the PRNG. With any decent cryptosystem, one bit change in the
input to the PRNG will cause every bit of the output to have a
50% chance of being different - that's a desirable property in a
cryptosystem. DES, and I assume IDEA, show this property.

	What you've got to look at is the predictability of the
input to the PRNG. PGP is in really good shape here, because it
bootstraps its PRNG with its input, which presumably is unknown
to the attacker. An example of a weak PRNG would be:

	`date | md5`

	For example:

otter-> cat foo
#!/bin/sh
date | /usr/local/bin/md5
date | /usr/local/bin/md5
sleep 1
date | /usr/local/bin/md5
otter-> foo
f4a66f827a8e62ad9c419f7e2117abc6
f4a66f827a8e62ad9c419f7e2117abc6
bcfa24d319ccdcad56a99be2e203e787

	As you expect the first two runs are exactly the same.
The second run is completely different. The seed, however, is
only very slightly changed (by one second). You could run
statistical analyses on the output for a long time and never
realize that your random number is really extremely easy to
crack. If I knew roughly what day you generated the "random"
number on, I could crack it in only 86,400 MD5 hashes, and
it's an operation that parallelizes trivially. *MUCH* cheaper
to attack the PRNG than the cryptosystem! And if you used a
toy PRNG to generate your RSA key, then you're lunchmeat.

	Anyhow, I've been over-long winded. I think PGP is
in good shape because of the aforementioned property of
using the message as a seed. Messages that don't change
much, or that change predictably, are subject to exhaustive
searching. A means of analysing the unpredictability of
the seed is more worthwhile. I made some basic starts at
doing this by ad hoc measures (generating repeated seeds
and running them through a program to count a minimum-bit
edit similar to diff) but I wasn't sure enough of the
validity of my approach to bother continuing it. My hat
is off to the guy who came up with the idea of seeding
the PRNG with the message. That was *clever*.

mjr.