6
$\begingroup$

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

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

$\endgroup$
4
  • 1
    $\begingroup$ When an attacker knows how you generate your password (and you always should assume that), an algorithm applied to the key becomes useless in terms of security. Expanding the keys does not add any security at all. You only can make it more memorizable which allows for longer initial random keys (which is the only thing you should care about) $\endgroup$
    – jjj
    Jul 26 at 1:38
  • $\begingroup$ @jjj well, a computationally expensive key-derivation function does add security because it makes brute-forcing take more time. But of course, computing such a function even once by hand would then have to take years, if not millions of years. $\endgroup$ Jul 26 at 10:12
  • $\begingroup$ "... a [password] that he never has to remember .... when he needs it, he is going to generate his password [out of] some key information that is stored in one place: his head". So you want Bob to not have to remember anything.... by remembering something? This seems really pointless. Just choose a sensible password instead of 51 random characters (as in your first example) which is unnecessarily long for any feasible attack method anyway. $\endgroup$
    – JBentley
    Jul 26 at 11:39
  • 1
    $\begingroup$ This reminds me of a past question of mine: Strong PHP hashing without salt. TL;DL the purpose is to use personal information to generate passwords, that I can reproducibly generate again. $\endgroup$ Jul 26 at 15:11
21
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ (assuming the attacker knows what you did) $\endgroup$
    – user253751
    Jul 25 at 15:59
  • 3
    $\begingroup$ That is indeed the best practice. and the question explictly states a desire to not rely on security by obfuscation. $\endgroup$
    – Meir Maor
    Jul 25 at 16:07
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ No need to use software. Just pick a song you remember all the words to to use as a word string. The universe of songs is big enough. Then on top of that pick an easily-remembered algorithm and keep it private ("the second and third letters of every word that starts with a consonant") and you'll have no problem keeping appropriately difficult-to-guess strings hundreds of characters in length entirely in your head. You can even write down which song encodes which passwords, without the derivation scheme even that's not enough to realistically brute-force. $\endgroup$
    – John Smith
    Jul 26 at 5:44
  • 2
    $\begingroup$ @JohnSmith If you are going to store information about your passwords, it should not be in an ad-hoc way --- just use a password manager. If you want your master key to be from some ad-hoc scheme fine, but I see no reason to do this, as it makes it difficult to argue the quantitative strength of your password. Moreover, training yourself to type some words "wrong" in a way that correlates with your passwords seems fairly suspect. $\endgroup$
    – Mark
    Jul 26 at 6:54
1
$\begingroup$

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))
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I understand your first point, but that is why the use-case is offline storage. I see what you are saying in your latter discussion. $\endgroup$
    – Patriot
    Jul 24 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.