Best way to encrypt lots of private keys with the same passphrase

Question

I'm working on software which deals with lots (several millions) of RSA private keys. Keysize is 2048.

I have to store them in a database, and I want them to be encrypted to mitigate risks of compromise from hostile access to the database. Naturally, applying a passphrase with PKCS #8 comes to mind.

I can't have a separate passphrase for each key because I can't store them securely. I can only store several passphrases in a secure vault.

But now I suspect that it's not safe to apply the same passphrase to millions of private keys with PKCS #8.

Could you please:

1. Confirm or refute my assumption that using the same passphrase to encrypt millions of keys with PKCS #8 significantly weakens encryption strength. If Eve gets enough encrypted keys, can she decrypt them knowing that an identical passphrase was applied? A kind of "many times pad" attack?

2. Suggest a better encryption method which uses the same passphrase (or a limited number of them).

Answer 1

Confirm or refute my assumption that using same passphrase to encrypt millions of keys with PKCS #8 significantly weakens encryption strength. If Eve gets enough encrypted keys, she can decrypt them knowing that same passphrase was applied? Kind of "many times pad" attack?

It depends.
If you are using PKCS#8 encryption using the methods from PKCS#5 v1.5 (and not >v2.0), then you are using ciphers with very short key-lengths, like DES. This is obviously bad, as we can reasonably brute-force the keys (of interest).

However, PKCS#5 (which is the encryption specified by PKCS#8) should generate a new random salt for each container and use password based key derivation with this salt and some reasonable iteration paramter to arrive at a key / IV pair for the encryption. That is, all private keys would be encrypted using different keys derived from different salts and the same password.

So overall the encryption is not weak because you encrypt a lot of data, but because you use a weak encryption method (if you use the old v1 PKCS#5 standard).

Suggest a better encryption methods which use same passphrase (or limited number of them).

Assuming the password is strong and not leaked, PKCS#5 v2.X should do the trick indeed. One might consider adding additional indirection though, that is use the password to derive a master secret (eg 256-bit) which is then fed to the PKCS#5 calls, so that you can easily change the password when it is eg leaked or people go, but they didn't take the derivation parameters / keys.

Answer 2

From a cryptographical perspective, a HSM comes to mind.

The main reason for using a HSM-based solution here is that you gain assurance against attacks. After all, HSMs are robustly designed for security and explicitly built to make it impossible to gain access to the key-data stored within the HSM.

Using a HSM, you can:

• Store the keys on the HSM itself, or
• Create an encryption key on the HSM and use that key (which is stored in the HSM) to encrypt the keys stored in the database.

This seems to provide plenty usable and secure ways to handle the scenario you describe.

Answer 3

I'd at least use different stages, e.g. encrypt a single private key using the password using a strong PBKDF (PBKDF2, bcrypt, scrypt, Argon2), and then use a hybrid cryptosystem with an authenticated cipher to encrypt each private key. This has efficiency advantages and lets you encrypt the private keys without requiring password access. You can also just move the encrypted private key off of the the system if it needs to be taken offline. Having a PIN protected smart card with the private encryption key would make a lot of sense.

However, to really protect such a system you should not just rely on cryptography alone; this requires a secure system with well specified access conditions and system boundaries. It it out of scope for this question and this site to design such a system; it would depend on your specific use cases, thread model and domain / system parameters. In the comments below the question I have made some suggestions to avoid the situation altogether.

Answer 4

While others have sufficiently covered (1), I'd like to point out a very cheap alternative to key encapsulation for (2); $<4$ bytes per key.

Because this does not use key-encapsulation this is incompatible with all existing keys, but all keys derived under this scheme are safe.

First we start by defining a root key from in your case a single (or few) password(s). I recommend that you use Argon2i, a data-independent Memory Hard Function (iMHF) that resists adversarial hardware acceleration.

let root = argon2i(salt, passphrase);

RSA key generation recap (simplified):

• Find two prime numbers $p$ and $q$ independently starting at an $N$-bit random odd number, incrementing by $2$ until the prime checks pass.

• Evaluate $n = qp, \lambda = lcm(p - 1, q - 1), e = 2^{16} + 1, d = e^{-1} \pmod \lambda$

By using a PRG and a seed we derive deterministic RSA keys. Although this is initially no faster than normal, we record tiny artifacts to skip the slow step of finding primes.

It would be a good idea to mask the offsets such that they do not reveal the fact that the prime number is at least $\text{offset} * 2$ after another prime. The mask, like the PRG must be unique per seed.

To generate the $k$-th key we call (PSEUDOCODE);

let seed = kdf(root, k);
let (d, n, offsets) = RSA::from_seed(seed);

We can assume the value of $e$, use $(d, n)$ to decrypt (or sign) and publish $n$ as our public key. The masked-offsets may be stored or published for the world to see.

How large are these offsets? While being overly conservative we can use $16$-bit numbers as counters to represent the $\text{offset} * 2$ distance from the initial PRG random number. This is overkill because it supports up to a prime gap of $2^{17}$ while the largest known gap is only $8350$.

One offset per prime totaling to 4-bytes.

To recover the key just apply the offsets with the seed (PSEUDOCODE):

let (d, n) = RSA::from_offsets(seed, offsets);

This skips finding prime numbers and assumes the claimed offsets are safe, trusting the offsets were produced correctly for this seed. You may of course verify that it derives primes.