Introduce derivation passphrases

[bbjubjub2494]

BIP-0039 has a the feature that an additional piece of user-supplied entropy can be mixed in with the seed at derivation time. Other software might call it things like "seed rotation" or "second factor". As a result, both are needed to reconstruct the correct master key, which can enable different recovery routines.

Motivation

Consider for example the recent case of a person who was pulled over by police with bodycams and as a result, had their mnemonic phrase exposed to the public as the footage was released. A passphrase acts as a stopgap in this situation since any attacker would need to also guess this passphrase, which can buy the legitimate owner quite a bit of time even for a passphrase that would be considered insecure if used standalone.

When cryptoassets are involved, there also exists a technique whereby the users leaves a smaller decoy or bribe amount with the plain seed so as to serve as an alarm if the mnemonic phrase is compromised. They then use the seed combined with a passphrase as their main wallet. However, it is not clear how to apply this to OpenPGP.

Finally, we note that paperkey tool also allows storing encrypted private key packets, which provides equivalent functionality.

Specification

If a passphrase is supplied, it is appended to the info parameter to the master key derivation process. Otherwise, the info parameter stays the same as the current specification, which is equivalent to an empty passphrase. (This is based on the BIP-0039 way.)

Downsides

#. This feature might create a false sense of security if users select trivial passphrases with it.
#. There already exists an output password parameter, which could result in confusion.

As a result, it might make sense to gatekeep this functionality behind some type of "expert" or "advanced" mode. But that also makes it less accessible.

Compatibility

The functionality does not affect recovery of existing keys. They can be treated as having an empty passphrase. As a result, it could be introduce as part of a minor 1.x release.

However, this introduces a concern that HKDF is too fast to feed user-selected password into, even though it is salted.

[bbjubjub2494]

If there is interest, I can provide a patch before the end of the year.

[kklash]

Cool idea! I like the idea of an option for generating an encrypted version of the recovery phrase.

Our goals will be distinct from BIP39's goals though, because plausible deniability wouldn't be a realistic use case for PGP. Reasoning for this is simple: Unlike a bitcoin wallet, PGP keys are intentionally tied with your identity, usually in a very public way (keyservers). If someone finds your recovery phrase and also knows your public key, there's no phony passphrase you could provide which would fool them.

However, encrypting the seed would be adequate protection for a case like you've described, acting as a stopgap measure against seed exposure.

This might be an opportunity to kill two birds with one stone, as I've lately been planning to add a run of a PBKDF like Scrypt or Argon into the Mnemonikey derivation procedure. The PBKDF run would be a perfect place to insert a user-chosen decryption password into the key derivation process.

Pitfalls to Avoid

In my experience working with BIP39 crypto wallets in the past, those who utilize BIP39 passphrases tend to make several common mistakes which we should try to mitigate with our design for Mnemonikey:

1. They forget that they used a BIP39 passphrase in the first place
2. They forget their passphrase after creating their wallet. Usually this takes the form of the user misremembering which passphrase they originally used. ("I swear, this is the correct passphrase!")
3. They mis-type the passphrase when deriving the wallet keys for the first time. When they recover their wallet later, they end up with a different set of keys.

We can solve problem 1 can solve by embedding information inside the recovery phrase somehow. Maybe we flip one specific bit in the version number which says 'this is an encrypted recovery phrase'.

For problem 3, the implementation should simply double-check the passphrase with the user before generating a recovery phrase for the first time.

Problem 2 is harder. We need a way for a Mnemonikey implementation to validate the user's supplied decryption password is probably correct. This doesn't need to be a 100% guarantee of correctness, even a few bits of checksum would be sufficient. The passphrase checksum should actually be a checksum on the key derived from the PBKDF, not a checksum of the passphrase itself (for security).

Currently we use a 5-bit checksum for the phrase itself, and we don't really have any extra room for another one. We could replace the 5-bit phrase checksum with a 5-bit passphrase checksum but that loses the benefits of the phrase checksum.

My first instinct is to add a 16th word so we'd have space to encode an extra checksum of perhaps 8 bits, and retain the remaining 3 bits of extra space for versioning information.

[kklash]

Another path we could take is to have a completely separate spec and tool to encrypt any set of words from the BIP39 word list. This would be totally disconnected from the Mnemonikey spec, reusable for other systems which use BIP39 word lists. It would conceptually be wholly separate.

I'm gonna think about this for a day or two, I appreciate your feedback! I wouldn't recommend starting work on anything just yet

[kklash]

Opened an issue to add Argon2id into the key derivation pipeline: #17

Once that and #18 are completed (probably in the same PR), I'll move on to adding a 16th word to the phrase. This will give us enough space to include extra versioning and checksum information we need to support encrypted recovery phrases.

[kklash]

#19

[kklash]

After #19 is merged, we can add support for user-chosen passphrases by including the password in the input to Argon2id. The root key (as defined in #19) will then be the product of the seed, key creation time, and password.

We can then add an extra word of space to the recovery phrase and use that space to encode a truncated checksum of the root key, applicable only to encrypted keys, as well as an expanded version number which will identify if the recovery phrase is an encrypted phrase or not.

One thing I'm still thinking about is how to make use of the extra bits afforded by a 16th word, in cases where the recovery phrase is not encrypted with a password.

Perhaps the answer is to simply treat every phrase as an encrypted one, with the appropriate root-key checksum still added even if no password is needed. The Mnemonikey implementation could then run the derivation process with an empty password first, and if the root key checksum mismatches, then the implementation would know that a password is very likely required, and can thus prompt the user. This would mean we don't actually need any extra versioning information to differentiate encrypted from unencrypted recovery phrases, but we'd still have the benefit of knowing which phrases are encrypted and which are not, albeit after a costly execution of Argon2id.

[kklash]

This excellent suggestion from a friendly reddit user also is suggesting the possibility of password encryption as a separate step:

While the 128 bit entropy is not a huge risk, the lack of password protection is I think a bigger issue. Let me propose an alternative that addresses both.

Let the seed be the hash of a 32 bit timestamp, 16 bit salt, 128 bit pepper. This will give us at least 144 bits of entropy, hence some margin for multi target attacks. I'm not sure if this hash needs to be expensive to compute, but it wouldn't hurt.

The recovery words will encode a 2 bit version, 30 bit timestamp, 16 bit salt, and the 128 bit encrypted pepper. This will require exactly 16 words and will avoid fractional bytes. I don't think a checksum is needed, as the words already have redundancy, the current checksum is weak, and in the end users can check the recovered public key. This will also allow paranoid users to choose their own words more easily.

For encryption you can use AES-256-ECB with the key derived using a secure password hash with the version, timestamp, 16 bit salt (and some personalisation string as prefix) as derivation salt. Unlike BIP39 Comments-Summary: Unanimously Discourage for implementation, this allows users to change their backup password after generating the key. A user could store a password-less copy in a secure location, and a password protected one in a less secure but more convenient environment.

I didn't include the version in the seed computation to allow upgrading the encryption of an existing key. If you start the epoch in 2023 we will have one more year to procrastinate.

The point i want to isolate and emphasize from among his suggestions is that Mnemonikey should allow users to change the password they use to encrypt their key backup phrase. This is critical as it rules out derivation passwords like in BIP39.

Rather, we should make password-based-seed-encryption a separate step from key derivation, so that users can convert back and forth between encrypted and unencrypted phrases.

[kklash]

This leads to having two different formats of phrases, one for encrypted phrases, and one for plaintext phrases. Since we'll need to distinguish between encrypted/plaintext phrases, let's ensure we have enough bit space in the version number for future iterations to improve.

Here's my first prototype suggestion:

Plaintext

Plaintext phrases will have version 0. They will be 15 words long.

version (3 bits)
seed (128 bits)
key_creation (30 bits)
backup_payload_checksum (4 bits)

This works the same as Mnemonikey currently does. Now that #19 has been merged, we use Argon2id to hash the seed and key creation time into a root key, on which we use HKDF-Expand to produce the PGP private keys.

Encrypted

Encrypted phrases will have version 1. They will be 16 words long.

version (3 bits)
salt (8 bits)
enc_seed (128 bits)
key_creation (30 bits)
dec_seed_checksum (4 bits)
backup_payload_checksum (3 bits)

To recover an encrypted phrase:

• Validate the checksum of the backup payload similar to the way mnemonikey recovery normally does, except the checksum is only 3 bits instead of 4: crc32(backup_payload) & 0x7 == backup_payload_checksum
• Derive a decryption key from a user-input password: seed_enc_key = argon2id(password, salt=salt+key_creation)
• Decrypt enc_seed: seed = aes128ecb(enc_seed, seed_enc_key)
• Validate the checksum of seed: crc32(seed) & 0xF == dec_seed_checksum

The decrypted seed will now probably be the true seed, assuming the user entered the right password.

Overview

• The distinct lengths of encrypted/plaintext mnemonikey phrases allows users to discern at-a-glance whether a recovery phrase is encrypted or not.
• We retain phrase checksumming, albeit with a higher likelihood of collisions
• The decrypted seed is checksummed so that implementations a way to detect erroneous passwords with reasonable probability.

Questions

• Is the salt even needed? Would using key_creation as the salt be sufficient?

[veqtrus]

The way you derive the root key needs to be the same whether a password is used or not. So if without the password you have argon2id(seed, timestamp), it needs to be that in the encrypted case too.

I don't see why you would need to commit 3 bits to the version, the plaintext and encrypted versions can both be v0 as they can be distinguished by the length. Use the extra bit to eliminate the possibility of having to define a new epoch.

version (2 bits)
key_creation (31 bits)
seed (128 bits)
backup_payload_checksum (4 bits)

version (2 bits)
key_creation (31 bits)
salt (7 bits)
enc_seed (128 bits)
dec_seed_checksum (4 bits)
backup_payload_checksum (4 bits)

dec_seed_checksum shouldn't be a CRC that leaks info about the seed, you can instead extract one more byte from argon2id(seed, timestamp) and copy over 4 bits.

The salt is useful for randomising the encryption.

[bbjubjub2494]

For me I was looking at it more from the angle of cipher + MAC, with the idea that cramming a proper MAC into 32bits isn't great for resisting forgery but ok for checksumming. The MAC would be keyed with the argon2 output too, which gives you a hint if the passphrase is correct or not. I chose to add 3 words because 18 words is also a standard bip39 setting. I also found that distinguishing based on length would be a possibility.

[kklash]

The way you derive the root key needs to be the same whether a password is used or not. So if without the password you have argon2id(seed, timestamp), it needs to be that in the encrypted case too.

Perhaps I should've clarified, with an encrypted phrase, there are two separate calls of argon2id:

1. Derive the seed encryption key: seed_enc_key = argon2id(password, salt=salt+key_creation)
2. Derive the root key from the decrypted seed: root_key = argon2id(seed, salt=key_creation)

So the root key is derived the same way, regardless of whether the phrase is encrypted or not. We could even use different password hashing algorithms but IMO it's simpler and perfectly fine to use the same algorithm with consistent and strong parameters.

don't see why you would need to commit 3 bits to the version, the plaintext and encrypted versions can both be v0 as they can be distinguished by the length.

Using distinct version numbers would allow Mnemonikey implementations to distinguish between encrypted and plaintext recovery phrases, with only the first word of the phrase. For example, the mnemonikey CLI tool would accept the first word, and implicitly know exactly how many more words to accept as input.

Without it, an implementation would need to offer the user an additional mandatory choice when recovering: "Are you recovering an encrypted 16 word phrase, or a plaintext 15 word phrase?" This would get more complicated if future Mnemonikey versions use different phrase sizes. We might decide to use version 2 for a plaintext 16 word phrase. It's better to be explicit, so that implementations can react properly based on the first word, without depending on user input.

I do agree it'd be nice if we could afford a 31st bit for the creation timestamp, but in a way, extra space for the version number actually allows us more flexibility in that dimension. With 3 bits, we have 8 possible version numbers. Assuming we use versions 0 and 1 for the original plaintext and encryped phrase formats respectively, that leaves us 6 remaining versions to use which could each define new epochs, allocate extra space for the timestamp, or allow for coarser creation offset granularity. Adding extra bits to the creation offset won't allow us the same future flexibility, and we'd miss out on 4 out of those 6 remaining version numbers.

dec_seed_checksum shouldn't be a CRC that leaks info about the seed, you can instead extract one more byte from argon2id(seed, timestamp) and copy over 4 bits.

Brilliant idea. Absolutely let's do that.

---

Another option I've considered is breaking compatibility with BIP39's wordlists, and creating our own custom 4096-word list, each word encoding 12 bits of information. This would allow us much more leniency with encoding space.

In a 16-word phrase where each word is 12 bits, We'd have 24 bytes (192 bits) of space, in which we could easily fit 128 bits of entropy, two 6-bit checksums, a healthy 16-bit salt, a 31-bit timestamp, and a 5 bit version number.

I opened a new discussion here for that

[kklash]

After #26 is merged, we'll have 12-bit words using 4 bit version numbers. In light of that, I'd propose the following format for encrypted phrases:

version (4 bits) (version 1)
key_creation (31 bits)
salt (19 bits)
enc_seed (128 bits)
dec_seed_checksum (5 bits)
backup_payload_checksum (5 bits)

Total size 192 bits. $\frac{192}{12} = 16$ words in the phrase.

[kklash]

Issue minted for the implementation: #27

[kklash]

PR opened to resolve this issue: #28