Your future passwords - breached already?

If you trust your brain to make up a password you’re in for trouble: someone may not only know it before you, but also its successors no matter how frequently you renew it.

In my previous post, I gave a lower bound on features a password should have in 2018 to be marked as relatively “acceptable”. I aimed at informing people, not alarming them.

Today I will complete this picture from a more unsettling angle. First, I will refine the lower bound and provide a more accurate, less generous estimate on how long it should last. Then, I will share a conjecture about passwords prediction: don’t take it too seriously though, it’s meant to keep you on your toes.

If you want to read on, you should first have a look at my previous post or you will get lost.

A milestone has been passed

To pick up where we left and squeeze more juice out of our model, I need to give a few words on a tool called renormalization. This scholar-sounding, brain-sedating word sounds like a very well-groomed mathematical operation like a Fourier transform. However, you should know that renormalization was carved by engineers to do very nasty things to the dismay of mathematicians. The key benefit is the ability to shake a cocktail of infinite values to make something useful out of it, in some context. 

Today we are going to use a similar idea, but not so extreme: we will handle finite values of incompatible types to make them comparable. Put it another way, we will compare cabbages with carrots. Not a big deal!

• If you remember, the 2012 benchmark was based on a set of passwords at most 7-characters long over a dictionary made of 95 items. This is our “cabbage” set. 
• Also remember how little impact extra characters have on security in the real world past a point: for that reason we preferred a smaller, more realistic dictionary holding 76 items (alphanumerical + 20 special characters). The corresponding passwords set is our “carrot” set.

Imagine for a split second that all the compute power used in 2012 to bruteforce the “cabbage” set was reallocated to bruteforce the more realistic “carrot” set. In this renormalized universe, what would be the length of passwords? Of course, since the computation power is the same in both cases, the bitwise length is identical for carrots and cabbages: 46 bits. But in terms of characters length, it is now 7.36 (or: 7*log2(95)/log2(76)) for carrots.

As of mid-2018, we have seen that the bitwise length of a weak passwords is 50 bits. In our renormalized set, this accounts for… Guess what? 8.002 character long passwords!

So it looks like we should celebrate a dangerous milestone: mid-2018 marks the end of acceptable 8 character long passwords.

An improved lower bound for acceptable passwords

So what becomes the new lower bound as far as character length is concerned? To find the answer we simply need to rince and repeat what we did in the previous post for cabbages.

We now define E as the set of passwords with 8 characters length (or 50 bits) or less and a dictionary size of 76. We’ve just seen that, sadly, all elements in E are bruteforce-weak. So let’s define a new set E’ bigger than E where all (bruteforce-weak) passwords from E are compressed. 

In E’:

? Half of the passwords are at least 1-weak by definition of d(.|.) (so it includes 2-weak, 3-weak, and so on…)

? This half also includes all bruteforce-weak passwords by construction of E’

How is E’ constructed? By picking the same dictionary as E, increasing the character password length, and making a compression map. 

What password length will we choose for E’? Well, let’s see for ourselves:

? 9 characters (or 56.2 bits)? the bruteforce-weak passwords (of length 50 bits or less) represent approximatively 2.7% of E’

? 10 characters (or 62.5 bits)? the bruteforce-weak passwords (of length 50 bits or less) represent approximatively 0.035% of E’

From that point on we have two options that depend on our risk appetite: either consider that 0.035% of a set is a significant minority, in which case the lower bound should be raised to at least 11 characters, or keep the current lower bound at 10 characters (but still raise the bitwise lower bound to 62.5 bits).

For the rest of this post I will take the latter option.

How long will the lower bound last?

If we assume Moore’s Law will stand for some time to come, the computation power at our theoretical disposal will have enumerated all 9 characters passwords (56.2 bits) in 9 years’ time (a 6 bits gain over 50 bits).

At that moment, it will be more than time to switch to 11 character passwords...

Conservatively, everybody should forget using 10 character passwords by the end of year 2022.

Conjecture for passwords history

When mental schemes are mapped to processes

The brain is not equipped with natural, accurate means to grasp randomness or even to detect it; it is tempted to devise (or rely on) a biased mental scheme to produce and renew passwords.

The basic idea of the conjecture can be stated as follows: a mental scheme is a stochastic process which can be inferred if one has access to the passwords history of a given password p using a lookup function that we will call previous(.)

We basically identify four such processes and label the complexity of their outcome (notice that only the last one is unbiased) according to what we know about their randomness deficiency:

? The stationary process, where previous(p)=p. This produces trivial passwords

? The deterministic process, where previous(p)=f(p). This produces very weak passwords

? The Markov process, where previous(p)=f(p, probability matrix). This produces weak passwords (at least 1-weak)

? The Bernoulli (aka "coin flipping") process, where previous(p)=f(0,1). This produces random passwords (the randomness deficiency is up to zero)

The list is arbitrary in many ways: first, we assume that the password-generating activity of the brain can be modeled by one of the four processes, not unlike the Church-Turing hypothesis. We may also argue on the way processes are split, the way password complexity is rated, the number of processes... But so are the foundations of the conjecture: you should take them or leave them.

The conjecture

The conjecture is as follows : if one knows n predecessors of a password p, it is possible to determine the complexity of all successors of p with O(1/n) uncertainty

If the above statement is true, any 8 character password (and all its successors) not produced by a random generator is already breached in 2018 and hashed into various rainbow tables.

Practical consequences

Now imagine a popular website you are registered on was hacked a few years ago. Examples are so numerous we have ample choice: let's say Ashley Madison, 2015. At that time, you were kindly asked to change your password. Chances are, you have renewed your Ashley Madison password several times since then.

You think you're safe now, but the truth is... The team who managed to break into this website and other actors of the dark net who are connected with them have had 3 years to analyze your passwords history.

They have caught up with your passwords renewal strategy and might even have overtaken you. You might have increased your password length from, say, 7 to 8 characters: no matter. If your passwords production scheme remains the same, and if it is not a coin-flipping process, your password is doomed.

Conclusion

You can either rely on a machine to generate acceptable passwords (and rely on another machine to remember them on your behalf), or rely on your brain to generate broken passwords.

So long for free will...