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
participants (3)
-
Eric Hughes -
The Phantom -
uri＠watson.ibm.com