Bitcoin Forum
October 23, 2017, 05:53:15 PM
 News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Proposal for eventual hash replacement  (Read 1225 times)
Shevek
Sr. Member

Offline

Activity: 252

 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:

1) h0 = SHA256(block header)
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
1508781195
Hero Member

Offline

Posts: 1508781195

Ignore
 1508781195

1508781195
 Report to moderator
1508781195
Hero Member

Offline

Posts: 1508781195

Ignore
 1508781195

1508781195
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
BitterTea
Sr. Member

Offline

Activity: 294

 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
Sr. Member

Offline

Activity: 252

 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
Jr. Member

Offline

Activity: 56

 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: 2240

 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: 2324

 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.

Cryptanalysis _is_ advances on mathematics.

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

Bitcoin will not be compromised
Shevek
Sr. Member

Offline

Activity: 252

 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.

Cryptanalysis _is_ advances on mathematics.

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

 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
Sr. Member

Offline

Activity: 252

 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]
 « previous topic next topic »