Bitcoin Forum
December 05, 2016, 02:48:20 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Proposal for eventual hash replacement  (Read 1127 times)
Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
June 17, 2011, 03:35:34 PM
 #1

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.

Comments are welcome.

Proposals for improving bitcoin are like asses: everybody has one
1SheveKuPHpzpLqSvPSavik9wnC51voBa
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480949300
Hero Member
*
Offline Offline

Posts: 1480949300

View Profile Personal Message (Offline)

Ignore
1480949300
Reply with quote  #2

1480949300
Report to moderator
BitterTea
Sr. Member
****
Offline Offline

Activity: 294



View Profile
June 17, 2011, 03:52:16 PM
 #2

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 Offline

Activity: 252



View Profile
June 17, 2011, 04:05:01 PM
 #3

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 Offline

Activity: 56



View Profile
June 17, 2011, 05:57:43 PM
 #4

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
*
expert
Offline Offline

Activity: 2086



View Profile
June 17, 2011, 06:04:45 PM
 #5

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

gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2016



View Profile
June 17, 2011, 06:10:42 PM
 #6

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).


Shevek
Sr. Member
****
Offline Offline

Activity: 252



View Profile
June 17, 2011, 07:17:30 PM
 #7

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
****
expert
Offline Offline

Activity: 416


View Profile
June 18, 2011, 12:39:47 AM
 #8


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 Offline

Activity: 252



View Profile
June 18, 2011, 08:51:26 AM
 #9


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]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!