Score:4

ECDSA (ecrecover) - How an attacker can construct a hash and signature that look valid

sr flag

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?).

fgrieu avatar
ng flag
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?
Andrew Rukin avatar
sr flag
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.
Score:3
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.