Uncrackable Passwords

“How long does my password have to be to be uncrackable?”

This question was asked recently on IRC. The person asking it was, no doubt, expecting a simple answer such as “20 characters” or “32 letters, numbers, and punctuation”, but I wondered if there was a proper answer to this.

So, let’s start with some background. What do we mean by and “uncrackable password”? We immediately dicounted the trivial solution of cracking the password by knowing it. So, we’ll go with the usual problem of “brute-forcing” the password. This involves checking one password, then the next, then the next; if your password was a number, brute forcing would start at 1, then try 2, then 3 and so on. For any given number of possibilities, the average password will be found in half the tries.

Now, in order to calculate the password length, we shall momentarily ignore the problems of character sets, special character etc. Instead, our cracker is trying to determine if a binary number is equal to the one we thought of. This helps us a lot, as we’ll see, shortly, because for any N-bit number that we choose, the cracker must, on average, try \(2^N\) attempts.

OK, so now we know what we’re trying to do, let’s start cracking!

One Monkey Typing Forever

In the first instance, we shall start with a single cracker, blindly trying one password after another. So, is there a limit on how many passwords the cracker can try? Well, to work that out, we came up with the idea of a “Planck Clock”. In order to work through the passwords one after the other, the cracker will need a clock and, using the idea of fundamental, universal limits, we posited that the fastest possible clock would be a pendulum that moves back and forth as fast as possible, moving as little as possible.

Now, most people know that “as fast as possible” means the speed of light in a vacuum. This is \(c = 299\;792\;458 \mbox{m/s}\). So what is “moving as little as possible”? Well, it turns out that there’s a quantity called the “Planck Length” which is commonly considered to be the smallest measurable distance (it is much smaller than we can manage at the moment, but the smallest theoretically discernable). The Planck Length is \(\ell_\text{P} \approx 1.616\;199 \times 10^{-35} \mbox{ m}\). So, it follows that our “Planck Clock” ticks at an astounding \(c / \ell_\text{P} \approx 1.855 \times 10^{43} \mbox{Hz}\).

And how long can this clock tick for? There are various theories as to the fate of the universe (big crunch, big freeze etc), but the longest is the “Heat Death of the Universe” whereby the universe keeps expanding and expanding and cooling and cooling until there is no free energy to do any work at all, thermodynamically speaking. This is estimated to be \(10^{1000} \mbox{years} = 3.154 \times 10^{1007} \mbox{s}\) from now.

So, following that, assuming that our cracker can test one password on each tick of the Planck clock and can continue to do so until the universe winds down, he can check \(1.855 \times 10^{43} \times 3.154 \times 10^{1007} \approx 5.861 \times 10^{1050}\) passwords. That’s a lot.

But now comes our special weapon. The logarithm base 2 of a number calculates the value of N such that \(2^N\) is equal to the number. This is the number we had earlier. So, given a number of password attempts, logarithm base 2 of that number gives us the length of password needed. So, given our calculation above, the “uncrackable password length” is \(log_{2} 5.861 \times 10^{1050} \approx 3490.573 \mbox{bits}\), or at least 437 bytes.

Infinite Monkeys

What if, instead of one cracker trying forever, we have a large number of crackers each trying once. By some estimates, there are around \(10^{80}\) atoms in the observable universe. If each one of those was used to store (somehow) each password attempt, then the “uncrackable password length” is quite simply \(log_{2} 10^{80} \approx 265.75 \mbox{bits}\) or at least 34 bytes.

Infinite Monkeys Typing Forever

As an extreme test, let us imagine that our cracker really has some power, that he can run a “Planck Clock” in every single atom in the universe, until the end of time. In that case, the cracker can manage \(5.861 \times 10^{1050} \times 10^{80} = 5.861 \times 10^{1130}\) attempts, giving us an “uncrackable password length” of \(log_{2} 5.861 \times 10^{1130} \approx 3756.330 \mbox{bits}\), or at least 470 bytes.

Summary

So, we’ve determined that the “uncrackable” password must be at least four hundred and seventy bytes long. Bear in mind, though, that these 470 bytes must be completely random. It’s generally a little difficult for people to remember entirely random bytes, so let’s assume that the password will consist of upper- and lower-case characters and numbers. This is quite nice, because it means that each character gives us about 6 bits of entropy (entirely random data). Given our longest “uncrackable password”, that means we need a password which is around 627 characters. Conveniently, that’s as long as this paragraph (minus its punctuation). Can you imagine having to write a paragraph as long as this one, every time you had to unlock your PC? Fortunately, there is a better solution.

There is a reason that we don’t have to type huge great paragraphs each time we log in. And that’s in better hashing algorithms. In our calculations, the cracker was attempting to match their attempt against our password. This is known as a “plain text” attack. However, current password best practices recommend hashing the password. The cracker would thus be required to perform a complex calculation for each attempted password. Some hashing schemes, such as bcrypt, scrypt and so on, mandate that the calculation must be performed many thousands of times before the final hashsum resulted. In that case, the number of possible attempts is reduced that many times and so the length of the password becomes considerably reduced.

But should you ever require a completely uncrackable password, you now know how long it should be.

Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *