Topic: Proposal for eventual hash replacement (Read 1353 times)

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.

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

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.


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


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


I want to contribute to these solutions.


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


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.

Cryptanalysis _is_ advances on mathematics.

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

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

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.

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


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

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.

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.