20 vs 33 word future/quantum proof?

[Prometheus]

Hello, I have a question

People often say that 12 words BIP39 or 20 words SLIP39 is totally enough and 24BIP39 or 33SLIP39 is just overkill.
But something in my mind says that I should better get more words to be more protected against stronger computers like quantum computers in the future.

[matejcik]

Grover’s quantum algorithm can reduce the difficulty of brute-forcing your seed against known target address by a square root – that is, reduce the difficulty from 128-bit to 64-bit.

This certainly sounds worrying! But.

1. 64 bits is still a lot. With today’s conventional hardware, brute-forcing only 64 bits of a seed, with the rest known to you, would take around 700 million GPU-hours (on a RTX 4090). If you buy that from a low cost GPU provider at 35 cents per hour, you’re looking at $245 million expenditure. And with thousands of GPUs, this will still total decades of real time.
   Of course, you can buy more powerful hardware to get there faster, but that may be ten times as expensive, for, say, twice the speedup.
2. The above calculation holds for classical hardware. There’s a lot of classical hardware lying around for rent. When quantum computers become reality, they are going to be more expensive and there is going to be less of them. This will significantly increase the total cost of any such attack.
3. All else being equal, a single quantum computation is going to end up slower than the equivalent classical one. The advantage of a quantum computer is that it can reduce 128 bits to 64 bits … but the actual time spent calculating the 64bit-equivalent task will be longer than a classical computer could do it.

In conclusion: if your cryptocurrency holdings are in the hundred-million-dollar range, maybe consider making your seed larger. But in such case, a much better choice is moving your holdings to a multi-signature wallet backed by multiple distinct seeds.

If it’s less than that, you can rest easy: nobody is going to spend hundreds of millions to steal your millions.

[Prometheus]

@matejcik

64 bits is still a lot. With today’s conventional hardware, brute-forcing only 64 bits of a seed, with the rest known to you, would take around 700 million GPU-hours (on a RTX 4090). If you buy that from a low cost GPU provider at 35 cents per hour, you’re looking at $245 million expenditure. And with thousands of GPUs, this will still total decades of real time.

Interesting, I always thought that something like 64bit would be very weak and could be broken by just on GPU in a few hours.
Seems that I was wrong.

@matejcik

• The above calculation holds for classical hardware. There’s a lot of classical hardware lying around for rent. When quantum computers become reality, they are going to be more expensive and there is going to be less of them. This will significantly increase the total cost of any such attack.
• All else being equal, a single quantum computation is going to end up slower than the equivalent classical one. The advantage of a quantum computer is that it can reduce 128 bits to 64 bits … but the actual time spent calculating the 64bit-equivalent task will be longer than a classical computer could do it.

So quantum computers and classical ones can’t cooperate one one task?

@matejcik

In conclusion: if your cryptocurrency holdings are in the hundred-million-dollar range, maybe consider making your seed larger. But in such case, a much better choice is moving your holdings to a multi-signature wallet backed by multiple distinct seeds.

If it’s less than that, you can rest easy: nobody is going to spend hundreds of millions to steal your millions.

If someone would start to mine seeds with a quantum computer, he couldn’t chose which seed to crack, so he would attack all seeds at the same time?
Or do I get something wrong there?

[matejcik]

@Prometheus

So quantum computers and classical ones can’t cooperate one one task?

Not in the sense you’re thinking of, no. Super simplified, the quantum computer runs all calculations at the same time, and a lot of work goes into getting back a useful result from the “all results at once” state.
In order to get something a classical computer can work with, you need the quantum computer to break down the result for you … and, at least in this case, that’s the exact same work you need to do to get the answer directly from the quantum computer.

@Prometheus

If someone would start to mine seeds with a quantum computer, he couldn’t chose which seed to crack, so he would attack all seeds at the same time?
Or do I get something wrong there?

Doing a quantum search with Grover’s algorithm is very different from trying all seeds one by one on a classical computer. There is a cost to reducing the difficulty from 128 to 64 bits, and it is this: Grover’s will give you exactly one answer to a question.

You have to choose your question wisely. One very good option is: “What seed corresponds to this specific Bitcoin address?” In which case, you’ll want to pick a rich target.
You could modify the question to “What seed corresponds to any one of all those Bitcoin addresses?” (In theory; i’m not a researcher so i couldn’t tell you how difficult it is to construct these kinds of questions in terms of quantum circuits.)
The problem is, you’re still getting just one answer out of the all possible ones.
If you include all addresses with balances, you could find a seed to the cheapest one in the set. If you want to find another answer, you’ll have to run the search again. There are tricks you can use to reduce the total number of searches to make the follow-up search faster, but you are still increasing the costs (and time spent) by a significant factor.

Unless your wallet is very fat, searching for your seed won’t pay for itself.

[Prometheus]

@matejcik

Not in the sense you’re thinking of, no. Super simplified, the quantum computer runs all calculations at the same time, and a lot of work goes into getting back a useful result from the “all results at once” state.
In order to get something a classical computer can work with, you need the quantum computer to break down the result for you … and, at least in this case, that’s the exact same work you need to do to get the answer directly from the quantum computer.

Ok, so they can’t cooperate in a productive sense.

@matejcik

Doing a quantum search with Grover’s algorithm is very different from trying all seeds one by one on a classical computer. There is a cost to reducing the difficulty from 128 to 64 bits, and it is this: Grover’s will give you exactly one answer to a question.

You have to choose your question wisely. One very good option is: “What seed corresponds to this specific Bitcoin address?” In which case, you’ll want to pick a rich target.
You could modify the question to “What seed corresponds to any one of all those Bitcoin addresses?” (In theory; i’m not a researcher so i couldn’t tell you how difficult it is to construct these kinds of questions in terms of quantum circuits.)
The problem is, you’re still getting just one answer out of the all possible ones.
If you include all addresses with balances, you could find a seed to the cheapest one in the set. If you want to find another answer, you’ll have to run the search again. There are tricks you can use to reduce the total number of searches to make the follow-up search faster, but you are still increasing the costs (and time spent) by a significant factor.

Ok, so maybe my error is that I think about quantum computers like they are just classical computers that are a lot more powerful, but in reality they are very different.

Thank you for answering my question

[Prometheus]

I remembered that a bitcoin address only has a effective entropy of 80 to 128bit, because of the birthday paradox.
If this is true then isn’t every additional entropy over 128bit completely useless?
Or does entropy over 128 bit has some valid increase of security in some sense. and if yes, how much?

[matejcik]

Not sure if “effective entropy” is the right term here.

Bitcoin private keys are on a 256-bit elliptic curve. The hardness of the underlying problem is only half that, 128 bits. Meaning you can calculate the private key from a known public key in 2¹²⁸ operations. It’s not brute-force trying every possible private key, there is an algorithmic shortcut.
(Note that this is the exact problem that Shor’s quantum algorithm is solving in polynomial time, that is, in human speak, Fast™)
This only applies if you know the public key. That means that addresses from which you don’t spend are safe…

…unless you also revealed an xpub for the account.

(Knowing an xpub for an account, and a single private key belonging under that xpub, allows you to calculate all the other private keys. So if you spent from an address A, and that address gets broken, and the attacker can find your xpub, the whole account is compromised.)

---

The “additional entropy” on top of 128 bits doesn’t make a single Bitcoin address more secure.
The point would be to protect your wallet as a whole: an attacker who breaks one of your Bitcoin accounts can’t use that information to find your other accounts, unless they directly attack the seed.

---

The birthday paradox is uninteresting here. It means that in about 2⁸⁰ tries, you can find two different Bitcoin private keys that have the same public address. It specifically does not mean that it’s someone else’s address. Typically it will be a completely fresh address with no balance, for which you and you alone happen to have two different private keys.

This would only become interesting if, at some point in the future, there are 2⁸⁰ total distinct Bitcoin addresses in existence for you to collide with.

[Prometheus]

@matejcik

Not sure if “effective entropy” is the right term here.

Bitcoin private keys are on a 256-bit elliptic curve. The hardness of the underlying problem is only half that, 128 bits. Meaning you can calculate the private key from a known public key in 2128 operations. It’s not brute-force trying every possible private key, there is an algorithmic shortcut.
(Note that this is the exact problem that Shor’s quantum algorithm is solving in polynomial time, that is, in human speak, Fast™)
This only applies if you know the public key. That means that addresses from which you don’t spend are safe…

Ok, so its a targeted attack rather then a generell attack.
Then it applys like you said before that attackers would obviously target a high value address.

@matejcik

The “additional entropy” on top of 128 bits doesn’t make a single Bitcoin address more secure.
The point would be to protect your wallet as a whole: an attacker who breaks one of your Bitcoin accounts can’t use that information to find your other accounts, unless they directly attack the seed.

So there are not only privacy but also security benefits of using multiple accounts.

@matejcik

The birthday paradox is uninteresting here. It means that in about 280 tries, you can find two different Bitcoin private keys that have the same public address. It specifically does not mean that it’s someone else’s address. Typically it will be a completely fresh address with no balance, for which you and you alone happen to have two different private keys.

This would only become interesting if, at some point in the future, there are 280 total distinct Bitcoin addresses in existence for you to collide with.

I initially thought, that this would mean that their are effective 2^80 possible addresses and someone could try to crack one.

Thank you for your answers, I learning a lot hear.