Lessons learned from cracking 2 million LinkedIn passwords

But that doesn't matter at all if the attacker is targeting your algorithm in particular.

Say my algorithm is to pick the password "1" * 1000 (that's the character 1 repeated 1000 times) and also pretend that 90% of the sites didn't have stupid limits and it was a valid password. It's certainly a long password. The time it would take to brute force it by testing all possible strings in order of increasing length is an unimaginable number. It's not on the scale of the universe - not on the scale of a million universes either.

But now let's say that this "the more characters the better" became a universal truth and everyone jumped on the same bandwagon and did the same quick hack of having 1000 1s. Suddenly, we're all screwed, because the algorithm "pick 1000 ones" is staggeringly weak. In fact, it provides no protection at all - the attacker already knows your password.

The true measure of security measures is not how long they last when no one knows about them - it's how long they last when everybody knows. "Pick 10 random symbols" will last for a while. "Pick 'password'", not even a second.

Where does "pick a meaningful English sentence" fall on the grand scale? That's one incredibly hard question to answer. It's also bloody difficult to break, for reasons of generating sentences, not password entropy.

And note that assumes there are about 2,048 common words to choose from, not the 171,000 you can find in a dictionary.

Why blacklist rather than whitelist?

    LC_ALL=C egrep '^[[:lower:]]{4,8}$' /usr/share/dict/words |
    shuf --random-source=/dev/random -n4 |
    fmt

That's picking from ~35,000 words, which I think is still good enough but avoids ending up with "interpreters incredibility disciplinary constitutionality". (I need the C locale to stop this old GNU grep being painfully slow.)

Well, calculating the "true" strength is difficult to do, because even though sophisticated tools are available to aid the process, the attackers are still human, and can input their own guesses that may or may not be more accurate. If the attacker knows (or can closely guess) the password rules used to generate your password, he or she has a better chance of getting a hit.

Let's look at a password like "My first car was a 1972 Monte Carlo". The password is 35 chars, 3 upper case, 6 special (spaces), and 4 numbers. The key space is all upper and lowercase english letters, all numbers, and all special characters. That's a key space of 95 characters, over 35 places. Objectively, there are 1.66 x 10^69 possible combinations. Given that the LinkedIn password crackers are slowed down at about 9 chars it seems like you're incredibly secure. But let's assume the attacker knows something about your password structure. Let's say they know that you use words (many people do, so it's a reasonable guess). Let's also assume that for numbers the attacker knows that years are popular for password numbers. Now instead of 35 chars, your password has 7 words and a date. We've changed the key space from 95 to about 100,000. (The exact number of words there are is a tricky number to pin down, but crackers have some good data on what the most popular ones are.) As for the date, there are really only a couple hundred interesting numbers, including all dates from this and last century, as well as common patterns.

Password strength is (key depth) ^ (key length). An uninformed attacker has 1.66 x 10^69 possible combinations (95^35), while an informed attacker has roughly 1.0 x 10^40 possible combinations (100,000^8). Obviously, the less an attacker knows (or can guess) about your password structure, the better chances your password has against being cracked.

Now, you asked about your password versus a random 8 char password. Let's take a "strong" password like "1~qQ%57h" This password also has upper and lowercase letters, numbers, and symbols. We can assume that there is nothing predictable about this password for this exercise. The password strength is 95^8, or 6.6 x 10^15, obviously much lower than the longer sentence, even if the attacker knows the sentence is 7 words and a date.

Now remember, our passwords are being matched against human crackers attempting to guess the ways our passwords are most likely put together. For now, most passwords are 6-12 characters. In fact, most websites only allow passwords of these kinds, so it makes the most sense for crackers to go after these passwords. But it's still an arms race. If we assume that webmasters see the light and allow (or enforce) long, sentence-like passwords, the crackers will adjust. It's plausible I think that 5-10 years from now, we'll see articles like this one that use sentence structure syntax as an attack method.

Until we discover and implement a better system that obsoletes passwords, the best we can really do is have long, complex, and unique passwords for everywhere we go, and have a system to manage them for us. I believe that something like LastPass or KeePass are the way to go for now.

*Disclaimer: This was written on a groggy Sunday morning. Do not rely on my calculations. Do not use any of the examples as passwords. Do please check my work.

That's only 4 tokens and you should assume at least some of the combinations are already in rainbow tables. I don't know how long it would take to create a rainbow table for the whole space, which is this big:

  72940^4 = 2.8304992 × 10^19

To put it in perspective, a 14-character password using only lower case English alphabet letters as individual tokens already beats this:

  26^14 = 6.45099747 × 10^19