<blockquote>
<ol>
<li>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?</li>
</ol>
</blockquote>
<p>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.</p>
<p>There exist algorithms that can do this with approximately <em>√n</em> operations (if the number of points on the curve is <em>n</em>). They are practical too (apart from needing an infeasible amount of computation): for example, they don't need much memory. Specifically, variants of <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms" rel="noreferrer">Pollard's rho</a> or <a href="https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm" rel="noreferrer">kangaroo</a> algorithm can be used to solve discrete logarithms on elliptic curves.</p>
<blockquote>
<ol start="2">
<li>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?</li>
</ol>
</blockquote>
<p>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 &quot;chain code&quot;, 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.</p>
<p>While it's true that the security of <em>individual</em> keys is never more than <em>2<sup>128</sup></em>, it's not exactly true for seeds. Having seeds with more entropy does mean that one cannot just compute <em>all</em> keys from a wallet even with a machine present that can perform <em>2<sup>128</sup></em> computations. This is the intuition that underlies making master keys and seeds larger, but again, this is overkill.</p>

CC BY-SA 4.0
2023-07-15T21:47:33.137Z
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
CC BY-SA 4.0
2023-07-15T21:55:26.787Z
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
CC BY-SA 4.0
2023-07-15T21:58:18.180Z
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.
Pieter Wuille
CC BY-SA 4.0
2023-07-15T22:00:07.143Z
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).
Pieter Wuille
CC BY-SA 4.0
2023-07-15T22:04:07.953Z
Yes, the comparison I made is probably wrong, but what I meant was that using the given algorithms, no other pair would be discovered on the way to the private key. I'm asking simply from a security perspective. In the sense that even with those algorithms it is very difficult to get the private key, because each pair would require a restart and a lot of computation.
dassd
CC BY-SA 4.0
2023-07-15T22:05:16.337Z
So my understanding is that a 512-bit seed would be even more secure than a 256-bit seed as far as the wallet itself is concerned, so increasing the bit count in this context makes sense?
dassd
CC BY-SA 4.0
2023-07-15T22:05:38.277Z
There are multi-target algorithms too, which can search for private keys for multiple public keys at once, I believe, but I don't have a reference for that. They don't discover things along the way at random though; you deliberately start a computation given multiple public keys.
Pieter Wuille
CC BY-SA 4.0
2023-07-15T22:06:56.380Z
Yes, more entropy is better, but once above 128 bits, and certainly past 256 bits, the gains diminish rapidly. It's almost certainly overkill to go significantly above 128
Pieter Wuille
CC BY-SA 4.0
2023-07-15T22:13:11.183Z
Yes, that's what I meant. In a sense, some pair will not be discovered along the way, as would be the case with brute force. So even those algorithms cannot "crack" Bitcoin itself. It's just that I still don't understand what you mean by saying that after 256 bits the benefits decrease. I mean, the HMAC-SHA512 function is used, shouldn't the security of the wallet itself (of the wallet globally, not of the keys themselves) actually increase with each bit up to 512?
dassd
CC BY-SA 4.0
2023-07-15T22:40:44.503Z
Yes, sure, the question is just how much that's worth if the attacker can break individual keys
Pieter Wuille
CC BY-SA 4.0
2023-08-03T10:20:44.753Z
@Filip my understanding is that to "properly backup" 12 words mnemonic is easier that to "properly backup" backup 24 words. Eg. it is easier to remember 12 words in head than 24. There are use-cases for this scenario.
WebOrCode
CC BY-SA 4.0
2023-07-15T21:37:12.713Z
2023-07-15T21:45:42.023Z
2023-07-15T21:45:42.023Z
Pieter Wuille
<p>I am reading the Master Bitcoin book and came across the following:</p>
<blockquote>
<p>From a security perspective, the amount of entropy actually used for
the production of HD wallets is roughly 128 bits, which equals 12
words. <strong>Providing more than 12 words produces additional entropy which
is unnecessary</strong>, and this unused entropy is not used for the derivation
of the seed in the way that one might initially suspect.</p>
</blockquote>
<p>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:</p>
<blockquote>
<p><strong>The security strength of a Bitcoin public key is 128 bits.</strong> An attacker
with a classical computer (the only kind which can be used for a
practical attack as of this writing) <strong>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.</strong> <strong>The implication of a security strength
of 128 bits is that there’s no apparent benefit to using more than 128
bits of entropy</strong> (although you need to ensure your generated private
keys are selected uniformly from within the entire 2^256 range of
private keys).</p>
</blockquote>
<p>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:</p>
<ol>
<li><p>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?</p>
</li>
<li><p>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?</p>
</li>
</ol>
<p>Something is seriously not clear to me here. Any help would be appreciated.</p>

<security><public-key><secp256k1>
What does it mean that the security of Bitcoin public keys and 256-bit ECDSA is 128 bits?
dassd
# What does it mean that the security of Bitcoin public keys and 256-bit ECDSA is 128 bits?

(Asked by: username_0 on 2023-07-15)

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.

**Tags:** security, public-key, secp256k1


---

## 1 answers

### Answer by username_1 on 2023-07-15. Score: 5 | Accepted answer

> 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](https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms) or [kangaroo](https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm) 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 *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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: 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).  
> **username_0**: Yes, the comparison I made is probably wrong, but what I meant was that using the given algorithms, no other pair would be discovered on the way to the private key. I'm asking simply from a security perspective. In the sense that even with those algorithms it is very difficult to get the private key, because each pair would require a restart and a lot of computation.  
> **username_0**: So my understanding is that a 512-bit seed would be even more secure than a 256-bit seed as far as the wallet itself is concerned, so increasing the bit count in this context makes sense?  
> **username_1**: There are multi-target algorithms too, which can search for private keys for multiple public keys at once, I believe, but I don't have a reference for that. They don't discover things along the way at random though; you deliberately start a computation given multiple public keys.  
> **username_1**: Yes, more entropy is better, but once above 128 bits, and certainly past 256 bits, the gains diminish rapidly. It's almost certainly overkill to go significantly above 128  
> **username_0**: Yes, that's what I meant. In a sense, some pair will not be discovered along the way, as would be the case with brute force. So even those algorithms cannot "crack" Bitcoin itself. It's just that I still don't understand what you mean by saying that after 256 bits the benefits decrease. I mean, the HMAC-SHA512 function is used, shouldn't the security of the wallet itself (of the wallet globally, not of the keys themselves) actually increase with each bit up to 512?  
> **username_1**: Yes, sure, the question is just how much that's worth if the attacker can break individual keys  
> **username_2**: @Filip my understanding is that to "properly backup" 12 words mnemonic is easier that to "properly backup" backup 24 words. Eg. it is easier to remember 12 words in head than 24. There are use-cases for this scenario.  

---

