Encrypting cryptocurrency seeds for cold storage

Question

I’d like some feedback on an encrypting algorithm. I’m not rolling my own, but even putting together well-proved pieces may create many pitfalls. (I don’t know if I'm stretching questioning in this forum. I'm after concrete feedback on concrete, potential pitfalls.)

The purpose:

• Cold storage of encrypted cryptocurrency seeds (i.e. secret keys).

EDIT: The seed (as used in this question) is the super secret plaintext. But often called seeds, as it is normally a binary array, and not ascii.

The purpose is the same as for BIP0038 (* see summary below).

Likelihood of someone reusing a passphrase is definitely present.

The algorithm should be as simple as possible, to avoid errors in implementations.

My proposal:

1. Generate cryptographically random seed (32 bytes) (Or input from user*)
   * EDIT: The seed is 32 random bytes. User may input a cryptographically random seed, generated somewhere else, if she wants to. The seed is used to generate public addresses. A bit like private/public key pairs. It's the private key, the seed, that I would like to encrypt and store.)
2. Input UTF-8 passphrase from user, applying canonical normalization
3. Generate cryptographically random salt (12 bytes)
4. (Possibly ask for an input on “toughness”, to adjust the argon2id parameters.)

.

5. Generate 32 byte encryption key, using Argon2id, using 2) and 3).
   I guess the argon2id options is a separate topic altogether.
   I think iterations = 2^{(something + toughness)}

.

6. Encrypt the seed 1) with AES-CTR, using salt from 3) as counter, and encryption key from 5).

7. Encrypted seed (6) + Salt (3) is concatenated and base32 encoded to uppercase, to make the most compact QR code, appended by ‘:T’ + <toughness>.

.

My reasoning and Questions

Any tripwires I’ve tangled myself into?

AES-GCM is preferred over AES-CTR. GCM has message authentication. But I don’t see mallability as an attack vector. You might as well burn the piece of paper, instead of scribbling on the QR code.

A) Are GCM and CTR equally good in this use-case? Both have a catastrophic failure if the same key and counter is re-used. (No difference there, that I am aware.)

B) Birthday problem. Why 12 byte salt?
Open for input. :)

Reading Birthday attack - Wikipedia, and if my math is correct:
An 8 byte salt would yield a likely birthday collision every 5x10^9 reuse of the passphrase.
A 12 byte salt would yield a likely birthday collision every 3x10^14 reuse of the passphrase.
But it will fit in the same size QR code, after base32 encoded. (Version 3, ECC level L.)

C) A 16 byte salt is still better. But is it needed?
Any considerations regarding Argon2id?

D) Is there a problem that the salt is reused for two different operations? (Both Argon2id and AES)

E) AES CTR vs CBC? The seed is 32 bytes long, so no padding is needed for CBC. Both need a random counter/iv. Are they equally good for this use-case, or does one of them have a better fit for the problem?

Why base32? Because QR has an optimized encoding for uppercase and digits. And security here is more than hacking. An unreadable QR code is just as disastrous.

Keepass is all very good for this too.
My use-case is scannable paper. And that my wife can use it if I get hit by a bus or fall off a cliff. :)

I apologize if this post being a bit long. But it's putting the steps together that causes the security to break.

Any comment are welcoming. :)
vbakke

.

* The BIP38. https://en.bitcoin.it/wiki/BIP_0038 Uses scrypt, and 2xsha-ing the passphrase first. The salt derives from the passphrase, so reusing the passphrase is an issue.

BIP38 feels overly complicated. Like someone tying lots of bad knots, instead of tying one knot properly to secure the load. Simplicity is also security.

Answer 1

Unless otherwise noted, I assume adversaries know the genuine QR-code, and can alter it and submit it for decryption. I posit the design requirements are:

• Confidentiality of $\text{seed}$, to as high a level as the passphrase + key stretching of Argon2 allows.
• Integrity of $\text{seed}$, to 64-bit security level [ample in the context, where we want to catch an incorrect passphrase, or an altered QR-code which decryption is attempted in a legitimate context, with some low limit on how many times].
• Ability to encode an arbitrary $\text{seed}$ [e.g. because it was generated independently of the procedure; this also is necessary to allow a change of passphrase without changing $\text{seed}$].

I suggest to get rid of AES-GCM, because we can do without it, and most portable implementations [not using AES instructions] use data-dependent memory accesses which can create side channels. Also, questions A/D/E disolve. Towards this:

• At step 5, generate 64 bytes [that is set 64 for tagLength in the invocation of Argon2]. Split the output into first 32 bytes $K_0$, and last 32 bytes $K_1$.
• For confidentiality, compute $C\gets K_0\oplus\text{seed}$ and encode it in the QR-code. On decryption, do $\text{seed}\gets K_0\oplus C$.
• For integrity, use Argon2i [1 for hashType] with $C$ as salt, $K_1$ as password, 8 as tagLength, minimum workfactor [that is 1 for parallelism, 8 for memorySizeKB, 1 for iterations], other parameters as in step 5 [empty key, empty associated Data, same version]. The 8-byte result $T$ is encoded in the QR-code. On decryption, it's compared to decide is we accept the QR-code with the given passphrase. That comparison needs not be side-channel protected, but if it fails, nothing except an error indication must be output.

Security arguments:

• The output of Argon2 is computationally indistinguishable from random, except if the passphrase is guessed; hence $C$ leaks nothing about $\text{seed}$.
• The integrity test using $T$ is functionally a MAC keyed by an output of the main Argon2 of step 5; that's why the extra Argon2 can be fast.
• We use Argon2i for integrity since it promises maximum side-channel resistance, and key stretching [which the other forms optimize] is not an objective.
• Removal of AES makes testing a passphrase only marginally easier, because the computational burden of AES decryption is negligible compared to the main Argon2 of step 5. In the check of a $\text{seed}$ candidate the way that's done on normal decryption, the extra Argon2 is arguably comparable in cost to AES-GCM. And the cost of AES decryption is typically low compared to other possible tests of a $\text{seed}$ candidate (like testing it against a public key or signature).

---

On the $\text{salt}$ size (B/C), the main goals of $\text{salt}$ are

• When adversaries attack many QR-codes and are content with breaking any [rather than one or few in particular], $\text{salt}$ prevents the reduction (by a mere factor of two) in the expected work for dictionary attacks that would occur for QR-codes which $\text{salt}$ collide.
• Making it futile to pre-compute Argon2 outputs [e.g. building rainbow tables] before getting one's hand on QR-code(s) [for a faster attack, or leveraging resources otherwise not available].

The proposed 12 bytes for $\text{salt}$ are fine from both standpoints: if we assume $2^{40}$ QR-codes, there's about one chance in $2^{12\cdot8-2\cdot40+1}$ (one in 130,000) that the first bullet applies. Except for passphrases and Argon2 parameters so weak that they give no useful protection, the second is no issue. In fact, from the perspective of one particular user, 6-byte $\text{salt}$ would be enough as long as the passphrase is not massively reused.

---

On using $\text{salt}$ as IV for AES (D): that's not an issue as long as there is no collision of both $\text{salt}$ and passphrase [because Argon2 makes no use of AES, hence the identity quickly dissipates]. If there is collision of both $\text{salt}$ and passphrase, both AES-GCM and this answer's proposal have the same issue: leak of $\text{seed}$ encoded in one QR-code leaks $\text{seed}$ in another. That's one area where AES-CBC has an advantage [because a difference in the first 16 bytes of $\text{seed}$ is likely to save the day].

---

GCM has message authentication. But I don’t see malleability as an attack vector.

AES-GCM encrypts just as AES-CTR does (except for an offset of one in the IV), but adds authentication. In the original proposal, GCM authentication has at least one important function: it catches using the wrong passphrase on decryption. Depending on what $\text{seed}$ is used for, malleability in the decryption could well be an attack vector. ECDSA is not claimed to resist in an attack context where adversaries can flit bits of the secret key.

---

Note: if the ability to encode an arbitrary $\text{seed}$ is not needed, we can set $\text{seed}\gets K_0$ and save the 32 bytes of $C$ [since it's all-zero]. This does not change security w.r.t. an adversary knowing the QR-code. If we want extra protection against adversaries not knowing the QR-code (which is quite reasonable), we can rename the $\text{salt}$ field of the QR-code to $\text{pepper}$ [to denote that it's secret to a degree], and increase it's size to say 24 bytes [which combined with the entropy in the passphrase and the Argon2 key stretching is more than overkill].

Answer 2

Sorry, this is abusing StackOverflow. I know this is not a forum, but there no possible way I can verify that I’ve understood it all, just by writing a comment. Hopefully, others may also benefit from this.

Get rid of AES Great input! Obvious now that you pointed it out. But I would never have thought of it as secure enough, myself. :)

Salt size With your algorithm, a salt collision would mean that an attacker could attack both the QRs simultaneously. But that only reduces the expected work by a factor of 2, as you say.

If I understand your example correctly, it assumes 2⁴⁰ QR codes with the same passphrase. I was thinking, in practice, an upper limit is more like a 100 QRs, or possibly a thousand. Meaning a 12 byte seed is a massive overkill.

Since salt collision is not catastrophic in your algorithm, I will reduce the salt size. (I’ll see what fits in regard to QR sizes, and the checksum.)

Integrity test I agree. And it would need to be part of the QR code, of course.

I guess the size of $T$ could be any length, right? But shortening it, would increase the chance for reporting a false positive that the passphrase was correct. (But the decrypted seed, would just not work.)

Better algorithm So if I try convert your algorithm to psudo code:

1. Seed = random(32 bytes)

2. Passphrase = UTF-8 bytes from user input

3. Salt = random(xx bytes)

4. Key64 = Argon2id(Passphrase, Salt)

   • tag length = 64 bytes

5. Split Key64 into: Key1, Key2 = Key64[0…31], Key64[32…63]

6. Encrypted = Key1 XOR Seed

7. Checksum = Argon2i(Passphrase = Key2, Salt = Encrypted)

   • tag length = 8 bytes (maybe less)
   • memory = 8KB, iterations = 1, parallelism = 1

8. QR = Concatenate(Encrypted, Salt, Checksum)

And for decrypt:

1. Encrypted, Salt, Checksum = Split(QR)
2. Input passphrase (as 2. above)
3. Key64 = Argon2id(Passphrase, Salt) (as 4. above)
4. Split Key64 to Key1, and Key2 (as 5. above)
5. Seed = Key1 XOR Encrypted
6. Verify = Argon2id(Key2, Salt) (as 7. above)
7. If Verify == Checksum, then All is good, else, Not good

Is this a correct translation of your suggestion, @fgrieu?