14
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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... $\endgroup$
    – Maarten Bodewes ♦
    Aug 20, 2013 at 0:00
  • 1
    $\begingroup$ Bitcoin's keys are used in ECDSA, which is defined to have the private key be uniformly random. If you replace the distribution with some human-brain based one then you are changing the cryptosystem. Presumably if you are asking this sort of question you are not an expert at cryptography, so please do NOT release software with your homebrew cryptosystems in it. $\endgroup$
    – Andrew Poelstra
    Jul 19, 2014 at 15:27
  • 1
    $\begingroup$ @AndrewPoelstra this question was asked almost a year ago. I've since learned a lot :) $\endgroup$
    – JP Richardson
    Jul 23, 2014 at 12:47
  • $\begingroup$ @JPRichardson Oh, sorry :) it appeared on my RSS feed very recently. In the Bitcoin world especially there is a lot of released amateur cryptography going around, and I am sometimes overwhelmed by it. Sorry to be so abrasive. $\endgroup$
    – Andrew Poelstra
    Jul 25, 2014 at 20:19
  • $\begingroup$ @AndrewPoelstra no worries :) Everything you stated is correct. Which is why I'm glad that I waited and soaked in all of the information before I started development on anything. $\endgroup$
    – JP Richardson
    Jul 26, 2014 at 1:01

7 Answers 7

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – JP Richardson
    Aug 28, 2013 at 0:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Aug 28, 2013 at 2:17
  • $\begingroup$ The salt defines when the adversary can begin their brute forcing efforts. If they cannot predict the salt, they can only start guessing the password after they first acquire the salt. Immediately acquiring the salt does not imply access to the key. Although in practice, if an adversary can read bits from your disk or memory, you've got bigger issues. $\endgroup$
    – cypherfox
    Mar 21, 2018 at 2:28
  • $\begingroup$ This is an absurd response. It is certainly not more secure to store a private key encrypted with the word "puppies" than it is to derive a key from the phrase "puppies". Probably, from a "simplicity" standpoint, simply deriving the private key from a password may be an improvement over the status quo... less moving parts, less places for the key to be stuck in RAM, etc. $\endgroup$
    – Erik Aronesty
    Jun 1, 2018 at 13:22
  • $\begingroup$ @ErikAronesty, I am suggesting you store it where the adversary can't get at it ("somewhere safe"), in which case your concern isn't applicable. If you concerned the adversary might have access, store it in encrypted form. Either the adversary has access to your private storage or they don't. If they don't, storing it encrypted is more secure. if they do, then both are equally bad -- and I already acknowledge that risk in the last parenthetical remark at the end of my answer. So my proposal is better in some important cases, and no worse in any case. $\endgroup$
    – D.W.
    Jun 1, 2018 at 18:43
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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