Elliptic curve only hash
Encyclopedia
The elliptic curve only hash (ECOH) algorithm was submitted as a candidate for SHA-3 in the NIST hash function competition
. However, it was rejected in the beginning of the competition since a second pre-image attack
was found.
The ECOH is based on the MuHASH hash algorithm, that has not yet been successfully attacked. However, MuHASH is too inefficient for practical use and changes had to be made. The main difference is that where MuHASH applies a random oracle
, ECOH applies a padding
function. Assuming random oracles, finding a collision
in MuHASH implies solving the discrete logarithm problem. MuHASH is thus a provably secure hash
, i.e. we know that finding a collision is at least as hard
as some hard known mathematical problem.
ECOH does not use random oracles and its security is not strictly directly related to the discrete logarithm problem, yet it is still based on mathematical functions. ECOH is related to the Semaev's problem of finding low degree solutions to the summation polynomial equations over binary field, called the Summation Polynomial Problem. An efficient algorithm to solve this problem has not been given so far. Although the problem was not proven to be NP-hard
, it is assumed that such an algorithm does not exist. Under certain assumptions, finding a collision in ECOH may be also viewed as an instance of the subset sum problem. Besides solving the Summation Polynomial Problem, there exists another way how to find second pre-images and thus collisions, Wagner's generalized birthday attack.
ECOH is a nice example of hash function that is based on mathematical functions (with the provable security
approach) rather than on classical "ad-hoc" mixing of bits to obtain the hash.
, ECOH divides the message 
into 
blocks 
. If the last block is incomplete, it is padded with single 1 and then appropriate number of 0. Let furthermore 
be a function that maps a message block and an integer to an elliptic curve point. Then using the mapping 
, each block is transformed to an elliptic curve
point
, and these points are added together with two more points. One additional point 
contains the padding and depends only on the message length. The second additional point 
depends on the message length and the XOR of all message blocks. The result is truncated to get the hash 
.
The two extra points are computed by
and 
. 
adds all the elliptic curve points and the two extra points together. Finally, the result is passed through an output transformation function f to get the hash result 
. To read more about this algorithm, see "ECOH: the Elliptic Curve Only Hash".
, with parameters (128, 64, 64). ECOH-384 uses the curve B-409: 
, with parameters (192, 64, 64). ECOH-512 uses the curve B-571: 
, with parameters (256, 128, 128). It can hash messages of bit length up to 
.
to a known and hard mathematical problem (the subset sum problem). It means that if one could find collisions, one would be able to solve the underlying mathematical problem which is assumed to be hard and unsolvable in polynomial time. Functions with these properties are known provably secure
and are quite unique among the rest of hash functions. Nevertheless second pre-image (and thus a collision) was later found because the assumptions given in the proof were too strong.
that are symmetric in 
variables and that vanish exactly when evaluated at abscissae of points whose sum is 0 in 
. So far, an efficient algorithm to solve this problem does not exist and it assumed assumed to be hard (but not proven to be NP-hard
).
More formally: Let
be a finite field, 
be an elliptic curve with Weierstrass equation
having coefficients in
and 
be the point of infinity. It is known that there exists a multivariable polynomial 
if and only if there exist < 
such that 
. This polynomial has degree 
in each variable. The problem is to find this polynomial.
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.
. It requires 2143 time for ECOH-224 and ECOH-256, 2206 time for ECOH-384, and 2287 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
. Let K be a natural number. We choose K different numbers for 
and define 
by 
. We compute the K corresponding elliptic curve points 
and store them in a list. We then choose K different random values for 
, define 
, we compute 
, and store them in a second list. Note that the target Q is known. 
only depends on the length of the message which we have fixed. 
depends on the length and the XOR of all message blocks, but we choose the message blocks such that this is always zero. Thus, 
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
with:
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:
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
. However, it was rejected in the beginning of the competition since a second pre-image attack
Preimage attack
In cryptography, the preimage attack is a classification of attacks on hash functions for finding a message that has a specific hash value.There are two types of preimage attacks:...
was found.
The ECOH is based on the MuHASH hash algorithm, that has not yet been successfully attacked. However, MuHASH is too inefficient for practical use and changes had to be made. The main difference is that where MuHASH applies a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
, ECOH applies a padding
Padding (cryptography)
-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
function. Assuming random oracles, finding a collision
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
in MuHASH implies solving the discrete logarithm problem. MuHASH is thus a provably secure hash
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
, i.e. we know that finding a collision is at least as hard
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
as some hard known mathematical problem.
ECOH does not use random oracles and its security is not strictly directly related to the discrete logarithm problem, yet it is still based on mathematical functions. ECOH is related to the Semaev's problem of finding low degree solutions to the summation polynomial equations over binary field, called the Summation Polynomial Problem. An efficient algorithm to solve this problem has not been given so far. Although the problem was not proven to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, it is assumed that such an algorithm does not exist. Under certain assumptions, finding a collision in ECOH may be also viewed as an instance of the subset sum problem. Besides solving the Summation Polynomial Problem, there exists another way how to find second pre-images and thus collisions, Wagner's generalized birthday attack.
ECOH is a nice example of hash function that is based on mathematical functions (with the provable security
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
approach) rather than on classical "ad-hoc" mixing of bits to obtain the hash.
The algorithm
Given, ECOH divides the message into blocks . If the last block is incomplete, it is padded with single 1 and then appropriate number of 0. Let furthermore be a function that maps a message block and an integer to an elliptic curve point. Then using the mapping , each block is transformed to an elliptic curveElliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
point
, and these points are added together with two more points. One additional point contains the padding and depends only on the message length. The second additional point depends on the message length and the XOR of all message blocks. The result is truncated to get the hash .The two extra points are computed by
and . adds all the elliptic curve points and the two extra points together. Finally, the result is passed through an output transformation function f to get the hash result . To read more about this algorithm, see "ECOH: the Elliptic Curve Only Hash".Examples
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:, with parameters (128, 64, 64). ECOH-384 uses the curve B-409: , with parameters (192, 64, 64). ECOH-512 uses the curve B-571: , with parameters (256, 128, 128). It can hash messages of bit length up to .Properties
- Incrementality: ECOH of a message can be updated quickly, given a small change in the message and an intermediate value in ECOH computation.
- Parallelizability: This means the computation of the
can be done on parallel systems. - Speed: The ECOH algorithm is about thousand times slower than SHA-1. However, given the developments in desktop hardware towards parallelizationParallel computingParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
and carryless multiplicationCLMUL instruction setCarry-less Multiplication is an extension to the x86 instruction set used by microprocessors from Intel and AMD which was proposed by Intel in March 2008 and made available in the Intel Westmere processors announced in early 2010. The purpose is to improve the speed of applications doing block...
, ECOH may in a few years be as fast as SHA-1 for long messages. For short messages, ECOH is relatively slow, unless extensive tables are used.
Security of ECOH
The ECOH hash functions are based on concrete mathematical functions. They were designed such that the problem of finding collisions should be reduciblePolynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
to a known and hard mathematical problem (the subset sum problem). It means that if one could find collisions, one would be able to solve the underlying mathematical problem which is assumed to be hard and unsolvable in polynomial time. Functions with these properties are known provably secure
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
and are quite unique among the rest of hash functions. Nevertheless second pre-image (and thus a collision) was later found because the assumptions given in the proof were too strong.
Semaev Summation Polynomial
One way of finding collisions or second pre-images is solving Semaev Summation Polynomials. For a given elliptic curve E, there exists polynomials that are symmetric in variables and that vanish exactly when evaluated at abscissae of points whose sum is 0 in . So far, an efficient algorithm to solve this problem does not exist and it assumed assumed to be hard (but not proven to be NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
).
More formally: Let
be a finite field, be an elliptic curve with Weierstrass equationWeierstrass's elliptic functions
In mathematics, Weierstrass's elliptic functions are elliptic functions that take a particularly simple form; they are named for Karl Weierstrass...
having coefficients in
and be the point of infinity. It is known that there exists a multivariable polynomial if and only if there exist < such that . This polynomial has degree in each variable. The problem is to find this polynomial.Provable security discussion
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 logarithmDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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.
Second pre-image attack
Description of the attack: This is a Wagner’s Generalized Birthday AttackBirthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
. It requires 2143 time for ECOH-224 and ECOH-256, 2206 time for ECOH-384, and 2287 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
. Let K be a natural number. We choose K different numbers for and define by . We compute the K corresponding elliptic curve points and store them in a list. We then choose K different random values for , define , we compute , and store them in a second list. Note that the target Q is known. only depends on the length of the message which we have fixed. depends on the length and the XOR of all message blocks, but we choose the message blocks such that this is always zero. Thus, 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
Collision
A collision is an isolated event which two or more moving bodies exert forces on each other for a relatively short time.Although the most common colloquial use of the word "collision" refers to accidents in which two or more objects collide, the scientific use of the word "collision" implies...
between the two lists. This gives us a message
with: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
points on the curve. We choose 
and get an attack with complexity 
. - ECOH-384 uses the elliptic curve B-409 with approximately
points on the curve. Choosing 
gives an attack with complexity 
- ECOH-512 uses the elliptic curve B-571 with approximately
points on the curve. Choosing 
gives an attack with complexity 