From: mjr@TIS.COM
Date: Wed, 15 Sep 93 12:09:12 PDT
To: cypherpunks@toad.com
Subject: Re: Testing randomness of PGP-generated IDEA keys
Message-ID: <16690.9309151905@otter.TIS.COM>
MIME-Version: 1.0
Content-Type: text/plain


Anonymous writes:
>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.

	Assume the current time is a wash. Any message sent is going
to have an approximate time (in seconds) inserted in the header as
the MTA moves it, so that value is searchable trivially. For example,
this message nicely contains a timestamp:

Date: Wed, 15 Sep 1993 18:22:10 UTC

	I figure searching all the seeds within 12 hours of that will
eliminate the time as a seed, and that's only 84,000 searches, which
is huge orders of magnitude easier than searching DES. You don't even
need gnarly fictional $1.5million DES-searching machines to do it.

	That leaves the MD5 of the input and randseed.bin. The MD5 of
the input is by definition unknown to the attacker in MOST cases,
right? If you're using this for confidentiality, that is. If the
input is known, then you're left with just randseed.bin.

>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'm not entirely clear on this. It uses the same mechanism
as the key and feeds it back through itself? What is the input into
this process? Again: ignore the apparent randomness of the output,
you need to look at the unpredictability of the input seed. Randseed.bin
should be kept secret, clearly, as it's part of your key.

>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.

	If I know the layout of the check and know that the only values
that will change are a serial number which increases monotonically, and
a value, which averages around $1,000, I can probably crack your PRNG in
an hour or two, depending on how many processors I throw at it. Remember
that this parallelizes trivially. Also, when you crack the PRNG with a
public key system, you *KNOW* instantly that you've gotten the correct
key, so the entire process is very hands off.

	One way of thinking about the problem is trying to count how many
bits of unpredictability go into your PRNG seed. If you're willing to
assume your adversary can brute-force search DES' 56-bit keyspace, then
you'd better assume he's also willing to brute-force search your PRNG.
So figure you want more than 56 bits of pure unpredictability as your
seed. This is a tricky problem. One option is to give the user a typematic
buffer: "hit keys for 30 seconds" - you NEED unpredictability!

mjr.