Upping the password ante

 kw: computer security, passwords, analysis

Almost thirteen years ago I wrote about making "million-year passwords", based on the fastest brute-force cracking hardware of the time, that was approaching speeds of 100 billion hashes per second. The current speed record I can find is only 3-4 times that fast, at just over 1/3 of a trillion hashes per second, but it is a lot cheaper. It seems the hardware scene hasn't changed as much as I might have thought.

I surmise that more sophisticated phishing and other social engineering schemes have proven more effective than brute-force pwd file crunching. However, the racks of NVidia GPU's being built to run AI training are ramping up the power of available hardware, so I decided to make a fresh analysis with two goals in mind: firstly, based on a trillion-hash-per-second (THPS) potential rate, what is needed for a million-year threshold?, and secondly, is it possible to be "quantum ready", to push the threshold into the trillion-year range?

I plan to renew my list of personal-standard passwords. The current list is five years old, and contains roughly twenty items for various uses. I have more than 230 online accounts of many types, so I re-use each password 10-15 times, and I activate two-factor authentication wherever it is offered. The current "stable" of passwords range from 12 to 15 characters long. I analyzed them based on an "All-ASCII" criterion, but since then I've realized that there are between six and 24 special characters that aren't allowed in passwords, depending on the standards of various websites.

The following analysis evaluates six character sets:

1. Num, digits 0-9 only. The most boneheaded kind of password; one must use 20 digits to have a password that can survive more than a year of brute-force attack.
2. Alpha1, single-case letters only (26 letters).
3. Alpha2, both upper-and lower-case letters (52)
4. AlphaNum, the typical Alphanumeric set of 62 characters.
5. AN71, AlphaNum plus these nine: ! @ # $ * % ^ & +
6. AN89, AlphaNum plus these 27: ! @ # $ % ^ & * ( ) _ - + { } [ ] | \ : ; " ' , . ? ~

The only sets that make sense are AlphaNum and AN71. The shorter sets aren't usually allowed because most websites require at least one digit, and usually, a special character also. AN89 provides a few extra characters if you like, but almost nobody allows a password to contain a period, comma, or any of the braces, brackets and parentheses. I typically stick to AN71.

The calculation is straightforward: take the size of the character set to the power of the password length. Thus, AlphaNum (62 in the set) to the 10th power (for a 10-character password) yields 8.39E+17. The "E" means ten-to-the-power-of, so 1E+06 is one million., a one followed by six zeroes. Negative exponents (the +17 above is an exponent) mean the first digit is that many characters to the right of the decimal point.

Next, divide the result by one trillion to get seconds; in scientific notation, just subtract twelve from the exponent, which yields 8.39E+05, or 839,000 seconds. The number of seconds in one year is 86,400 × 365.2425 (86,400 seconds per day, 365.2425 days per Gregorian year). Divide by this; in this case, the result is 0.0266, or about 9.7 hours.

Are you using a 10-character alphanumeric password? It will "last" no more than 9.7 hours against a brute-force attack with a THPS machine. If you were to replace just one character with a punctuation mark, such as %, the machine would find out, after 9.7 hours, that your password is not alphanumeric with a length of ten. It would have to go to the next step in its protocol and keep going. If its protocol is to run all 10-character passwords in AN71 (perhaps excepting totally alphanumeric ones, since they've all been checked), 71 to the tenth power is 3.26E+18. The number of seconds taken to crack it is now 3.26 million, about a tenth of a year: 38 days.

We're still kind of a long way from a million-year level of resistance. To save words, I'll present the full analysis I did in this chart.

The chart is dense, and the text is rather small. You can click on it to see a larger version. The top section shows the number of seconds of resistance each item presents, with one hour or more (3,600 seconds) highlighted in orange. The middle section lists the number of days, with a pink highlight for more than seven days. The lower section lists the number of years with four highlights:

• Yellow for more than two years.
• Blue for more than 1,000 years.
• Green for more than one million years.
• Pale green for more than one trillion years, what I call "quantum-ready".

For what I call "casual shopping", such as Amazon and other online retailers, the "blue edge" ought to be good for the next few years. For banking and other high-security websites, I'll prefer the darker green section. That means, using AN71, I need 13-character passwords for the thousand-year level, and 14-character passwords for the million-year level.

There is one more wrinkle to consider: The numbers shown are the time it takes a THPS machine to exhaust the possibilities at that level. If your password is "in" a certain level, it might not last that long, but it will last at least as long as the level to its left. For example, AN71 of length 12 shows 520 years. Not bad. If you have an AN71 password of length 13, the cracking machine would need 520 years, to determine it isn't 12 characters or fewer, but once it starts on 13-character passwords, maybe it will take it half or more of the 36,920 years indicated to find it, but it might luck out and get there much sooner. But it still consumed 520 years getting this far. Anyway, if you're going for a certain criterion, adding a character makes it definite that at least that length of time would be needed for the hardware to get into the region in which your password resides.

Another way to boost the resistance is to have at least two special characters, one (or more) from the AN71 set, and at least one from the rest of the AN89 set, such as "-" or "~", wherever a website allows it. Then a machine that checks only within AN71 will never find it.

With all this in mind, I plan to devise a set of passwords with lengths from 13 to 16 characters, using primarily AN71. On the rare occasion where I can't use special characters, I'll have AlphaNum alternatives with 14 to 17 characters prepared. I'll test if I can use a tilde or hyphen, and use one of them if possible for the really high-security sites.

A final word about password composition. I actually use pass phrases with non-alpha characters inserted between words or substituted for certain letters, and occasional misspellings. Starting with a favorite phrase from Shakespeare, Portia's opening clause, "The quality of mercy is not strained", one could pluck out "quality of mercy" (16 characters) and derive variations such as:

• qUal!ty#of#3ercY
• QW4lity70f8M&rcy
• quality$of~MERC7
• qua1ity2of2M3rcyy (AlphaNum with an appended letter)

…and I could add more than one character in place of the space(s) between words…

It is also worth keeping abreast of news about quantum computing. What exists today is dramatically over-hyped. It may not always be so. But I suspect a trillion-year-resistant password will remain secure for at least a generation. 

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 52¹⁰, or 1.45x10¹⁷ possible strings to check. At 10¹¹ 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 21^st 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.

Is twelve bytes enough?

kw: computers, hacking, passwords

Following up on an earlier post: There are two things a cybercriminal needs to obtain to begin cracking a bunch of passwords from their encrypted record (hashes). Firstly, the file of the hashes themselves, and secondly, knowledge of the hashing algorithm. DES is quite popular, but is by no means the only one in use. The best feature of a good hashing algorithm is that it does not reveal the length of the original password. Heaven help you if your online bank uses a weak hash or doesn't hash at all!

So, having somehow stolen a file of passwords, the cracker proceeds by trying character strings in some logical sequence, producing the hash, and seeing if it matches any of the hashes in the file. This matching step can be very fast, but I suspect it takes a while if you have a million hashes to check.

The record speed of a special-purpose cracking machine is just under 10¹¹ tests per second, when attacking a single hash. Obviously, it is much more efficient to sort the file of hashes using the hash as a key, then use a binary search to check a generated hash. A million hashes can be checked with only ten lookups. Not knowing how long those ten lookups might take, though, I'll continue the analysis by considering a hacker who is determined to get me, and has only one hash to test each iteration, at that 10¹¹/sec rate. What do I need to do to hold off the attack for at least a year? Simply put, since a year has 3.156x10⁷ seconds, I need a password long enough and complex enough to be a member of a universe with at least 3.156x10¹⁸ members. To push that out by a factor of a thousand, you need 3.156x10²¹ members.

Let us assume the perpetrator uses a logical series of steps, based on human nature. Shorter passwords are still most common; lower-case letters only and UPPER-case letters only are very common; adding a numeric digit, or a few, is getting more popular; MiXeD-case is somewhat rarer; mixed case plus digits is very rare, and the addition of special characters is done only if someone forces you to do it, or you are very, very paranoid. Someone having a super-cracker machine won't bother with a dictionary hack, but will just use all combinations.

Here is what it takes, for now, and for ten years from now when a cracking box might be 1,000 times as fast:

• UPPER- or lower-case only. N = 26^L. For L = 13, N = 2.48x10¹⁸, not quite enough, so go with 14 letters, where N = 6.45x10¹⁹, for now. For later, you need 16 letters
• Either case plus some digits. N = 36^L. For L = 12, N = 4.74x10¹⁸, OK for now. For later, L = 14.
• MixEd-cASe letters. N = 52^L. For L = 11, N = 7.52x10¹⁸, good for now. For later, L = 13.
• Now add digits. N = 62^L. You still need L=11 for now, because 62¹⁰ = 8.39x10¹⁷. For later, 12 is enough.
• Finally, if the full ASCII set is allowed, N = 95^L. For L = 10, N = 5.99x10¹⁹, more than good enough for now. For later, 11 characters is sufficient.

Of course, as one progresses down this list, it gets harder to remember the password unless you are quite clever creating it. If fourteenletter or FOURTEENLETTER is as hard to crack as M#nE3pa$5w, though, which one is the better choice? And for the future, dEEPsnowINspring, at 16 letters of mixed case, is from a universe of 2.86x10²⁷; probably good for the rest of your life.

Strength in length

kw: computers, hacking, passwords

The time will come when, if you want to have a secure password, it will have to be something like

Now i$ the t1m3 4 all g00d men 2 c0m3 2D aid of th31r Cntry

or, if spaces remain disallowed,

Nowi$thet1m34allg00dmen2c0m32Daidofth31rCntry

Now that larger numbers of cyber criminals have turned from stealing data to stealing money from online banking systems, protecting online accounts is even more necessary. The most frequent attacks recently have been aimed at an institution's customer records. If your bank is any good, your password is not stored with your account, but a "hash", or encrypted version of the password. When you log in, your password is encrypted to a hash and compared with the hash on file. If a criminal obtains those online records, the password is difficult to extract from the hash…difficult but not impossible.

Suppose that, like many, your password is only six characters, all lower case, perhaps with a numeric digit or two included; a password like my1dog. Someone wishing to crack your record will start with letters-only, then letters plus one digit, and so forth. A six-letter lower-case password will be one of 26⁶ possible strings, from aaaaaa to zzzzzz, a total of about 309 million possibilities. Let one letter be a digit, and the total becomes 428 million. Those sound like a lot. But the criminals in this billion-dollar industry aren't afraid to spend money on hardware, and a recent exploit by the system Deep Crack was able to test nearly 100 billion possibilities per second. Your password would be extracted within 0.004 seconds!

Of course, for some time, it has been required at most banking sites to use at least eight characters, and it is "suggested" that both lower case and upper case and digits be mixed. The possibilities then get more numerous, because 26+26+10 = 62, and 62⁸ = 218 trillion. That's more like it! Let's see, 218 trillion divided by 100 billion = 2,180 seconds, or about 36 minutes. If someone wants those passwords bad enough, and has the equipment, the hard part is getting the banking records in the first place. That done, passwords can be extracted at the rate of forty per day of CPU time. That is still not very comforting. Eight is not enough.

In length is strength. For the current time, it is better to use nine or ten characters, and keep things mixed up. Each added character multiplies cracking time by 62: 9 char means 37 hours and 10 char means 97 days. That is more like it. However, each decade that passes, ultimate computer speeds increase by a factor of 1,000. In about 2020, cracking a 10 character alphanumeric password will be achievable in about 2½ hours.

If you want a password to last a while, the time is now to go to at least 12-character passwords, which are nearly 4,000 times as hard to crack as 10-character ones. If your banking site allows certain punctuation marks also (such as $ # % @ * ), that just makes things even harder for the criminal.

Now, however are you going to remember such passwords? I find it hard to remember 5Zep38xN, which was suggested to me by an institution not long ago. Of course, I didn't use that, but created a longer one, based on an algorithm. I have a different algorithm now, so I can discuss the older one in relative safety. It worked like this:

• Choose a 12-letter word such as homozygosity.
• Break it into two or three parts (I usually used 2, but let's use 3 here): homo zygo sity .
• Mix the three in sequence: hzsoyimgtooy .
• Replace certain letters with numbers or punctuation: hz$oy1mgt00y (notice I didn't change one of the o's to a zero).

Now you have the problem of remembering it! hz$oy1mgt00y is not memory friendly. You simply have to keep a list. I keep my list in two parts: Part 1 contains such passwords and their generating words, and Part 2 has the account identity and just the generator word. I carry Part 2 and keep Part 1 hidden away. For further security, I have user names, wherever possible, that are as obscure as the passwords. I keep the decoding information on Part 1 and "reminders" on Part 2. With practice, if I can't remember the password from the hints on Part 2, I can regenerate it on the fly.

Passwords such as the one created here (Don't use it! Use a different starter word) will require a cracking computer to go through nearly 4x10²¹ combinations, which will require more than 1,000 years. In another ten years, it'll still take a year or more, so somebody will really have to want it bad to attempt it. And by then, who knows, maybe the web site will look at me through my web cam, listen to my voice, and "recognize" me. I'll address the problem of duress later…