mjr@TIS.COM said:
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.
Yeah, this is a good point. I was assuming that there was no simple way of determining the possible keys from the time and other information you'd get with a random PGP-encrypted file that you wanted to crack. *If* that is the case, then looking at the output of the PRNG is useful to show that the worst-case of a brute force attack using all possible keys cannot be improved by taking the relative frequencies into account when creating the possible keys. It would be embarassing if 0x2A appeared 100 times more frequently than any other byte value, or if there was a strong correlation between the bytes in each key, for example. Whatever the case, we can probably write off any idea of brute force attack like the DES one, unless you have a few billion years to play with. (In which case, you'll do better attacking the RSA key anyway)
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:
[ Description deleted ]
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.
Yes, obviously you're right. PGP seems to take the randseed.bin file, the MD5 of the input, and the current time, and munge all of them together using the IDEA encryption routines to create the final results. So, it's not at all clear how to test this end of things (one of the reasons why I decided to look at the output rather than the input). I'll have to poke around more in the code and see if I can work out what it's actually doing with all this stuff to get some idea of how to test it, if possible. The contents of randseed.bin are created by generating some random bytes using the same generation routine as the key and encrypting it with the key, so they should be as random as the sample I created. I could easily rewrite the program to generate the files and just calculate the MD5 and look at that, but, like you, I'm not sure that will tell us anything. Still, I can easily afford the CPU time, so it might be worthwhile anyway. Overall, I'm willing to accept that the key generation works pretty well at this point. What bearing might this have on the suggestions of using electronic cheques (presumably encrypted with PGP) ? If the cheque is a standard format, that might open up some possibilities with this kind of approach, especially if you know who it came from and/or who it's payable to.
My hat is off to the guy who came up with the idea of seeding the PRNG with the message. That was *clever*.
mjr.
Definitely. In fact, I wonder if this explains the 'fatal flaw' that people have mentioned. According to the comments in the code, the MD5 was introduced as an improvement over the previous method of generating the key, so perhaps there really was a flaw in this key generation that has now been fixed, or at least greatly improved. ------------------------------------------------------------------------- To find out more about the anon service, send mail to help@anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin@anon.penet.fi.