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.
Ah, got it Larry. I do recall seeing that messge in XP & 2003, since my default pwd is 16 characters.
On the whole password security thing, the whole point of complexity is to make dictionary attacks a waste of time. Combine that with a reasonable minimum length so that it's an even call between brute forcing the hash or brute forcing the password itself, then add in account lockout and mandatory password expiration, and the only remaining issues are (1) users writing down their passwords, and (2) backdoor stuff.
It's amazing how often discussions about password security wander off into all kinds of interesting tangents without even considering the two most basic defenses, good old account lockout and mandatory password expiration, both of which have been around since the year dot.
@mh: Performing a one-way hash on a password is designed to provide security in a way that neither password expiration nor account lockout are able: in the case that your data is compromised, hashes ensure that you haven't given your intruder a list of email addresses and passwords to start running through Paypal (or any other site for that matter).
I don't want to put words into Larry's mouth; however, I would say that the lesson in this post is not making a point about information security directly, rather, it is pointing out how a system's underlying design can subvert the security attempts of even the most cautious user.
As a question to anyone reading this, is brute forcing a viable option for breaking a hash? I always figured that rainbow tables were going to be where password recovery was heading.
I write down some of my passwords. One example used to be that if someone stole my wallet then they could get my money, use my credit cards, and log into some of my employer's computers (if they could get into the building). One example now is that if someone breaks into my apartment then they can get my computers and they can order a pizza to be sent to me (or to them if they want to risk waiting for it).
I'd say that a strong written-down password is better than a weak memorable one. Also a strong written-down password is better than one that's stored in HKCU.
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