1993-01-27 - weak point of PGP implementation

Header Data

From: Eric Hughes <hughes@soda.berkeley.edu>
To: cypherpunks@toad.com
Message Hash: d30bbdaa05bb47b41bf306d25b1792baec62cf45042e60fdc2ccc28cb5974c6b
Message ID: <9301270327.AA17865@soda.berkeley.edu>
Reply To: <Pine.3.05.9301261648.A20494-b100000@stein2.u.washington.edu>
UTC Datetime: 1993-01-27 03:29:55 UTC
Raw Date: Tue, 26 Jan 93 19:29:55 PST

Raw message

From: Eric Hughes <hughes@soda.berkeley.edu>
Date: Tue, 26 Jan 93 19:29:55 PST
To: cypherpunks@toad.com
Subject: weak point of PGP implementation
In-Reply-To: <Pine.3.05.9301261648.A20494-b100000@stein2.u.washington.edu>
Message-ID: <9301270327.AA17865@soda.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain

Matt mentions three potential weaknesses in PGP: RSA key length, the
IDEA cypher, the pass phrase.  Let me add:

4. The random number generator used to make session keys.  If this is
weak, then an opponent might be able to guess them feasibly.  This attack
does not require breaking the underlying cryptography.

5. Weak random numbers for RSA key generation.  If the numbers in the
random number pool are not as random as they should be, then one might
simply simulate the prime generation algorithm and compile a table of
potential PGP primes.  Simply running trial division on this list
versus a storehouse of public keys might reveal common factors.  Even
running Euclid's algorithm to find g.c.d.'s on a such a storehouse
versus itself might produce factorizations.

From my quick reading of genprime.c, the PGP key generation algorithm
searches sequentially from a random starting point.  Thus it will tend
to find primes that are preceded by large blocks of composite numbers.
This alone reduces the search space some, possibly considerably.

Has anybody measured how good the keystroke timings are, anyway?