Generating PGP key *without* random generator? (using fixed input only)

Question

I understand why in general, a strong random generator or source of entropy is used when generating PGP keys.

However, I have a use case where I want to generate PGP keys deterministically, i.e. based on certain fixed input, so that the same input will always result in the same PGP key.

Basically what I want is: instead of using 'real' random data, I want to generate the key from hash(passphrase), which can be considered pseudorandom data. Which will suit the purpose just as well, except this way I can regenerate the PGP key from just a passphrase.

Is there a solution that does this already, or would that involve messing with existing PGP software, and replacing their use of RNGs with my own source of entropy?

Answer 1

Yes, this could be done. It would be easy to implement and use this in a way that would be horribly insecure (e.g. with too short a passphrase, and not enough key stretching), but if used carefully, it could even be secure.

Basically, what you'd do would be:

1. Generate a secure passphrase, e.g. a sequence of randomly chosen words. This can be done separately from the other steps. The passphrase needs to contain enough entropy that it cannot be guessed by brute force using currently available or foreseeable technology. I'd say that means at least 80 bits (≈ 7 or 8 words at 10 to 12 bits/word), but you might want to go for up to 128 bits or so if you're feeling paranoid. Double your estimate if you're worried about quantum computers becoming practical.

2. Use a key stretching KDF to convert the passphrase into a pseudorandom seed (of sufficient length; I'd say at least 256 bits). The PGP standard already includes such a KDF (RFC 4880 § 3.7.1.3, Iterated and Salted S2K), but something like scrypt would be even better. You can't use a random salt, because you want deterministic output based on the passphrase only, but you should still be able to get around 20 to 30 bits of effective extra resistance to brute force attacks (letting you use a somewhat shorter passphrase, and/or have a wider security margin) with little noticeable slowdown in normal use.

3. Use the output of the KDF as the seed to a deterministic PRNG, and use the PRNG as the randomness source for the key generation algorithm.

4. Optionally, temporarily store the generated key in memory (e.g. through the use of a background agent program) to avoid having to repeatedly retype the passphrase.

Note that all the parameters for steps 2–4 (other than the passphrase) need to be either fixed or specified by the user. In particular, this includes the KDF and PRNG algorithms and any subcomponents (e.g. hash function) and adjustable parameters (e.g. iteration count) they may use, as well as the method used to generate the key.

Some variation, e.g. in the details of primality testing for RSA key generation, may be tolerable, provided that it has no more than a negligible probability of affecting the output, but other changes (e.g. anything the affects the order in which candidate primes for RSA are generated and tested) are likely to cause the same passphrase to no longer yield the same key. In particular, this means that it would probably not be a good idea to rely on any third-party PRNGs or key generation code whose internal implementation might change, and that any implementation should be accompanied by a detailed unit test suite to detect any changes in behavior.

I'm not personally aware of any existing programs that would support something like this, but there are open-source PGP implementations (like GnuPG) out there, so if you wanted to write one yourself, at least you wouldn't have to implement the whole PGP standard from scratch.