From: an31185@anon.penet.fi (Anon of Ibid)
Date: Wed, 15 Sep 93 11:24:22 PDT
To: cypherpunks@toad.com
Subject: Re: Testing randomness of PGP-generated IDEA keys
Message-ID: <9309151822.AA11900@anon.penet.fi>
MIME-Version: 1.0
Content-Type: text/plain


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.