Make a Strong, Easy-to-Remember Password Using Classical Cryptography?

Question

Passwords can be tough to remember. For example:

H7535637353959595*9608J614625C1313^398583I0397897j^

So Bob wants to make and use a good password for GPG that he never has to remember. He will rarely use this password (asymmetric encryption for off-line storage). When he needs it, he is going to generate his password with pencil and paper out of some key information that is stored in one place: his head.

He hopes to employ classical cryptography to turn what he has been unwilling or unable to remember into something that is available. How could Bob make a password strong enough for GPG by using classical methods?

Importantly, he wants to avoid "security" through obfuscation.

Some of the characteristics and principles behind the VIC Cipher came to mind (anyway):

1. A 5-digit number (truly random)

67106 stretched to 10 digits, 67106 + (6+7=3) + (7+1=8) , etc. 6710638169

2. Memorized short phrase: kantscriticalphilosophy (using the first 20 letters). Resulting in 5169827304 and 2159346708

To make a long story short, following Bob's process, mostly like that of the VIC cipher (chain addition, creating permutations of 1 to 0, digit addition without carries), we arrive here:

    5730481269
    NO ADIEUS
  3 BCFGHJKLMP
  9 QRTVWXYZ

3. Bob uses the straddling keyboard on his memorized long phrase:

ITISRAININGINAMSTERDAMBUTNOTINPYONGYANG and puts the result in a columnar transposition whose length is three (not a broken transposition).

Adds a pepper, if you will, at the end of the transposition rows: *^^ and 11=A, 22=B, etc., 111=a, 222=b, etc., 1111=!, 2222=@, etc.

Result: H7535637353959595*9608J614625C1313^398583I0397897j^

With a little practice, it is not difficult to remember a process like what the VIC cipher uses.

Questions:

1. Can a method like this create a password strong enough to use in, let's say, GPG?

2. What would a strong method using classical cryptography for password generation look like?

Answer 1

I fail to see why one would want to use classical or pencil and paper tools for derivation. For anyone attacking your technique it will make no difference. An attacker with a modern computer will only brute force the part you memorized. Any key stretching done on pencil and paper will be a minor nuisance at best; anything done on paper will add no time at all to a brute force attack.

Memorizing something from a high entropy source using various memory techniques is actually useful. Picking words at random or using acronyms can be helpful to memorize something with sufficient entropy. If this is then used with a proper modern key derivation function it can be very hard to attack.

Memory tricks - good

Pen and paper stretching - pointless

Answer 2

If there is no upper bound on the length of the password to be used, the most common suggestion I know to create strong, easily-memorable (for some definition of "easy") password is diceware.

The basic idea behind it is that it chooses each word via a roll of 5 d6's (e.g. each word has $6^5= 7765= 2^{12.92}\approx 2^{13}$ options). The entire password is then some combination of $k$ independent words, giving a password with $\approx {13k}$ bits of entropy. You can then choose $k = 6$ (or other options you want) to get a password with $\approx 80$ bits of entropy.

I just generated the password:

YearlingExquisiteWorstUnsortedDenoteSkipper

Can I memorize it immediately? No. Could I make up a story in $\approx 10$ minutes to vastly aid memorization? Probably. It also has the (massive) benefit that even relatively technologically unadvanced users could feasibly remember the generated password. It also has the (again, massive) benefit that it is "just" encoding a standard $\approx 80$ bit password using a (public) word list to aid human memorization. Mathematically, there is nothing non-trivial going on that may be able to be attacked.

Answer 3

Normally you would use a key derivation function, but since this question is about classical cryptography, I'll stick to the basics. An example of what I'll be doing below can be found on Wikipedia.

I'll assume the user can remember multiple words of different lengths, for example ["london", "istanbul", "sheffield"].

You can use a Vigenere cipher with multiple keys. When you do this, the key for the cipher becomes as long as the least common multiple of the key words. Using the example words, we get 72 characters.

We then start with a string of 72 "A" characters, and then encrypt it using the Vigenere cipher with each key word.

Keywords: ['LONDON', 'ISTANBUL', 'SHEFFIELD']
Least common multiple: 72
Initial key: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Encrypted with LONDON: LONDONLONDONLONDONLONDONLONDONLONDONLONDONLONDONLONDONLONDONLONDONLONDON
Encrypted with ISTANBUL: TGGDBOFZVVHNYPHOWFEOAEIYTGGDBOFZVVHNYPHOWFEOAEIYTGGDBOFZVVHNYPHOWFEOAEIY
Encrypted with SHEFFIELD: LNKIGWJKYNORDUPSHIWVEJNGXRJVISKEDZSQQWLTBNIZDWPCYLOHMRXGZAMVCAKGDJJTIITB
Final result: LNKIGWJKYNORDUPSHIWVEJNGXRJVISKEDZSQQWLTBNIZDWPCYLOHMRXGZAMVCAKGDJJTIITB

Here's some Python code that does this.

#!/usr/bin/env python3
import math
import sys

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

vigenere = {}

for i, letter in enumerate(ALPHABET):
    a = list(ALPHABET)
    for _ in range(i):
        a.append(a.pop(0))
    vigenere[letter] = a

keywords = [x.upper() for x in sys.argv[1:]]

print("Keywords:", keywords)

key_len = math.lcm(*[len(x) for x in keywords])
print("Least common multiple:", key_len)

key = ["A"] * key_len

print("Initial key:", "".join(key))
for keyword in keywords:
    for i in range(key_len):
        key_letter = keyword[i % len(keyword)]
        index = ALPHABET.index(key[i])
        key[i] = vigenere[key_letter][index]
    print(f"Encrypted with {keyword}:", "".join(key))

print("Final result:", "".join(key))

Answer 4

Judging by the use-case and solution it's really a pointless thing to do. GPG is used on a computer, so why would you want to create steps to generate the password manually if in the end you'd still need to write it via keyboard?

If anything, it's a possible attack vector if the instructions get leaked e.g. via a co-located person or you forgetting it somewhere where the cameras/people can read it.

If you want strong password, that's not often used and is properly created... then just use a password manager to hold both the keypair and a random garbage password for it. A proper password manager can manage multiple password databases, thus you wouldn't have a single point of failure.

What you would have is an encrypted blob you need one password for. At the same time you can have two password DBs, one for keys, one for password, so 2 passwords total. Separate them to two places and yet another layer of safety.

So TL;DR you'd have only N-times the password and location to remember and anything else would be random, so unbruteforcable in a reasonable time and secured against dictionary attacks as well + if you don't disclose the locations then even if your passwords have been leaked (social engineering or simple copy-paste into chat mistake), the attacker would still need to get the "treasure chest". A key without a keyhole is just a worthless item.

And it's the best thing for memorization because, well, you don't need to remember the GPG password, nor the algo that generated it.