Vipul is correct for 12 characters, but the story changes when you go
up to 24 character passwords. For all passwords from 1 to 24
characters, you would have to repeat this for each length and add them
all together. I'll just consider 24 character passwords. I'll also
simplify the math by assuming there are 2^6 = 64 allowed characters in
the password.
There are (2^6)^24 = 2^144 possible passwords
There are still only 2^128 possible hashes.
So on average, there are 2^144 / 2 ^128 = 2^16 passwords that hash to
each possible hash.
Or, for a given hash, the possibility that a random password with that
hash is in fact the original password is only 1 in 65536. At random,
you are much more likely to have found a collision than to have found
the original password.
This is all academic, however, because there is no way you could brute
force even 2^128 values, much less 2^144 values.
Chuck
On 1/4/06, Vipul Kumra <vipul.kumra_at_airtightnetworks.net> wrote:
>
> 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_at_airtightnetworks.net]
> Sent: Wednesday, January 04, 2006 1:34 PM
> To: 'Jeff Robertson'; 'webappsec_at_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_at_digitalinsight.com]
> Sent: Wednesday, January 04, 2006 6:49 AM
> To: webappsec_at_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
> -------------------------------------------------------------------------------
>
>
-------------------------------------------------------------------------------
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
-------------------------------------------------------------------------------
Received on Jan 06 2006
Intro
