FW: RE: MD5 math question

["Vipul Kumra" <vipul.kumra () airtightnetworks net>]

Hi,

To add on to my last post, I'll try to put some numbers over it.


Let's have some assumptions here:

> > Assume that a password between 1 and 24 ASCII characters was stored as

> > an MD5 hash. No salt.

For now lets assume the password is of fixed 12 characters in length
(The only allowable range being a-z & A-Z). So the total possible
combinations are 52^12.


So what's the probability? 

-> MD5 checksums are 128 bits wide (typically expressed as a sequence of
32 hexadecimal characters). So there are 2^128 =
340282366920938463463374607431768211456 possible combinations.

-> We have 12 characters password (see assumption above), so there are
52^12 = 390877006486250192896 possible combinations.
The MD5 algorithms has good random distribution across its 2^128-bit
range. 

So the chance of any given password colliding with any other password is
one in 2^128/52^12 = one in 870561228402439969


Summary:

1) MD5 has a 128 bit hash so a brute force attack to find a collision
requires at most 2^128 applications of MD5. 

2) 2^64 by the birthday paradox.

3) Xiaoyun Wang and Hongbo Yu have an attack that requires 2^39
operations. This attack takes at most an hour and 5 minutes on an IBM
P690 (supercomputer).
 
4) With respect to a collision attack, the attacker will be able to find
two messages that will produce the same hash, but the attacker cannot
choose what the hash will be. So this rules out attacks on hashed
passwords, at least practically for now, with current processing speeds.

5) Since a collision attack can find to messages that will produce the
same hash, it is possible to use this to break message signing, such as
DSA and RSA. Where a hash of the message is generated first and then
signed cryptographically.


Interesting link to refer:

MD5 Collision Generation for MD5:
http://www.stachliu.com/collisions.html?coral-no-serve


Regards,
Vipul Kumra




-----Original Message-----
From: Vipul Kumra [mailto:vipul.kumra () airtightnetworks net]
Sent: Wednesday, January 04, 2006 1:34 PM
To: 'Jeff Robertson'; 'webappsec () securityfocus com'
Subject: RE: MD5 math question



Hi Jeff,

Interesting Question...


I cannot give you the exact figures but can point you to some links,
which might help you to find it yourself. The documents referred are
mathematically too technical for me to understand. It would be great if
you can tell me the answer to the question you asked, once you get it.

The links are:

http://en.wikipedia.org/wiki/MD5

http://eprint.iacr.org/2004/199.pdf


Also, it's easier for you to find two messages with the same digest then
match a specific value, which you are trying to accomplish here, because
of Birthday Paradox (Birthday Attack).


Birthday Paradox:

.       How many people in one room, for over 50% chance of one person
sharing your Birthday - 253.

.       How many people in one room, for over 50% chance of two persons
sharing the same birthday - 23.

.       Hence, it is easier to find two messages with the same digest
then match a specific value.



Regards,
Vipul Kumra





-----Original Message-----
From: Jeff Robertson [mailto:jeff.robertson () digitalinsight com]
Sent: Wednesday, January 04, 2006 6:49 AM
To: webappsec () securityfocus com
Subject: MD5 math question


Assume that a password between 1 and 24 ASCII characters was stored as
an MD5 hash. No salt. What is the probability that someone cracking the
password will find not the password that the user originally chose, but
a different password that happens to collide with it? Intuitively it
seems so unlikely that you wouldn't ever expect to see it. But what is
the probability really?

------------------------------------------------------------------------
-------
Watchfire's AppScan is the industry's first and leading web application
security testing suite, and the only solution to provide comprehensive
remediation tasks at every level of the application. See for yourself.
Download AppScan 6.0 today.

https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
------------------------------------------------------------------------
-------



-------------------------------------------------------------------------------
Watchfire's AppScan is the industry's first and leading web application 
security testing suite, and the only solution to provide comprehensive 
remediation tasks at every level of the application. See for yourself. 
Download AppScan 6.0 today.

https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
-------------------------------------------------------------------------------