6 ms·

I think the other article (http://apenwarr.ca/log/?m=201105 http://apenwarr.ca/log/?m=201105) written about bitcoin failing is more detailed and contains potent

by dogas 15y ago

I think the other article (http://apenwarr.ca/log/?m=201105 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.

nodata 15y ago
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..
sbierwagen 15y ago
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.
- bad_user 15y ago
  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.
  - sbierwagen 15y ago
    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.
    - rlpb 15y ago
      ...subject to your key being safe, produced from a good source of entropy and never used anywhere else. Is this provable?
      - foxhill 15y ago
        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.
        tptacek 15y ago
        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.
        foxhill 15y ago
        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.
- regularfry 15y ago
  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...
junklight 15y ago
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)
limmeau 15y ago
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_public-key_protocol 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.
- mike_esspe 15y ago
  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.
  - vessenes 15y ago
    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.
paxswill 15y ago
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.
Goladus 15y ago
> 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/Grover%27s_algorithm http://en.wikipedia.org/wiki/Quantum_computer http://en.wikipedia.org/wiki/Quantum_computer
- gwern 15y ago
  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.
  - jessedhillon 15y ago
    Inverting a function in O(N^0.5) is useless?
    - gwern 15y ago
      Double the hash length (use SHA-512 rather than SHA-256) and you're done, no?
hugh3 15y ago
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.
pornel 15y ago
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.

by dogas 15y ago

nodata 15y ago

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

sbierwagen 15y ago

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.

bad_user 15y ago
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.
- sbierwagen 15y ago
  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.
  - rlpb 15y ago
    ...subject to your key being safe, produced from a good source of entropy and never used anywhere else. Is this provable?
    - foxhill 15y ago
      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.
      - tptacek 15y ago
        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.
        foxhill 15y ago
        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.
regularfry 15y ago
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...

junklight 15y ago

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)

limmeau 15y ago

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

mike_esspe 15y ago
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.
- vessenes 15y ago
  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.

paxswill 15y ago

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.

Goladus 15y ago

> 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/Grover%27s_algorithm http://en.wikipedia.org/wiki/Quantum_computer http://en.wikipedia.org/wiki/Quantum_computer

gwern 15y ago
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.
- jessedhillon 15y ago
  Inverting a function in O(N^0.5) is useless?
  - gwern 15y ago
    Double the hash length (use SHA-512 rather than SHA-256) and you're done, no?

hugh3 15y ago

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.

pornel 15y ago

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.