4
$\begingroup$

I found information, that it is possible to construct a hash and signature that look valid if the hash is not computed within the contract itself (we are talking about ECDSA/ecrecover here).

So, the task is to construct a hash + v, r, s that would resolve to a particular address using ecrecover(). I have access to several signed hashes.

Can anybody provide an additional clue how it would be possible? Unfortunately, there is very little information on this topic (or Google does not like me?).

$\endgroup$
2
  • $\begingroup$ Please confirm that in "construct a hash + v, r, s" the v is a version that's a fixed constant and can be removed from the question. With "access to several signed hashes" we already have an $(\mathsf{hash},r,s)$ matching the particular public key, which solves the stated problem. $(\mathsf{hash},r,n-s)$ also does. Is the real question: given $(\mathsf{hash},r,s)$ known to verify against an ECDSA public key that can be recovered, construct $(\mathsf{hash'},r',s')$ with $\mathsf{hash'}\ne\mathsf{hash}$ that verifies against the same public key? $\endgroup$
    – fgrieu
    May 26, 2023 at 10:36
  • $\begingroup$ Hi fgrieu, you are spot on! This is the correct question: given (hash,r,s) known to verify against an ECDSA public key that can be recovered, construct (hash′,r′,s′) with hash′≠hash that verifies against the same public key. $\endgroup$ May 26, 2023 at 11:31

1 Answer 1

3
$\begingroup$

I'll use the definition of ECDSA and notation in sec1v2 §4.1. I'll assume "access to several signed hashes" has allowed to unambiguously find the public key $Q_U$ using "ecrecover", which I guess is essentially ECDSA public key recovery except the hash of the message rather than the message is given, and I don't know how the case of multiple possible public keys is resolved. I'll ignore the "v" part of the question: that seems to be a version byte.

Per this comment, the real question is to construct $(H,r,s)$ with $H$ different from any other hash we have been given, such that ECDSA signature verification would pass for signature $(r,s)$, public key $Q_U$, and an hypothetical message which hash is $H$.

We can proceed as follows:

  • Draw $u_1$ and $u_2$ each random in $[1,n)$.
  • Compute point $(x_R,y_R):=u_1\,G+u_2\,Q_U$ as in step 5 of ECDSA signature verification. In the extremely unlikely case that's the point at infinity $\mathcal O$, retry at the first step (alternatively: compute the private key as $-u_1\,{u_2}^{-1}\bmod n$ and stop for celebration).
  • Perform steps 6 and 7 of ECDSA signature verification to compute $v$, and set $r:=v$. This whole step reduces to $r:=x_R$ for curves in prime fields including all secp curves.
  • Compute $s:=r\,{u_2}^{-1}\bmod n$ then $e:=s\,u_1\bmod n$.
  • Convert $e$ per big-endian binary convention to a bitstring $H$ of the hash width. If $e$ is too large, retry at the first step. This can't happen in the common case that the number of bits in $n$ is no more than the number of bits in the hash, e.g. secp256k1 and SHA-256; but it occurs with probability 99.80% for secp521r1 and SHA-512.
  • If $H$ happens to be one of the hashes that we have been given, retry at the first step. This is extremely unlikely.

Here, $e$ matches $H$ as produced by step 3 of ECDSA signature verification; $u_1=e\,s^{−1}\bmod n$ and $u_2=r\,s^{−1}\bmod n$ as in step 4; and thus verification would pass for signature $(r,s)$, public key $Q_U$, and an hypothetical message which hash is $H$.

Note: adaptation is needed for variants of ECDSA which use a different verification procedure. E.g. if a certain parity is required for $s$ and that's not met, change $s$ to $n-s$ in the end.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.