From: an31185@anon.penet.fi (Anon of Ibid)
Date: Tue, 14 Sep 93 16:59:04 PDT
To: cypherpunks@toad.com
Subject: Testing randomness of PGP-generated IDEA keys
Message-ID: <9309142358.AA14909@anon.penet.fi>
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 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.