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)
:
- Hash the input
password
.
- Seed the PRNG with that hash.
- Generate a key using that PRNG, as per the normal key generation procedure.
- 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.