Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
Normally private keys are wrapped using a secret key derived from a password, preferably using a key derivation function like PBKDF2 as you mentioned - e.g. using a wrapped key container such as PKCS#8... –  owlstead Aug 20 '13 at 0:00
add comment

4 Answers

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).

share|improve this answer
    
What if the salt was hidden from an attack too? i.e. what if I used the salt as another password so to speak, perhaps one generated by the system? –  JP Richardson Aug 28 '13 at 0:00
    
If have a way to keep data secret from an attacker but ensure it is known to authorized users, then don't mess around with passwords or salts or anything: just use a cryptographic key that is known to authorized users but not available to attackers. On the other hand, if you don't have a way to do that, then no amount of additional salt (that's known to the attacker) will change any of my bottom line conclusions. –  D.W. Aug 28 '13 at 2:17
add comment

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).

share|improve this answer
    
Thanks. I've updated my question. –  JP Richardson Aug 20 '13 at 0:26
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.