weak point of PGP implementation

tcmay says:

----
With strong crypto, e.g., with 300 decimal digit moduli, the "costs"
of decryption by brute force could easily exceed the GNP/GDP of the
U.S.
...
bagged" the house, perhaps a simple pass phrase was used in lieu of
memorizing 300 digits, and so on.
----

I've been wondering about this. It seems as though the weak point of PGP
is one of three possible things:

	1) RSA key length (a key length of 10 digits might be a good
target, but noone using pgp uses anything so absurdly small, so this can
be all but ruled out barring any huge jumps in factoring .. 

	2) 'conventional cryptography' used for encoding the secring.pgp
files, etc. What crypto, exactly, is used? How strong is it? If the NSA
knocked on the door and demanded your computer, would it try to crack your
key, or would it go directly for the secring.pgp file?

	3) length/triviality of pass phrase. This is, I would think, the
weakest point mentioned yet. How long does the pass phrase have to be
until this point becomes as secure as the weaker of the above two? If all
bits of your passphrase were random, how long would an exhaustive search
take? 

matt


Matt Thomlinson
University of Washington, Seattle, Washington.
Internet: phantom@u.washington.edu      	    phone: (206) 528-5732
PGP 2.0 key availaible via email or finger phantom@hardy.u.washington.edu

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?

Eric

Eric Hughes says:
> Matt mentions three potential weaknesses in PGP: RSA key length, the
> IDEA cypher, the pass phrase.

Probably the first two even a paranoid person won't call "weaknesses".
The pass-phrase - th docs should give some guidelines, as to how one
must choose his pass-phrase (if it's already there - apologies :-).

> Let me add:

And now you're talking! (:-)

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

It looks  like that [former] Soviet professor found and pointed out
exactly those weaknesses: poor RSA keys (making factoring about two
orders of magnitude easier) and poor something else (I couldn't
understand what he meant, sorry :-). Quite possible he hit
session keys (as likely as not)...
--
Regards,
Uri         uri@watson.ibm.com      scifi!angmar!uri 	N2RIU
-----------
<Disclamer>


From cypherpunks-request  Tue Jan 26 21:28:06 1993