Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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!
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.
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.
