4

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.

1 Answer 1

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

  1. 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 2128, 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 2128 computations. This is the intuition that underlies making master keys and seeds larger, but again, this is overkill.

11
  • When you say that there are algorithms that can find the private key faster, what exactly do you mean by that? To get from a certain public key to his private one, without brute force? Also, does this mean that the given algorithm will have to be "restarted" for each key? Also, does it mean that those algorithms are better when looking at discovering a single private key, but globally that's not the case because if I brute-forced the private key, I could discover other public-private key pairs along the way and create a lookup table?
    – dassd
    Jul 15, 2023 at 21:47
  • I thought the seed should be 128 bits, not less than that. As far as I understand a larger seed does not affect the security of the keys, but it can affect the security of the whole wallet because even if some key is "discovered" whose security is 128 bits, this will not be the case for the whole wallet because its entropy is much higher (say 512 bit), so the other keys will remain secure. So it's potentially good to have seed and mnemonics larger than 128 bits, even though it doesn't just increase the security of the final keys?
    – dassd
    Jul 15, 2023 at 21:55
  • If you're interested in the details, read the algorithms I linked to. They exploit the structure that elliptic curve points form a cyclic group; it does not consist of just trying various things - it's a long computation of roughly 2^128 steps that in the end, with high likelihood, reveals the private key. It's not comparable to exhaustive search. Jul 15, 2023 at 21:58
  • And yes, indeed. If the seed is just 128 bits, the seed itself can be found with 2^128 steps, which gives the attacker all your keys. If you have a 256-bit seed, a 2^128 attack can attack individual keys generated from the seed, but not the seed itself (which would need a 2^256 attack). Jul 15, 2023 at 22:00
  • 2
    Yes, sure, the question is just how much that's worth if the attacker can break individual keys Jul 15, 2023 at 22:40

Your Answer

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

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