m
Pedersen hash weaknesses
Pedersen hash has been popularized by Zcash team as ZK-friendly hash function suitable for Merkle trees. Its simplest version operates on an elliptic curve with two fixed generators G and H with unknown discrete log relation. Then to hash two integers (a,b) one computes
P = aG + bH
and takes some compressed version of P (e.g. x-coordinate) as a result. There are several extensions of this construction to longer messages using multiple generators [1] or just by a recursive Merkle-Damgard calling. In contrast to regular hash functions like Keccak there is a formal security proof for collision resistance as any collision implies a discrete logarithm relation between G and H.
There are several problems with this construction. First, from the implementation perspective it is quite complicated. To hash messages within some field F, one has to define an elliptic curve with the order bigger than |F| but the coordinates being in F. For zero-knowledge proofs one has to convert elliptic curve equations into degree-2 constraints, and also work with the bit representation of (a,b) in order to reduce the scalar multiplication to point addition and doubling. Altogether this makes quite a non-trivial circuit, but it is still doable.
From the cryptographic point of view the situation is worse. Pedersen hash has several properties quite unexpected from a cryptographic hash function. First, it is homomorphic: H(ab,cd) = H(a,b) + H(c,d). This property alone is not problematic and is even common for cryptographic commitments and many other primitives. However, it implies that the function is vulnerable to length-extension attacks: given H(A) it is easy to compute H(A,B) for some integer tuples A and B. This property, being present in SHA-0/1/2 and forbidden in SHA-3, caused many attacks like [2]. It makes a natural MAC construction MAC(M) = H(K || M) insecure, and rules out a common domain separation method of creating many functions from one as H_i(x) = H(i||x).
Finally, the preimage security of Pedersen is weaker than expected. For an n-bit elliptic curve it is not 2^(n/2) as one would hope for. If the hashed message is l-bit long for l<n the preimage search cost is not min(2^l,2^(n/2)) but only 2^(l/2). Indeed, let a and b be l/2 -bit long. Then define f(x) = xG and g(y) = P-yH. Thus the preimage for P is just a collision between f and g, which can be found memoryless in 2^(l/2) steps. Last but not least, the multi-target preimage security is even lower: to find 2^k preimages for l-bit messages, one performs only 2^(l/2+k/2) hash function calls thus making the amortized preimage search cost as low as 2^(l/2-k/2). In concrete numbers, if one hashes 1000 128-bit messages with Pedersen, each preimage costs you only 2^59.
We do not recommend using Pedersen hash in protocols and applications.
[1] https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html
[2] http://netifera.com/research/flickr_api_signature_forgery.pdf
Pedersen hash has been popularized by Zcash team as ZK-friendly hash function suitable for Merkle trees. Its simplest version operates on an elliptic curve with two fixed generators G and H with unknown discrete log relation. Then to hash two integers (a,b) one computes
P = aG + bH
and takes some compressed version of P (e.g. x-coordinate) as a result. There are several extensions of this construction to longer messages using multiple generators [1] or just by a recursive Merkle-Damgard calling. In contrast to regular hash functions like Keccak there is a formal security proof for collision resistance as any collision implies a discrete logarithm relation between G and H.
There are several problems with this construction. First, from the implementation perspective it is quite complicated. To hash messages within some field F, one has to define an elliptic curve with the order bigger than |F| but the coordinates being in F. For zero-knowledge proofs one has to convert elliptic curve equations into degree-2 constraints, and also work with the bit representation of (a,b) in order to reduce the scalar multiplication to point addition and doubling. Altogether this makes quite a non-trivial circuit, but it is still doable.
From the cryptographic point of view the situation is worse. Pedersen hash has several properties quite unexpected from a cryptographic hash function. First, it is homomorphic: H(ab,cd) = H(a,b) + H(c,d). This property alone is not problematic and is even common for cryptographic commitments and many other primitives. However, it implies that the function is vulnerable to length-extension attacks: given H(A) it is easy to compute H(A,B) for some integer tuples A and B. This property, being present in SHA-0/1/2 and forbidden in SHA-3, caused many attacks like [2]. It makes a natural MAC construction MAC(M) = H(K || M) insecure, and rules out a common domain separation method of creating many functions from one as H_i(x) = H(i||x).
Finally, the preimage security of Pedersen is weaker than expected. For an n-bit elliptic curve it is not 2^(n/2) as one would hope for. If the hashed message is l-bit long for l<n the preimage search cost is not min(2^l,2^(n/2)) but only 2^(l/2). Indeed, let a and b be l/2 -bit long. Then define f(x) = xG and g(y) = P-yH. Thus the preimage for P is just a collision between f and g, which can be found memoryless in 2^(l/2) steps. Last but not least, the multi-target preimage security is even lower: to find 2^k preimages for l-bit messages, one performs only 2^(l/2+k/2) hash function calls thus making the amortized preimage search cost as low as 2^(l/2-k/2). In concrete numbers, if one hashes 1000 128-bit messages with Pedersen, each preimage costs you only 2^59.
We do not recommend using Pedersen hash in protocols and applications.
[1] https://iden3-docs.readthedocs.io/en/latest/iden3_repos/research/publications/zkproof-standards-workshop-2/pedersen-hash/pedersen.html
[2] http://netifera.com/research/flickr_api_signature_forgery.pdf
Пидорский хэш не для чётких пацанов онли
