On Wed, 23 Feb 2000, Bryan Andersen wrote:
>
> Javier Romero <[EMAIL PROTECTED]> wrote on 2/23/00 11:59 am:
>
> >Hi Sirs.
>
> >Is posible unveil MD5 passwords?
>
> Not easily. It's technically possible but is computationally not feasable.
>
> >If it is so, How time take it?
>
> A very long time.
Here's a better answer, from "The Feasibility of Breaking PGP":
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.
-- Brute Force of MD5 --
The strength of any one-way hash is defined by how well it can
randomize an arbirary 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.
-- Pure Brute Force Attack against MD5 --
The output of MD5 is 128-bits. 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.07E22
years. (To find m would require the same amount of time.)
-- The birthday attack against MD5 --
Find 2 messages that hash to the same value is known as a
collision and is exploited by the birthday attack.
The birthday attack is a statistical probability problem. Given
n inputs and k possible outputs, (MD5 being the function to take
n -> k) 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 > sqrt(k), there is a good
chance of finding a collision. In MD5's case, 2^64 messages need
to be tryed. 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.)
For a successful account of the birthday against crypt(3), see:
url:
ftp:/infonexus.com/pub/Philes/Cryptography/crypt3Collision.txt.gz
-- Other attacks against MD5 --
Differential cryptanalysis has proven to be effective against one
round of MD5, but not against all 4 (differential cryptanalysis
looks at ciphertext pairs whose plaintexts has specfic differences
and analyzes these differences as they propagate through the
cipher).
There was successful attack at compression function itself that
produces collsions, 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?
-
[To unsubscribe, send mail to [EMAIL PROTECTED] with
"unsubscribe firewalls" in the body of the message.]
