[mixedbit]

I wonder if someday we will see someone generating all the bitcoins on a laptop. How the article says, the math behind most cryptosystems were never proven to be unbreakable, it is just believed to be so, because no one managed to show otherwise.

[jabbany]

Probably both yes and no.

As of right now bitcoin depends pretty heavily on SHA256 and with hash functions being quite important cryptography primitives, there's always ongoing work on breaking them (tremendous upside to anyone who can manage to break common ones), so it's pretty feasible that eventually it will be broken. (We've already seen the fall of MD5 and SHA-1 in recent-ish years)

However, cryptocurrencies are a human system as much as they are a computing technology. If weaknesses start being discovered SHA256 or the EC signing of bitcoin, then in all likelihood they'd just fork the chain and upgrade the hash or signing mechanism.

[RL_Quine]

It’s pretty unlikely that sha2 will ever broken in a way which actually has a meaningful security impact to bitcoin, especially considering that almost every value in the system is sha2(sha2()) which nullifies a lot of attacks against hashes which need careful control of the input. Some newer tools in the system use a single hash (it’s unclear why a double one was used in the first place), but all the same it remains highly unlikely.

Complete breaks of ECDSA are likely to be devastating as many keys in the data are re-used hundreds of thousands of times, but a weakening of it can be mitigated by moving to a new signature standard, which isn’t even consensus incompatible due to the upgradability built into the script language.

[kmeisthax]

Consensus compatibility is nice, but Bitcoin has a unique problem: those old signatures own coins. Phasing out a signature algorithm means confiscating the coins in question, as the rightful owner will no longer be able to spend them anymore. Leaving them open would just let private actors break wallets to confiscate the coins themselves, with the added bonus that burnt or lost coins could be recovered, effectively increasing the supply of coins on the market. And Bitcoin has a lot of early-adopter money supply locked up behind dead hard drives - it would crash the market.

Other systems that use ECDSA don't have this problem because they rely on CAs and central authorities. For things like, say, the TLS PKI; if you miss the flag date to change ciphers you aren't forever locked out of your domain. Your site just goes down until you bother to upgrade your servers and rotate keys.

Is there any known/stated policy as to how to handle phasing out a signature algorithm in Bitcoin?

[jabbany]

No idea, but I could imagine something where you have a period of time on the chain where both signature types are allowed, and people can just migrate their coins by transferring from the old wallet to one based on the new signature system. Then after a certain cutoff, the chain can phase out the old signature system entirely.

Of course this only works if the old system is just "weak" rather than "broken". There is no way to recover if the signature system is completely broken, but if ECDSA is broken then we have more to worry about than just Bitcoins.

[Spooky23]

Not only that, but bazillions of coins are dead. My 4 bitcoins that were lost to a hard drive failure a decade ago are gone, and “reanimating” them wouldn’t even be theft.

[DoctorOetker]

would you mind pointing at those coins, perhaps even add relevant public key information if still known?

[kevincox]

> especially considering that almost every value in the system is sha2(sha2())

Why does this give a meaningful improvement? Is this just security through obscurity? Presumably if this had significant benifits sha2 would have been defined this way to start with right? Or is it just that other users will be broken before this "double strong" version so that you have more warning? But isn't shaw defined as a number of rounds anyways?

[RL_Quine]

It’s a historical thing people used to do for length extension attacks, but it’s irrelevant where it exists in bitcoin, for example as branches in a merkle tree where every input is of a fixed length (another hash). For Bitcoin a good portion of all the CPU time involved in verifying is just doing hashes of hashes, so it just is what it is.

It has the side effect of making some attacks where you need control of certain bytes of the input (see the md5 commission tool) harder because you’ve now got to find an exploit which makes it through both hashes.

[athrowaway3z]

'breaking' a hash can mean many different things. Among many others, two types of attacks are:

- a specific prefix/suffix data can be created to force a collision.

- A message of exactly N bytes can quickly create a collision.

Both attacks would be reported as a hash being broken. But its assumed to be unlikely that a well designed hash would have a flaw that breaks the hash in both ways. Keyword being assumed. But with good reason.

AFAIK sha has only been broken by a variable length suffix attack.

With sha2(sha2()) it would have to be broken both ways.

[copperx]

I'd love a mathematical explanation because my intuition also says it cannot be more secure.

[jabbany]

My guess is the grandparent refers to this kind of attack: https://en.wikipedia.org/wiki/Length_extension_attack

Basically, many cryptographic hashes support fixed-length hashes of variable message lengths by breaking the message into blocks, chaining their hashes* and taking the final hash.

The weakness here is if you know the length of a prefix and its hash, you can generate more valid hashes of messages that contain the unknown prefix but with custom suffixes. This is relevant if you use the hash for authentication (i.e. MAC) as it allows producing certain types of custom messages that would also validate.

However, this has largely been a non-issue for a long time now as it takes very little tweaking of the protocol (stuff being authenticated) to make adding suffixes useless. Double hashing is one such mitigation, because the outer hash is now working over a fixed size input, meaning to attack it you'd need to the signed message instead of just appending to it.

*: This approach of chaining hashes of blocks is also used in other contexts that you may be familiar with ;)

[323]

Even if you don't reuse keys you will be vulnerable the moment you do the first transaction - it will be the miner who sees your public key first. Even if you mine your own transactions you will be vulnerable, because the block could be orphaned, and anyone could then see your public key.

[NicolaiS]

In case Bitcoin needed to upgrade e.g. secp256k1, then a logical/easy way to avoid this problem is with a simple commitment scheme.

[svnpenn]

> will ever broken

[SV_BubbleTime]

>a single hash (it’s unclear why a double one was used in the first place), but all the same it remains highly unlikely.

Because of one of something is good, more is always better. This is how my brother in law cooks, and it's... "flavorful" in a bad way.

[Beldin]

That's the one actual value of bitcoin / cryptocurrencies: we can be fairly sure that no one broke the used hashing algorithms (1). The valuation of these coins is such that not just any individual, but even a state actor would just go for it.

(1) to such a degree that it would allow the attacker to create new blocks at will.

Assume 1 bitcoin is $50k; break it only once a day and make over 15 million × block reward a year. I doubt many governments could resist.

[jabbany]

Not at all...

I mean if you break either the hash or the signature, then there are bigger fish to fry than just Bitcoin. You'd essentially be on your way to breaking much of the crypto used to secure significantly more valuable information -- the kind of information you measure with human lives rather than dollars.

Actually, if you (or more likely a nation state actor) did break either the hash or signature, you'd be crazy to reveal that fact on something as trivial as Bitcoin. That'd be like breaking ENIGMA and just using it to publish the German weather reports lol.

[pcthrowaway]

Interesting discussion from a few years ago in "What would you do if you discovered a sufficiently fast way to do prime factorization?" - https://www.reddit.com/r/compsci/comments/314ulw/what_would_...

[matheusmoreira]

Old reddit link for convenience: https://old.reddit.com/r/compsci/comments/314ulw/what_would_...

[ayende]

That amount of money is not even a rounding error.

And it is likely to be very obvious and public.

You will crash the market, so can't really do that multiple times.

And if you can Crack this there are better targets

[dogeprotocol]

Thats true, its a critical risk to Bitcoin, Ethereum etc. The digital signature scheme protecting Bitcoin accounts use elliptic curves which can also be broken using quantum computers.Transactions can be forged using broken accounts.

It's fairly easy to underestimate the time required to change a non quantum resistant to a quantum resistant one.

To protect Bitcoin from quantum computers, the blockchain has to be forked as early as possible, with all blocks re-signed with quantum resistant digital signature schemes. Devil is in the details though.

The Doge Protocol project will fork Bitcoin and move it to a quantum resistant hybrid scheme.

[zaroth]

This is inevitable for all coins with published public keys, which all the early coins are. So, e.g. all of Satoshi's coins. For coins where the public key is hashed, perhaps not inevitable.

Depending on how you look at it, it's either the built-in doomsday for Bitcoin, or it's a built-in multi-billion dollar bounty for exposing the existence of a quantum computer capable of cracking the private key given a Secp256k1 public key (that's the EC curve bitcoin uses).