When you're analyzing the strength of a password, make sure you know what's done with it.

Every once in a while, I hear someone making comments about the strength of things like long passwords.

For example, if you have a 255 character password that just uses the 26 roman upper and lower case letters, plus the numeric digits.  That means that your password has 62^255 possible values, if you can try a million million passwords per second, the time required would exceed the heat death of the universe.

 

Wow, that's cool - it means that you can never break my password if I use a long enough password.

 

Except...

The odds are very good that something in the system's going to take your password and apply a one-way hash to that password - after all, it wouldn't do to keep that password lying around in clear text where an attacker could see it.  But the instant you take a hash of a secret, the strength of the secret degrades to the strength of the hash.

It's another example of the pigeonhole principle in practice - if you put N+M items into N slots, you're going to have some slots with more than one entry.  The pigeonhole principle applies in this case as well.

 

In other words, if the password database that holds your password uses a hash algorithm like SHA-1, your 62^255 possible character password just got reduced in strength to a 256^20 possible value hash[1]. That means that any analysis that you've done on your password doesn't matter, because all an attacker needs to do is to find a different password that hashes to the same value as your password and they've broken your password.  Since your password strength exceeds the strength of the hash code, you know that there MUST be a collision with a weaker password.

 

The bottom line is that when you're calculating the strength of a  password, it's important that you understand what your password looks like to an attacker.  If your password is saved as an SHA-1 or MD5 hash, that's the true maximum strength of your password.

 

[1]To be fair, 256^20 is something like 1.4E48, so even if you could still try a million million passwords per second, you're still looking at something like a million million years to brute force that database, but 256^20 is still far less than 62^255.

Comments

• Anonymous
  November 12, 2007
  [1] explains a reason why longer or more complicated passwords are more secure though.  Rather than spending a million million years trying to brute force a password you go the other way.  You spend a little bit of time and lots of memory to generate a database of encrypted words, combinations of words, and words combined with symbols and/or numbers (crossed w/ a salt).   Then instead of trying to brute force one password you might try and search all available (higher privileged) hashed passwords and find one that matches.  While there's some chance that a more secure password would collide with one of these passwords that chance is lower than a short or simple password colliding with one of these passwords (given that ALL short or simple passwords will likely collide).  Therefore you've likely increased your security by having your password hiding in the shadows where the hackers aren't looking. What might be interesting (and probably done somewhere) would be taking password verification up a level: Instead of just disallowing simple passwords also check a database of hashed passwords to see if there's any hits.  If so also reject that password even if the password would otherwise meet the security requirements. Of course I guess that only ups the antity: Now the hackers may know where NOT to look. Sigh...

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 12, 2007
  The comment has been removed

• Anonymous
  November 13, 2007
  There MUST be a collision, but

1. In practice, people have passwords no longer than 20 characters,
2. So, there are good chances that the collision passwords will be longer than 100 characters. So, theoretically, you must be right, but that doesn't change practice anyhow.

• Anonymous
  November 13, 2007
  Przemyslaw, You could do that, but you would still have the same problem.  Now, instead of there being N_sha1 possible passwords, there are now N_sha1*N_md5 possible passwords (2^160 * 2^128 == 2^288) which is still much smaller than the pre-hashed password space originally proposed of 62^255 ~ 2^1518.32. Also, you don't want to be using md5 for anything.

• Anonymous
  November 13, 2007
  The comment has been removed

• Anonymous
  November 13, 2007
  The comment has been removed

• Anonymous
  November 13, 2007
  The comment has been removed

• Anonymous
  November 14, 2007
  Aaron: Maybe I'm just showing my ignorance here, but what's wrong with MD5?

• Anonymous
  November 14, 2007
  The comment has been removed

• Anonymous
  November 14, 2007
  The comment has been removed

• Anonymous
  November 15, 2007
  The comment has been removed

• Anonymous
  November 15, 2007
  The comment has been removed

• Anonymous
  November 16, 2007
  Ah, got it Larry. I do recall seeing that messge in XP & 2003, since my default pwd is 16 characters.

• Anonymous
  November 16, 2007
  The comment has been removed

• Anonymous
  November 17, 2007
  The comment has been removed

• Anonymous
  November 18, 2007
  The comment has been removed

• Anonymous
  November 18, 2007
  I wonder if the NSA do something like "select ClearText from Password where MD5=<value> or Sha1=<value>". They'd only need 1.3E36 (give or take) 1TB harddrives... :) http://en.wikipedia.org/wiki/SHA_hash_functions implies SHA1 is still reasonably secure at the moment. MD5 collisions can be found in a minute according to http://en.wikipedia.org/wiki/MD5