Low-tech high-security passwords

You’ve seen this advice many times: use a different password for each website you log into, including lowercase, capitals, numbers, and special symbols. Change it often. If you don’t, a hacker that breaks into one of those websites might be able to get into your bank account and your Facebook page, emptying the first of money and filling the second with child porn. But I’d bet you don’t do it because it’s just too hard to come up with a good password for each website, and then remember it. In this post, I’ll be telling you a paper-and-pencil trick derived from one whose author is none other than Turing award winner Manuel Blum, but far less taxing on your brain.

Here’s what Manuel Blum suggests you do, which is explained in some detail in this article:

1. Come up with these two items that you then memorize: (1) a random mapping of the alphabet into the decimal digits 0-9 (a number of letters will map to the same digits, but that’s okay), and (2) a random permutation of the digits 0-9. Together these two items constitute your secret key.
2. For each website you need to log in, decide what the “challenge” string will be. Most often it will be the name of the website so you don’t have to strain your brain thinking about it, and this is perfectly okay. If that is too short (eight characters or less), append some constant string to make it longer. It is okay if the string you append is always the same, so long as a hacker would have a tough time guessing it.
3. Now perform the following calculation in your head:
   1. Take the letters of the challenge and turn them all into digits using the secret alphabet mapping you memorized. For instance, the challenge for amazon.com is “amazon” (too short, but it will do as an example), which turns into these digits: 929073 because your alphabet mapping was “a” = 9, “m” = 2, and so forth.
   2. Now take the first digit, add it to the last, and keep only the last figure (9+3=12, so we keep 2), and then type in the digit occupying this place (10th for the 0) in your secret permutation (if the permutation was 5870163429, then the 2nd digit is 8).
   3. For the rest of the digits, add the last digit you typed to the next one in the challenge turned into numbers, and find the digit in the permutation occupying the position given by the last figure in the result (we obtain in succession 8+2=10 -> 9, 9+9=18 -> 4, 4+0=4 -> 0, 0+7=7 -> 3, 3+3=6 -> 6, for a final result: 894036).
4. If the website takes this directly, you’re done. If it also requires lowercase, capitals, and so forth, append a ready-made string (fine if it’s always the same) to appease the password censor. So we may end up entering “894036aB$” to log into amazon.com.

The reason why this works is that you are applying a nonlinear operation (the alphabet mapping) for every input letter, and then another nonlinear operation (the digit permutation) for every output digit. If we call the letters x₁, x₂, and so forth all the way to x_n, the alphabet mapping f(x), the permutation g(x), and the output numbers y₁, y₂, etc., we have the following equations:

y1 = g(f(x1) + f(xn) mod 10)
y2 = g(f(x2) + y1 mod 10)
.............
yn = g(f(xn) + yn-1 mod 10)

This is quite similar to the operations involved in the FibonaRNG cipher, described not long ago on this blog, except that in FibonaRNG the functions f(x) and g(x) are alphabet permutations that convert letters into other letters, and it’s mod 26 rather than mod 10. So here’s the simplification of Blum’s method that I propose: use letters in all the operations, which means using a Tabula Recta to help with the base 26 operations, but one whose headers have been modified by means of secret permutations (a “Tabula Prava” as described in this article). Since the user will likely end up carrying a printed Tabula Recta in his/her wallet, there is little harm writing in those headers (assuming there is enough security on one’s person) on the table itself, thus avoiding memorization altogether. I will illustrate it with an example to follow the steps:

1. Come up with two secret mixed alphabets. In this article, I present a method for generating them from a passphrase of triple length. In this case we need only 25 x 2 = 50 characters, which means that the passphrase must be 150 characters long, which we write down as three rows, and then combine column by column by means of serpentine operations on the Tabula Recta (find first letter at the top, go down to find the second letter, then left or right to find the third, and finally up to read the result). Then for each group of 25 letters in the result, write down every new letter found, or the immediately preceding one still available if a letter has already been used. Put the first alphabet on the left side of the Tabula Recta, the second one at the top, to form the Tabula Prava. Let’s say my passphrase is the first paragraph of Dickens’s “Oliver Twist.” Then I will obtain the following work table:

   AMONGOTHERPUBLICBUILDINGSINACERTAINTOWNWHICHFORMAN
   YREASONSITWILLBEPRUDENTTOREFRAINFROMMENTIONINGANDT
   OWHICHIWILLASSIGNNOFICTITIOUSNAMETHEREISONEANCIENT
   --------------------------------------------------
   QRRVQHOLEJEMISPEZQCNHXNVXZXPDRJSZKGLTWIVNHTZFKZDKN

   from which I obtain the substrings “QRRVQHOLEJEMISPEZQCNHXNVX” and “ZXPDRJSZKGLTWIVNHTZFKZDKN.” The first yields this alphabet: “QRPVOHNLEJDMISKCZGBFAXYUWT”, and the second this one: “ZXPDRJSYKGLTWIVNHQUFEOCBMA” resulting in the Tabula Prava below, which I will use from now on for all operations:

   Z X P D R J S Y K G L T W I V N H Q U F E O C B M A
   ---------------------------------------------------
   Q | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z | Q
   R | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A | R
   P | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B | P
   V | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C | V
   O | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D | O
   H | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E | H
   N | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F | N
   L | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G | L
   E | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H | E
   J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I | J
   D | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J | D
   M | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K | M
   I | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L | I
   S | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M | S
   K | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N | K
   C | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O | C
   Z | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P | Z
   G | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q | G
   B | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R | B
   F | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S | F
   A | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T | A
   X | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U | X
   Y | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V | Y
   U | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W | U
   W | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X | W
   T | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y | T
   ---------------------------------------------------
   Z X P D R J S Y K G L T W I V N H Q U F E O C B M A

   The process above gives you the equivalent of 177 bits of entropy, which may be overkill in many cases. You can simplify things, at the expense of some of that surplus security, if you use your memorized key phrase (perhaps a simple collection of words) directly to form each alphabet. Again, the algorithm is: write any new letter as it appears, and if the letter has already been written, write the first one preceding it on the alphabet that is still available (cycle to the end if necessary); when you run out of key letters, write the rest of the alphabet in reverse order. Example: “among other public” gives the alphabet “AMONGLTHERPUBKICZYXWVSQJFD”. This process gives you an average 1.58 bits of entropy per letter, or 10 bits per dictionary word.

2. Now do the Blum algorithm starting with the letters in the challenge, but instead of sum modulo 10, look up the challenge letter at the top of the Tabula Prava, then go down to find the previous letter of the result, then left or right to read off the next result letter. For the first letter, use the last challenge letter instead of previous result letter. Let’s say the challenge is “amazon” because I am generating a password for amazon.com. I look up “A” at the top (first letter) and then go down until I find “N” (last letter), then left or right to read “K” at the edge, which I write down. Then I look up the second letter at the top, “M”, and go down until I find the previous result letter “K”, and then left or right to read “I” at the edge, which I write down. I do the same with all challenge letters and in the end I have this working table, where I have repeated the last challenge letter at the start of the bottom row so I combine the letters in each column every time I go to the Tabula Prava:

   AMAZON
   NKIJJKX

3. The result (bottom row minus the first letter) will be a random-looking letter sequence of the same length as the challenge, which will be quite secure just by itself: “kijjkx”. If login requirements involve capitals, symbols, or digits, add a constant string of the appropriate composition to appease the automatic censors.

I have made a little JavaScript program implementing this process, so you can experiment to your heart’s content. The program also gives some statistical properties of the output Password, so you can check just how “random” it is (and therefore hard to crack). This won’t be very significant for the typical 10 to 20 characters long password, but if you paste in a long challenge (say, a piece of text containing a few thousand characters), you will see that, even though all letters appear with the same frequency, which is good, the string fails the independence test (last one), meaning that some pairs of letters are more frequent than others, a statistical artifact deriving from the challenge being a piece of real text. So don’t use this process to generate a “hash” of the challenge, but it should be fine for passwords. I haven’t checked this, but it is highly likely that Blum’s algorithm suffers from the same defect, so it should not be called a “hash” either.

I have also made a 8.5″ x 11″ graphic containing a Tabula Recta that you can print any time you want, and where you can write in your mixed alphabets. If you want to carry it in your wallet, cut out the extra paper as in the picture below, then fold it so it fits.

Would an attacker who obtains a password so derived be able to compromise other passwords? This would involve coming up with the two mixed alphabets, which is like obtaining the functions f(x) and g(x) from the equations near the top of this article, starting from a knowledge of the result and, presumably, the challenge text from which it is derived. As we saw in this other article, this converts into a system of linear equations where the unknowns are f(“a”) to f(“z”) and g^-1(“a”) to g^-1(“z”), that is, 50 of them (the last letter in each alphabet is always forced by the others). So 50 equations are needed, which likely would require four or five compromised passwords, not just one. This would buy you time to change the passwords in all your logins, starting from a different set of alphabets.

In the case of Blum’s algorithm, a hacker would need 36 letters, which might come from three or four compromised passwords if everything lines up all right. This by itself is not enough of a problem to prefer the algorithm presented here, however. The clincher is that you need to memorize the parameters for Blum’s method whereas the Tabula Prava you can carry in your pocket. If the mixed alphabets are of the kind that you make directly from key words, you will still have perfect security if you write them in right before using the Tabula, and then erase them. Otherwise you can leave them written in, in which case you should treat that piece of paper as you would treat your house keys. You can also the other side of the paper to write down some frequently used passwords and do away with the whole algorithm until you want to change the passwords again 😉

Update: a year and a half have passed since I wrote this, but the general strategy outlined here is still valid, and in fact works great with a computer helping the user do do the number crunching and stronger, well vetted algorithms. The result is the Chrome and Firefox extension SynthPass, which I have just released into the respective web stores. This article talks about it.