Re: MD5 math question

[exon <exon () home se>]

Charles Miller wrote:
> On 04/01/2006, at 12:18 PM, Jeff Robertson wrote:
>
> > 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?
>
>
>  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.

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.

As for not using salts, read this. You'll change your mind.
http://discuss.develop.com/archives/wa.exe?A2=ind0301b&L=advanced-dotnet&T=0&F=&S=&P=4424


Here are some (good) links I found fairly quickly on MD5 being broken. 
Google has lots more.

http://www.schneier.com/blog/archives/2005/03/more_hash_funct.html
http://www.schneier.com/crypto-gram-0409.html#3
http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html
http://it.slashdot.org/article.pl?sid=05/11/15/2037232&tid=172&tid=93&tid=228
http://www.cs.bham.ac.uk/~mdr/teaching/modules04/security/lectures/hash.html
http://www.chiark.greenend.org.uk/pipermail/ukcrypto/2004-August/074400.html
http://csrc.nist.gov/hash_standards_comments.pdf

/exon

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