Why is it necessary to ensure signature verified with the recovered key?

[adam254689]

https://github.com/RustCrypto/signatures/blob/8516671bb56abe998d3e88d941df7862b6d58985/ecdsa/src/recovery.rs#L313C9-L313C47

I'm not super familiar with the details of ECDSA, but for my workload this verify_prehash check doubles the runtime. Is there any situation where this check will actually fail?

[tarcieri]

Computing the recovered key involves solving a system of linear equations.

If the signature doesn’t verify, an attacker can trick you into recovering the wrong key.

[adam254689]

Computing the recovered key involves solving a system of linear equations.

If the signature doesn’t verify, an attacker can trick you into recovering the wrong key.

Can you elaborate a bit more on this? Would the system of linear equations not constrain that the recovered key verifies? A concrete example where vk.verify_prehash(prehash, signature) returns an error would be super useful.

[tarcieri]

Would the system of linear equations not constrain that the recovered key verifies

It does not. An attacker can easily solve for whatever key they want if there is no requirement that the signature verifies.

[adam254689]

Would the system of linear equations not constrain that the recovered key verifies

It does not. An attacker can easily solve for whatever key they want if there is no requirement that the signature verifies.

Are you saying that if an attacker has control over the input, then they can get recover_from_prehash to produce whatever verifying key they want, but in that case, the verification would return an error? If so, could you provide an example where the verification fails?

[tarcieri]

I’m currently on vacation and don’t have time to put together a contrived example for you

[XuJiandong]

In Bitcoin's secp256k1 implementation, the recovery routine doesn't include verification of the recovered public key. You can see this in the Bitcoin secp256k1 code.

If the recovered public key isn't correct, an error occurs when comparing it to the correct public key or public key hash. Therefore, we can skip this expensive verification.

In https://www.secg.org/sec1-v2.pdf:

1.6.2. Verify that Q is the authentic public key. (For example, verify the signature of a
certification authority in a certificate which has been truncated by the omission of
Q from the certificate.) If Q is authenticated, stop and output Q.

If Q is equal to expected pubkey(not verify again), we can stop immediately.

[tarcieri]

I think it would be okay to add a separate *_noverify method or something like that, however it’s a much safer default to verify and not output potentially incorrect public keys