"All cryptography is breakable" criticism

[caveden]

I've recently been challenged with this "criticism", "all cryptography is breakable, it's just a matter of time", and thus concluding that bitcoin is not safe.

I'm pretty confident that the odds of a fatal flaw in algorithms so established like ECDSA or SHA-256 are so tiny that we should not even bother.
I wonder though if somebody here has some data that could help me hold such claim.

For example, what was the worst case of "broken cryptographic algorithm"? By "worst" I mean which took the longest to happen and/or affected the largest number of people who were already trusting the algorithm.
Has any fatal flaw ever been found in an algorithm as old (at the time the flaw was discovered, of course) as ECDSA for example? It's a bit clear to me that the longer an algorithm resists to professional scrutiny, the less likely it is to have a flaw. But having some numbers would probably help.

Thanks!

[1715109493]

1715109493

[1715109493]

1715109493

[1715109493]

1715109493

[ElectricMucus]

Well SHA256 is not provably secure. But besides that a brute force attack on it is not versatile.

A provably secure hashing algorithm just has the advantage that it is as difficult to break as solving some hard mathematical problem. That does not mean that SHA256 is inferior to provably secure methods but it could be.
But then again the strongest rebuttal of the argument is that if SHA256 were to be broken the stakes for the current world are much higher than just bitcoin...

[drakahn]

I've recently been challenged with this "criticism", "all cryptography is breakable, it's just a matter of time", and thus concluding that bitcoin is not safe.

I'm pretty confident that the odds of a fatal flaw in algorithms so established like ECDSA or SHA-256 are so tiny that we should not even bother.
I wonder though if somebody here has some data that could help me hold such claim.

For example, what was the worst case of "broken cryptographic algorithm"? By "worst" I mean which took the longest to happen and/or affected the largest number of people who were already trusting the algorithm.
Has any fatal flaw ever been found in an algorithm as old (at the time the flaw was discovered, of course) as ECDSA for example? It's a bit clear to me that the longer an algorithm resists to professional scrutiny, the less likely it is to have a flaw. But having some numbers would probably help.

Thanks!

if bitcoin is not "safe" because nothing is safe... then bitcoin is as safe as anything else, lol

also there are 2^160 or 1461501637330902918203684832716283019655932542976 possible addresses IIRC so brute force is gone as the "matter of time" argument

[caveden]

if bitcoin is not "safe" because nothing is safe... then bitcoin is as safe as anything else, lol

The person in question was probably implying that cryptography is not safe (not "everything"), and that we should therefore not trust any significant amount of money in it.

also there are 2^160 or 1461501637330902918203684832716283019655932542976 possible addresses IIRC so brute force is gone as the "matter of time" argument

It's not about brute forcing I'm talking about, that's obviously out of the question.
I'm talking about a potential flaw in the algorithm, like that WEP one.

[damnek]

A fairly well-known cryptosystem that got broken that comes to my mind is the Merkle-Hellman knapsack cryptosystem:
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
It was supposedly based on a "hard" problem, namely the knapsack packing problem, but it turned out that the sampling of random instances used for the knapsack crypto system does not yield an average-case hard problem (which is necessary for crypto).

[ElectricMucus]

Yes there could be a flaw in the SHA-256 algorithm that we don't know about. See my ramblings above...

A fairly well-known cryptosystem that got broken that comes to my mind is the Merkle-Hellman knapsack cryptosystem:
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
It was supposedly based on a "hard" problem, namely the knapsack packing problem, but it turned out that the sampling of random instances used for the knapsack crypto system does not yield an average-case hard problem (which is necessary for crypto).

That was just broken because it actually implemented an easier subset of the problem. Real provably secure methods are not breakable.

[caveden]

Thanks damnek.

So that one lasted 6 years, apparently. The wikipedia page doesn't say much about how widely used it was, but since we are talking about early 80s, I imagine it wasn't that much used.

So, "auction" started. Any bids higher than 6 years?

[caveden]

Yes there could be a flaw in the SHA-256 algorithm that we don't know about.

Yeah, and the world could also really end this year, but come on... what are the odds?

Do you know of any algorithm nearly as old and widely used as SHA-256 or ECDSA that have ever been broken?

[DarkEmi]

Cryptography relies on the mathematical conjecture P!=NP.

We can solve P in polynomial time (n^2) and can solve NP in exp time (2^n). (I am simplying a lot but thats basically it.)

As long as P!=NP breaking something as small as a 30 item input is basically impossible (just compare the size of 2^30 with 30^2)

Lets just say there has not been the tiniest hint that P might be equal to NP after decades of research, and most of the computers scientists think this is impossible.

This is also related to the existence of "one way function" and this conjecture has hold for a loooooong time

Edit : but yes the average case must be hard as well, not just the worst

[ElectricMucus]

Yes there could be a flaw in the SHA-256 algorithm that we don't know about.

Yeah, and the world could also really end this year, but come on... what are the odds?

Do you know of any algorithm nearly as old and widely used as SHA-256 or ECDSA that have ever been broken?

no

But I have some affinity for Conspiracy Theories, who knows what the NSA is hiding

[rjk]

Even MD5 was broken, and it was used for the SSL CA system for a while. So it's true that vulnerabilities can be found later. The thing is, Bitcoin uses more than one form of cryptography: SHA256, RIPEMD-160, and ECDSA.

Breaking SHA256 would be pretty monumental, but it wouldn't allow you to spend peoples' coins for them. To do that, you would need to break ECDSA, which is comparatively new.

[caveden]

Rjk, about MD5, how "broken" was it? I realized it became fairly easier to crack it, but it still needed a considerable effort in calculations. If a serious flaw is found in any of bitcoin's algorithms, but we have time to change the algorithm in use, that's still not that catastrophic.
Still on MD5, according to wikipedia, it took only 5 years from MD5 birth (1991) for a considerable flaw to be found. From that point on its usage was already questionable. 9 years later a more serious flaw. Only in late 2008 its obituary was finally published. So, it didn't happen "all of the sudden". If anything comparable were to happen with SHA-256, we should have time to adapt.

DarkEmi, I believe we can safely rule out the possibility of someone proving P==NP. If that ever happens, bitcoin is the least of our problems.

[kgo]

You also need to take a broken implementation into account.  That is probably more likely than cracking ECDSA, barring construction of non-trivial quantum computers.

http://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/

https://www.us-cert.gov/cas/techalerts/TA08-137A.html

http://www.prng.net/faq/netscape-ssl/

[caveden]

You also need to take a broken implementation into account.  That is probably more likely than cracking ECDSA

Good point.
How "trustworthy" is bitcoind implementation of ECDSA and SHA-256? I suppose Satoshi didn't implement it himself, did he? How long have the libraries used being available?

[rjk]

In re: MD5 - These guys proved it to be not collision resistant: http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf
Also see the wikipedia article on it.

[DarkEmi]

DarkEmi, I believe we can safely rule out the possibility of someone proving P==NP. If that ever happens, bitcoin is the least of our problems.

Then that means that all potential "vulnerabilities" of cryptography are just bad implementations

[Come-from-Beyond]

If Bitcoin survive 51% attack from a guy with a lot of FPGAs/ASICs, it will definitely die when USA government set a quantum computer on it. Even if SHA-256 has no weaknesses, such computer could easily increase Bitcoin difficulty to unreachable for the others level. Play with ur bitcoins until u can...

[Mike Jones]

If Bitcoin survive 51% attack from a guy with a lot of FPGAs/ASICs, it will definitely die when USA government set a quantum computer on it. Even if SHA-256 has no weaknesses, such computer could easily increase Bitcoin difficulty to unreachable for the others level. Play with ur bitcoins until u can...

After serving for too long in Airforce R&D, all I can tell you is that if the US government made a quantum computer, it wouldn't run for more than a week.

Everything is sub-contracted out to private contractors nowadays. I don't recall any capable of making a quantum computer.

[rjk]

If Bitcoin survive 51% attack from a guy with a lot of FPGAs/ASICs, it will definitely die when USA government set a quantum computer on it. Even if SHA-256 has no weaknesses, such computer could easily increase Bitcoin difficulty to unreachable for the others level. Play with ur bitcoins until u can...

Please cite actual mathematics to make this possible, and proof that such a computer exists and can out-perform what we have now.

Hint: It's not possible with current technology, go read some earlier threads in relation to Quantum computing.

[Come-from-Beyond]

Please cite actual mathematics to make this possible, and proof that such a computer exists and can out-perform what we have now.

Hint: It's not possible with current technology, go read some earlier threads in relation to Quantum computing.

A month ago I read an article about breakthrough in quantum computing made by a Russian scientist working in the USA. The article was in russian, it will take some time to find english edition.

EDIT: Found it - http://big5.xinhuanet.com/gate/big5/news.xinhuanet.com/english/sci/2012-07/04/c_131694826.htm