Hacker News Reader

Comment by dogas | Hacker News Reader

I think the other article (http://apenwarr.ca/log/?m=201105) written about bitcoin failing is more detailed and contains potentially more plausible ways of how bitcoin can fail. The openwarr article refers to potential failures with the SHA256 backbone of bitcoins.

"With bitcoin, a single failure of the cryptosystem could result in an utter collapse of the entire financial network. Unlimited inflation. Fake transactions. People not getting paid when they thought they were getting paid. And the perpetrators of the attack would make so much money, so fast, that they could apply their fraud at Internet Scale on Internet Time.)"

IANA cryptography expert. Is this feasible in the way the author predicts? Could SHA256 be cracked quickly, a la MD5? My gut is that it won't be able to, but I can't back up my argument.

View on HN

That's not a "potentially more plausible" way for it to fail. It's merely a theoretical vulnerability. The bursting of a bubble in the price of a worthless asset, though -- that's, historically-speaking, a dead certainty.

Come on, people. This isn't the first asset bubble in history (though it may be the most cleverly-designed). We all know how it ends. People keep paying ever-higher prices for the asset, hoping it will go up. And it does for a while. Then one day, the price of the asset stops going up, people realise they don't want to own this asset now it's stopped going up, the value collapses, ka-pow, it returns to a more natural value.

For a real estate bubble, this may mean a halving in prices, because the natural value of real estate is quite high. For bitcoins, the natural value is zero.

While attacks against the basic building blocks of cryptosystems (like the SHA256 hash or AES block cipher) are rare, the protocols built upon those blocks can be independently vulnerable.

Take the Needham-Schroeder public key protocol from 1979, for example. http://en.wikipedia.org/wiki/Needham-Schroeder_protocol#The_... . It's simple and "obviously" foolproof, but a vulnerability was published in 1995, 16 years later.

Right now, we don't know if the bitcoin protocol has such a flaw. However, if it turns out to have an exploitable flaw, the entire bitcoin network will have to switch to a new protocol, which I haven't heard described as something they have a concrete plan for.

Such switch happened once.

It was found, that due to overflow, someone issued a lot of bitcoins to themselves in the block. During several hours was released a new client, which ignored flawed blockchain. When most people moved to a new client, the new blockchain overcame the exploited one.

Though it was when bitcoin wasn't popular.

I was (and still am) a bitcoin user during this period, it was managed relatively easily and quickly; major miners updated their clients and within a few hours, the competing blockchain had died off.

This would likely be even easier to accomplish today; as things currently stand, all mining pools and groups have a vested interest in maintaining the integrity of the blockchain.

I'm definitely not a crypto expert, but the way I read it was simply that if sha256 gets defeated, bitcoin is screwed.

I don't so why it couldn't be defeated, most of the other crypto systems which were going to last us for centuries got defeated..

It's not can it be broken, but when. It took 13 years for MD5 to be thoroughly broken. There are already theoretical attacks on SHA-256, which is one of the reasons there is currently a competition for SHA-3. If Bitcoin is to be a currency, it needs to have long-term stability, which is not helped by basing itself on crypto-systems that will be broken eventually.

> IANA cryptography expert. Is this feasible in the way the author predicts? Could SHA256 be cracked quickly, a la MD5? My gut is that it won't be able to, but I can't back up my argument.

IANA cryptography expert either, but my understanding is that the biggest threat to SHA is quantum computing.

http://en.wikipedia.org/wiki/Grover%27s_algorithm

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

I am not an expert either, but I can't see what Grover's algorithm has to do with quantum computers. When you look at the known algorithms for them, quantum computers seem pretty useless... It's not hashes that fear quantum computers but existing public key crypto.

Inverting a function in O(N^0.5) is useless?

Double the hash length (use SHA-512 rather than SHA-256) and you're done, no?

If SHA-256 gets completely broken, then yes. However, such instant breakdown may not happen in practice:

* weaknesses found usually still require some computation time, which may be prohibitively expensive. Reducing 2^128 to something like 2^90 is terrible disaster from crypto perspective (and buyer confidence), but won't open floodgates for fake coins (if faking a coin costs thousands times more than mining/buying, then nobody will bother on large scale).

* attacks typically have certain limitation, e.g. only generate collisions, but not preimage, or apply only to certain types/lenghts of data. Hash could be totally broken for one set of cases (MD5 digital signatures are useless) and at the same time still hold strong for other (MD5-hashed salted passwords are safe, as best known preimage attack is 2^123), so even if some terrible flaw in SHA256 is found, it may not be applicable to the way Bitcoin uses the hash.

It doesn't even need to be a real problem - just one that the investor perceive as a problem. And given that the tech is pretty complex and beyond the understanding of a lot of people using bitcoin then that risk is even greater.

And as with any investment scheme the potential for manipulation by rumour is also very real. There is a lot of regulation around more mainstream investment and money mechanisms to stop this (and it still happens) - bitcoin, which has no centralised "defender", will be just as prone to it.

I would imagine that now a wider audience is becoming aware of bitcoin we will start seeing this kind of thing in the next few months (and possibly are already doing)

This is more along the lines of "SHA256 has not been proven to be secure, therefore, it may be cracked." It would require novel discoveries in mathematics to do so.

Actually many cryptographic algorithms that got defeated, haven't been defeated with "new discoveries in mathematics". Also, you can't really prove that such an algorithm is secure. You can only prove that it exhibits certain properties that make it more secure versus other algorithms.

Judging by how cryptographic methods got defeated in the past, I think it's safe to assume that it's only a matter of time.

  Also, you can't really prove that such an algorithm is secure.

Incorrect. One Time Pad encryption is provably secure. (Proven by Claude Shannon, no less; as in, the guy who invented information theory.) It is impossible to decrypt if you do not have the key.

...subject to your key being safe, produced from a good source of entropy and never used anywhere else. Is this provable?

keeping the key safe, yes, using the key once, yes, but need not be random at all (with in reason - a key of 0s is feasible, under the pretense that the cipher text, which would be equal to the plain text, is the cipher text for any message with the same length, for some key)

the key space being the same size as the message space, and cipher text space means that all messages of equal length are possible, with no way of knowing which one is the correct one. i suppose, a theoretical attack would be to be to enumerate all messages in the english language, XOR them with the cipher text, and see which resulting keys come close the properties of the PRNG used..

even non-determinism can't help you here, i'm afraid.

I leave the reason that this is among the funnier HN crypto comments ever as an exercise to the reader. And, of course it happened on a Bitcoin thread.

never once tried to argue that it is a practical approach...

additionally, attempting to exhibit intellectual superiority by making someone look stupid, isn't infuriating, it's just sad.

i wouldn't conduct myself like that in public or on the internet. it's a shame that anyone thinks it's acceptable.

One time pads strain the definition of "encryption" and are by convention a bozo filter for people talking about crypto. For instance, downthread, you have someone saying that an all-zeroes OTP key would in theory be fine.

In reality, all OTPs do is shift forward in time a relationship that must still be secured through some other means.

So, from now on, when we talk about the feasibility of breaking crypto, let's implicitly constrain "crypto" to "crypto that people can use in practice".

i think you've misunderstood what i was saying. the OTP is definitely not a practical method of encryption, obviously.

and no, OTPs do not require that the that any secure relationship be formed forward in time.

in fact, restricting "crypto" to "crypto that people can use in practise" doesn't rule out the OTP - it was used with great success in both world wars, owing to the fact that agents were able to share keys before the fact, use them once, and then discard them.

finally, at no point would i ever suggest using the OTP as a means of encryption in place of a public key system, especially one with a key of 0s. why you suggest such a thing is beyond me.

It's not impossible to prove cryptographic algorithms are secure. It's just really, really, really difficult. So difficult it's not even proven that one way functions exist in the first place! (For context: if one way functions exist, then P!=NP).

Proving cryptographic algorithms are secure involves proving statements over all turing machines. For example, one definition of a 'secure' pseudo random number generator is one such that no turing machine can distinguish its output from 'true' random (with 2/3 certainty) in polynomial time.

However, we do know a really-really-probably secure one way function. If there are any one way functions, then it is secure. It just isn't really practical. http://en.wikipedia.org/wiki/One-way_function#Universal_one-...

As someone says, one-time pads are impossible to decrypt without they key. But you can guess the key or use some other brute force mechanism.

My guess, SHA-256 will fall to a quantum computing algo in a few years.

As someone says, one-time pads are impossible to decrypt without they key. But you can guess the key or use some other brute force mechanism.

Actually, you can't even reliably brute force a one time pad. The key is always the same length as the message. All plausible messages of length N are equally valid solutions for a brute forcing algorithm.

>All plausible messages of length N are equally valid solutions for a brute forcing algorithm.

Assuming there is no out-of-band information to use to attack the ciphertext then yes I agree is unlikely to find a unique solution.

Aside: I'd never considered that key length was dictated by the term "one-time pad".

You could be using a One Time Pad for key management. This is certainly feasible now, since a couple of Gigabytes of data is now considered a manageable amount.

Hashing algorithms aren't generally as well understood as reversible encryption algorithms. It's entirely possible that these novel discoveries are just around the corner.

And when that happens...

Reply on news.ycombinator.com