Mental cryptography and good passwords

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum

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

24 comments

  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
    etc.

    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
    etc

    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).

    • I also found these relevant https://xkcd.com/936/ and https://xkcd.com/792/. The strictly word-based password scheme has the same fault of not having a capital letter, number, symbol, etc., and so I use the string-constant appending scheme described on this article. As a play on of “salt” I sometimes call it “pepper”.

  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??

  10. I see several problems here:
    – I don’t think you can do it fast with a long enough password.
    – As it is mapped to digits you can calculate the number of tries for your password easily and see that you probably want to have at least 15 letters (digits)
    – APPENDING the dog name doesn’t change the part before, so you better prepend it if you want a new password when you change it.
    – choosing something related to the website makes brute forcing your code easy. The entropy of both permutations isn’t very high, so your secret password needs to have good entropy.
    – When the word needs to be secure and different for each site anyway, you can just use this word.

  11. paste.debian.net/hidden/1d7e7964
    I propose another method to easily create and remember how each password
    is constructed. It does borrow an idea from Manuel Blum: that is the 1st
    character is added to the last and this new character added to the 2nd and
    so forth… So I think this an appropriate place to post.

    The system is based on a simple paper slide rule which can be made on the fly.
    The formatting here won’t work because of the font, so please check this link

    Just for demo purposes the keyed alphabet in my example is based on UK QWERTY
    keyboard but any keyed alphabet can be used in the bottom row.
    There are lots of ways to create a keyed alphabet – the important thing is it
    is not easily guessed (as would be in my example) and is easy to remember.

    The issue of when a site requires upper/lower case, number/symbol is easily
    overcome by appending or pre-pending each created password with such as; a1#

    A short remembered word is used before the site name – in my example LOG
    Because the 1st pair to be coded 1st letter L and the last of site name it
    is ok to always use the same short word as will code differently each site.

    If the site insists you regularly change your password it’s usually ok
    to change just one character such as a1# to b1# or a1# to a2#

    In my example LOGHSBCBANK password would be; CJHGNGOHICDa1#

    and LOGGMAIL password would be; VPCOQJKCa1#
    Of course the a1# can be inserted anywhere such as; VPa1#COQJKC
    and you could adapt the method in other ways to make it unique to you!

    TLDR;
    I note in previous posted replies that it is suggested a brute force attack
    may discover the passwords for your other sites if one particular site was
    compromised – but this is not clearly cipher-text – just a password –
    so Kerckhoff’s principle need not apply here and for such a short ‘cipher-text’
    entropy is not easily measured. An attacker would at most (IMO) try his luck
    on your other accounts only with the compromised password or variations of it,
    he has no way of guessing or any reason to think you have a ‘system’ He will
    soon be off to try his luck elsewhere with one of the other compromised
    passwords hoping he finds someone silly enough to use the same password for all
    of their other accounts!

  12. > 3. Compute b1, the first digit of your password, by adding a1 and aN

    In your worked example, you add a0+aN not a1+aN. Did you intend to renumber the “a” sequence to start from 1 instead of 0 in step 2?

    Then:

    > 4. Compute the subsequent digits by bj = g( (bj-1 + aj) mod 10 )

    This says to compute b2, the second digit of output, using a2 which is the _third_ digit of input, because you have 0-indexed “a” sequence and 1-indexed “b” sequence; that surely isn’t right?

  13. Nikko,

    I’m interested in your technique. I have some questions though, and wonder if you have fleshed out your ideas any more in other places? One question, what is the purpose of reversing the alphabet on the second row? Does that add any security to just having the second row be the alphabet with an extra ‘A’ on the end? Using the combination of the last letter with the first letter works nicely to create different passwords for various sites, but if multiple sites end with the same letter, then those sites would all have passwords that share the same prefix. Is that a security concern? Would it be better to interleave the letters, such that LOG and gmail become LgOmGail or something like that?

    Thanks!

Leave a Reply


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