Mental cryptography and good passwords

Good passwords are hard to remember. A pattern that makes a password memorable is likely to make it vulnerable to attack. If remembering one secure password is hard, remembering many such passwords is entirely impractical. So people who have gone to the effort of creating one good password use it for many different accounts. A security breach anywhere that password is used means that the password is vulnerable everywhere else it is used.

It is much safer to have different passwords for every account. Then if one password is compromised, the damage is limited to a single account. One way to accomplish this would be to have software compute a password for each account by encrypting the name of the account. For example, your password for Home Depot could be the result of encrypting the text “homedepot.” This way accounts with different names would automatically have different passwords. (In practice, it might be possible but highly unlikely for two account names to result in the same password.)

If you generate your passwords this way, you have to trust the software that is generating them. What if that software turns out to have a security hole, either as a result of malice or error? If you could carry out the encryption in your head, you would not need to trust any software.

Is it possible to create encryption algorithms that a human can execute but that a computer cannot break? It doesn’t seem at first that this should be possible, but Turing Award winner Manuel Blum believes it may be. He presented his proposed algorithm at the Heidelberg Laureate Forum. He emphasized that his method takes a lot of up-front effort to learn but then it can be carried out quickly. To prove this claim, he demonstrated that at least one person has in fact used the method, namely himself! He said he can usually come up with a password in under 20 seconds.

Manuel Blum Credit: hlff / Flemming

Manuel Blum
Credit: hlff / Flemming

To use Blum’s method you must memorize two things: a random mapping of letters to digits, and a random permutation of the digits 0 through 9. The random map and the random permutation are your personal keys so you must keep them secret. They must be truly random — any pattern that makes them easier to memorize may make your system easier to break — and that’s why this up-front memorization is hard. But it only has to be done once.

Call your mapping of letters to digits f. You might have, for example, f(a) = 8, f(b) = 3, f(c) = 7, etc. Since there are more letters than digits, some letters will be mapped to the same digit.

Let g be the function that sends each digit to the next one in your permutation. So if your permutation was 0298736514 then g(0) = 2, g(2) = 9, g(9) = 8, etc.

Now here is how you use the method to generate passwords.

  1. Convert the name of your account to a sequence of n letters.
  2. Turn this sequence of letters into a sequence of digits using your map f. Call this sequence of digits a0a1a2an.
  3. Compute b1, the first digit of your password, by adding a1 and an, taking the last digit, and applying the permutation g. In symbols, b1 = g( (a1 + an) mod 10 ).
  4. Compute the subsequent digits by bj = g( (bj-1 + aj) mod 10 ).

So if your account name converts to “abc” in step 1, this becomes 837 in step 2. The first digit of your password would be 1 because the first and last digits of 837 add to 15, and g(5) = 1. The second digit would be 0 because the previously computed password digit, 1, and the second digit of 837 add to 4 and g(4) = 0. The third digit would be 3 because 0+7 = 7 and g(7) = 3. Thus your password would be 103. (In practice your account names would need to map to more than just three characters, but using “abc” kept the example short.)

The way you create a sequence of letters for an account could be anything you like. For example, you could add your dog’s name to the end of every account name if you’d like. If a particular password is compromised, you could change your password by putting something new on the end, say the name of your neighbor’s dog, and going through the encryption process again.

This method only produces digits. If a particular account requires, for example, that all passwords contain a letter and a punctuation mark, you could stick an arbitrary fixed sequence like “k$” on the end of the digits. If the digits produced by Blum’s algorithm create a secure password, always adding the same characters on the end makes the password no less secure.

Blum’s method is practical, though it takes memorization and practice. More generally, it is an illustration of a research into the possibilities of human computation.

Video of Blum’s complete lecture – including slides

18 comments Write a comment

  1. Bruce: You are correct, and my error in the second digit caused the third digit to be wrong. I’ve submitted a correction to be posted.

  2. A good idea in theory, but I see problems that make this not practical:
    – you have to remember the account names (ex: is it “gmail” or “googlemail”)
    – some sites enforce (annoying) policies about how your password should be formatted. Adding “k$” will only work when the site requires one letter and one non-alphanumeric character. But then some will require capital letters, or n different digits, etc … It is impossible to predict beforehand a single suffix that would suit all such policies you could ever encounter
    – even then, sometimes sites could force you to change your password (either they suspect they have been compromised, or they just have a policy of forcing you to change regularly), and with a “hard” site->password mapping, you cannot do that

  3. Re 1st comment: by using the domain name as challenge e.g. fedex for fedex, ebay for ebay, etc, one avoids this problem.

    Re 2nd comment: it’s easy to change a password by attaching a digit to the challenge:
    MAGIC1 -> 4 3 6 1 1 5
    MAGIC2 -> 2 9 2 8 4 9
    MAGIC3 -> 9 8 4 2 3 9
    MAGIC4 -> 1 2 3 4 0 4
    MAGIC5 -> 3 1 1 5 7 5
    MAGIC6 -> 6 0 9 0 9 2
    MAGIC7 -> 0 4 0 7 8 2
    MAGIC8 -> 7 7 8 6 5 8
    MAGIC9 -> 5 6 5 9 2 7

    Re 3rd comment:
    You are absolutely right. Remembering the original password requirements (length, allowed characters, characters not allowed) can be a pain. This will be a problem until sites requesting passwords remind users of their requirements.

  4. The method as explained in the lecture doesn’t meet reasonable security concerns. For example, on one slide there a number of plaintext/ciphertext pairs:

    BRAIN -> 06076
    TRAIN -> 27732
    GRAIN -> 35618
    DRAIN -> 54349

    From these four pairs one can deduce enough information about the mapping g( ) to determine the hidden secrets. In this case, the permutation cycle that determine g( ) is:

    (8, 1, 0, 6, 2, 7, 9, 3, 5, 4 )

    with g( ) it is now easy to decrypt the rest of the system.

  5. Todd: In that example, you have a chosen clear text attack, and Blum did say that the method is vulnerable to such an attack.

    I don’t think he mentioned that in his lecture. I had lunch with him some time later and he said that he wished he could give a list of pros and cons of the method, but that would be too much for the time allowed. He did mention chosen text attacks as a con.

    In the context of a password scheme, however, you’re not obligated to give an attacker encrypted versions of chosen text. If you start with domain names, and you have accounts on four domains that differ only in their first letter, and all four are hacked, and someone has access to your passwords on all four sites, then you’re in trouble, though that’s far-fetched.

    • Yes, John, you’re correct that those four plaintext/ciphertext pairs are convenient for determining g( ), but the method I used is so simple that I did it on a few pieces of paper by hand. The key observation is that letters appearing more than once in a single plaintext/ciphertext pair or repeated across a few plaintext/ciphertext pairs reveal enough information to attack the system. This is not a chosen plaintext attack.

      For example, DRANA -> 8 1 2 4 3, by itself reveals that g( 1 + f(A) ) = 2 and g( 4 + f(A) ) = 3. Since there is one k in {0,…,9} such that g(k) = 2, we can conclude that g(k+3) = 3. I found it easy to reconstruct g( ) by hand using such relationships. It wouldn’t take more than a few 8 character domain names to limit g( ) to a number of possibilities that could be rapidly tested by a computer program. Once this is done, the system is effectively broken.

      Further, consider a plaintext like DRANAGA, it has ciphertext 8 1 2 4 3 9 8. Notice that this gives away the cipher text for DRANA.

  6. a workaround for the letter-to-digit mapping without brute memorizations would be to use a cyclic generator mod 9, e.g:
    A: 1×5 mod 9 = 5
    B: 2×5 mod 9 = 1
    C: 3×5 mod 9 = 6
    D: 4×5 mod 9 = 2

    you could use the same technique to generate a g() permutation.
    1×7 mod 9 =7
    2×7 mod 9 =5
    3×7 mod 9=3
    4×7 mod 9=1

    the multipliers need to be relatively prime to 9 (ie, 2, 4, 5, 7, 8)

    • The problem is that the security inherent in the random number generator is reduced to 5 choices, giving the password <3 bits of entropy!

  7. Is there any posted-online analysis of this particular algorithm? Mainly I’m interested in humane hashing or humane psuedorandomnumber-generating algorithms for non-cryptographic purposes, although if there are good humane algorithms for cryptogrpahic purpose, I’d definitely be interested. I doubt/hunch that this one is good for psuedorandom number generating.

    Also, how should the random map be generated? The 26 letters vs 10 numbers thing presents an issue that can be done a couple different ways (I don’t know which is best/intended). Each letter independently randomly assigned a number (allowing more than minimum collisions or missing values), or bijection with the numbers 1-20 union six random numbers from 21-30 and then modulating (minimum amount of collisions).

    I barely know about crypography (or even computer science in general).

  8. The mapping could be done with the aid of the QWERTY keyboard. It should be easy to memorize a random permutation of keyboard keys by typing it out frequently, just like a password.

    1. Permutate the website name in QWERTY-space
    2. Use the digit row to map to digits. e.g. Q,A,Z -> 1; W,S,X -> 2; etc.

    In fact, the addition could be done in QWERTY-space too, so we don’t even need a mapping into the numerical domain. Each key can be described as a three-dimensional vector (column, row, case).
    key1 + key2 = (column1, row1, case1) + (column2, row2, case2) = ((column1 + column2) mod 10, (row1 + row2) mod 4, (case1 + case2) mod 2)

    The addition of columns is aided by the digit row of the keyboard.

    So the algorithm is reduced to:
    1. b_1 = g(a_1 + a_n)
    2. b_i = g(b_i-1 + a_i)

    In other words:
    1. Add the first and the last letter of the domain name.
    2. Permutate -> password letter
    3. Add next letter in domain name
    4. Continue at step 2

  9. Is it really worth all this effort? Passwords made of only numbers and stuffs like that are always weak even it has a complex semantic behind its construction. In the end, they are just a stream of characters and a simple brute force algorithm can break it. Or did I misunderstand something??

Leave a Reply

Bitte ausrechnen und die Zahl (Ziffern) eingeben

E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +