"All cryptography is breakable" criticism

Foxpup

legendary

Activity: 4542

Merit: 3393

Vile Vixen and Miss Bitcointalk 2021-2023

Quote from: niko on October 03, 2012, 12:28:44 AM

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.

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.

Quote from: niko on October 03, 2012, 12:28:44 AM

How hard would it be technically to enable spending of "old" ECDSA coins into the network based on a different signing algorithm?

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.

anu

legendary

Activity: 1218

Merit: 1001

RepuX - Enterprise Blockchain Protocol

Quote from: niko on October 03, 2012, 12:28:44 AM

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?

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.

Etlase2

hero member

Activity: 798

Merit: 1000

Quote from: niko on October 03, 2012, 12:28:44 AM

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.

niko

hero member

Activity: 756

Merit: 501

There is more to Bitcoin than bitcoins.

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?

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: MoonShadow on October 01, 2012, 08:23:08 AM

Quote from: anu on October 01, 2012, 01:45:22 AM

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.

Quote

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.

MoonShadow

legendary

Activity: 1708

Merit: 1010

Quote from: anu on October 01, 2012, 01:45:22 AM

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.

Quote

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.

MoonShadow

legendary

Activity: 1708

Merit: 1010

Quote from: JoelKatz on October 01, 2012, 01:32:29 AM

Quote from: bustaballs on September 30, 2012, 02:09:39 PM

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.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: anu on October 01, 2012, 01:45:22 AM

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.

Quote

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.

anu

legendary

Activity: 1218

Merit: 1001

RepuX - Enterprise Blockchain Protocol

Quote from: JoelKatz on October 01, 2012, 01:32:29 AM

Quote from: bustaballs on September 30, 2012, 02:09:39 PM

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

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: bustaballs on September 30, 2012, 02:09:39 PM

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.

bustaballs

member

Activity: 115

Merit: 10

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?

anu

legendary

Activity: 1218

Merit: 1001

RepuX - Enterprise Blockchain Protocol

Quote from: FactoredPrimes on September 30, 2012, 12:22:41 AM

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.

FactoredPrimes

newbie

Activity: 14

Merit: 0

Quote from: Gabi on July 30, 2012, 10:56:24 AM

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 Cheesy

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.

runeks

legendary

Activity: 980

Merit: 1008

Quote from: DeathAndTaxes on September 29, 2012, 05:40:28 PM

Quote from: runeks on September 29, 2012, 04:58:32 PM

Quote from: caveden on July 30, 2012, 02:59:48 PM

Quote from: anu on July 30, 2012, 02:48:49 PM

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.

MoonShadow

legendary

Activity: 1708

Merit: 1010

Quote from: Gavin Andresen on September 29, 2012, 07:17:01 PM

Quote from: MoonShadow on September 29, 2012, 07:08:51 PM

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.

Gavin Andresen

legendary

Activity: 1652

Merit: 2311

Chief Scientist

Quote from: MoonShadow on September 29, 2012, 07:08:51 PM

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

legendary

Activity: 1708

Merit: 1010

Quote from: Etlase2 on September 29, 2012, 07:04:49 PM

Quote from: MoonShadow on September 29, 2012, 06:32:13 PM

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.

Etlase2

hero member

Activity: 798

Merit: 1000

Quote from: MoonShadow on September 29, 2012, 06:32:13 PM

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

legendary

Activity: 1708

Merit: 1010

Quote from: Etlase2 on September 29, 2012, 06:24:18 PM

Quote from: mrb on September 29, 2012, 05:20:45 PM

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.

MoonShadow

legendary

Activity: 1708

Merit: 1010

Quote from: FreeMoney on July 30, 2012, 08:01:28 PM

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.

Topic: "All cryptography is breakable" criticism (Read 7617 times)