Missing point-at-infinity check in int secp256k1_ecdsa_sig_recover() can cause non-deterministic results

[SergioDemianLerner]

In https://github.com/bitcoin/secp256k1/blob/master/src/ecdsa_impl.h the public key recovery method ends with:
secp256k1_ecmult(&qj, &xj, &u2, &u1);
secp256k1_ge_set_gej_var(pubkey, &qj);
secp256k1_num_free(&rn);
secp256k1_num_free(&u1);
secp256k1_num_free(&u2);
return 1;
}
The public key is stored in qj. And, afterward, always returns 1 (success). Nevertheless it is possible to choose the values r,s of the ECDSA signature so that qj end up being the point-of-infinity. qj is copied to pubkey and transformed from Jacobian coordinates into affine coordinates. In the current version of secp256k1_ge_set_gej_var(), only the infinity field is copied, so the remaining fields are left in an undefined (platform-dependent) state. If Bitcoin (using a new opcode) or other cryptocurrency were to rely on this method to obtain a pubkey, the blockchain could be forked by including in a block a transaction containing a specially crafted signature what is valid on one platform but invalid on another.
The solution is to insert the appropriate infinity check between ecmult and set_qej:

secp256k1_ecmult(&qj, &xj, &u2, &u1);
If (secp256k1_gej_is_infinity(&qj)) {
return 0;
}
secp256k1_ge_set_gej_var(pubkey, &qj);

In Bitcoin this method is used in the by verifymessage RPC method or GUI dialog. This means that it may be possible in theory to verify an incorrect signature.
Nevertheless, I see it very hard that by chance (pubkey.GetID() == keyID) in rpcmisc.cpp, In other words, the contents of the memory area of qj overlaps with pubkey, which is not expanded in the stack (only the KeyID is stored). Something similar happens with (!(CBitcoinAddress(pubkey.GetID()) == addr)) in signverifymessagedialog.cpp.

But a vulnerability must not be ruled out without an complete analysis of the stack state during the execution of secp256k1_ecdsa_sig_recover()

[sipa]

Nice catch, that must indeed be fixed.

Regarding your reasoning: secp256k1_gej_t and secp256k1_ge_t have (intentionally) undefined values for x/y/z when infinity is set, so that's not a problem on itself. Also, the internal data types of libsecp256k1 are never exposed (so the API can remain platform-independent), and there is always conversion to/from serialized datatypes first. However, the serialization code for public keys does not check the infinity flag, which is indeed an error.

[sipa]

Can this be closed?

[SergioDemianLerner]

Yes.