Initialize a PRNG with a password

Question

Let's assume that we have a secure PRNG. Is it "safe" to initialize it with password, or seed based on a password like SHA256(password)?

If yes, is it "safe" to generate an RSA or DSA key from it?

---

The idea behind this is to initialize a PRNG with a password, then use it to generate RSA or DSA keys. So, the scheme will always generate the same prime numbers when generating private keys, meaning that you would not need to store your private key anywhere but would instead regenerate it each time it was needed. Only the password would need to be stored (or remembered).

UPDATE: Obviously this scheme would inherit the general risks of bad password choices, but how about a password requiring a reasonable range of characters. Alternatively, one could use 2 passwords, where the system uses the 2nd password as the salt of an PBKDF2 calculation.

Answer 1

No, it's not safe to seed a PRNG with the hash of a password, then generate a key from that PRNG. That is especially bad with DSA and shared parameters $(p,q,g)$, and only slightly less unsafe for RSA, or DSA with per-key parameters $(p,q,g)$. Two essentials things are missing: some slow step, and salt.

If the proposed procedure was applied, all there is to do to test (with high confidence) if a given password is the right password boils down to Check(password):

1. Hash the input password.
2. Seed the PRNG with that hash.
3. Generate a key using that PRNG, as per the normal key generation procedure.
4. Return true if the public part of the key generated in step 3 matches the known public key; else return false (for symmetric cryptography, use the key generated in step 3 to decipher a portion of ciphertext, test if the result matches known-plaintext; or, lacking sizable known plaintext, the test that byte distribution in the candidate plaintext is uneven according to a chi-squared test, deciphering more plaintext in case of doubt).

None of these steps is compute-intensive; that's the first problem. An adversary can enumerate likely passwords until it steps on the right one. A password cracker's basic function is to test passwords, approximately from most likely to least likely, using the above Check(password) procedure, until it returns true; at which point it is trivial to recover any non-public part of the key, and any plaintext.

If we assume that the actual password has been chosen randomly, or that the password cracker is good at ordering the passwords tested from most likely to least likely, then the expected cost of finding a password with $N$ bits of entropy is $C\cdot2^{N-1}$, where $C$ is the average cost of the Check(password) procedure above. Costs can be expressed in monetary or energy units; or in core·time, in which case the expected duration of the attack is its cost divided by the average number of cores.

In the particular case of DSA with shared parameters $(p,q,g)$, step 3 boils down to generating $x$ with $0<x<q$ (the private part of the key) by a straight invocation of the PRNG, then computing $y=g^x\bmod p$ (the characteristic part of the public key). That modular exponentiation, if performed naively, is the bottleneck of Check(password). It is not unrealistic to test $10^4$ passwords per core per second even with this straightforward algorithm; and there's an easy time-memory trade-off to speed that exponentiation by I guess a factor of 10 or more, by pre-computing $g^u\bmod p$ for $u$ of the form $u=v·2^{j·w}$ and $0≤v<2^w$, which allows reducing the number of modular multiplications by a factor of ${3\over2}·w$ compared to straight modular exponentiation. I'll thus assume a cost of $10^{-5}$ core·second (perhaps that requires dedicated CPU instructions for the hash and block cipher used by the PRNG, but that's increasingly common).

XKCD's estimate for the entropy in a 4-word password is $N=44$ bits; let's use that, even though it seems more than common practice. We get an expected $2^{44-1}·10^{-5}/3600/24≈10^3$ core. days to find the password. Using rented CPU time at $\\\$0.2$ per core·day (based on EC2 spot price), the expected monetary cost is $\\\$200$ plus adapting an existing password cracker. For Sequoia and its 1572864 cores, that's $2^{44-1}·10^{-5}/1572864/60≈1$ minute.

With RSA, or DSA with per-key parameters, testing a password is perhaps two decimal orders of magnitude more costly (because step 3 is much more complex), and that will make the scheme correspondingly less insecure; but that's an artifact, and still very insecure.

Also, only step 4 in that Check(password) procedure depends on the key; that's the second problem. This fact allows the attacker to amortize all other costs against the keys of several users. All there is to do is replace step 4 by If the public part of the key generated in step 3 matches any of the known public keys, return an identifier of that key; else return not_found; that change introduces negligible extra cost (for each password tested: little more than a single indexed memory accesses into little more memory than needed to store the public keys). That trivial change reduces the expected cost of attack proportionally to the number of users, which is a disaster for security. As a related issue, a rainbow table can be computed once for only a few times the cost or delay that would be necessary for finding the password for one particular key; after that initial effort, most keys are breakable with no sizable cost or delay.

Add that the password with the worse entropy is often what matters to the attacker (e.g. when restricting or accounting for use of a resource shared among several users) and that a sizable fraction of users choose poor passwords, and you'll find that a practical attack is feasible at low cost with a high probability of success using only commodity hardware.

---

The right technique if it is wanted to generate a key from a password is to replace the hashing (and optionally the PRNG) by stretching of the password (and if at all possible a per-user salt) into pseudo-random bits, using an appropriately parameterized Password-Based Key Derivation Function. A typical PBKDF is a public, deterministic, computable function accepting as input a password (assumed secret), salt (possibly public), and some parameter(s) controlling the cost of its evaluation (and typically, the size of the output). That PBKDF shall behave like a Pseudo-Random Function of (at least) its password and salt inputs.

The PBKDF transforms the password and salt (or something derived from them) iteratively, a high and parameterizable number of times. The transformation is such that it is unlikely that a shortcut requiring fewer iterations is feasible. The number of iterations should be chosen as high as tolerable for legitimate use. That dramatically raises the attacker's cost, since it must evaluate the PBKDF in step 1 of Check(password). Most importantly, optimization of later steps (like PRNG, key generation including modular exponentiation, primality test..) no longer helps the attacker significantly.

The minimum common PBKDF is PBKDF2, based on iterated hashing; a very serious drawback is that it is very susceptible to hardware-assisted acceleration, using ASICs or GPUs. A better one is Bcrypt also known as Eksblowfish, which by using 4kiB RAM makes such acceleration less economical. The state of the art is scrypt: it offers larger and parameterizable RAM usage (in turn raising cost of attack significantly and in a relatively precisely predictable manner); has a structural safeguard against massive hardware acceleration by virtue of using Salsa20/8; can use multiple cores (if available) to reduce the time penalty perceived by a legitimate user, and comes with convincing security argument.

The salt can be a (say) 128-bit random (that's the best when it is possible); or just a unique identifier (like the email of user concatenated with a value common to all users of a given server). It is enough that the salt is different for each public key to ensure that a password cracker must evaluate the PBKDF for each password·key combination tested, rather than for each password tested; and salt comes almost for free in most practical applications. Further, if the salt is unpredictable, the adversary can't start an attack before getting the salt.

Using a salted PBKDF, the expected cost to test a password becomes a parameter that can be adjusted, as a compromise between security and cost of legitimate use. Parameterize script to require 0.5 seconds on a 4-cores machine with a gigabyte of RAM per core (a fair desktop PC; that may translate to 3 seconds on a lost-cost dual-core portable PC); use the email address associated with the key and an arbitrary fixed string as salt; and you can have fair confidence that today's supercomputer would take weeks per XKCD-class password guessed (ignoring the hard-to-estimate difference between one of Sequoia's 1572864 cores and one in that desktop PC, the expected duration of the attack is $2^{44-1}·0.5·4/1572864/3600/24>129$ days, thus odds that an attack succeeds in less than 2 weeks are less than one in 36). Adjust the parameters every odd year (when you force users to change password and key), and you have decent long term security.

Caveat: it is highly recommendable to have in addition the key-dependent on something secret beyond the password, made part of the salt. That's a practical necessity when users are allowed to choose their password and have no incentive to choose a good one.

---

In addition: it is customary to allow users to change passwords while keeping the same public key. One simple technique is:

• Generate a true-random seed S, e.g. 256-bit, that will remain unchanged as long as the user keeps the same asymmetric key.
• Stretch password and salt into a symmetric key K, e.g. 256-bit, using an appropriately parameterized PBKDF.
• Store the exclusive-OR of S and K; that will be used to recompute S from the password, and will be adjusted to change the password without changing S.
• Seed PRNG with S.
• Generate asymmetric key (public and private) using PRNG.

An often-used, slighting more complex technique towards the same goal is to symmetrically encipher the asymmetric key using K; that avoids re-generation of the asymmetric key each time the password is entered, and most importantly allows interoperability of various generation algorithms and PRNGs.

---

It is further asked:

If there was a strict requirement to derive a key from a few bits as possible (if you need salt at some point, it counts against those bits), would seeding a PRNG from N bits be acceptable, or is there a better method in terms of security level per bit to input?

If salt is counted as input the same way as a secret password (despite salt being usually assumed public and coming for free, e.g. the name or email of the key holder), then one is best with no salt.

Again, and in summary, if the input entropy is low, it is bad to feed that precious little to a PRNG (be it directly or through a standard hash) then use the PRNG to establish a key (be it asymmetric, or for a fast symmetric algorithm). Somewhere in the chain between the input and anything the attacker can observe (public key or ciphertext), there must be an inherently costly process, that is a PBKDF. Its salt input should be different for each user, if at all possible without reducing the entropy in what's secret. If a user must remember the whole secret input, not using a PBKDF amount to gross negligence; same for not salting that PBKDF if any characteristic of the user is available.

Answer 2

A cryptographic PRNG doesn't care what you feed it as entropy, as long as you provide enough. Furthermore, the PRNG will not reveal anything about its internal state, including what was fed to it as entropy. So in this sense it's safe to use a password as entropy: the PRNG will not expose it.

The problem with a password is that compared with normal keys, it has lousy entropy. A pretty good password has 44 bits of entropy; RSA Labs estimates that a 3072-bit RSA key has a security level of 128 bits, and even a lowly 1024-bit RSA key has a security level of 80 bits. It would take a very complex password to reach even that level. (The security level, like the entropy, estimates how much work is necessary to find the key by brute force.)

To mitigate the risks of brute force guesses, make sure to apply some form of key stretching to the password. The idea is that rather than applying a fast procedure to deduce the RNG state from the password, you must apply an inherently slow procedure. Use the result of the stretching the PRNG seed.

This is still not a good idea if you can avoid it, because it reduces cracking the key to cracking the password. In addition to guessing, the attacker might resort to shoulder surfing, hardware keyloggers and other techniques that would not compromise a key file.

To get the best protection, generate a random RSA key with a proper RNG (with the full security level for the chosen key size), and store an encrypted version of the key in the file. Most software that works with keys has a built-in feature to protect a key file with a password. You get a form of two-factor authentication, since the attacker would have to obtain both the key file and the password to get the key. Furthermore, even if the attacker manages to obtain the key file, then as long as you notice it quickly and you used a nontrivial password (that takes days to crack, not seconds), you have a window of time to repudiate the key before the attacker finds the password. And if the password is compromised but not the key file, you can repudiate the key, or if possible you can change the password of the key file and destroy all the copies of the old key file.

In practice, there is usually little point in having an RSA key derived solely from a password. You can only type this password on a trusted machine anyway. If the machine is trusted, then you might as well plug in a USB token containing the key file or download the key file from another trusted machine.

P.S. Your ideas on password generation are flawed. Special characters aren't nearly as useful as length for a strong password, and the most important thing is to be able to quantify how random it is. Do read XKCD #936: Short complex password, or long dictionary passphrase? (but beware that Jeff Atwood's answer, despite its high score, is deeply flawed: read instead AviD's answer and Thomas Pornin's answer and Misha's answer). Also read How secure are passwords made of whole english sentences.

Answer 3

It's usually not safe to initialize it with a password, because of the risk of brute-force attacks. Do a search and you'll find lots of warnings about this risk.

Your proposed password generation method does not say anything about how long the password is or how you will choose it. If it's a 8-character password, no, it won't be secure. If it's a random 16-character password, and it's generated uniformly at random, it is adequate.

Using a password as a salt for PBKDF2 does not make sense; instead make the password long and strong.

Bottom line: it's not a good idea to use a password or passphrase to generate your private key, because in real life passwords/passphrases almost never have enough entropy.