Bitcoin Forum
December 01, 2022, 02:31:32 PM
 News: Latest Bitcoin Core release: 23.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Proposal for eventual hash replacement  (Read 1326 times)
Shevek (OP)
Sr. Member

Offline

Activity: 252
Merit: 250

 June 17, 2011, 03:35:34 PM

It is well known that Achilles' heel of bitcoin is the hash function: sooner or later it will be successful attacked and someone will got decisive advantage on mining because of (partially) feasible inverse mapping: hash -> block header.

I know, it is much more critical the scenario where elliptic curve (EC) fails, but EC is somehow safe. The insecurity of EC does not depend on smart cryptanalysis, but in advances on mathematics and/or quantum computing.

Indeed, Satoshi recognize this fact and proposed transition to eventual SHA3 in the future. In the linked post, Satoshi mentions the possibility that the breakdown comes suddenly.

So I propose an ordered transition to a new hash scheme for block validation in about 4~5 years. I have a concrete proposal about this new scheme, that relays its strength on the elliptic curve mathematics. Let's see it.

First, we must have a traditional non trivial hash function, that yields 256 bit output. Let's take SHA256. So, the process is:

2) h1 = SHA256(h0); actually, h1 is the output to be compared with the target in order to validate the block.
3) m = h1 mod n, where n is the prime order of the curve.
4) Now an EC product is performed: R = m·Q, where Q is the fixed point in the curve.
5) r = Rx*p + Ry, where (Rx,Ry) are the coordinates of point R and p is the prime generator of the field
6) h2 = SHA256(r)
7) h3 = h2 XOR h0. The process outputs h3 as the 256-bit hash to be compared with the difficulty-tuned 256-bit target.

The strength of the process lies on the impossibility of back-mapping R -> m, in the same manner the strength of an EC-signed transaction does. It really does not matter whether SHA256 is broken or not, because the security is trusted to EC.

The counterpart is the computation overhead: an EC-product could cost roughly 1000 times more than a hash computation. But... in the context of mining, does it really matter? The system should take care of this hashing change, thus the difficulty level should be decreased accordingly. The miners will work as hardly as before.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
There are several different types of Bitcoin clients. The most secure are full nodes like Bitcoin Core, which will follow the rules of the network no matter what miners do. Even if every miner decided to create 1000 bitcoins per block, full nodes would stick to the rules and reject those blocks.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
BitterTea
Sr. Member

Offline

Activity: 294
Merit: 250

 June 17, 2011, 03:52:16 PM

It is well known that Achilles' heel of bitcoin is the hash function: sooner or later it will be successful attacked and someone will got decisive advantage on mining because of (partially) feasible inverse mapping: hash -> block header.

Really? I don't think so.

Let's say an attack is found. It's only beneficial as long as it remains a secret. Once it is out in the wild, everyone uses it and the difficulty essentially just increases by whatever factor.
Shevek (OP)
Sr. Member

Offline

Activity: 252
Merit: 250

 June 17, 2011, 04:05:01 PM

It is well known that Achilles' heel of bitcoin is the hash function: sooner or later it will be successful attacked and someone will got decisive advantage on mining because of (partially) feasible inverse mapping: hash -> block header.

Really? I don't think so.

Let's say an attack is found. It's only beneficial as long as it remains a secret.

That's why the hash change should be done not too late, regardless the actual hashing breakdown state-of-art.

Once it is out in the wild, everyone uses it and the difficulty essentially just increases by whatever factor.

I come back to Satoshi's comment. Changing the hash function in the future looks mandatory.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
joan
Newbie

Offline

Activity: 56
Merit: 0

 June 17, 2011, 05:57:43 PM

I come back to Satoshi's comment. Changing the hash function in the future looks mandatory.

I'm sorry but, from his comment:
- we probably don't need to worry before several decades.
- we will have technical solutions to circumvent the problem.

Hardly the Achilles' heel.
(Check the wiki page on Weaknesses, it's listed there and you can see it's definitely not a top concern).
Energy better be used to tackle other shortcomings.
Luke-Jr
Legendary

Offline

Activity: 2576
Merit: 1119

 June 17, 2011, 06:04:45 PM

ECDSA will break with quantum computing. SHA won't. I'd think ECDSA is the bigger risk.

gmaxwell
Moderator
Legendary

Offline

Activity: 3822
Merit: 7210

 June 17, 2011, 06:10:42 PM

I know, it is much more critical the scenario where elliptic curve (EC) fails, but EC is somehow safe. The insecurity of EC does not depend on smart cryptanalysis, but in advances on mathematics and/or quantum computing.

It's also worth noting that EC based hashes were rejected as part of SHA3 (e.g. ECOH).

Shevek (OP)
Sr. Member

Offline

Activity: 252
Merit: 250

 June 17, 2011, 07:17:30 PM

I know, it is much more critical the scenario where elliptic curve (EC) fails, but EC is somehow safe. The insecurity of EC does not depend on smart cryptanalysis, but in advances on mathematics and/or quantum computing.

Uhmm... yes, may be.

I mean "advance in mathematics" the kind of things that are shown with Theorems (see the capital...), such as the factorization of composite numbers. The kind of mathematics that are used in hash breaking are statistics and sometimes theorems (with no capital).

I think a qualitative difference still stands.

It's also worth noting that EC based hashes were rejected as part of SHA3 (e.g. ECOH).

I guess because of the high consumption of computing resources (anyway, citation is needed, I agree).

I come back to Satoshi's comment. Changing the hash function in the future looks mandatory.

I'm sorry but, from his comment:
- we probably don't need to worry before several decades.

Optimistic prediction. May be true or not. Better to think the worst case.

- we will have technical solutions to circumvent the problem.

I want to contribute to these solutions.

Hardly the Achilles' heel.
(Check the wiki page on Weaknesses, it's listed there and you can see it's definitely not a top concern).
Energy better be used to tackle other shortcomings.

I don't agree this is not a big concern.

ECDSA will break with quantum computing. SHA won't. I'd think ECDSA is the bigger risk.

Quantum computing is far to be technically functional. Similar situation as nuclear fussion: the theory and the technological environment is ready since decades, but the definitive solution is still far away.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
ByteCoin
Sr. Member

Offline

Activity: 416
Merit: 277

 June 18, 2011, 12:39:47 AM

It's also worth noting that EC based hashes were rejected as part of SHA3 (e.g. ECOH).

I guess because of the high consumption of computing resources (anyway, citation is needed, I agree).

ECOH was rejected due to a second preimage attack

Michael A. Halcrow, Niels Ferguson - A Second Pre-image Attack Against Elliptic Curve Only Hash ({ECOH})

I haven't read it in detail, but I believe that they tried to design it so that a birthday paradox attack would fail but the measures they took proved to be ineffective.

ByteCoin
Shevek (OP)
Sr. Member

Offline

Activity: 252
Merit: 250

 June 18, 2011, 08:51:26 AM

It's also worth noting that EC based hashes were rejected as part of SHA3 (e.g. ECOH).

I guess because of the high consumption of computing resources (anyway, citation is needed, I agree).

ECOH was rejected due to a second preimage attack

Michael A. Halcrow, Niels Ferguson - A Second Pre-image Attack Against Elliptic Curve Only Hash ({ECOH})

I see. Thanks for the tip.

When SHA3 started, I was thinking around algorithm based on EC. But I finally I gave up. The problem with EC-hashing is the message splitting in blocks. If the message is one-block only, the EC is unfeasible. But if not, you must merge the different blocks some way. And EC has a "wonderful" property:

A=a·Q, B=b·Q; (A+B)=(a+b)·Q

So, it is not easy to merge the resulting EC-products in some non trivial way. Finally, the strength of the algorithm lies on the merging mechanism, not in EC itself.

As far as I read, this attack points to this fact.

My proposal targets an eventual inverse mapping (even if partial) weakness of SHA256, so EC is done almost at end, with only one block, result of previous hash. BTW, tt is possible to redefine h0 and h1 to discourage searching of collisions.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
 Pages: [1]