"All cryptography is breakable" criticism

[istar]

Everything is "breakable".

Gold, banks, stone, diamonds, art.

[Come-from-Beyond]

Citation from the article:

"In addition to a quantum computer, Lukin envisioned the system being used in applications that include “quantum cash” (a payment system for bank transactions and credit cards that relies on the coding of quantum bits to frustrate counterfeiters) and quantum networks (a highly secure communications method that uses quantum bits to transmit data)."

Time for Qubitcoin has come!

[Gabi]

SHA-256 is used by all the world, banks, governments, companies etcetc. If it get broke...well we can easily switch to something else with a client update. Meanwhile the entire world would collapse 

[Come-from-Beyond]

SHA-256 is used by all the world, banks, governments, companies etcetc. If it get broke...well we can easily switch to something else with a client update. Meanwhile the entire world would collapse 

The rest of the world will be fine, coz they use SHA-256 only for signing.

[DeathAndTaxes]

The rest of the world will be fine, coz they use SHA-256 only for signing.

Is a false statement.  SHA-256 is used in a variety of applications.

[check_status]

Currently, the best public attacks break 41 of the 64 rounds of SHA-256 or 46 of the 80 rounds of SHA-512, as discussed in the "Cryptanalysis and Validation" section below.

There are two meet-in-the-middle preimage attacks against SHA-2 with a reduced number of rounds. The first one attacks 41-round SHA-256 out of 64 rounds with time complexity of 2253.5 and space complexity of 216, and 46-round SHA-512 out of 80 rounds with time 2511.5 and space 23. The second one attacks 42-round SHA-256 with time complexity of 2251.7 and space complexity of 212, and 42-round SHA-512 with time 2502 and space 222.

http://en.wikipedia.org/wiki/SHA256

Yu Sasaki, Lei Wang, and Kazumaro Aoki, Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512
http://eprint.iacr.org/2009/479.pdf

Jian Guo, Krystian Matusiewicz (2008-11-25). Preimages for Step-Reduced SHA-2
http://eprint.iacr.org/2009/477.pdf

Couldn't an attacker replace unknown inputs/variables with known inputs/variables, then all of the targets data which uses encryption from that point forward would be breakable by the attacker?

[Come-from-Beyond]

The rest of the world will be fine, coz they use SHA-256 only for signing.

Is a false statement.  SHA-256 is used in a variety of applications.

OK. I'll explain. SHA-256 is used for hashing. Of coz it's used in a variety of applications. But if someone get a quantum computer and manage to falsify a digitally signed contract then only authentic owner of the contract will be harmed. If someone manage to falsify an SSL certificate then only visitors of the site will be harmed. But if someone manage to find block nonces every second, then everyone who uses bitcoins will be in troubles.

[Hawkix]

Couldn't an attacker replace unknown inputs/variables with known inputs/variables, then all of the targets data which uses encryption from that point forward would be breakable by the attacker?

That's where the double SHA256 will save our asses, IMHO. Reminds me that Satoshi had to be really smartass.

[DeathAndTaxes]

Couldn't an attacker replace unknown inputs/variables with known inputs/variables, then all of the targets data which uses encryption from that point forward would be breakable by the attacker?

You mean predict the future?  The inputs will be unknown until they are known. 

What the the prior block has for block 500,000?  Everyone will know once block 499,999 has been accepted by the network but there is no way for the attacker to predict the future and make the unknown inputs for block 500,00 known today.

[DeathAndTaxes]

OK. I'll explain. SHA-256 is used for hashing. Of coz it's used in a variety of applications. But if someone get a quantum computer and manage to falsify a digitally signed contract then only authentic owner of the contract will be harmed. If someone manage to falsify an SSL certificate then only visitors of the site will be harmed. But if someone manage to find block nonces every second, then everyone who uses bitcoins will be in troubles.

Quantum computers aren't  a magic bullet.  Yes using Shor's algorithm the search speed can be increased exponentially however at what cost?   For example say once ASICs become mainstream the cost to attack/defend the network using ASICs is $20,000 per TH.  Now say a quantum computer which could implement shor's algorithm on 256bit numbers could be built for $50,000 per TH equivelent.  Who cares?  An attacker is going to take the more economical option.

So quantum computer is only a threat if all 5 elements are true
a) it is possible to build a quantum computer which can implement shor's algorithm on 256bit numbers
b) it is possible to build a quantum computer large enough to 51% attack the network
c) it is possible to build a quantum computer that makes such attack more economical than ASIC based brute force
d) quantum technology can be restricted so that a computer meeting requirements a,b, c isn't available to "defenders"
e) Bitcoin protocol isn't changed to implement quantum resistant block hashing algorithm

The idea that a,b,c,d & e will all remain true at the same time is implausible.  a & b are technical limitations and currently impossible although they MAY be possible in the future.  c is likely only true if quantum computers are being mass produced.  If c is true then it is very likely d isn't true.   a,b,c &d aren't going to happen overnight so as implausible as that set on conditions is some years or decades before it becomes true Bitcoin could adopt a quantum reistant hashing algorithm making conditon e false.

[Come-from-Beyond]

Now say a quantum computer which could implement shor's algorithm on 256bit numbers could be built for $50,000 per TH equivelent.  Who cares?  An attacker is going to take the more economical option.

The USA government doesn't care of economical issues (it can print a lot of dollars). When existance of Bitcoin becomes a political problem, it will be solved using all resources of USA economy.

[drakahn]

Now say a quantum computer which could implement shor's algorithm on 256bit numbers could be built for $50,000 per TH equivelent.  Who cares?  An attacker is going to take the more economical option.

The USA government doesn't care of economical issues (it can print a lot of dollars). When existance of Bitcoin becomes a political problem, it will be solved using all resources of USA economy.

lolwat?

[rjk]

Now say a quantum computer which could implement shor's algorithm on 256bit numbers could be built for $50,000 per TH equivelent.  Who cares?  An attacker is going to take the more economical option.

The USA government doesn't care of economical issues (it can print a lot of dollars). When existance of Bitcoin becomes a political problem, it will be solved using all resources of USA economy.

In that case, why would they bother to fuck around with unproven quantum technology instead of using their own ASIC?

[Come-from-Beyond]

In that case, why would they bother to fuck around with unproven quantum technology instead of using their own ASIC?

Coz Bitcoin is still in its infancy.

[check_status]

Couldn't an attacker replace unknown inputs/variables with known inputs/variables, then all of the targets data which uses encryption from that point forward would be breakable by the attacker?

You mean predict the future?  The inputs will be unknown until they are known. 

What the the prior block has for block 500,000?  Everyone will know once block 499,999 has been accepted by the network but there is no way for the attacker to predict the future and make the unknown inputs for block 500,00 known today.

No, I'm not talking about predicting the future. I'm saying an attacker gains access to a computer which is encrypting shit in sha-256. The sha-256 program is modded to make what is encrypted there after breakable by the attacker. Now when the encrypted material is intercepted it is trivial for the attacker to decrypt yet still appears to be valid sha-256 encryption. Maybe the code is modded so more collisions occur or some other innocuous change. If the user doesn't validate the code integrity the user will never know the mod exists.

[anu]

Yes using Shor's algorithm the search speed can be increased exponentially however at what cost? 

What does Shor's algorithm have to do with hashing? And isn't the hashing so complex that decoherence will happen in the middle of the QC anyway?

[rjk]

Couldn't an attacker replace unknown inputs/variables with known inputs/variables, then all of the targets data which uses encryption from that point forward would be breakable by the attacker?

You mean predict the future?  The inputs will be unknown until they are known.  

What the the prior block has for block 500,000?  Everyone will know once block 499,999 has been accepted by the network but there is no way for the attacker to predict the future and make the unknown inputs for block 500,00 known today.

No, I'm not talking about predicting the future. I'm saying an attacker gains access to a computer which is encrypting shit in sha-256. The sha-256 program is modded to make what is encrypted there after breakable by the attacker. Now when the encrypted material is intercepted it is trivial for the attacker to decrypt yet still appears to be valid sha-256 encryption. Maybe the code is modded so more collisions occur or some other innocuous change. If the user doesn't validate the code integrity the user will never know the mod exists.

SHA256 is not encryption. I'm not sure what you are trying to say. You can't "decode" it. One of the functions of a hashing algorithm is taking a large arbitrary input such as a multi-gigabyte file, and outputting a very short string of letters and numbers that can uniquely identify that large file. You can't reverse the process, you can only hope to break the algorithm in such a way that a different input will make the same output - and this is currently impossible.

EDIT: I see your mention of code changes - and sure, if an insecure or deliberately compromised implementation of the algorithm is used, there would be problems. But stuff like that is hard to do on purpose, since all nodes have to agree, and good luck updating all of them to use your compromised code.

[check_status]

Then why does the NSA hold a contest to see if anyone can find out what a file is composed of by cracking the hash?

[caveden]

Everything is "breakable".

Gold, banks, stone, diamonds, art.

In case it hasn't been clear to everybody else, this is precisely the kind of silliness that I wan't to point out. (EDIT: That is, I want to point out how silly it is to think like that!)

[caveden]

Quantum computers aren't  a magic bullet.  Yes using Shor's algorithm the search speed can be increased exponentially however at what cost?   For example say once ASICs become mainstream the cost to attack/defend the network using ASICs is $20,000 per TH.....

I think the "magic bullet" of quantum computing, concerning bitcoin, would be used against ECDSA. AFAIK, if you manage to build one in secret, you could start stealing some bitcoin addresses secretly.
But still, I believe the devs will have the time to change the pubkey algorithm before such threat becomes a reality.