Bitcoin Forum

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!

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...

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

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.


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.

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).

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


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

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? :)

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?

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

no

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

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.

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.

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/

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?

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.

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

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.

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

Everything is "breakable".

Gold, banks, stone, diamonds, art.

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!

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  :D

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.

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?

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.

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

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.

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.

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?

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.

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.

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?

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.

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?

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!)

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.

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.

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. :)

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.

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...

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 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.

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?

Thanks!

But.. why always double-hashes?

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?

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.

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.

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

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.

I think $5 wrench still defeats one time pad.

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

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.

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.
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.

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 (http://en.wikipedia.org/wiki/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.

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.)

I would point out extension attacks are only possible when the payload is of arbitrary size.  Bitcoin blockheaders are fixed sized, exactly 640 bits not a bit more or a bit less.   Thus even if you found a payload which has a longer length but generates the same hash it wouldn't be a valid bitcoin blockheader and thus would be rejected by the network.

Still it is possible that Satoshi either didn't understand this or misunderstood the implications of a extension attack and used the double hash as a method to "prevent" the attack.  It certainly is plausible and is the most likely explanation I have heard so far.

Breaking a bank's website security does not give you access to the vault.

No way.  These days $5 would get you a wrench about four inches long and two ounces.  At least a $30 wrench is required to defeat a one time pad.

Nor would breaking bitcoin's blockchain security give you access to anyone's vault that you, personally, didn't already own in the recent past. 

And my understanding of why there are two consecutive uses of SHA256 was more about establishing 'hooks' for a future use of a more advanced hashing algo alongside the current one, permitting the network to upgrade over an extended period of time without the potential of exposing the system to an unknown attack vector or requiring a rapid upgrade cycle.

I don't think it was the block chain security to which I was referring, considering that that does not give you access to any money.

Well, on that note, it would be wise if the development team were to consider the adoption of a second address schema using a different public/private algo.  This way, in the event that a flaw in the current one is discovered, there will be an option to move funds to before the blackhats have the chance to exploit any flaws.

Right now?  What if we did that and it turned out the second public/private algo was broken first? ECDSA is a NIST standard that has been very well studied and has no known vulnerabilities.  There are much, much, much higher items on the development TODO list, like figuring out a nice GUI for multi-device transaction authorization.

I did write up plans for migrating to a new algorithm here:
  https://gist.github.com/2355445  (See the "using a quantum-resistant digital signature algorithm" example at the end).

Easy!  Easy!  I was not aware this was already under consideration.  You're doing a fine job, Gavin; not everyone here is out to get you.

Yes. Also, as far as I can tell, the attack isn't relevant unless you're hashing a secret, which the Bitcoin protocol doesn't use. Ie. the point of the attack is the ability to extend a message that has been hashed together with a secret, to produce a valid hash of a message that consists of m+p+m' where m is the original message including a secret, p is the SHA-256 padding, and m' is the message you want to add to the end.

I guess the point is that it's not apparent whether some future use-case of the protocol could make such an attack useful, and doing two rounds of SHA-256 vs. just one is so inexpensive that we might as well avoid that concern by just always hashing twice. It really should be the default use of SHA-256 anyway, which is why SHA-3 is required to implement this feature (or a feature that offers the same protection) by default. Ie. it's a SHA-256 bugfix that may or may not be necessary, but there's practically no reason not to do it.

Most systems can switch out one hashing system for another. For example, when md5 was shown vulnerable to collisions SSL signatures simply switched to another hashing method.

Bitcoin has the disadvantage of being set in its ways. The majority of clients would have to be updated to at the same time switch to another method. Even if such a thing could be coordinated and the bitcoin contract ammended in the wild it would take a lot of time to organize it. Those that failed to update would reject these new blocks.

Which means they would update because otherwise they reject their own transactions. EDIT: I assume of course that such a change would not be controversial and lead to a blockchain fork.

So what's the supposed danger here? Some super quantum computer manages to instantly solve all of the blocks and thus take all of the new coins?

The danger is some super quantum computer manages to find an ECDSA private key that corresponds to every Bitcoin address.

Should be enough if finding a private key to any given address is trivial.

Reminds me: Does anyone know why addresses are 160 Bit, and not 256? That way, there seem to be ~ 2^96 private keys for any given Bitcoin address - so the true length of a private key is also only 160 Bit. What would happen if anyone used a new private key for a transaction that does not correspond to an already published public key?

TIA
-Anu

To keep the accounts as short as possible to make it easier to communicate them.

Unless someone specifically thought to check, nobody would know.

I've recently been informed that the next address schema is likely to be a 'quantum resistant' algo, although I don't understand it.  It's low on the to-do list though, since there are more pressing threats.

Not quite true, the published address isn't really the public key, it's a hash of the public key with a checksum thrown in for error correction.

Wouldn't matter anyway, since that is how bitcoins' transactions work.  A user creates a private key, it's corrosponding public key, and the address.  The address is published and can receive coins, but the public key isn't published until the first time coins are spent from that address.  The way this works is that addresses cannot be reversed to their public key, but the public key is required before the other nodes can verify the digital signing of any spending transactions.  So every time coins are spent from that address, the public key is included in the transaction and the transaction is signed with the private key.  Other nodes can then verify that the signing key is mathmaticly related to the public key presented & the address is related to the public key by the standard hashing algo used.  If I'm getting some details wrong, I'm sure someone will correct me, but this is the general idea.

Yup, that is correct.  To spend, you sign the transaction with the private key, and then provide that signature and the corresponding public key to the network.  The network then verifies that 1) the signature could only have been calculated using the private key that corresponds to the public key provided, and 2) that the public key does actually hash down to the hash (address) in the prevout.

A key point is that using a public key once does not claim it or make it special.  If someone manages to find a different private/public key pair with the same pubkey hash, that key is just as valid for other transactions using the same hash as the original was.

I apologize if this has been asked here already and I missed it (it seems obvious) - are there recent examples of cryptographic algorithms being broken in a sudden, catastrophic fashion? I see it much more likely that a "weakness" is published first, thus giving everyone some time to migrate to a new signature algo and send their coins to the new system. How hard would it be technically to enable spending of "old" ECDSA coins into the network based on a different signing algorithm?

Catastrophic failures are not at all common (if ever) for well-tested algorithms. Speculative ones get busted with some regularity. Old ECDSA coins would need to be spent to a new address that is either a new public key or a new hash from a new public key. According to what I've read, this can be done without a hard fork, but unless all miners are upgraded the network will fork, at least temporarily.

The German enigma code. Although the adjectives "recent" and "catastrophic" are a matter of historical scope and political convictions / nationality, respectively. I suppose most people today would not call it catastrophic, but luckily.

I don't think this has ever happened to any reputable modern algorithm (someone please correct me if I'm wrong). All now-broken cryptographic algorithms that I know of were widely known to be broken long before an actual attack was successfully demonstrated.

Of course it's possible to send "old algorithm" coins to an "new algorithm" address. It's already happening: compressed public keys technically function as a new algorithm, even though it's all ECDSA.