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 wrote a program to read in /usr/dict/words, and loop around generating files containing a random number (using the unix random() call) of random sentences using the words in the dictionary, and encrypt them with a test 384-bit key. The copy of PGP I was using was modified to dumped the 24-byte key/random prefix combination into a file, which the main program read out and processed. Firstly, it maintained a table of counts for each byte value, and secondly (since I gave up statistics years ago), XOR-ed all the bytes in each 24-byte sample together and maintained a table of frequency of XOR values as a simple check for randomness in each 24-byte sample. After running for a few days, the results were: Total bytes generated : 3000504 (125021 runs) Frequency : High: 11960 Low : 11377 Mean: 11721 Spread: 584 (4 %, +2 %, -2 %) Within 50% of mean : 2505989 (83 %) XOR Freq : High: 553 Low : 432 Mean: 488 Spread: 122 (25 %, +13 %, -11 %) Within 50% of mean : 107652 (86 %) Since, as I said, I'm not a statistician, my definitions of the above categories are : Mean - expected frequency, i.e. total number of bytes generated/256, Spread - absolute difference between frequencies of rarest and most common byte values, plus difference as percentage of mean, and spread above and below the mean as a percentage of the mean (rounded to nearest) Lastly, the program summed the frequencies of the bytes whose frequency was between (mean-(mean-low)/2) and (mean+(high-mean)/2), giving the result as an absolute value and a percentage of the total number of bytes generated.
From this, it looks to me like the random number generation is, indeed, pretty random, and if you're trying to break an arbitrary PGP-encrypted file by a brute-force attack on the IDEA-encrypted section, then you don't have any shortcuts based on frequency of bytes in the key. If anyone with a better grasp of statistics wants the original data to look at (25k, containing 24 arrays of byte frequencies and one of XOR frequencies), let me know and I'll email it to you.
So, if there is a 'fatal flaw' in PGP, it looks like it must be either the known plaintext, or it must be somewhere in the prime generation code. Since I know nothing about fast methods of testing primality, someone else is going to have to look into that.... (Unless I get bored enough to hunt out some books on the subject) ------------------------------------------------------------------------- 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.