Innovation and design

Memorising a stronger cryptographic key for the same effort

by | Published

The method described in the 2018 article [KEY] for memorising a cryptographic key allows someone to reconstruct any 128-bit number that they have been given to memorise. That article implicitly assumes that the number is the cryptographic key itself. This article describes a way to use the same memorisation method with an alternative approach to cryptographic key derivation having two advantages:

  1. The key is very likely to have more entropy for the same amount of memorisation work, although there is no obvious way to make a quantifiable guarantee of how much more.
  2. There is no need to retain lookup tables for conversion from the mnemonic back to the key.

The two approaches are shown in Figure 1.

    _______
   /       \
   | TRNG  |
   \_______/
       |
       V       H = 128 bits
  +---------+   +--------+
  |128 bits |-->| Key 1  |
  +---------+   +--------+
       |            ^
  _____V_____    ___|____
 /   __O__   \  /        \
 |     |     |  | Words  |
 |    / \    |  | reverse|
 |Personal   |  | lookup |
 |memorising |  |        |
 |choices    |  |        |
 \___________/  \________/
       |            ^
       V            |
 +-----------------------+
 |   16-word mnemonic    |
 +-----------------------+
       |     H > 128 bits
    ___V___
   /       \
   |  KDF  |
   \_______/
       |
       V
  +--------+
  | Key 2  | H > 128 bits
  +--------+
Figure 1. Two alternative ways of using a mnemonic to (re)generate a cryptographic key, shown in the same diagram only for concision. In both cases the mnemonic is chosen in the same way, described in [KEY]. Key 1 illustrates after-the-fact memorisation, as assumed in [KEY], where the key is fixed before memorisation. Key 2 illustrates an alternative way, where any additional entropy (H) from human choices of words to memorise also goes into a key derivation function (KDF) and hence the key. The human input can only increase and never reduce the entropy from the original random number, because that number could be extracted from the mnemonic, even though it will not be.

In the second approach, a key derivation function (which could be a simple cryptographic hash) is used to convert the mnemonic itself into a key. This means the choices made for words to memorise in the mnemonic have become part of the key generation process.

In the world of crypto-currencies, BIP39 (bitcoin improvement protocol) is a standard for writing a strong secret as a mnemonic. It uses this second approach, applying a KDF directly to the mnemonic rather than using the original random number. However BIP39 does not obtain any entropy advantage from this, because it has a bijective mapping from binary number to mnemonic which does not allow any human choice in the mnemonic. It does reap the second advantage of being able to get from the mnemonic to the key without needing a record of the mapping between mnemonic and the original random number.

Practical discussion

Of course the extra entropy generated by the second approach will be wasted unless the key is big enough to hold it. In Figure 1, with 128 bits from the random number generator, Key 2 would have to be longer than 128 bits to derive any benefit. But another idea is to reduce the size of the original random number while still using a 128-bit key. Then there will be less to memorise.

For those who think they absolutely need 128 bits of security, this will not do because, as noted, there does not seem to be a way to put a rigorous lower bound above zero on the entropy contributed by the human choices.

Despite this, intuition suggests that the memoriser's choices will very likely contribute at least several bits with each word in the mnemonic system of [KEY]. To see why, consider the following example of a table entry taken from it.

0xb2 = 35;13 = L;C = 178 { abh agi bun die jux muf onl vol wro }
abhor agile agitate bun bunch bundle bung bungalow bungee bunk bunker
bunny bunsen die diesel diet juxtapose muff muffin muffle muffler mufti
onlooker volatile volcano volley volt volume volunteer voluptuous wrong
wrote

This is a table of possible words to represent the particular byte value of 0xb2. In the system in [KEY] the memoriser can choose any word from the list, or any other word that starts with the same three letters.

For this choice to have a min-entropy of less than one bit, one of these words would have to be so much more preferable than all the others that it was chosen over half the time.

If we assume that we get on average at least even a single bit of entropy from the choice of word, for each word, then we could for example reduce the number of words to memorise from the 16 in [KEY] to say 15, leaving 120 sure bits from the random number, and still expect to get at least entropy of 120 + 15 = 135 bits in total after the choices in the mnemonic. And intuitively this seems like a conservative estimate.

To be sure if you need 128 bits of security, this is heading back towards the dangerous territory of current password practices where a naive user is left to invent their own randomness, but it is perhaps not quite the same thing. It is not clear, for example, in the list above, how the memoriser could make such a bad choice that it contributed almost no entropy, or even a priori which the bad choice would be, whereas it is very clear what a bad password looks like. This might be an area for further study.

Terminology

KDF
Key derivation function
TRNG
True random number generator

References

[KEY].
How to remember a 128-bit key using ‘constrained choice’, Stephen Hewitt, August 2018.
[PW].
How to remember a provably strong password: a new way using ‘constrained choice’, Stephen Hewitt, Cambridge Clarion, July 2018.

Related articles