# Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key?

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!

• 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. – Stephen Touset Sep 14 '16 at 23:10
• 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.) – Reid Rankin Sep 14 '16 at 23:14
• 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. – Stephen Touset Sep 14 '16 at 23:26
• 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 – Richie Frame Sep 15 '16 at 0:42
• 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. – CodesInChaos Sep 15 '16 at 10:45

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.