Re: MD5 math question

[Charles Miller <cmiller () pastiche org>]

On 06/01/2006, at 12:06 PM, exon wrote:

> Charles Miller wrote:
> >  From my back-of-the-envelope calculation, your intuition is   
> > misplaced. :)
> > Even if you assume only 6 bits of variance per password character   
> > (which is just a-zA-Z0-9 plus two punctuation chars), that's  
> > 2^144  possible 24-character passwords. MD5 is a 128 bit hash, so  
> > that's  2^16 passwords for every hash value, or only a 1 in 65,000  
> > chance  that the
> > first matching hash you come across in the password space  is, in  
> > fact, the correct password.
>
> Without knowing the correct password there is no way of knowing  
> that the collision isn't it, and from a practical point of view it  
> doesn't matter in the slightest.

It's unfeasable to brute-force 2^144 passwords anyway. It was just an  
intellectual exercise.

There is, however, a significant theoretical difference between "some  
data that hashes the same as a password" and the original password  
itself. Most people re-use passwords between different applications.  
The former will only be portable between apps that use the same  
hashing algorithm and salt, while the latter will work everywhere.

> Considering the fact that MD5 has been broken though, I'm fairly  
> surprised it even came up to discussion. It's not exactly hard to  
> find info or even collision-generators.

The attack on MD5 is a collision attack, not a preimage attack. You  
can create differing messages with identical hashes, but you don't  
get to choose what that hash is. You can't match an existing hash any  
easier than you could before.

http://www.cryptography.com/cnews/hash.html

This vulnerability makes MD5 unsuitable for certain cryptographic  
applications, but it makes no difference to MD5 as a password-hashing  
algorithm. The collision has to be generated by the person coming up  
with the original data to be hashed, and I can't think of any way  
someone could benefit from doing this on their own password.

Charles

-------------------------------------------------------------------------------
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
-------------------------------------------------------------------------------