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.