"All cryptography is breakable" criticism

[DeathAndTaxes]

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.

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.

[Etlase2]

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

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

[MoonShadow]

I think $5 wrench still defeats one time pad.

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.

[MoonShadow]

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

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

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.

[Etlase2]

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.

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.

[MoonShadow]

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.

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.

[Gavin Andresen]

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.

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

[MoonShadow]

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.

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.

[runeks]

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.

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.

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.

[FactoredPrimes]

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 

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.

[anu]

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.

[bustaballs]

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?

[JoelKatz]

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.

[anu]

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

[JoelKatz]

Does anyone know why addresses are 160 Bit, and not 256?

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

What would happen if anyone used a new private key for a transaction that does not correspond to an already published public key?

Unless someone specifically thought to check, nobody would know.

[MoonShadow]

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.

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.

[MoonShadow]

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.

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.

What would happen if anyone used a new private key for a transaction that does not correspond to an already published public key?

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.

[kjj]

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.

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.

What would happen if anyone used a new private key for a transaction that does not correspond to an already published public key?

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.

[niko]

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?

[Etlase2]

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.