Memo: Re: MD5 math question

[tim.m.james () hsbc com]

Jeff,

I agree with Tim's final answer of 2^-128 for the probability that a random
plaintext will have the same MD5 hash as a fixed password. That's simply
because there are only 2^128 possible MD5 hashes.

I think I can go a bit further in the analysis, for what it's worth....

> From your description you have a space of about 94^24 plaintexts - I'm
guessing that all 94 printable ASCII characters can be used in your
passwords. The actual space size is 94^24 + 94^23 + 94^22 +....+ 94 which
is approximately 2.3*10^47. There are 2^128 possible hashes, which is 3.4
*10^38. That means there are about 700 million plaintexts for each hash
value - plenty of collisions then. The problem is in finding one of those
700 million clashing plaintexts from the entire space of 2.3*10^47, which
is a 1 in 2^128 chance. You'll have to try approximately 2^127 plaintexts
before you can reasonably expect to get a match.

Even if your original plaintext passwords aren't randomly chosen from the
94 printable ASCII characters (and use just [a-zA-Z0-9], say), the chance
of a randomly chosen plaintext having the same MD5 hash as the originally
chosen password is still 2^-128.

Tim

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