Cracking PGP Myth Banishment Notes

by Route

PGP is a hybrid cryptosystem. It contains 4 crytpographic elements, each of which is subject to a different type of cryptographic attack. It contains a symmetric cipher, an asymmetric cipher, a one-way hash, and a random number generator.

-- The symmetric cipher --

IDEA, finalized in 1992 by Lai and Massey is strong. It is the toughest block cipher known of today. There have be no advances in the cryptanalysis of standard IDEA that are publically known. (I know nothing of what the NSA has done, nor does most anyone.)

The best method of attack, therefore, is brute force. As we all know the keyspace of IDEA is 128-bits. To recover a particular key, one must, on average, search half the keyspace. That is 127 bits. Fine. If you, for the sake of argument, had 1 billion machines that could try 1 billion keys/sec. It would still take all these machines longer than the universe as we know has existed and then some, to find the key. Not a likely event. IDEA, as far as present technology goes, not vulnerable to attack, pure and simple.

-- The asymmetric cipher --

RSA, the first *full fledged* public key cryptosystem was designed by Rivest, Shamir, and Adleman. It has withstood *years* of *intense* cryptographic scrutiny. RSA gets it's security from the apparent difficulty in factoring very large composites. However, nothing has been proven with RSA. It is not *proven* that factoring the public modulous is the only (best) way to factor RSA. It is also not proven that factoring *has* to be as hard as it is. There exists the possiblity that an advance in number theory may lead to the discovery of polynomial time factoring algorithm. But, none of these things has happened, and nothing points in that direction. However, 3 things that *are* happening and *will* continue to happen are the advances in: factoring technique and computing power, and the decrease in the cost of computing hardware. These things, esp. the first one, work against the security of RSA. However, as computing power increases, so does the ability to generate larger keys. It is *much* easier to multiply very large primes than it is to factor the resulting composite.

So, as it stands now, the best way to crack RSA is through factoring the public modulus. This, as far as we know, is not an easy task, if the public modulous is large enough (there are numerous examples of smaller keys falling to concerted effort). Using the General Number Field Sieve, a 1024-bit key would likely require 3E11 MIPS years to factor. 20 years from now (assuming no breakthoughs in factoring technology) this keyspace will likely be insecure. Today, it is not. But, the ultra-conservative will opt for 2048-bit keys, which is not a bad idea in my opinion.

It is very difficult to make predictions in this area of computing/ cryptography. Arjen Lenstra the most succesful factorer will not make predictions oast 10 years.

To sum it up: RSA is vulnerable to factoring. --DON'T LET ANYONE WITHOUT A PHD IN THEORECTICAL MATH TELL YOU OTHERWISE-- If you use a large enough public key, all the worlds computers cannot factor your key (using present factoring technology). RSA would not have lastest this long if it was as fallible as some crackpots would like you to believe.

-- The one-way hash --

MD5 is the hash used to hash the passphrase into the IDEA key and to sign documents. Message Digest 5 was designed by Rivest. It's output is four 32-bit blocks, which form a 128-bit hash of the input. MD5 has no known practical security weaknesses. It has a weakness in the compression function, allowing for collisions, but this does not allow for any practical attack. There are two attacks against MD5 (or any hash function). The first is to find a another input that will hash to same value. Not very practical or likely.

Remember the output is 128-bits. That's a BIG number. The other attack, the birthday attack, trys to find two random messages that hash to the value. This is also impractical (although not as much as the first one).

Since English has 1.3 bits of information per character, and IDEA uses a 128-bit key, a passphrase of about 100 characters will maximize the randomness of the resulting hash. How many of you use 100 character passphrases?

-- The PRNG --

I do not have enough info on the PSNG used by PGP as of yet. This section under construction.