A valid criticism of Bitcoin's design?

[ATC777]

I was talking to someone about Bitcoin on my brokerage forums and he says:

Not to say it's not acceptible, or that it could not be adjusted, but I give it 5-10 more years max.  The premise of elliptic curve cryptography has always been that solving the discrete logarithm for an elliptic curve is not computationally feasible.  That said, every few years we hear about someone pounding on one for years and out comes a solution.  Realistically though, it is only a matter of time before these can be solved in polynomial time, or computational processing becomes so fast that it doesn't matter for the number of bits employed.

The key is, will ordinary people use this, and the answer is "probably not".  As, my occupation is systems design and development, I would consider myself closer to a potential user than ordinary persons, and I wouldn't even consider using Bitcoin for anything.  I have no idea though.. anything can catch on.  Who would have thought I would ever be able to pay with paypal at Home Depot 10 years ago.

 

I'm not even sure what exactly he's talking about... it sounds like he doesn't understand how Bitcoin works and the model of increased mining difficulty as processing power rises?

[1714611723]

1714611723

[1714611723]

1714611723

[coder_guy]

What is this I don't even...

[ATC777]

What is this I don't even...

I'm trying to make sense of what he's saying so I can respond properly, but it sounds like he doesn't know what he's talking about... There are a lot of people participating in the discussion (who know nothing about technology/cryptography) who might be lead astray by tossing around a few $2 words (or I should say 0.148 BTC words lol). 

[juhakall]

In the first paragraph, he seems to be thinking that when SHA256 is likely broken in the next 5-10 years, Bitcoin will be doomed. Two questionable assumptions in there: that SHA256 will actually be compromised, and that Bitcoin can't adapt to some new algorithm. Both might turn out to be true, but I wouldn't count on that.

[maaku]

What is this I don't even...

I'm trying to make sense of what he's saying so I can respond properly, but it sounds like he doesn't know what he's talking about... There are a lot of people participating in the discussion (who know nothing about technology/cryptography) who might be lead astray by tossing around a few $2 words (or I should say 0.148 BTC words lol). 

He doesn't know what he's talking about. The algorithms we know for reversing ECDSA are not polynomial time. Unless he knows something about computational theory that the rest of the world does not, there is no reason to believe that it is even possible for there to exist a polynomial time solution. And with the exponential time solutions which are currently the best we know about, you could literally turn the entire observable universe into a 100% efficient computer and run it until the heat death of the universe, and you you're not likely to find a solution. Moore's law does not apply here.

[greyhawk]

What is this I don't even...

I'm trying to make sense of what he's saying so I can respond properly, but it sounds like he doesn't know what he's talking about... There are a lot of people participating in the discussion (who know nothing about technology/cryptography) who might be lead astray by tossing around a few $2 words (or I should say 0.148 BTC words lol). 

He doesn't know what he's talking about. The algorithms we know for reversing ECDSA are not polynomial time. Unless he knows something about computational theory that the rest of the world does not, there is no reason to believe that it is even possible for there to exist a polynomial time solution. And with the exponential time solutions which are currently the best we know about, you could literally turn the entire observable universe into a 100% efficient computer and run it until the heat death of the universe, and you you're not likely to find a solution. Moore's law does not apply here.

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?

[Revalin]

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?

It just cuts the effective key size in half.  The current 160-bit signatures will be brute forced in 2^80 operations.  That sounds weak, but it's going to be a long time before quantum computers reach 160-bit levels (if ever), and even when they do the operations per second will be very low and 2^80 will be infeasible for a long time thereafter.


The OP was talking about ECDSA, though.  There's certainly a chance that a weakness will be found, but there's no expected timeframe for that.  It's not a case where increasing computer power will break it in 5-10 years.

[Foxpup]

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?

It just cuts the effective key size in half.  The current 160-bit signatures will be brute forced in 2^80 operations.  That sounds weak, but it's going to be a long time before quantum computers reach 160-bit levels (if ever), and even when they do the operations per second will be very low and 2^80 will be infeasible for a long time thereafter.

You're thinking of Grover's algorithm. Shor's algorithm does indeed break ECDSA in polynomial time, though we're a very long way off a useful implementation. And note that Bitcoin public keys are 256 bits, not 160 bits - the hash is 160 bits, but this is not broken by Shor's algorithm.

[Syke]

Realistically though, it is only a matter of time before these can be solved in polynomial time, or computational processing becomes so fast that it doesn't matter for the number of bits employed.

That was the general thinking, maybe 20 years ago. General cryptography has advanced sufficiently enough in recent years that no computer, ever, will be fast enough to crack them. Let me quote a real expert:

brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

[etotheipi]

Quantum computers indeed would break ECDSA, allowing private keys to be derived from public keys in polynomial time.   I suppose a mathematical breakthrough in finite field theory could do the same, but astoundingly unlikely.  But Bitcoin is the least of the world's problems when this happens:  the entire web of trust, SSL/PKI/CA architecture would be broken, rendering useless most internet crypto that we all rely on.  The world will have a lot of problems when QCs start to come into regular existence.  In particular, there will be a gap between when they start to become available to the wealthy, but are not ubiquitous enough to enable widespread quantum encryption to replace it.

But it still wouldn't be that bad.  There are quantum-resistant algorithms that can be run on classical computers.  So it's pretty ridiculous to single out Bitcoin for being susceptible to QCs without mentioning that all sensitive communications on the internet will be susceptible.  And without mentioning that there are alternatives.  

In fact, Bitcoin is wholly prepared to deal with this:

(1) By avoiding address reuse, you're 99% safe even in a world full of quantum computers -- because your address is the hash of your public key, and thus no one knows your public key until you've already submitted a signed transaction to the network.  Even in 50 years when QCs are "fast", they probably won't be fast see your public key, back out your private key, sign your coins to themselves, and then broadcast that tx ... all before your transaction has propagated to a majority of nodes.  Yes yes, isolation attacks... but see #2

(2) The Bitcoin network has the property that you can actually change stuff like crypto algorithms, hashing algorithms, etc, by incrementing a version number and encouraging all nodes to use the new [QC-resistant] algorithms.  Of course, it's not a trivial change, but the network would survive and users would be able to continue using the old encryption for a short time until the transition is made, as long as they never reuse addresses.   Especially large transactions could be submitted directly to miners to avoid isolation issues.

I would say the OP quote is simply under-informed.

P.S. -- Also, these worst case scenarios assume that QCs just pop out of nowhere and suddenly exist on everyone's desktops.  The fact is, we'll see QCs coming decades in advance... so all this "OMG need to swap crypto algorithms immediately!" stuff is overblown.

[kjj]

Hashing appears to be totally resistant to quantum attacks.  Grover's algorithm can solve any circuit quickly, but circuit has a peculiar meaning, and it is a tricky thing.  We don't have or expect to be able to have the capability in the foreseeable future to build a classical circuit for SHA, much less a quantum one.  If you don't believe that, read up on the SHA algorithm, and then think about what you'd need to do to unroll that in the time dimension to a single flat circuit that doesn't use iteration or memory.  Your VHDL compiler would stab you if it could.

An ECDSA break due to Shor's is likely to be a bigger problem, possibly even within my lifetime (say, the next 50 years or so).  In 2001, a (maybe) quantum computer factored 15 into 3*5.  This feat was achieved again in 2012, but this time with a computer that we are almost positive is actually quantum.  They've moved up to factoring 21 now.

But keeping quantum systems stable gets harder as you add complexity, meaning that the issue isn't merely one of applying well known classical techniques to shrink and replicate gates.  We sorta strongly suspect that quantum computing is possible, in the sense that our current understanding of physics doesn't explicitly disallow it, but it will be a long and ugly road getting up to useful scales.

[ATC777]

Wow, this has been a compact college lecture on cryptography and computer science -- I'm glad to see that there are so many brilliant folks in the Bitcoin community.  

Just listen to this discussion and think about what computers could be like in the year 4000... I think even the computers of 2050 will blow our minds... Perhaps someday we'll compute the true state of Schrödinger's cat! lol

[Raize]

etothepi is right. The only risk that occurs from the end user perspective is from address reuse, and we're still going to see this coming, not to mention the whole idea of "secure online purchasing" is going to break down while this occurs. If anything, this will completely invalidate HTTPS which will be a much bigger deal.

Also, keep in mind that QCs aren't really anything but theoretical right now. We could use some combination of symmetric encryption plus ECDSA if needs be.

[Atruk]

But it still wouldn't be that bad.  There are quantum-resistant algorithms that can be run on classical computers.  So it's pretty ridiculous to single out Bitcoin for being susceptible to QCs without mentioning that all sensitive communications on the internet will be susceptible.  And without mentioning that there are alternatives.

I think it is important to note with this that the quantum resistant algorithms that have been published tend to fall rather quickly to classical cryptanalysis. In a couple decades there will probably be a few quantum resistant public key algorithms that have passed rigorous review, but at the moment there isn't really a more secure alternative to ECDSA. At least not a more secure alternative against Shore and Grover.

[etotheipi]

But it still wouldn't be that bad.  There are quantum-resistant algorithms that can be run on classical computers.  So it's pretty ridiculous to single out Bitcoin for being susceptible to QCs without mentioning that all sensitive communications on the internet will be susceptible.  And without mentioning that there are alternatives.

I think it is important to note with this that the quantum resistant algorithms that have been published tend to fall rather quickly to classical cryptanalysis. In a couple decades there will probably be a few quantum resistant public key algorithms that have passed rigorous review, but at the moment there isn't really a more secure alternative to ECDSA. At least not a more secure alternative against Shore and Grover.

Try some Unbalanced Oil & Vinegar.

[Atruk]

But it still wouldn't be that bad.  There are quantum-resistant algorithms that can be run on classical computers.  So it's pretty ridiculous to single out Bitcoin for being susceptible to QCs without mentioning that all sensitive communications on the internet will be susceptible.  And without mentioning that there are alternatives.

I think it is important to note with this that the quantum resistant algorithms that have been published tend to fall rather quickly to classical cryptanalysis. In a couple decades there will probably be a few quantum resistant public key algorithms that have passed rigorous review, but at the moment there isn't really a more secure alternative to ECDSA. At least not a more secure alternative against Shore and Grover.

Try some Unbalanced Oil & Vinegar.

UOV looks promising and hasn't been worked around yet, but it is still a bit too soon to trust with anything of value. I'm kind of surprised it hasn't been incorporated into one of the alt-coins yet, but those projects tend to fuss a bit more on "proof of " and reward issues more than securing the system indefinitely.

[chmod755]

QCs aren't really anything but theoretical right now.

This company claims it's not just theoretical (but I think those "quantum computers" - if they're real - can't break ECDSA right now): http://www.dwavesys.com/en/products-services.html

[gmaxwell]

I think it is important to note with this that the quantum resistant algorithms that have been published tend to fall rather quickly to classical cryptanalysis. In a couple decades there will probably be a few quantum resistant public key algorithms that have passed rigorous review, but at the moment there isn't really a more secure alternative to ECDSA. At least not a more secure alternative against Shore and Grover.

Uh. This is untrue.

First, grover just gives you a sqrt() speedup.  So double the number of bits and you're done against it. It's very important, but not terribly relevant to crypto security.

Lamport signatures are intuitively QC and classically strong, and I have never heard anyone even suggest an attack class that would attack lamport signatures without breaking all other practical signature implementations (because all practical signature algorithms use a hash on the input first).   The down side is that you're looking at 16kb+ signatures, which is why we don't have them in Bitcoin today.  (AFAIK all of the other post QC signature systems have big signatures/keys/ or both... as well as the questionable classical security that you mention).

Which brings up a point that has been missed in this discussion: ECDSA is not fundamental to bitcoin's "design"— e.g. you don't see it mentioned in bitcoin.pdf.  Should ECDSA begin looking like it may be becoming practically insecure, one of the reserved nop instructions could be deployed to activate another signature scheme (Lamport, perhaps, if nothing better comes along) in a way which is backward compatible with existing software.

Moreover, when Bitcoin is used correctly— addresses only used once— the fact that we send coins to the hash of a pubkey and only disclose the pubkey on spending constitutes a kind of abbreviated Guy Fawkes signature system, so an ECDSA weakness would not be an effective attack unless it could be pulled off in the limited time between announcing a transaction and it becoming buried in the chain.

I can't imagine how the implementation of Bitcoin could be any better relative to this issue when considering the need to balance speculative security against basic viability— as I think the blockchain would already be about 1TB if it used 512bit lamport. Using ECDSA and having a flexible and upgradable script system that will allow upgrading it is really the only prudence decision. The limited pubkey exposure with proper use provides a little more security.

This company claims it's not just theoretical

Dwave's products are not quantum _computers_, and there isn't any debate about that— there is some debate over if they use quantum effects at all but even if they do they're to quantum computers what a machine that can only add is to a classical computer. They aren't even claimed to be quantum turing complete, their design doesn't have any obvious path to become quantum turing complete... and right, they can't do crypto because of this.

[Atruk]

Thanks for the elaborate rebuttal. I have to say, if I'm going to be wrong this is a very nice way to be wrong. I have to admit I wasn't thinking about blockchain size and I'm not familiar with Lamport.

This company claims it's not just theoretical

Dwave's products are not quantum _computers_, and there isn't any debate about that— there is some debate over if they use quantum effects at all but even if they do they're to quantum computers what a machine that can only add is to a classical computer. They aren't even claimed to be quantum turing complete, their design doesn't have any obvious path to become quantum turing complete... and right, they can't do crypto because of this.

Right D-Wave has some quantum products and some computing products, but the quantum component is not a computer. It's more of a quantum sorting machine than a quantum computing machine. It's great for protein folding though.

[Revalin]

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?

It just cuts the effective key size in half.  The current 160-bit signatures will be brute forced in 2^80 operations.  That sounds weak, but it's going to be a long time before quantum computers reach 160-bit levels (if ever), and even when they do the operations per second will be very low and 2^80 will be infeasible for a long time thereafter.

You're thinking of Grover's algorithm. Shor's algorithm does indeed break ECDSA in polynomial time, though we're a very long way off a useful implementation. And note that Bitcoin public keys are 256 bits, not 160 bits - the hash is 160 bits, but this is not broken by Shor's algorithm.

You are correct.  The lame thing is I actually know that.  https://bitcointalk.org/index.php?topic=54542.msg651428#msg651428

tl;dr: ECDSA will break terribly, but we can use another pubkey algorithm if necessary, and all addresses with no spent coins should be safe since they're also protected by the hashes.