Memo: Re: MD5 math question

[tim.m.james () hsbc com]

Agreed - if the original question was "how likely is it that a brute forcer
gets the WRONG password but the hash is correct and hence authentication is
successful", then the answer is "highly likely"! In Charles' case, of 6-bit
entropy per password char, it's a 65535/65536 chance. The chance of it
being the correct password is 1 in 65536.

My example used 94 characters of entropy per password character (all
printable ASCII chars) and the answer then is about 1 in 700 million of it
being the correct password (and the rest incorrect).

Pesky probabilities.....

Your intuitive result is true when using a small password space - let's say
case-insensitive letters plus the 10 digits - there are 36^24 passwords
(roughly 2^124) and in this case there are far more hash values than there
are passwords- about 16 times as many hash values in fact. So hash
collisions are then very unlikely, and if you get a password that gives the
correct hash then it is likely to be the only one that gives that hash. The
probabilities here are pretty tricky to calculate - you need to think about
2^124 samples of a 2^128 population and calculate the probability of
expected frequencies of each member of the population.  Your final answer
will then be derived from an expected frequency of 2 and over and their
respective likelihoods.

That's enough probabilities now. Interesting question though. My summary is
- if the password space is big, then the chances of the wrong password
hashing to the correct hash are high. If the space is small and the hash is
correct, it's probably from the correct password and not another. The
"break-even" point is around 2^128 passwords, which is roughly when using
24-chars of 5-bit entropy.

Tim





Charles Miller <cmiller () pastiche org> on 04 Jan 2006 03:54

To:    Jeff Robertson <jeff.robertson () digitalinsight com>
       webappsec () securityfocus com
cc:
bcc:

Subject:    Re: MD5 math question


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.

And that's only if you assume the original password lives inside [a-
zA-Z0-9.!]{24}, not the "1-24 ASCII characters" of the original
question.

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





************************************************************
HSBC Bank plc
Registered Office: 8 Canada Square, London E14 5HQ
Registered in England - Number 14259
Authorised and regulated by the Financial Services Authority
************************************************************


-----------------------------------------
This E-mail is confidential.                      
                                                  
It may also be legally privileged. If you are not the addressee you may
not copy, forward, disclose or use any part of it. If you have received
this message in error, please delete it and all copies from your system
and notify the sender immediately by return E-mail.
                                                  
Internet communications cannot be guaranteed to be timely secure, error
or virus-free. The sender does not accept liability for any errors or
omissions.


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