Tuesday, April 03, 2012

Make a million-year password

kw: computer security, passwords, analysis

An online bank recently had all its clients upgrade their passwords. In the past, passwords were 4- to 6-digit numbers. Now they have to be an 8- to 10-digit number. Taken at face value, a 10-digit password is not very secure. It has only ten billion possible values, and a special-purpose computer built for cracking encrypted passwords (known as "hashes") can try all ten billion in a tenth of a second. What makes this site more secure is that the password must be entered via a special translation screen that converts it to some kind of text, and it is the text that they check when you are logging in.

Banks and brokerage companies have been slow to attain useful levels of security, but they are getting there. I am rankled by the limit many of them have of ten characters for the length of a password. It is barely adequate, as this chart shows:

Here, based on the number of character strings of each type, we see how long the fastest known machine can try all possible combinations. For example, consider ten characters, limited to upper and lower case letters. There are 5210, or 1.45x1017 possible strings to check. At 1011 per second, the process takes 1.45 million seconds, or 16.7 days.

On average, a password will be found somewhere in the middle of the process. Thus a password such as PlentyHard, or pLeNtYhArD, may take seven or eight or nine days to crack. If you are lucky, it'll take longer; if the cracker is lucky, it might be found almost immediately. Depending on the strategy used by the software, shorter combinations will have been tried already, which might take eight hours, or as much as eighteen. So you see it is necessary to go one step further, either down or to the right, to ensure that at least this level of difficulty is presented to a cyber criminal.

For example, changing a few characters to digits puts you in the next column, such that the full 16.7 days must pass first, before the program tries the next set, which can take three months to crack. But adding a character is much better: PlentyHardy gets into a set that takes 2.4 years to scan, and PlentyHard7 boosts that to 16.5 years, with the 2.4 years as a minimum that has to be got through before the software even tries strings that contain a digit or two.

Here's the rub. Moore's Law for computer power isn't over yet. At present, maximum speed is doubling about every three years. That means that in thirty years, the fastest password cracking machine might be able to check 100 trillion combinations per second. That cuts a 2.4 year task down to under a day. PlentyHard7 just isn't hard enough any more. To be really secure, we need to use passwords that are of thousand-year grade today, so they'll last a while. Even better, let's get into the red territory on the chart above, passwords that will withstand attack for a million years at the 100 billion-per-second rate. They'll still be proof against attack at the kiloyear level in 2040.

Some possibilities:
  • A single-case password with at least 19 characters (e.g. tumblingtumbleweeds)
  • A lower-case-plus-numeric password with 17 characters or more (e.g. dr1ft1nga7ongw1th)
  • A mixed-case password with 16 or more characters (e.g. RoundTHEMountain)
  • A mixed-case-plus-numeric password with at least 15 characters (e.g. Sh3778be8C0m1ng)
While you could save one more character by adding some punctuation, it is hardly necessary. A long, mixed-case password is plenty good enough.

You can see from my examples that I like to use song titles or lyrics and modify them with case shifts and digit substitutions. I am required at work to use at least one punctuation mark, so I might choose Sh377$be$C0m1ng, which can hold off the cracker for billions of years, at present. It is likely to remain secure throughout the 21st Century.

The whole applecart might get upset if quantum computing becomes useful. To crack a password, however, the set of N qubits will have to hold an entire set of hashes of length N. Just getting four values into a qubit has yet to be reliably achieved. Getting more than two qubits to coordinate has also yet to be achieved. Quantum-tronics is quite a bit harder than electronics! But if a quantum computer could set up a string of N qubits with trillions of distinguishable states, a password's hash of size N would be cracked in a single machine cycle (some fraction of a billionth of a second).

If this becomes a reality, we'll be forced to return to banking the old way, with brick-and-mortar branch offices staffed with armies of tellers, handling transactions manually. Even the telephone might be suspect, as programs get better at simulating human interaction. Some things about the good old days are still good.

1 comment:

RunningZombie said...

I know this is a rather dumbed down version of your well written post, but... have you seen this comic about password strength?
http://xkcd.com/936/