Bitcoin Forum
December 14, 2017, 11:01:49 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 »  All
  Print  
Author Topic: "All cryptography is breakable" criticism  (Read 7358 times)
caveden
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 01:28:34 PM
 #1

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!

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513249309
Hero Member
*
Offline Offline

Posts: 1513249309

View Profile Personal Message (Offline)

Ignore
1513249309
Reply with quote  #2

1513249309
Report to moderator
1513249309
Hero Member
*
Offline Offline

Posts: 1513249309

View Profile Personal Message (Offline)

Ignore
1513249309
Reply with quote  #2

1513249309
Report to moderator
ElectricMucus
Legendary
*
Offline Offline

Activity: 1596


God of the code.


View Profile WWW
July 30, 2012, 01:35:02 PM
 #2

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
Hero Member
*****
Offline Offline

Activity: 504



View Profile
July 30, 2012, 01:35:09 PM
 #3

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

14ga8dJ6NGpiwQkNTXg7KzwozasfaXNfEU
caveden
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 01:41:12 PM
 #4

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.

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
damnek
Hero Member
*****
Offline Offline

Activity: 636



View Profile
July 30, 2012, 01:47:26 PM
 #5

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
Legendary
*
Offline Offline

Activity: 1596


God of the code.


View Profile WWW
July 30, 2012, 01:52:07 PM
 #6

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
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 01:53:51 PM
 #7

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? Smiley

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
caveden
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 01:55:16 PM
 #8

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?

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
DarkEmi
Full Member
***
Offline Offline

Activity: 223



View Profile
July 30, 2012, 01:56:43 PM
 #9

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

ProProfi.com
The first home improvement service cryptocurrency project
ICO | Discuss on Forum
ElectricMucus
Legendary
*
Offline Offline

Activity: 1596


God of the code.


View Profile WWW
July 30, 2012, 01:57:37 PM
 #10

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 Wink
rjk
Sr. Member
****
Offline Offline

Activity: 448


1ngldh


View Profile
July 30, 2012, 01:58:55 PM
 #11

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.

Mining Rig Extraordinaire - the Trenton BPX6806 18-slot PCIe backplane [PICS] Dead project is dead, all hail the coming of the mighty ASIC!
caveden
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 02:10:17 PM
 #12

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. Wink If that ever happens, bitcoin is the least of our problems.

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
kgo
Hero Member
*****
Offline Offline

Activity: 549


View Profile
July 30, 2012, 02:10:56 PM
 #13

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
Legendary
*
Offline Offline

Activity: 1106



View Profile
July 30, 2012, 02:14:12 PM
 #14

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?

18rZYyWcafwD86xvLrfuxWG5xEMMWUtVkL
rjk
Sr. Member
****
Offline Offline

Activity: 448


1ngldh


View Profile
July 30, 2012, 02:16:51 PM
 #15

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.

Mining Rig Extraordinaire - the Trenton BPX6806 18-slot PCIe backplane [PICS] Dead project is dead, all hail the coming of the mighty ASIC!
DarkEmi
Full Member
***
Offline Offline

Activity: 223



View Profile
July 30, 2012, 02:19:55 PM
 #16



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

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

ProProfi.com
The first home improvement service cryptocurrency project
ICO | Discuss on Forum
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1792

Newbie


View Profile
July 30, 2012, 03:05:36 PM
 #17

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
Newbie
*
Offline Offline

Activity: 14


Bitcoin's Chief Executive Officer


View Profile
July 30, 2012, 03:09:19 PM
 #18

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.

Don't you worry about Bitcoin, let me worry about Bitcoin.

1HjH1Gm45w1m6J44VmXezvih3NzgXG7YfE
rjk
Sr. Member
****
Offline Offline

Activity: 448


1ngldh


View Profile
July 30, 2012, 03:10:13 PM
 #19

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.

Mining Rig Extraordinaire - the Trenton BPX6806 18-slot PCIe backplane [PICS] Dead project is dead, all hail the coming of the mighty ASIC!
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 1792

Newbie


View Profile
July 30, 2012, 03:15:20 PM
 #20

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
Pages: [1] 2 3 4 5 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!