From: ghsvax!hal@uunet.UU.NET (Hal Finney)
Date: Fri, 4 Dec 92 10:03:39 PST
To: cypherpunks@toad.com
Subject: Re: Weakness of the PGP scheme ?
Message-ID: <9212041755.AA17036@nano.noname>
MIME-Version: 1.0
Content-Type: text/plain


Vanguard@gribb.hsr.no asks about trying all the IDEA keys.  If you
will look in idea.h you will see that the IDEA key is 16 bytes long,
which is 128 bits.  This is long enough to make trying them all
impossible.  Trying to predict one IDEA key by knowing the previous
one also looks hard, as PGP basically cycles IDEA on random input and
takes the output as the keys.  If you could predict this output it
would be similar to breaking IDEA.

On the other hand, PGP normally keeps its random information in a
small file called randseed.bin.  It uses the contents of this file
plus the current time of day in seconds as the input to generate the
IDEA key.  If you stole this file from someone (it's not
cryptographically protected, unlike the secret key ring), and you know
within several hours or a day when he sent each message, you could
probably calculate all possible IDEA keys in a feasible amount of time
(by trying all plausible values for the time of day in seconds).  This
would also let you calculate the new contents of the randseed.bin
file.  As long as you didn't miss any messages he sent, you could keep
doing this and break all of his outgoing messages.

You can prevent this by removing your randseed.bin file and
substituting an empty file (or one that is less than 16 bytes long) in
its place.  This will cause PGP to prompt you for random keyboard
input each time you send a message, which would make it impossible for
the attack above to work.  It would mean less convenience, though.

The relevant routines are make_random_ideakey() and
strong_pseudorandom() in crypto.c, as well as the code in random.c.

Hal
74076.1041@compuserv.ecom