Elliptic Curves subject to Quantum Computer attacks, ramifications for Bitcoin?

shorena

copper member

Activity: 1498

Merit: 1499

No I dont escrow anymore.

Quote from: tspacepilot on September 13, 2015, 11:22:06 PM

Quote from: oblivi on September 13, 2015, 11:31:47 AM

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

It seems like there's a lot of half-informed discussion on this thread. SHA256 isn't the signature algorithm.

This thread was supposed to be about ECDSA, and as far as I know, a good QC weakens ECC in a way that it doesn't do to RSA. Shorena's first post in here correctly points out that public keys aren't directly revealed in a transaction which spends to an address (just the hash of them is), so there's some security there for addresses which haven't been reused.

I guess I'm still wondering about how the UTXO set would be protected in the case where a QC which could break ECC was developed. Clearly some sort of hard-fork, but what would it look like? How could you get all of the bitcoin owners to take notice and do X to protect their transactions? It seems like people with paper wallets and cold-storage might have to take action. How could they be notified? Maybe I'm missing something obvious, but I'd like to hear discussion on that topic because it's definitely not obvious to me what to do.

I think that all the talk of SHA256 and mining and asics is missing the point of this thread.

I dont think everyone will react in time, but I also have problems with the idea that such an attack comes out of nowhere. My hope is that (similar to suggested RSA key sizes) to switch to a different algorithm will be done in advance.

Its a bit late, but this[1] paper by DJB is probably an interesting read.

[1] http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

tspacepilot

legendary

Activity: 1456

Merit: 1076

I may write code in exchange for bitcoins.

Quote from: oblivi on September 13, 2015, 11:31:47 AM

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

It seems like there's a lot of half-informed discussion on this thread. SHA256 isn't the signature algorithm.

This thread was supposed to be about ECDSA, and as far as I know, a good QC weakens ECC in a way that it doesn't do to RSA. Shorena's first post in here correctly points out that public keys aren't directly revealed in a transaction which spends to an address (just the hash of them is), so there's some security there for addresses which haven't been reused.

I guess I'm still wondering about how the UTXO set would be protected in the case where a QC which could break ECC was developed. Clearly some sort of hard-fork, but what would it look like? How could you get all of the bitcoin owners to take notice and do X to protect their transactions? It seems like people with paper wallets and cold-storage might have to take action. How could they be notified? Maybe I'm missing something obvious, but I'd like to hear discussion on that topic because it's definitely not obvious to me what to do.

I think that all the talk of SHA256 and mining and asics is missing the point of this thread.

Amph

legendary

Activity: 3206

Merit: 1069

Quote from: shorena on September 13, 2015, 10:52:02 AM

Quote from: Amph on September 13, 2015, 10:46:17 AM

Quote from: shorena on September 13, 2015, 10:12:19 AM

Quote from: Amph on September 13, 2015, 08:23:42 AM

Quote from: Lauda on September 13, 2015, 07:00:57 AM

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

i'm in agreement with you, and i never said that sha256 could be broken directly with quantum, but it could be done indirectly, in the sense that we need to change the algo

because even if miners are not affected, who want to spend it is affected and if bitcoin is useless because of this, miners are also mining useless coins, which mean that they will not continue to mine and bitcoin will die

So why is your argument that the mining equipment has to be replaced?

if they are forced to change the algo, they need to change asic too, i though that it was very clear

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: NorrisK on September 13, 2015, 08:00:15 AM

That would mean that the private key would be cracked from the public key withing 10 minutes of broadcasting the transaction right? Would it really become that easy with quantum computing?

I would say 10 ms, not minutes.

Lauda

legendary

Activity: 2674

Merit: 2965

Terminated.

Quote from: oblivi on September 13, 2015, 11:31:47 AM

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

SHA256 has no known vulnerabilities which makes it great. However, if we come to a day where SHA256 is not enough (because for a quantum computer it could be potentially 128bit), then we can upgrade to SHA512. I'm almost sure that aside from software changes, the current hardware would still work.

oblivi

hero member

Activity: 700

Merit: 501

None. Worrying about SHA256 being broken in our lifetimes is a waste of time. Also, if SHA256 gets broken it will mean the entire society of information is done since most of the encryption behind all kind of infrastructures including traditional banking are backed by SHA256 so it would be game over for everyone not only Bitcoin.

shorena

copper member

Activity: 1498

Merit: 1499

No I dont escrow anymore.

Quote from: Amph on September 13, 2015, 10:46:17 AM

Quote from: shorena on September 13, 2015, 10:12:19 AM

Quote from: Amph on September 13, 2015, 08:23:42 AM

Quote from: Lauda on September 13, 2015, 07:00:57 AM

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

i'm in agreement with you, and i never said that sha256 could be broken directly with quantum, but it could be done indirectly, in the sense that we need to change the algo

because even if miners are not affected, who want to spend it is affected and if bitcoin is useless because of this, miners are also mining useless coins, which mean that they will not continue to mine and bitcoin will die

So why is your argument that the mining equipment has to be replaced?

Amph

legendary

Activity: 3206

Merit: 1069

Quote from: shorena on September 13, 2015, 10:12:19 AM

Quote from: Amph on September 13, 2015, 08:23:42 AM

Quote from: Lauda on September 13, 2015, 07:00:57 AM

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

i'm in agreement with you, and i never said that sha256 could be broken directly with quantum, but it could be done indirectly, in the sense that we need to change the algo

because even if miners are not affected, who want to spend it is affected and if bitcoin is useless because of this, miners are also mining useless coins, which mean that they will not continue to mine and bitcoin will die

shorena

copper member

Activity: 1498

Merit: 1499

No I dont escrow anymore.

Quote from: Amph on September 13, 2015, 08:23:42 AM

Quote from: Lauda on September 13, 2015, 07:00:57 AM

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

The mining algorithm is based on SHA 256(SHA 256(data)) which is believed not to be affected by quantum computing. As LaudaM said, a quantum computer is not just a very powerful computer, but its a machine that computes differently and thus handles certain tasks (e.g. factorization, or modul n division[1]) better than a normal computer. It does not handle everything better.

Quantum computing would probably break ECDSA which is used when signing a transaction or message. Considering what Come-from-Beyond said about the times it would render bitcoin useless as you no longer can spend your coins without someone instantly[2] (or at least very fast) calculating your private key from the public key that is part of the transaction. Mining however would not be affected as there is no ECDSA only sha256[3].

[1] Note: factorization is the basis for RSA security, for ECDSA its a modul n divison.
[2] I have no idea how long it would actually take so I will just assume this as a worst case scenario.
[3] https://en.bitcoin.it/wiki/Block_hashing_algorithm

Amph

legendary

Activity: 3206

Merit: 1069

Quote from: Lauda on September 13, 2015, 07:00:57 AM

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).
If you continue the nonsense from the last thread, I will stay away from this one. I will not waste my time once more.

wut? are you able to read or what, he said that it certainly possible to change the algo, and i said that it is not so easy as he think, simple as that, you are going overboard with your no-sense man...or you have comprehension problem, most likely

also no i was right in that thread i was saying the same excat thing he said in this quote that i quoted(but with different words of course), go back and find the thread you will see

NorrisK

legendary

Activity: 1946

Merit: 1007

Quote from: Come-from-Beyond on September 13, 2015, 04:05:05 AM

Quote from: shorena on September 12, 2015, 06:10:32 PM

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

That would mean that the private key would be cracked from the public key withing 10 minutes of broadcasting the transaction right? Would it really become that easy with quantum computing?

Lauda

legendary

Activity: 2674

Merit: 2965

Terminated.

Quote from: Amph on September 13, 2015, 06:53:15 AM

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

You were not misunderstood, you were wrong just as you are once again. Nobody is talking about changing the mining algorithm (which is not susceptible to attacks for now, aside from using brute-force (impossible within out lifetime).

Update:
I do not have any more patience for people who will not admit to being wrong (see Shorena's post for confirmatino). Amph has been put on ignore.

Amph

legendary

Activity: 3206

Merit: 1069

Quote from: shorena on September 12, 2015, 06:10:32 PM

Quote from: tspacepilot on September 10, 2015, 02:45:34 PM

I saw this in Slashdot yesterday:

http://it.slashdot.org/story/15/09/09/1938206/cryptographers-brace-for-quantum-revolution

Quote

Tokolosh writes:
An article in Scientific American discusses the actions needed to address the looming advent of quantum computing and its ability to crack current encryption schemes. Interesting tidbits from the article: "'I'm genuinely worried we're not going to be ready in time,' says Michele Mosca, co-founder of the Institute for Quantum Computing (IQC) at the University of Waterloo..." and "Intelligence agencies have also taken notice. On August 11, the US National Security Agency (NSA) revealed its intention to transition to quantum-resistant protocols when it released security recommendations to its vendors and clients." Another concern is "intercept now, decrypt later", which presumably refers to the giant facility in Utah.
In related news, an anonymous reader points out that the NSA has updated a page on its website, announcing plans to shift the encryption of government and military data from current cryptographic schemes to new ones that can resist an attack by quantum computers.

Then I looked a bit at the wikipedia page on elliptic curve cryptography and it seems that ECC is especially vuneralble to quantum attacks compared to RSA crypto of equivalent key lengths. From what I understand, the main advanage to date of ECC over RSA is that you can get equivalent security for shorter key-lengths. A 256bit ECC key is supposed to provide security on the order of like a 1028bit RSA key. However, apparantely quantum computers nullify this advanage.

Does this have ramifications for bitcoin? In a worst-case scenario in which our fundamental crypto is broken, would bitcoin be able to upgrade the protocol to use a different crypto system? How would the UTXO set be secured?

Thanks in advance for educating me you guys.

I hope LaudaM chimes in.

Bitcoins main defense against quantum attacks are the hashes. Assuming ECC is broken and a private key can be calculated from a public key within reasonable time, youd still have to get the public key first. Since the address used are not public keys and the public key is only revealed once you signed something. You are "fine" as long as you dont spend your coins and have them on an address that was never used. That would be a very serious problem, but considering that ECC is used not only for bitcoin it might be worse for other systems.

It is certainly possible to switch to an algorithm that is considered to be safe in such an event, but AFAIK its a hard fork.

this is exactly what i was talking about in our dispute, that time we were fighting for the whole quantum story in that thread, but i was misunderstood, i or i wan't able to say it clearly

the problem with changing the algo, is that every miners must change their equipments, if you thing that almost 400peta of hash can be changed to a new algo with no problem, you're being naive

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: tsoPANos on September 13, 2015, 04:46:31 AM

Even a quantum computer will take some time to crack your key, most likely several hours!

Where is "several hours" pulled from? On a QC factorization takes near the same time as multiplication.

tsoPANos

hero member

Activity: 602

Merit: 500

In math we trust.

Quote from: Come-from-Beyond on September 13, 2015, 04:05:05 AM

Quote from: shorena on September 12, 2015, 06:10:32 PM

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

Well I disagree with that.
Even a quantum computer will take some time to crack your key, most likely several hours!
Provided with a reasonable transaction fee, your transaction will need no more than 15 minutes to confirm!
We are not there yet, and a hard fork could be scheduled to allow addresses using some kind of post-quantum cryptography.

On the other hand, multi-transaction addresses like public casino hot wallets with lots of coins might be problematic.

coinplus

legendary

Activity: 1386

Merit: 1058

When there is a collusion or any kind of threat for bitcoin private key or for bitcoin address. We need not to worry bitcoin will simply shift to new improved algorithm for the protection of our hard earned bitcoins. Bitcoin's core plan lies on its cryptography.

Kprawn

legendary

Activity: 1904

Merit: 1073

The reality would be... If this was successful .....Bitcoin would collapse and all coins will become worthless. The success of Bitcoin is in the demand for it... Who will want BTC if

anyone can take it from you? Who will accept it as payment... if you cannot own it or keep it safe? You would kill the cow, that produce the milk.

The price per Bitcoin will drop to zero. Huh

Lauda

legendary

Activity: 2674

Merit: 2965

Terminated.

Quote from: shorena on September 12, 2015, 06:10:32 PM

I hope LaudaM chimes in.

Your post is quite well explanatory as well.

A few months ago, when shorena and I engaged in some thread related to quantum computing, I had stated that ECDSA would be our first problem. The Eliptic Curve Digital Signature Algorithm (for those that do not know) is used for signing transactions in Bitcoin. To simplify, if the algorithm gets broken, anyone with a quantum computer could extract a private key from any public key and take the Bitcoin stored on it.

However, this is not even remotely as simple as people seem to think. The public key of an address isn't really made public, but your Bitcoin address is (which is a hash of it). In other words, a quantum computer can't derive the public key from your Bitcoin address. Also by the time someone computes your private key and manages to import it you could already send your funds elsewhere.

Quote from: Kprawn on September 13, 2015, 04:43:24 AM

Nonsense.

I wouldn't even know where to begin with your post.

killerjoegreece

legendary

Activity: 1666

Merit: 1007

Professional Native Greek Translator (2000+ done)

thats a bit worrying for bitcoin. i hope it does not become a reality that soon Cheesy

Come-from-Beyond

legendary

Activity: 2142

Merit: 1009

Newbie

Quote from: shorena on September 12, 2015, 06:10:32 PM

You are "fine" as long as you dont spend your coins and have them on an address that was never used.

Funny that you will never be able to spend these coins, once you broadcast a transaction the adversary can get your private key and send a double-spending with a higher fee.

Topic: Elliptic Curves subject to Quantum Computer attacks, ramifications for Bitcoin? (Read 1549 times)