Topic: If ECDSA is ever cracked/exploited/quantum computed ? (Read 3739 times)

Agree with this guy, I'll render everything we know regarding digital security useless.

I'll be honest if people are able to figure out how to crack today's asymmetric crypto (elliptic curve, discrete log, or otherwise), the least of your issues will be the price of BTC.  You'll probably be more concerned with your online traffic being captured and pretty much every login to online banking systems or other exploitable secret information being exposed.

You're right in pointing out that it probably would destroy BTC, but that wouldn't seem so bad compared to all the other issues

If I recall correctly some early transactions were sent directly to public keys instead of sent to the public key hash therefore the public key is available in the block chain for some early transactions.

Maybe, also the response from the network could be a hardfork ...
making better cryptography should consider also people in long term run not just making more space in block to accept more transactions.

This is not true.  Only the hashes of his public keys are in plain view, so there's nothing to attack.  Even if ECDS were completely cracked, nobody could do anything with the hashes of these keys.

You are perfectly right, and I consider it a design error (one of many) in bitcoin not to have enforced this in the protocol.  In the same way that an UTXO can only be spent once, an address could be used only once.  This would have simplified VASTLY several aspects of the protocol (there would have been no need for a transaction hash: given that an address only occurs once in an output, the address itself is sufficient to indicate the transaction ; this would have avoided transaction malleability, it would have divided the amount of data in a transaction by about half, ....).

That would crack up the world...  Dare not to even think about it!

Very true.  In fact all those millions of dollars can be seen as a "test" of the security of the ECDSA since they are just sitting there waiting for someone to crack ECDSA and take them.

To answer the question about address reuse above:

Reusing addresses -> very secure but damaging to the privacy of the Bitcoin system and the fungible property of Bitcoins.

Using addresses once -> even more secure and enhances the privacy of the Bitcoin system and preserves the fungible property of Bitcoins.

Address reuse is a minimal security concern but security is not the only issue.

None of Satoshi's mined coin transactions used P2SH. Therefore all of his public keys for about 1 million coins are in plain view. They have not been cracked and generating a private key from its public key is theory.

Why is it that most exchanges, pools, and most of the addresses on the BTC richlist all reuse the same address over and over again.

They sent multiple deposits to the address and then made multiple transactions from the address

I like reusing addresses because I know that I will be able to retrieve the BTC because I got proof that the transaction will go through because it went thru once in the past.

Imagine sending all your life savings to a BTC paper wallet and in 10 years trying to spend it and there is some "error".

I've been trying to sort this out myself. I posted a question on reddit (https://www.reddit.com/r/Bitcoin/comments/677y1b/how_to_steal_coins_if_some_oneway_function_is/) that summarize what I've figured out. I haven't seen any comments on it, so I'm not sure if there's anything incorrect in it.

Reposting here:

I'm trying to grasp the different implications if any one-way function of the address creation process is flawed. I've come up with two different types of potential flaws

• The output space for the function is smaller than anticipated so brute-force becomes viable
• One can craft an input that produce a certain output.

Both of these imaginary flaws can be found in either the specification or in an implementation. I only focus on specification flaws here, but I do think the same analysis holds for implementation flaws as well. The tables list my understanding of what needs to be done in order to steal someone's coins, given that only the public key hash or script hash is known. Are these tables correct? Is there any important information to add?

*Version 0 addresses*

Function	Small output space	Can craft input
Random number generator	Doomed!	N/A
Public key derivation	Doomed!	Must pre-image attack RIPEMD(SHA())
SHA256	Doomed!	Must pre-image attack RIPEMD AND brute force public key derivation
RIPEMD160	Doomed!	Must brute force SHA(pubkeyderivation())

*Pay-to-script-hash addresses*

Function	Small output space	Can craft input
SHA256	Doomed!	If I know the script [1], I can craft a second script with same SHA256 value. If script is not known, I need to pre-image attack RIPEMD160
RIPEMD160	Doomed!	Must pre-image attack SHA256

[1] is very likely. For example a party in a multisig address knows the script and can rip off the other parties.

We are doomed if any of the functions are brute-forceable. That means that the more fancy one-way functions we use, the more vulnerable we are.

Sources:

* https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
* https://bitcointalk.org/index.php?topic=141848.0
* https://bitcoin.stackexchange.com/questions/9202/why-does-bitcoin-use-two-hash-functions-sha-256-and-ripemd-160-to-create-an-ad

As long as you use each of the default receiving addresses only once then you are not reusing the addresses.  I am not sure how that can be made more clear.  If you send, or have people send, Bitcoins to the same address more than once then you are reusing the address.

Also, if you spend the Bitcoins from an address, then send Bitcoins to that same address again, then spend them from that address again you are reusing the address.

Ideally there should only be one single transaction to send Bitcoins to the address and then one single transaction to spend the Bitcoins from the address and then the address should never be used again.

guys, what do you think
how safe is to keep some BTC in the coldwallet for 20 years with no attention to crypto world?

I can't understand if my addresses are re-used. Example:

I create a wallet with Electrum and it generates by default some receiving addresses (A, B, C...)
then if I receive one incoming transaction in A and another in B, I have re-used my addresses or both are safe?

If ECDSA is cracked, there are more fun things to do than to steal 100 BTC !

Basically I think if ECDSA gets cracked then most likely any active addresses won't be targetted to attract attention. If people's cold storage all of a sudden gets stolen, people would start complaining and eventually a conclusion might be drawn that ECDSA is broken due to re-used addresses using public keys.

Most likely someone would target those large 50-100 BTC addresses with unspent outputs since 2010 and assume that its a lost key.

That might even be happening right now but we don't know it.

It would be stupid to hack every public key which is 50% of all the coins in existence and crash the price to $0 and get nothing.

I am not arguing that it is not harder to steal or doesn't increase privacy, which is obviously true.

But the value of Bitcoin depends on being able to transact securely. If there is a 6 month attack with independent trials, and there are 6 miners attacking, then every month some transaction will get stolen.

What would the value of Bitcoin be? Would anybody still give a dime for a Bitcoin in such scenario? What would be the use of being the "more secure" owner of a worthless coin?

I use the Ledger HW.1 which I see is not anymore on sale on the official ledger website, however it does it job good. I do this because I want to have a single address to receive the payments but will ask a new address every time now when I will want to receive money, this hardware wallet does what you say spends entire amount even when they have come from micro payments (this really result in very expensive fees for me which I am glad to pay as long as it does it job the way I like it).

What hardware wallet do you use?

Why do you do this?  Most modern hardware wallets are designed to not do this.  Why do you do this again?

That's a poor assumption given the discussion you were participating in:

---

Which is why I specified...

The fundamental assumption is that the address only gets one payment.  If you screw with the fundamental assumption and hand out an address for multiple payments then I am not sure.  I have never done that with my Trezor.  Would be an interesting experiment I guess.

Even if the user received dozens of payments to the address?  The wallet spends ALL those outputs at once?  Doesn't that result in expensive transaction fees?

Trezor (and other good HD wallets) always spend the entire amount on the address and the change goes to a new address every time as WarrEagle described in his example.  So every address generated by the wallet gets used exactly twice:  once when the BTC are sent to the address and once when they are spent.

This is a good summary !

All depends of course HOW ECDS is cracked.  While "an attacker needs 6 months" versus "an attacker has only 10 minutes" SOUNDS totally different, in matters of cryptographic security, in fact, the difference is near nothing.  In fact, some time ago, I fell myself in the trap, so I'm explaining what I got wrong, so that others don't get it wrong.

Cryptographic security is usually expressed grossly in "bit level".  If a system has a security of, say 64 bits, it grossly means that the amount of trials an attacker needs to perform, is 2^64.  A "trial" is of the same level of individual difficulty as the "normal single operation" the normal user needs to do to sign/check/encrypt/... whatever is the purpose of the system.

The ECDS system used by bitcoin has keys of 256 bits, and, because a general attack is known on this type of systems (called "Pollard rho" method), has a security which is half the key length, that is: 128 bits.  In other words, if I'm given a 256 bit public key, using Pollard rho method, I need about 2^128 trials to find the private key that goes with it.  That's in general considered not feasible for the foreseeable future, so it is considered strongly secure.

If ECDS is "cracked", it means that a new method is available that can calculate the private key in MUCH LESS than 2^128 trials.  In fact, the type of curve Satoshi used, a Koblitz curve, is known to undergo an attack that can win a few bits, but not much (at least, what is publicly known).

Seriously cracked means, for instance, that the security level goes down to 60 bits, or 50 bits or 90 bits... depending on the attack method.  As we don't know the method, we can't know what will be the "level of cracking".

Now, suppose that an attacker can do it in 6 months.  It would mean that he can crack an n-bit security in 6 months.  How much lower must the security go for him to be able to do it in 10 minutes ?  This is 26000 times shorter.  It means, something like 15 bits less security.

So the difference between "cracking in 6 months" and "cracking in 10 minutes" is 16 bits of security.  If we already came down from, say, 128 bits nominal ECDS security to, say, 70 bits (so that it can be done in 6 months, say), it is hard to say that going down to 55 bits is not going to happen soon !

So, essentially, when the "long term" ECDS protection is broken, chances are that the short term protection isn't going to help either.  There's only 16 bits of security difference between them.

As to quantum computers, sufficiently large quantum computers can crack ECDS *completely*.  It essentially means that no matter the length of the key, such a computer can crack it in a matter of milliseconds.  In fact, the only thing is that the bigger the key (the more bits in the key) the *bigger* the quantum computer needs to be, but not so much the longer it takes for it to crack the key.

That depends on the wallet you are using, and whether that 2 BTC was received as a single payment or multiple payments to the same address.

Doesn't the change from a transaction go into a separate wallet address, say you have 2 BTC in your wallet adress and you send 1 BTC to someone, doesn't the remainder...or change go into a separate address?

Thanks. Noted. I will start using a different address every time and create a new address from this hardware wallet anytime I will need to receive money. I thought hardware wallets were unhackable but I guess they offer the user just better security against malware and such and not against dedicated attacks.

Time to move all the funds to a new address as soon as I get home.

When you eventually spend some of the bitcoins that are stored in your hardware wallet, you will broadcast your public key to the entire world.  The public key will be permanently stored in the blockchain for all to see for all of time.

Any outputs that don't get spent will then be vulnerable since they are still associated with that address and therefore with that public key.

Hey Danny , very nice explanation and I understand it well until now but a question comes naturally to me because I always use the same addresses from my hardware wallet.

How would the hacker for example know my private key of an existing bitcoin address which stays connected only to my hardware wallet, is it possible for such address to be cracked from the hackers when the ECDSA is supposedly broken ? Normally it shouldn't but I am curious about this.

Unknown.  That depends on the weakness that is discovered. Since a significant weakness hasn't been discovered yet, it's impossible to know.


Possibly.

However, lets imagine for a moment that ECDSA is broken in such a way that the time to crack a private key from a public key is reduced to 6 months.

If I always use a new address for every transaction, then all of my bitcoins are protected by SHA256 and RIPEMD160.

If you have an address that you've re-used, then you might have bitcoins sitting out there on the blockchain with their public key exposed.  An attacker can spend the next 6 months working out your private key and then steal your bitcoins.

If I send a transaction, the attacker has (on average) 10 minutes to figure out the private key, craft a replacement transaction that pays the bitcoins to him, and then convince a miner to mine his transaction instead of mine.

Which is safer?  Your bitcoins sitting on the blockchain with an exposed public key allowing the attacker to continuously try to craft a transaction that takes your bitcoins until you get around to sending them to a new address?  Or my bitcoins that have a window of 10 minutes on average to try to both crack the key AND convince a miner to accept a double-spend transaction in place of the existing one?

The increase in security from using a new address for every transaction is quite small, but it is still better than re-using addresses.

Using a new address for every transaction can also increase your privacy a bit.

I don't quite understand why hiding the public key behind a hash really helps.

If ECDSA is broken, that is if a private key can be found from a public key in limited amount of time, can't we assume that the time taken to find the private key consists of independent trials?

And if so, can't any node simply keep attempting at incoming transactions, stealing one every N days? Making every transaction a gamble?

It's too hard just to manage and maintain one address that's why the majority of users are re-using the same address because we're lazy asses myself included.
I heard in the same university scientists & engineers experimenting with prototype quantum computers, they are testing new mechanisms and algos at the same time.
One of which is to figure out a way and successfully change a parameter of a program in computer A and the changes take effect even faster than the speed of light in that program installed on computer B.
Imagine the possibilities and endless applications for such technology.

I doubt that Byteball has such target, but yeah, it's an opinion.
CLAM was a coin that did a similar airdrop, based on Dogecoin addresses back then. I feel like Byteball just tried to copy a successful airdrop (and even make it better).


Many do reuse BTC addresses. Many have started with wallets like Multibit (Classic) and just imported their address into something else (Electrum), I expect many to work with few addresses to have strict control on their private keys in case of wallet failure. There are some that use vanity addresses.
All these reuse their address. If theft would start to happen, people will start crying loud!
So for now I'd say that we are still safe.


I find Cryptonote coins safer than Bitcoin clones in this matter.
But right now it's like living in Kentucky and fearing of a tsunami, even thinking on moving to Tibet. Overkill...


I don't know which products use ECDSA - I know that some digital signatures do - but yes, Bitcoin will clearly not be the only one affected..

Signing a message is the same as re-using an address, Byteball might be an attempt, not really hacking but just an attempt to test some methods?
Cracking the mechanism requires finding and properly guessing the longest-largest prime number used in encryption am I correct?
If we were to use every time one address only then we wouldn't have the issue with change outputs and blocks could as well contain more transactions.
What would be the next step to secure the internet? maybe using quantum entanglement, I'm sure by the time scientist manage to successfully build a real quantum computer they can as well solve the problem of how to sync particles in great distances from each other simultaneously any change taking effect.

I think that if ECDS is broken, we have more worries than bitcoin.  Essentially, everything which is based upon it, which is A LOT, is broken.

Bitcoin has an accidental protection of addresses that were never spend, by the fact that an address is a hash of a public key.  However, as pointed out, that protection is gone from the moment that an address is used more than once, and I consider this as a kind of design error in bitcoin to ALLOW for more than one usage of an address (in the same way that double *spending* is impossible on bitcoin, one could have made double crediting impossible - with each address, there would only have been one possible UTXO, and hence could only be spent once too).

That said, it is not too late, and people owning coins could at any moment, before ECDS is broken, decide to strictly adhere themselves to such single-spend policy, by transacting all their coins to new addresses, of which they will never reuse anything.  For that, however, they should also avoid people to credit their same addresses multiple times, and because that's not forbidden in the bitcoin protocol, that can always happen.

I don't think it would lose all of it's value but it would certainly lose most of it. Bitcoin would simply turn into a game of who can hold on to the most bitcoins without making the critical error of re-using your addresses and sacrificing your bitcoins to the vultures who are perpetually flying overhead.

That actually might sound like a fun (and dangerous) game, but you're ultimately right. Bitcoin would be compromised and wouldn't be taken seriously as a store of value if that occurred.

On Reddit today there is a huge discussion to never re-use any BTC addresses because you expose your public key. Since the pub key only has ECDSA protection unlike a BTC address which has 2 more hashes on top; its more vulnerable for theft.

However I looked up most addresses with transactions and it seems that almost 50% of the large (>100 BTC addresses) all have re-used BTC addresses.

So if ECDSA is ever cracked wouldn't it mean the end of Bitcoin ? If bitcoin goes to $0 due to this huge flaw along with most alt-coins then it doesn't seem like NOT re-using your addresses would make a difference.

Also aren't many products such as Sony Playstation also using this same type of ECDSA?