How can one securely generate an asymmetric key pair from a short passphrase?

Question

Background info:
I am planning on making a filehost with which one can encrypt and upload files. To protect the data against any form of hacking, I'd like not to know the encryption key ($K$) used for a file, so the user will have to asymmetrically encrypt $K$ and send it as well. The reason for this double encryption is that you can still share (individual!) files with other accounts by encrypting $K$ with the public keys of those users, too.

My problem is: How can a user can get a public and private key without the server saving/knowing the private key and without the user having to remember a passphrase of 250 hex characters?

Question:
Is there a way to derive a key pair from a password, like PBKDF-2 does for symmetric encryption?
Suggestions on rearranging the cryptographic steps in an easier way are welcome, too.

Alternatively:
It is also possible to encrypt the private key with a PBKDF-applied password and store it on the server, but I'd like to keep things 'simple'. ;)

Note: At this point I don't care if it requires RSA, ECC or an obscure cryptography scheme.

Answer 1

The best you can hope for is the following:

1. You derive the password into a "big enough" (e.g. 128 bits) secret key $K$ with a Key Derivation Function like PBKDF2. There are some details to be aware of (see below).

2. You use the secret key $K$ as seed for a Pseudorandom Number Generator. The PRNG is deterministic (same seed implies same output sequence) and produces random bits.

3. You use the PRNG in the key pair generation algorithm for whatever asymmetric algorithm you want to use. This step is cheap and simple for discrete-logarithm based algorithms like DSA, ElGamal, Diffie-Hellman, and their elliptic-curve variants, provided that the group parameters are known in advance (e.g. it is hardcoded in all relevant pieces of software that you are doing ECDSA / ECDH with the standard P-256 elliptic curve defined by NIST). For RSA, this is less cheap and simple, because the key generation process entails generating random integers until primes are reached. This is still doable.

Since this procedure is deterministic (for a given source password), you can run it again every time you need the private key.

---

Now the trouble with passwords is that they are from the relatively small and non-uniform space of "things which fit in the mind of an average user". They are vulnerable to exhaustive search, which, for passwords, is traditionally named dictionary attack. There are three generic ways to cope with that problem:

• Do not let the attacker learn any piece of data which allows him to verify a password guess. In the usual context of storing password hashes in a server for user authentication, this means that you do not want attackers to be able to read the database; this is why Unix-like systems have switched to shadow passwords about 15 years ago. You still want to store hashed passwords, and use the two other protections, because illicit read-only access does happen in the real world.

• Use a configurably slow key derivation function. This makes dictionary attacks proportionally slower -- but also normal usage slower, by the same factor. This is why KDF such as PBKDF2 or bcrypt include an iteration count. You want to raise that count up to the highest value which is still tolerable for your users.

• Use a salt to prevent attack parallelism. Parallelism is about attacking N passwords (not necessarily simultaneously) for less than N times the cost of attacking one (precomputed tables are a kind of parallelism). The salt is a public piece of data which acts as a variation to the KDF; this is equivalent to saying that there are many distinct KDF, and the salt says which one you use.

In your scenario, you do not have the first protection: the resulting public key is, by nature, public, and thus can serve for offline dictionary attacks. The attacker just has to try possible passwords until he finds the same public key. That's intrinsic to what you want to achieve.

The third protection (the salt) could also prove difficult. The salt needs not be secret, but it still must have some level of integrity. Wherever the salt is stored, the user who wants to recompute his private key must be reasonably assured that he is using the right salt (otherwise he will compute the wrong private key). Depending on the usage scenario, it may or may not be easy to have such a storage space. A partial solution is to use the user name as salt (presumably, the user will be able to remember his own name); as salts go, user names are less than ideal, because:

• two users on two distinct server installations (using the same software) may have the same name;
• when a user changes his password, he does not change his name;

and this breaks the "unicity" property that the salt tries to achieve. Still, the user name as salt is much better than no salt at all (better yet, use the user's email address as salt: users remember their own address, and email addresses are, by nature, unique worldwide). If you do not use any salt at all, then two distinct users on the same system, who happen to choose the same password, will end up with the same key pair, and simply listing the public keys will show it immediately.

---

Note: deriving the private key from the password means that when the user changes his password, he also changes his private key. Chances are that this is a problem. This is one of the reasons why you could prefer an indirect system, where a totally normal key pair is stored somewhere, symmetrically encrypted with a password-derived key. Thus, when the password is changed, you just decrypt the key with the old password, and encrypt again with the new password. But this requires an available storage area. This model is directly supported by, e.g., GnuPG.

Answer 2

A common approach is to encrypt the private key with a symmetric key derived from a pass phrase. This will be as secure as the chosen pass phrase. I'd suggest sticking with this approach; its conventionality makes it "simpler" than a solution that hasn't been studied well.

Answer 3

Yes, you can use PBKDF to derive keys for asymmetric encryption too. This is most convenient with encryption schemes such as ElGamal, IES or their elliptic curve variants, where a private key is simply a random number chosen from a given interval. In principle, you could do the same with RSA too, but the key generation process is more cumbersome.

(RSA key generation can be viewed as a process that takes in a random bitstream and outputs, with probability approaching 1 over time, an RSA key pair. To deterministically derive an RSA key based on a passphrase, you'd need to specify every detail of the key generation algorithm itself, so that changes to the algorithm cannot change the output, and then use a pseudorandom bitstream derived from the passphrase as the random input.)

You might also want to take a look at this recent question at crypto.SE, which involves a somewhat similar problem (re-deriving asymmetric crypto keys from stored random values at runtime).

Answer 4

In case you want to look into generating an asymmetric key pair from a password, here is one example scheme which also includes some discussion about its use (full disclosure: I am involved in defining the associated standard). Using such "decentral identities" offer a lot of opportunities.

The main trade-off is though users will not need to remember "250-character hex passwords", the typical user's "semi-random 8-character password" does not cut it. The password needs to be sufficiently long and sufficiently random that the associated key space of asymmetric keys generated from password data is large enough to withstand brute-force attacks, e.g. in the range of ~16 entirely random characters in the set a-z, A-Z, 0-9.

However, the benefit to a user of learning one single "really complex" password is the same keypair can be used with multiple services, and different keys (identities) can easily be generated by introducing slight non-random variations to key generation input data.

Here is a python example of key generation from password (the associated library is open source so you can just try it out and also look up key generation code from source).