As Karellen hinted at, it is extremely taxing to remember passwords with enough entropy that they cannot be cracked with current hardware.
Sure I could memorize a GUID and use that as a password, but that’s not easy. The most random password most people will come up with is randomly-capitalized first letters of words in a sentence they remember – the search space here can be limited by relative frequencies of letters at the beginning of English words.
To paraphrase Bruce Schneier: You can’t memorize passwords complex enough to be uncrackable, so don’t; Generate some long, random passwords and write them down on a card you keep in your wallet.
My personal favorite password strategy - pick a word 6 to 8 characters long, then in that word, randomly pick 3 or 4 letters and replace them with their ASCII code. So long as you can remember the word, and roughly which letters you type, you can figure out the missing ASCII. Plus you eventually learn most of the 6583677373 codes. That’s leet.
Ummm…hey…
Could social-networking (who said MySpace!?) and/or their seedier cousins (who said AFF/porn!?) actually be fronts for password harvesting? Could the harvested password data then be hypothetically used as a training set for some AI routines to deduce patterns in password selection? Could the routines hypothetically deduce the ‘human element’ from a large enough initial data set (or, a constantly growing data set)?
Harvesting by day, training by night, raids against ecommerce/banking/etc on the weekend?
inspired by:
e.g. Using some kind of combinatorial reverse-markov-chain generator that creates sentences in probabilistic order, and doese leet/capitals/number substitutions as it goes.
A minor point, but don’t forget the times quoted in the article to crack a password are worst-case – the average time will be half the quoted amount, for each.
[passphrases] do need to be longer than you think.
This is a complete and utter myth. We can’t even do proper machine translation, much less generate a complete set of all possible sentences-- there are FAR more possible words and combinations than ASCII characters in any given position. This was discussed to death in the comments at the URL below, so please read through those before immediately responding.
You can’t memorize passwords complex enough to be uncrackable,
Oh yes I can. Here’s an example password that’s brainlessly easy to memorize and uncrackable.
Hey, guys. Before criticizing people for choosing 8-character passwords, remember that many online services don’t even allow for anything longer than that.
Brute Force, even if it’s as “advanced” as presented here is just silly because it presumes to have the kind of access it would never have to a truly secure system. Think about it, the method presented here presumes it can just brute force passwords as fast as hardware (in this case a GPU) will allow.
But what happens if the system locks you out from trying passwords after 3 consecutive failures? And I’m not even talking about -long- lockouts… those tend to be inconvenient to legit users. What if we made the lockout a mere, say, 30 seconds?
Let’s try some math shall we? Unless I made a mistake somewhere, this should be correct. Simply a matter of adding 30 seconds for every 3 passwords to the actual hardware time, right?
Without lockout: 53,459,728,531,456 / 200,000,000 pps / 60 / 60 / 24 = 3.1 days (as per this blog)
With lockout: ((53T / 200M pps) + ((53T / 3) * 30 sec)) / 60 / 60 / 24 = 6187468583+ days (16940365+ years)
Oops. There goes all their effort, dwarfed by the time they spend waiting to be allowed to try the next password.
@Jeff “Passphrase” Atwood:
Oh yes I can. Here’s an example password that’s brainlessly easy to memorize and uncrackable.
“I drive a 1998 Ford Contour.”
That’s just 5 dictionary words and a common number (recent year). It’s “brainlessly easy to memorize” because has a very low amount of entropy. Maybe the average rainbow table out there now won’t get it, but it just requires a different type of (no more sophisticated) attack.
The only way you can make a password more secure against any type of guessing is by adding real entropy, and there’s only so much entropy a person can easily memorize.
Don’t get me wrong, I agree that using such a passphrase would be secure against most types of attacks we see today, but only because it’s such an uncommon thing to do. If everyone was using passphrases, we’d see rainbow tables and dictionary attacks for passphrases.
I don’t see anything in the comments in the link you give that directly addresses the point Karellen and I are making. In fact, it seems you were seriously underestimating the ingenuity of some crackers and legitimate software developers alike:
“I guess the hypothetical attack tool you are talking about would have a complete command of English (and perhaps other languages/words/grammatical errors that might slip in)? I don’t know how it would know what capitalization and punctuation rules make sense to try, or even which words statistically follow other words. I am not sure this attack tool you’re describing A) even exists or B) is possible to create.”
This is more or less how Google’s translator works. It’s also how I would go about cracking a passphrase. Note that it’s not a complete command of any language - it’s all about heuristics. All passwords humans come up with have characteristics and patterns in common (just like their languages). If we can come up with the right statistics on passwords/languages, we can (and usually do) limit the search space enough to make password cracking feasible.
Mike:
Copies of databases are stolen all the time by crackers and insiders. We don’t even know about most of these incidents. After California passed a (pretty dodgy) disclosure law, we found out that Citigroup leaked data on 3.9 million people!
Your “three tries and you have to wait” security doesn’t help too much in these (common) cases. Of course, we need to get big companies to stop storing passwords in plaintext or symmetrically encrypted text before we should even be worrying about password strength.
Jeff:
Sorry for the flood of comments, I just wanted to add one more thing.
I think we’re not seeing eye-to-eye because you’re talking about cracking passwords with a 100% probability of success. In the real world, if a target system has 10 administrators, you only need a 10% chance of success. This is why heuristics can be applied to pretty much all human-generated passwords with great practical results.
Plus, it’s hard for a human to repeatedly make his password 10x better, but the attacks become better and better at an alarming rate – whether by faster hardware or better cryptanalysis methods. These Russian jokers saw a 20x increase in speed just by finding and exploiting parallelizable aspects of an existing encryption algorithm (I imagine this is what they’re patenting, not the use of the GPU per se). I’m sure similar properties exist in all major cryptographic algorithms, and we’ll find them sooner or later.
Well, you pretty much answered yourself there with the last paragraph.
You’re right, the 3-tries-lockout method doesn’t help in those cases. But then, it’s quite obviously not meant to. That’s a whole different scenario. This blog post, unless I’m mistaken, is about brute forcing -passwords- and not password hashes. And -that- can be effectively prevented with 3-try-lockout.
Password hashes are a different story, but can also be effectively secured. Due to the “recent” advent of hash-to-password lookup tables for most common hash functions, it’s obviously not a good idea to just md5() your passwords (I’m not even going to touch on not encrypting or using symmetric encryption; we’re talking security here after all, not non-security).
Instead, it’s much better to use a custom, secret hash function that adds complexity and obscurity by means of nesting hash functions, using salt, using constant values besides the password (like the username), scrambling the hash(s), etc… or any combination thereof. Essentially using something unique to your service and preferably unknown to potential attackers even if they manage to get their hands on your database.
Er, my apologies… I AM mistaken, this is about brute forcing hashes. That’s what I get for forgetting to drink my coffee.
In that case though… the real issue here is not secure passwords but security of the system itself. Like you pointed out, it’s all too common that even large companies leak sensitive information or entire databases. THAT is the real issue.
After all, if someone manages to get their hands on a dump of a large companies database, there’s more than just password hashes in there already. And if someone has physical access to the machine itself, well… then it’s all moot anyway because they can do whatever they want with it.
Mike:
I’m not sure I see the distinction you’re making between brute forcing passwords and passwords hashes. I’m sure in the vast majority of brute force attacks, the attacker has the passwords hashes.
But I have to ask you, please don’t use custom, secret hash functions or security methods. There are well-documented methods for storing passwords and challenge-response authentication that are both mathematically sound and proven in practice. If an attacker has access to your database, he probably has access to your source code as well, in which case security through obscurity fails miserably.
And one more thing, avoid MD5 altogether if you can. It’s better than nothing, but there have been successful collision-producing attacks against it. There’s usually no reason not to use SHA-2 at 256 bits or higher.
I just have a ruleset for creating passwords based on the name of service, type of service(bank, email, forums etc) this keeps me feeling reasonably safe and i am yet to forget a password.
I also like to throw in repeating characters into that because people watching your hands type can rarely pick up on the double taps.
“But I have to ask you, please don’t use custom, secret hash functions or security methods. There are well-documented methods for storing passwords and challenge-response authentication that are both mathematically sound and proven in practice. If an attacker has access to your database, he probably has access to your source code as well, in which case security through obscurity fails miserably.”
Why not?
Even if we assume an attacker has access to the source code with the custom chain of hash functions (which as you correctly point out voids the obscurity), there’s still the added complexity and unique nature of the hashes.
You can’t possibly be saying the first is just as secure as the second? The latter…
Can’t be reverse mapped with a vanilla lookup/“Rainbow” table (at least not the top level sha512)
Would require a separate lookup table for each user (if the attacker is willing/able to build custom ones)
Would take at least twice as long to brute force for a single user (assuming most of the cpu time is spent on the hash functions and not on comparison or concatenation)
And it doesn’t have to end there. You could nest them further, use different hash functions, split up the username and password or scramble them (take every odd char from username and every even char from password for on hash; and vice versa for a second) and so on and so forth. You can add as much complexity as you like.
“Security through obscurity” is never a good thing to rely on, that’s (or should be) common knowledge. But that’s not what this is. This is security through complexity (takes more cpu cycles to generate each hash) and through uniqueness. And we can all see just how much lack of the latter compromises security by looking at Windows and IE.
If everyone uses the same method for storing passwords then eventually someone will find a way around it. No matter how mathematically sound or practice proven it is.
The salt needs to be random, and different per password. Basically, what you intended the username for. The username is just as predictable as the password in the cases you care about.
Also, you want to use a hash function that isn’t designed to be fast (including basically any hash function useful for message signing). The idea is to make calculating hash(salt + dictionary) as slow as possible, while still processing a login in a user-acceptable amount of time.
Im still glad to see at least windows vista has upgraded it’s passwords by default past the old LM hash which you used to be able to crack 14 letter passwords in 10 minutes on new hardware. Next for windows password salting by default.
