WebApp Sec mailing list archives
Memo: Re: MD5 math question
From: tim.m.james () hsbc com
Date: Fri, 06 Jan 2006 18:17:35 +0000
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 -------------------------------------------------------------------------------
Current thread:
- Memo: Re: MD5 math question tim . m . james (Jan 06)