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