4

How long would it take to crack passwords up to 10 letters long if you knew the hashes were MD5 with a salt (that you know)?

user49637
  • 723
  • 6
  • 9
  • Is this an academic question to help you make a security decision? If so, just use a salt :) – Christopher Wirt Jun 23 '14 at 14:16
  • The risk should be considered very high if youre using unsalted md5 hashes, since the attacker can test one password against many hashes at once. Consider all hashes comprimised – Christopher Wirt Jun 23 '14 at 14:52
  • 1
    Unfortunately, a universal salt is very similar to not having one at all. The only difference is that your keyset is now M+N where M is the length of the salt and N is the length of the password. As I said, with the resources and lengths people go to get a password associated with an email address (which is something I'm assuming of your database), I'd say even 10 and 11 characters are at risk. ALWAYS consider all keys compromised in this situation. – Christopher Wirt Jun 23 '14 at 14:56
  • However, if you want a true assessment of if those 10 or 11 character passwords are safe, then something like 60% are likely to be compromised by a wordlist hybrid attack alone. – Christopher Wirt Jun 23 '14 at 14:59
  • Rainbow tables wouldn't have to be rebuilt if the salt is already in the keyset. If your salt is, for example, 'salt', then your attacker would simply extract the part of the rainbow table that begins with those four characters. Always assume an attacker has the best possible rainbow table, or at least a full alphanumeric one. – Christopher Wirt Jun 23 '14 at 15:01
  • Then you're pretty resistant to a rainbow table attack, but if the attacker knows that's the salt, then a word-list attack is still just as feasible. – Christopher Wirt Jun 23 '14 at 15:04
  • Related: [Is MD5 considered insecure?](https://security.stackexchange.com/q/19906/11825) (billions of candidate passwords per second on a single GPU) – kenorb Oct 11 '17 at 22:39

1 Answers1

7

Computation is simple enough, though there are some hidden assumptions.

On this site, one can find benchmarks for some GPU-based cracking systems. One of them, featuring no less then eight AMD R9 290X GPU, can compute 93.8 billions of MD5 per second.

There are 2610 = 141167095653376 possible sequences of 10 letters. At 93.8 billions per second, they can all be hashed in about 1500 seconds, i.e. 25 minutes. On average, finding the right password will take half that time (sometimes you get lucky, sometimes you don't).

However, mind the details:

  • MD5 is a hash function. Its standard definition does not speak of passwords or salts. When you have "passwords hashed with MD5 and a salt", then you really are using some unspecified algorithm which uses MD5 as one of its internal elements. Whether the computational cost of the algorithm can be reduced to "just one MD5" depends on that algorithm. Some MD5-based password hashing functions actually imply several MD5 invocations, possibly a lot (in that sense, PBKDF2 with HMAC/MD5 is an algorithm "based on MD5" and can involve billions of invocations for each password).

  • The computation above assumes 10 lowercase letters. If the password may include both lowercase and uppercase letters, and they are treated differently, then the number of combinations rises to 5210 = 144555105949057024, for a corresponding brute force time of 17.8 days. If we use printable characters (the 95 ASCII signs, excluding control characters but including space), the number of combinations rises again, up to 9510 = 59873693923837890625, for a brute force time of about 20 years (again, this is for the complete space exploration; attack time will be half that value on average).

  • Conversely, when normal human users are supposed to generate a password, they come up with "witty" passwords, not "random" passwords. Among 10-letter possible passwords, some are widely more probable than others. Attackers will try the passwords by beginning with the more probable ones, and this reduces attack time quite a lot.

  • The system used here as example is quite big in amateur terms (8 big GPU...), but an industrious attacker may accumulate more power. He may also rent it (from commercial cloud systems), which can be cost effective. There is no absolute answer to your question if you do not first define the attacker's budget.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • An 8-char password _may_ be strong enough if the system uses a proper password hashing function, i.e. bcrypt with enough iterations. Iterations make the function slow enough so that the honest server may still hash about 10 times per second, and the rich attacker cannot try more passwords than, say, 1000 per second. – Thomas Pornin Jun 23 '14 at 15:11
  • And the important property is not _length_ but _entropy_. You need enough characters to allow the entropy to express itself, but length is not enough. The password is strong exactly inasmuch it is unknown to the attacker. – Thomas Pornin Jun 23 '14 at 15:12
  • @user49637 http://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ Passwords that have a method to their madness lack the same true entropy that a random password has. If its a word in any language, with any amount of witty leet-speak or uppercase-lowercase substitution, its true entropy is very low. So length really isn't as important as randomness. If you can remember your passwords, they're probably bad passwords. – Andrew Hoffman Jun 23 '14 at 15:32
  • @user49637 Well the question you're asking is pretty much identical to what the arstechnica link put to practice, and they had 90% success. So yeah, unless the passwords are completely random and of sufficient length, they'll probably be cracked by advanced password tables. – Andrew Hoffman Jun 23 '14 at 15:39