PGP Attack FAQ: The one-way hash
MD5 is the one-way hash used to hash the passphrase into the IDEA key and to sign documents. Message Digest 5 was designed by Rivest as a sucessor to MD4 (which was found to be weakened with reduced rounds). It is slower but more secure. Like all one-way hash functions, MD5 takes an arbitrary-length input and generates a unique output.
Table of contents
Can MD5 be brute-forced?
The strength of any one-way hash is defined by how well it can randomize an arbitrary message and produce a unique output. There are two types of brute force attacks against a one-way hash function, pure brute force (my own terminolgy) and the birthday attack.
The pure brute-force attack against MD5
The output of MD5 is 128 bits long. In a pure brute force attack, the attacker has access to the hash of message H(m). She wants to find another message m' such that H(m) = H(m').
To find such message (assuming it exists) it would take a machine that could try 1,000,000,000 messages per second about 1.07 times 1022 years. (To find m would require the same amount of time.)
The birthday attack against MD5
It is theoretically possible that two messages hash to the same value. This is known as a collision. The birthday attack exploits such collisions.
The birthday attack is a statistical probability problem. Given n inputs and k possible outputs, there are n(n-1)/2 pairs of inputs. For each pair, there is a probability of 1/k of both inputs producing the same output. So, if you take k/2 pairs, the probability will be 50% that a matching pair will be found. If n is greater than sqrt(k), there is a good chance of finding a collision.
In MD5's case, 264 messages need to be tried. This is not a feasible attack given today's technology. If you could try 1,000,000 messages per second, it would take 584,942 years to find a collision. A machine that could try 1,000,000,000 messages per second would take 585 years, on average.
Are there other attacks against MD5?
Differential cryptanalysis looks at ciphertext pairs whose plaintexts has specific differences and analyzes these differences as they propagate through the cipher. Differential cryptanalysis has proven to be effective against one round of MD5, but not against all four.
There was successful attack at the compression function itself that produces collisions, but this attack has no practical impact the security. If your copy of PGP has had the MD5 code altered to cause these collisions, it would fail the message digest verification and you would reject it as altered... Right?
Will MD5 always create a secure key?
The RSA private key is stored encrypted with a key that is derived from a passphrase entered by the owner. This key is created by hashing the passphrase using MD5. If a weak passphrase is used, this may affect the security of the private key.
According to conventional information theory, the English language has about 1.3 bits of entropy (information) per 8-bit character. If the pass phrase entered is long enough, the reuslting MD5 hash will be statisically random. For the 128-bit output of MD5, a pass phrase of about 98 characters will provide a random key of
How many people use a 98 character passphrase for their private key in PGP? Below is 98 characters...
10 20 30 40 50 60 70 80 90
1234567890123456789012345678901234567890123567890123456789012345678901234567890123456789012345678
1.3 comes from the fact that an arbitrary readable English sentence is usually going to consist of certain letters, (e,r,s, and t are statiscally very common) thereby reducing its entropy. If any of the 26 letters in the Latin alphabet were equally possible and likely (which is seldom the case) the entropy increases. The so-called absolute rate would, in this case, be:
In this case of increased entropy, a password with a truly random sequence of English characters will only need to be:
For more info on passphrase length, see the PGP passphrase FAQ.