Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Killdozer on October 12, 2012, 10:36:58 PM



Title: Privkey signatures with another algo for security against future ECDSA attack
Post by: Killdozer on October 12, 2012, 10:36:58 PM
(If this has been discussed already or similar idea is implemented, please point me there.)

The chances are very small that ECDSA will be broken suddenly (perhaps not very soon, but unexpectedly). However that is possible, we never know. There are mathematical problems that were unsolvable for decades, to be finally resolved, to everybody's surprise. As I understand, for bitcoin this would mean death: no owner of any address will be able to prove that he really was the owner of the address.

Again, this is a very hypothetical scenario, but if Bitcoin is to become really widely adopted, this probably should be addressed. No single mathematical problem should be responsible for total world chaos.

So I propose a simple solution: make a widely accepted mechanism for publishing a signature based on another algorithm in the blockchain, that would prove the ownership of a certain address. That way, in the future, if the bitcoin crypto would be broken, it will be easy to prove that somebody had the private key for a certain address before the breakage.

This could for example be done like this: A user that wishes to ensure the proof of ownership of a private key, generates a new public key pair using a different algorithm than what is used in bitcoin (RSA is the logical choice). Since ECDSA and RSA are based on different mathematical concepts, chances that they both will be broken at the same time are MUCH smaller than that any one of them will be broken at all.

Using this new public key, the user encrypts a strong hash of his ECDSA private key with his RSA public key, and makes the encrypted result public in the blockchain, along with the RSA public key (or it's hash perhaps).

This way, in the future, if the ECDSA will be broken, there will still be no ready mechanism for everything to just work as it did, but the users will at least have the ability to prove that they did have their ECDSA private key at the time of making this signature public in the block chain.

If the RSA will be broken first, we'll just revise this method using some other public key algo instead, republicising signatures made with it instead.


Implementing this would not require any change in the protocol, just a general consensus on the format of these signatures. They could be made public in some way in the scripts of transactions with nominal transfer amounts. At this point no other node needs to understand these transactions, they just have to be in the public block chain history for the idea to work.

In the future, if the shit would hit the fan, a new bitcoin version would be made anyway (incompatible with the old ones), and then that version could be made to understand these transactions, but that may never happen, so for now it would be enough to just make this information stick in the block chain.

Thoughts?


Title: Re: Address signatures with another algo for added security against ECDSA breaking
Post by: SätöshiTable on October 13, 2012, 12:23:09 AM
even if you prove ownership that way,
nobody will know if the outgoing transaction was done by the owner or the thief.

when someone breaks ECDSA and bitcoin is still big enough, they will first clear all the coins


Title: Re: Address signatures with another algo for added security against ECDSA breaking
Post by: Killdozer on October 13, 2012, 06:57:06 AM
Let's say this happens when bitcoin is widely adopted everywhere, with big companies standing behind it. When the world realizes that it has been broken, they will rollback the state of the blockchain to the point of time right before the breakage. All of the transactions done before that point can relatively safely be assumed done by the real owner.

Such rollbacks have been done in other major systems, stock markets, etc., when big bugs have been found.

This is not a perfect solution for this situation, many people and companies will still loose money. (Like you say, they will try to clear all the coins everywhere and try to get out some other kind of wealth. But they won't be able to take out "everything". When the breakage will become known, all the markets/merchants/companies dealing in bitcoin will put their business on hold of course. The losses will only be what the thiefs will be able to take out before that happens.)

So why do this at all if this is not a perfect system? Because without this, every single bitcoin will become worthless, with no possibility to rollback anything. With this, it'll be just a bad day for the companies that were hit first (the effect is going to be much smaller, because the news about this is likely to spread in a day or so, and most methods of "withdrawing" other types of wealth than bitcoin take much more time to process).


Title: Re: Address signatures with another algo for added security against ECDSA breaking
Post by: CIYAM on October 13, 2012, 07:03:06 AM
Interesting coincidence that I created this thread today: https://bitcointalk.org/index.php?topic=118182.0

:)


Title: Re: Address signatures with another algo for added security against ECDSA breaking
Post by: Killdozer on October 16, 2012, 11:18:12 AM
Yeah, except your topic does not address the same thing at all :P


Title: Re: Privkey signatures with another algo for security against future ECDSA attack
Post by: DannyHamilton on October 16, 2012, 01:12:19 PM
. . . No single mathematical problem should be responsible for total world chaos . . .
Am I mistaken?  I thought that this issue was already dealt with in the original protocol?

Given a public key, wouldn't you have to break 3 separate algorithms simultaneously to determine the private key?  I thought that Bitcoin used RIPEMD-160, SHA-256, and ECDSA.

https://en.bitcoin.it/wiki/Protocol_specification#Addresses


Title: Re: Privkey signatures with another algo for security against future ECDSA attack
Post by: yaffare on October 16, 2012, 02:11:07 PM

Given a public key, wouldn't you have to break 3 separate algorithms simultaneously to determine the private key?  

If the ECDSA-public-key is not public you are right. In the other case you are wrong.

Example:
A sends 5 BTC to 1btcaddress
B sends 5 BTC to 1btcaddress
1btcaddress spends the 5 coins from A.

To spend the coins 1btcaddress must reveal the ECDSA-public-key.

If you beat ECDSA you could now take the 5 BTC which 1btcaddress still has. These are the coins send by B.

If you beat ECDSA there are enough ECDSA-public-keys out there to make you rich in BTC.


Title: Re: Privkey signatures with another algo for security against future ECDSA attack
Post by: DannyHamilton on October 16, 2012, 03:20:33 PM

Given a public key, wouldn't you have to break 3 separate algorithms simultaneously to determine the private key?  

If the ECDSA-public-key is not public you are right. In the other case you are wrong.
. . .
To spend the coins 1btcaddress must reveal the ECDSA-public-key.
. . .
If you beat ECDSA there are enough ECDSA-public-keys out there to make you rich in BTC.
And this is one of the reasons that we are encouraged to use a new address for every transaction?


Title: Re: Privkey signatures with another algo for security against future ECDSA attack
Post by: Killdozer on October 17, 2012, 11:35:09 AM
Quote
And this is one of the reasons that we are encouraged to use a new address for every transaction?

Since the attacker would need the public key, using each address only once would help against that it seems, but in the current state of Bitcoin it is certainly not very easy to use each address only once in every situation. It is especially difficult for services which have their addresses public, donation addresses, green address features of some companies, etc.