Since ECC over P-256 provides only 128 bits of security, I'd like to cut corners and generate a private key using HKDF to generate 32 bytes of key material from an input secret that's only 16 bytes long, on the theory that it's no harder to brute-force the KDF than it is to break the key using Pollard-rho.

This seems like a bad idea, but I can't prove it!

  • $\begingroup$ My intuition is that this results in effectively 64 bits of security, but I'd be curious to hear a counterargument as to why not. $\endgroup$ – Stephen Touset Sep 14 '16 at 23:10
  • 2
    $\begingroup$ You get the n/2 speedup only if you're solving the ECDLP, and knowing that the key was generated via a hash of a 128-bit value doesn't help you do that. (I think.) $\endgroup$ – Reid Rankin Sep 14 '16 at 23:14
  • 1
    $\begingroup$ I think the flaw in my intuition is that the bits in the HKDF output have correlated entropy, and you're right — that doesn't, I think, help you solve ECDLP. $\endgroup$ – Stephen Touset Sep 14 '16 at 23:26
  • $\begingroup$ You can probably get away with a single iteration of a 256-bit hash, HKDF would only be necessary if you want multiple 256-bit keys from the secret $\endgroup$ – Richie Frame Sep 15 '16 at 0:42
  • 2
    $\begingroup$ For single-key scenarios it's fine. But multi-target attacks will affect your 128-bit seeds much more than they affect 256 bit ECC keys. $\endgroup$ – CodesInChaos Sep 15 '16 at 10:45

This is 100% safe, assuming your 128 bits of entropy is generated properly, and assuming your attacker is only trying to attack one key.

If you did use, say, 17 bytes (136 bits) of entropy for your KDF, then the attacker would simply choose to break the ECC using Pollard Rho, instead of breaking the KDF using brute-force, and in this case they would still not need to do any more than $ 2^{128} $ work. (This is the weakest-point principle in action). This means that using more than 128 bits of entropy to generate a 256-bit ECC key is useless, unless your attacker is trying to break multiple keys.

In that case, using 256 bits of entropy to generate the ECC key would be completely justified, since it prevents certain batch attacks. Daniel J. Bernstein has a great blog post about batch attacks.

  • 2
    $\begingroup$ I think this is a good answer, but the fact that you should use a KDF may have to be highlighted somewhat more. Prefixing the 128 bit with zero's may not be the best way to generate the 256 bit secret value (even though the use of a KDF is kinda implied in the question). $\endgroup$ – Maarten Bodewes Dec 14 '16 at 11:00

The best attacks for (general) elliptic curves are square-root attacks (i.e., Pollard rho method and the likes). This means that ECC with a 256-bit key offers 128 bits of security. As a result, 128 bits of entropy are enough to generate a 256-bit ECC key.

  • 3
    $\begingroup$ I'm really looking for something a bit more reassuring than simply a "yes". $\endgroup$ – Reid Rankin Sep 15 '16 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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