Generate Elliptic Curve Private Key from User Passphrase?

Question

I'd like to generate a private elliptic curve key from user input like pass phrase. Is the best way to do this with a key derivation function like PBKDF2? Is there a better way?

Edit (based upon @poncho's questions)

To be specific, this is for a Bitcoin ECC private key. It seems to me that if a user picks a passphrase like puppies, it makes sense to try to use PBKDF2, Bcrypt, or Scrypt to increase entropy.

Something like...

eccPrivateKey = pbkdf2(HMAC−SHA, "puppies", randomSalt, 10000, 256)

right? Should any inputs or outputs be hashed? So, is it acceptable (security perspective) for the output of the pbkdf2 to be the private key?

@poncho, hopefully my use case implicitly answers your questions regarding the brute forcing. i.e. don't care how long it takes to generate as long as it's under a few seconds. Care very much about dictionary and precomputational attacks.

Answer 1

Using PBKDF2/Bcrypt/Scrypt might be the least-bad way, but that doesn't mean it's a good way. If your passphrase is puppies, it doesn't matter whether you use PBKDF2, Bcrypt, or Scrypt: you've got serious problems. If someone tries to crack your key, you're going to be toast: your key will be cracked within minutes.

Bottom line: this sounds like a bad idea to me, if there's any possibility at all that the passphrase might be weak (which, in practice, there will be). I would not use this to protect my money.

Instead, you should be generating a truly random or cryptographically-strong random number for the private key, then storing the private key somewhere safe. If you want to store the private key in encrypted form, you can derive a symmetric encryption key $K$ from a passphrase and store the private key encrypted under $K$ (though please understand that this will likely be vulnerable if someone manages to steal a copy of the encrypted private key).

Answer 2

There is something off in your setup:

• You care about precomputation and dictionary attacks.
• You assume a password like puppies.
• You didn't mention any other kind of secret.
• More formally: You didn't state an attack model. What access does the attacker have? Is there some kind of secure data storage? Are any other encryption schemes useable?

To be honest, in this case you are not going to get any serious level of security. Passwords are as good as its entropy. If you use a kdf like pbkdf2, bcrypt, etc. you only increase the time for testing each word in the dictionary. It is a still only a linear factor for the dictionary attack. Using a salt does not change the dictionary attack in a single user case either: The required computations are done exactly once.

Your main problem is the lack of entropy for something like an ECDSA private key. If you have a function with a low entropy domain, a deterministic function will output a low entropy range of values, and it does not matter for dictionary attacks whether your function is oneway or not.

A problem here might be that you focused more on your proposed solution than on the actual problem, context and goal. If you limit the access of the attacker to the signature and not the users computer, a random ECC key stored securely on the users computer is enough. If the user has some other kind of signature key (e.g. a PGP key), you could use such a signature on the correct password as input to a KDF. There might be other ways to generate an ECC private key, but it all depends on your actual setting.

Answer 3

Well, whether there's a better way depends on what you mean by 'better'; that is, what are you actual requirements? On the other hand, depending on what you are doing with the EC key, it may be that the overall design your assuming (map a passphrase to an EC private key) is itself unsuitable (and the actual function you use doesn't actually change that).

If you're asking about whether to use a key derivation function, the obvious question is 'as opposed to what?'. To convert a passphrase to an EC private key, what you're doing is mapping a text string into an integer between 1 and $q-1$ ($q$ being the order of the curve), if you don't use a key derivation function, you're going to use something that looks a lot like a key derivation function (even if we might use different terminology to describe it; such as 'seeding a CSRNG with tha passphrase as a seed, and using that output').

Instead, what you should be asking is 'what do I need from a key derivation function right here'.

Now, that, I can't immediately answer for you; you need to consider what you need. For example:

• Do you care how fast the EC private key is generated? How fast does it need to be compared to the performance of the device you're generating it on?

• How much do you care about dictionary attacks against the EC private key? If someone gets the public key, and then runs through a dictionary to try to obtain the private key, how difficult should that be?

• Do you care about precomputational attacks; that is, if the attacker is allowed a large amount of computation before hand, is he able to build a table to make recovering the password (and private key) from a public key much faster?

Depending on your answers, a key derivation function (or similar) might not be at all suitable. For example, if you are using these EC keys are credentials (so that they need to be immune to any dictionary-style attacks for extremely long periods of time), then this design (which maps a passphrase to a EC private key) might not be suitable at all, because it does nothing to prohibit an attacker from scanning through plausible passphrases; you may need to rethink your approach. For example, you might require some long term secret (that you stir into the key derivation process); this long term secret would prevent any possibility of a dictionary attack (because the attacker wouldn't have that).

Answer 4

Please see https://cbcrypt.org specifically https://cbcrypt.org/doku.php#documentation_and_api. There is a method CBCrypt.GenerateKeyPair(string CBCryptHostId, string username, string password) created specifically for this purpose.

This does not relate specifically to BitCoin, but if you start with something like a password, salt it with details of where you're going to send it, stretch it with something like SCrypt, use the result to seed a PRNG from which an asymmetric key factory derives a key, then you have deterministically derived an asymmetric key from the password. CBCrypt does this with ECDH, but in theory you could do it with any key type you wished.

It is important for such a system to have a rate limiting function applied before deriving the resultant key, before sending the public key to another party. However, salting & stretching can only help so much.

If you have a password with only 11 bits of entropy in it (for example, your password is a common dictionary word) then an attacker can still crack your password in ... let's say 250 seconds guaranteed (4 minutes) or 125 sec expected (2 minutes, >50% probability) with a mediocre laptop.

Even with good salting & stretching applied with a good rate limiting function such as SCrypt, let's assume an attacker is able to guess 4 guesses per second per CPU core they have available. A moderate attacker 400 guesses per second, call it 4,000 guesses per second. Assume they have more efficient algorithms than you - because they benchmarked the hell out of everything available, and maybe have hardware acceleration. They can do 40,000 guesses per second. If you want your password to withstand 10 years of brute force with 99% certainty, you'll need log2((40000*60*60*24*365*10)/0.01) ~= 51 bits of entropy in your password. Remember, this is a moderate attacker, with a moderate level of certainty. A sophisticated attacker could be much larger, and if the value of what you're protecting is higher, then you'll also need a much higher level of certainty than 99% in 10 years.

Answer 5

Yes. $\;\;\;$ A slightly better key derivation function for this purpose is $\:$bcrypt$\:$. $\;\;\;$ The key derivation function $\:$scrypt$\:$ hasn't been around as long, but if it doesn't have weaknesses then it's even better.

Answer 6

There is no way to generate a secure key-pair from the password "puppies".

If you are using a 256-bit elliptic curve and want the full 128-bit security it can offer, any password from which you directly derive a key needs to have over 100 bits of entropy. If you use a key derivation function, like PBKDF2 or scrypt, with parameters that require a few seconds to derive the key, it can have something like 20 bits less than the full 128 without being the weakest link.

The easiest way to get such a password is to generate it with a process that ensures that amount of randomness. For example, an eight word Diceware passphrase is 103 bits.

If you do need "puppies" to work as a password, you need to generate a random ECC key, then protect that with the password in a way that doesn't allow the attacker to make (many) password guesses. For example, store it on a server that requires password authentication and severely limits guessing. Even then it is probably too weak.

Answer 7

I'm going to assume the question asked is the question you want answered. Enough people have responded as if it's bad question.

1. In order to secure a weak passphrase you must use a key derivation function. The problem is that KDFs are trumped quickly by Moore's law.

2. You should compute the maximum value for the KDF based on the amount of time it takes on the target architecture. If it takes one second to compute your key, brute forcing a 7 letter password will take 5000 years or so. Even assuming Moore's law, and assuming an attacker has access to 1000 machines, that should be OK for a year or so. Setting it to a few seconds is probably good enough for many applications where the value of the data could not possibly justify the attack.

3. Despite what others say, if forward-compatibility doesn't matter ... a KDF/derived private key is just as good (bad) as a KDF/encrypted private key with a weak password. Both are private. The only bad thing is "future proofness". It can't be "re-derived" without also changing the public key. Whereas an encrypted private key can be re-encrypted... moved offline, etc.... leaving the public key unchanged.

4. In a way, however, the idea that the private key can be strengthened later is a weakness of traditional public/private key management. Far better for a weak key to always remain known (privately) as weak, and any new, stronger keys to be published and possibly signed as published by a prior weak key. For bootstrapping into the future, this is far superior. So maybe we should consider always using KDF's for private keys... rather than encrypting them, and just be far more fluid about re-deriving them when the user wants to change a password.