Elliptic curve only hash

Four ECOH algorithms were proposed, ECOH-224, ECOH-256, ECOH-384 and ECOH-512. The number represents the size of the message digest. They differ in the length of parameters, block size and in the used elliptic curve. The first two uses the elliptic curve B-283: ${\displaystyle X^{283}+X^{12}+X^{7}+X^{5}+1}$, with parameters (128, 64, 64). ECOH-384 uses the curve B-409: ${\displaystyle X^{409}+X^{87}+1}$, with parameters (192, 64, 64). ECOH-512 uses the curve B-571: ${\displaystyle X^{571}+X^{10}+X^{5}+X^{2}+1}$, with parameters (256, 128, 128). It can hash messages of bit length up to ${\displaystyle 2^{128}}$.

One way of finding collisions or second pre-images is solving Semaev Summation Polynomials. For a given elliptic curve E, there exists polynomials ${\displaystyle f_{n}}$ that are symmetric in ${\displaystyle n}$ variables and that vanish exactly when evaluated at abscissae of points whose sum is 0 in ${\displaystyle E}$. So far, an efficient algorithm to solve this problem does not exist and it is assumed to be hard (but not proven to be NP-hard).

More formally: Let ${\displaystyle \mathbf {F} }$ be a finite field, ${\displaystyle E}$ be an elliptic curve with Weierstrass equation having coefficients in ${\displaystyle \mathbf {F} }$ and ${\displaystyle O}$ be the point of infinity. It is known that there exists a multivariable polynomial ${\displaystyle f_{n}(X_{1},\ldots ,X_{N})}$ if and only if there exist < ${\displaystyle y_{1},\ldots ,y_{n}}$ such that ${\displaystyle (x_{1},y_{1})+\ldots +(x_{n},y_{n})=O}$. This polynomial has degree ${\displaystyle 2^{n-2}}$ in each variable. The problem is to find this polynomial.

The problem of finding collisions in ECOH is similar to the subset sum problem. Solving a subset sum problem is almost as hard as the discrete logarithm problem. It is generally assumed that this is not doable in polynomial time. However a significantly loose heuristic must be assumed, more specifically, one of the involved parameters in the computation is not necessarily random but has a particular structure. If one adopts this loose heuristic, then finding an internal ECOH collision may be viewed as an instance of the subset sum problem.

A second pre-image attack exists in the form of generalized birthday attack.

Description of the attack: This is a Wagner’s Generalized Birthday Attack. It requires 2¹⁴³ time for ECOH-224 and ECOH-256, 2²⁰⁶ time for ECOH-384, and 2²⁸⁷ time for ECOH-512. The attack sets the checksum block to a fixed value and uses a collision search on the elliptic curve points. For this attack we have a message M and try to find a M' that hashes to the same message. We first split the message length into six blocks. So ${\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$. Let K be a natural number. We choose K different numbers for ${\displaystyle (M_{0},M_{1})}$ and define ${\displaystyle M_{2}}$ by ${\displaystyle M_{2}:=M_{0}+M_{1}}$. We compute the K corresponding elliptic curve points ${\displaystyle P(M_{0},0)+P(M_{1},1)+P(M_{2},2)}$ and store them in a list. We then choose K different random values for ${\displaystyle (M_{3},M_{4})}$, define ${\displaystyle M_{5}:=M_{3}+M_{4}}$, we compute ${\displaystyle Q-X_{1}-X_{2}-P(M_{3},3)-P(M_{4},4)-P(M_{5},5)}$, and store them in a second list. Note that the target Q is known. ${\displaystyle X_{1}}$ only depends on the length of the message which we have fixed. ${\displaystyle X_{2}}$ depends on the length and the XOR of all message blocks, but we choose the message blocks such that this is always zero. Thus, ${\displaystyle X_{2}}$ is fixed for all our tries.

If K is larger than the square root of the number of points on the elliptic curve then we expect one collision between the two lists. This gives us a message ${\displaystyle (M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})}$ with: ${\displaystyle Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}}$ This means that this message leads to the target value Q and thus to a second preimage, which was the question. The workload we have to do here is two times K partial hash computations. For more info, see "A Second Pre-image Attack Against Elliptic Curve Only Hash (ECOH)".

Actual parameters:

• ECOH-224 and ECOH-256 use the elliptic curve B-283 with approximately ${\displaystyle 2^{283}}$ points on the curve. We choose ${\displaystyle K=2^{142}}$ and get an attack with complexity ${\displaystyle 2^{143}}$.
• ECOH-384 uses the elliptic curve B-409 with approximately ${\displaystyle 2^{409}}$ points on the curve. Choosing ${\displaystyle K=2^{205}}$ gives an attack with complexity ${\displaystyle 2^{206}.}$
• ECOH-512 uses the elliptic curve B-571 with approximately ${\displaystyle 2^{571}}$ points on the curve. Choosing ${\displaystyle K=2^{286}}$ gives an attack with complexity ${\displaystyle 2^{287}.}$