What does it mean that the security of Bitcoin public keys and 256-bit ECDSA is 128 bits?

Question

I am reading the Master Bitcoin book and came across the following:

From a security perspective, the amount of entropy actually used for the production of HD wallets is roughly 128 bits, which equals 12 words. Providing more than 12 words produces additional entropy which is unnecessary, and this unused entropy is not used for the derivation of the seed in the way that one might initially suspect.

It says that using more than 12 words (128 bit entropy) is unnecessary. It sounded extremely strange to me, because the seed from which wallets are made can go up to 512 bits. Thus, 256 bit entropy would provide a higher degree of security. So I did some research and in the third edition of the given book (which is still being written) I came across the following:

The security strength of a Bitcoin public key is 128 bits. An attacker with a classical computer (the only kind which can be used for a practical attack as of this writing) would need to perform about 2^128 operations on Bitcoin’s elliptic curve in order to find a private key for another user’s public key. The implication of a security strength of 128 bits is that there’s no apparent benefit to using more than 128 bits of entropy (although you need to ensure your generated private keys are selected uniformly from within the entire 2^256 range of private keys).

So I understand where the claims are coming from that it's not worth having more than 12 mnemonic codewords (128 bits), although the given claim is not clear to me at all. Upon further research, I found out that 256-bit ECDSA has 128 bits of security. And this is where my confusion started, so I have two questions:

1. What does it mean that the security of 256-bit ECDSA, and therefore Bitcoin keys, is 128 bits? I mean, if I have approximately 2^256 possible points on the elliptic curve (thus possible public keys), and therefore private keys, doesn't that require approximately 2^256 computations to find the public key (or slightly less if the key is reached early)? From this it looks to me like the security is around 256 bits?

2. If security is 128 bits, then why do we even have a 512 bit seed? I mean, why isn't it 128 bits, because the extra bits don't increase security?

Something is seriously not clear to me here. Any help would be appreciated.

Answer 1

1. What does it mean that the security of 256-bit ECDSA, and therefore Bitcoin keys, is 128 bits? I mean, if I have approximately 2^256 possible points on the elliptic curve (thus possible public keys), and therefore private keys, doesn't that require approximately 2^256 computations to find the public key (or slightly less if the key is reached early)? From this it looks to me like the security is around 256 bits?

You would be right if exhaustive search was the only way to determine the private key for a given public key. That is not the case however.

There exist algorithms that can do this with approximately √n operations (if the number of points on the curve is n). They are practical too (apart from needing an infeasible amount of computation): for example, they don't need much memory. Specifically, variants of Pollard's rho or kangaroo algorithm can be used to solve discrete logarithms on elliptic curves.

2. If security is 128 bits, then why do we even have a 512 bit seed? I mean, why isn't it 128 bits, because the extra bits don't increase security?

Conservative security. Having a seed that is less than 128 bits of entropy would certainly be detrimental to security, and more than 256 bits is unlikely to be helpful. BIP32, the standard now almost universally used for key derivation, uses a 256-bit key + a 256-bit additional "chain code", for master keys. In retrospect that may have been overkill (disclaimer: I'm the author of BIP32, and I certainly didn't know as much about cryptography back then as now), but it's also relatively cheap, in that the master keys are rarely observed by humans.

While it's true that the security of individual keys is never more than 2¹²⁸, it's not exactly true for seeds. Having seeds with more entropy does mean that one cannot just compute all keys from a wallet even with a machine present that can perform 2¹²⁸ computations. This is the intuition that underlies making master keys and seeds larger, but again, this is overkill.