"All cryptography is breakable" criticism

[JoelKatz]

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 would just respond, "It's safe for less than whatever that amount of time is". If a vault can be cracked in a hundred thousand years, it's safe to store something in it for a few decades.

[DeathAndTaxes]

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.

SHA-256 is a hashing function.  There is no such concept as decryption.  There is only plaintext -> hash.  Also if an attacker has access to the computer doing the hashing couldn't they simply make a copy of the secret being hashed before it is hashed.

[DeathAndTaxes]

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?

They don't.  You likely misunderstood the intent and purpose of the contest.

Nobody not even the creator of a hash can convert a hash back to the plaintext.
All you can do it take the KNOWN SECRET hash it and compare it to the stored hash.  If they match then you have validated the secret.

[caveden]

So, the champion of losers remains "Merkle–Hellman knapsack cryptosystem"?
6 years before being broken?

And, can I say MD5 was the most "messy" case of broken cryptographic algorithm (caused more actual damage)? Or WEP caused more trouble? Hard to compare I imagine...

[check_status]

Then how did they crack this if reversing a hash is not possible?
http://www.wired.com/dangerroom/2010/07/solve-the-mystery-code-in-cyber-commands-logo/

[caveden]

I would just respond, "It's safe for less than whatever that amount of time is". If a vault can be cracked in a hundred thousand years, it's safe to store something in it for a few decades.

I don't believe the guy was talking about brute-forcing it, but finding a flaw in such algorithms. To me, he was implying that every cryptography algorithm has flaws, and it's just a matter of time before they are exploited.
I wanted to counter-argue on how unlikely it is to find such fatal flaws in any of the algorithms used in bitcoin.

[caveden]

The thing is, Bitcoin uses more than one form of cryptography: SHA256, RIPEMD-160, and ECDSA.

RIPEMD-160? For what is this one used in bitcoin? (guessing attempt, to create the address from the public-key?)

[anu]

The thing is, Bitcoin uses more than one form of cryptography: SHA256, RIPEMD-160, and ECDSA.

RIPEMD-160? For what is this one used in bitcoin? (guessing attempt, to create the address from the public-key?)

Step 3 in https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

[Mike Jones]

The thing is, Bitcoin uses more than one form of cryptography: SHA256, RIPEMD-160, and ECDSA.

RIPEMD-160? For what is this one used in bitcoin? (guessing attempt, to create the address from the public-key?)

Step 3 in https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

I am now blown away.

[kokjo]

The thing is, Bitcoin uses more than one form of cryptography: SHA256, RIPEMD-160, and ECDSA.

RIPEMD-160? For what is this one used in bitcoin? (guessing attempt, to create the address from the public-key?)

Step 3 in https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

I am now blown away.

why?

[caveden]

Step 3 in https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

Thanks!

But.. why always double-hashes?

[JoelKatz]

I would just respond, "It's safe for less than whatever that amount of time is". If a vault can be cracked in a hundred thousand years, it's safe to store something in it for a few decades.

I don't believe the guy was talking about brute-forcing it, but finding a flaw in such algorithms. To me, he was implying that every cryptography algorithm has flaws, and it's just a matter of time before they are exploited.
I wanted to counter-argue on how unlikely it is to find such fatal flaws in any of the algorithms used in bitcoin.

There's no need, since he hasn't claimed that finding a flaw is likely. You can simply agree with him about every algorithm having flaws and it being just a matter of time before they are exploited. But it doesn't follow from this that it's unsafe. It's just a matter of time before a house gets hit by an asteroid. That doesn't mean houses are unsafe.

[check_status]

I would just respond, "It's safe for less than whatever that amount of time is". If a vault can be cracked in a hundred thousand years, it's safe to store something in it for a few decades.

I don't believe the guy was talking about brute-forcing it, but finding a flaw in such algorithms. To me, he was implying that every cryptography algorithm has flaws, and it's just a matter of time before they are exploited.
I wanted to counter-argue on how unlikely it is to find such fatal flaws in any of the algorithms used in bitcoin.

There's no need, since he hasn't claimed that finding a flaw is likely. You can simply agree with him about every algorithm having flaws and it being just a matter of time before they are exploited. But it doesn't follow from this that it's unsafe. It's just a matter of time before a house gets hit by an asteroid. That doesn't mean houses are unsafe.

If the house deteriorates to dust before the asteroid strikes the spot where the house had been, is it still considered a win?

[rjk]

Then how did they crack this if reversing a hash is not possible?
http://www.wired.com/dangerroom/2010/07/solve-the-mystery-code-in-cyber-commands-logo/

I see where you are confused about it now. What the person who solved it did was not decryption or reversing - their process would have been somewhat like the following:

1. Determine the type of number, if possible. In this case, it is a valid MD5 hash. (This is assumed because an MD5 hash is typically represented as a 32-bit hexadecimal number)
2. Attempt to hash arbitrary strings using MD5 to find out whether they match the number.

This person probably tried several bits of data, one of which was the actual original information (the mission statement). Since a hash is supposed to be deterministic (it produces the same output from a given input, no matter how many times you do it), he got a hash that matched what he was looking for and could therefore assume that his input data was the same as their input data, and that he had solved the puzzle.

[anu]

"All cryptography is breakable", as far as I know 1 time pads are still unbreakable.

Indeed, they are provably unbreakable given certain conditions. I was also wondering about the assumption that algorithms and all crypto are bound to be flawed. They are not. For example it's possible to implement a perfect MAX(x,y) function. And there may simply be no sub exp(N) way of factoring the product of 2 primes.

[JoelKatz]

"All cryptography is breakable", as far as I know 1 time pads are still unbreakable.

So is, "I'm thinking of a number. I've encrypted it and gotten 15. What number am I thinking of?"

[niko]

It's just a matter of time before a house gets hit by an asteroid. That doesn't mean houses are unsafe.

It's more interesting than this. While it's just a matter of time before a house is destroyed by an asteroid, it's not just a matter of time before a given cryptological function is broken. Like with other human endeavors, it's also a matter of limited resources, motivation, and luck. It's a matter of time, available personnel, money, luck, health, management, unpredictable resorce-shifting events, etc. You'll notice that, for entropic reasons, most of these factors are likely to prolong, not shorten the time required to break, build, or invent something.

So, it's not just a matter of time in this case.

[FreeMoney]

I think $5 wrench still defeats one time pad.

[runeks]

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.

The thing is, none of the cryptographic primitives that Bitcoin uses (SHA-256, RIPEMD-160, ECDSA) have been proven secure.

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.

It should be noted that the only way MD5 has been broken is that it's possible to construct two blocks of data that hash to the same value. Even if this attack was successfully applied for SHA256, it wouldn't affect Bitcoin. It would be a sign to find a new hash function, because it's a sign of weakness, but it's not a problem in itself.

I would just respond, "It's safe for less than whatever that amount of time is". If a vault can be cracked in a hundred thousand years, it's safe to store something in it for a few decades.

I don't believe the guy was talking about brute-forcing it, but finding a flaw in such algorithms. To me, he was implying that every cryptography algorithm has flaws, and it's just a matter of time before they are exploited.
I wanted to counter-argue on how unlikely it is to find such fatal flaws in any of the algorithms used in bitcoin.

Well, in order to prove that every cryptographic algorithm has flaws, he would need to find a flaw in every cryptographic algorithm. So please ask him to do so, or his claim is just an assumption.

Step 3 in https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

Thanks!

But.. why always double-hashes?

To prevent length-extension attacks. These attacks are a known weakness in the current SHA hash functions, but the new SHA-3 hash function - to be announced soon - will have built-in measures to secure against this. The double-SHA-256 is sort of a workaround to this vulnerability.

What worries me is some freak could look through a list of hashes some day and his brain make a connection giving birth to a new field of mathematics, order always seems to come from chaos. If he's that smart he'll probably keep his mouth shut and make billions though

Actually, I think this might be the new way of breaking hash functions. And as far as I recall, this was exactly how MD5 was broken. The Chinese researcher Wang Xiaoyun, who originally broke MD5, literally completely memorized the inner workings of the Merkle-Damgård construction that is the heart of MD5 - and SHA-1 and SHA-2 as well. She had a mental image of the states of the function through all its rounds, and used this to visually "figure out" which bits were important and which were not. It's not at all infeasible that this could be applied to SHA256.

[mrb]

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.

Very simple counter-argument: "online banking uses cryptography too (HTTPS), do you also consider it unsafe?" Of course not.

When cryptographic flaws will be found in Bitcoin, they will simply be fixed by an update of the protocol and algorithms. Very much like HTTPS had to be "fixed" in the past (BEAST attack, MD5 collisions, etc.)