search

starkware-libs / cairo-lang

Apache License 2.0
1.34k stars 263 forks source link

Valid signature rejection not that negligible and possibly exploitable #39

Open veorq opened 2 years ago

veorq commented 2 years ago

crypto.signature.signature.verify() rejects signatures with an r, inverse s, or message (hash) greater than 2**251 < EC_ORDER:

https://github.com/starkware-libs/cairo-lang/blob/4e233516f52477ad158bc81a86ec2760471c1b65/src/starkware/crypto/starkware/crypto/signature/signature.py#L199-L201

There's a gap of ~2^196 values, thus a probability to hit an invalid r or s that is of the order of 2^(196-251)/2 = 2^-54, when generating an ECDSA sig for some fixed message using a standard algorithm (rather than Cairo's sign(), which enforces these constraints).

I can't think of a specific attack scenario at the moment, but I would expect to find applications where either 1) that accidental failure rate would be unacceptably high, or 2) adversaries could bruteforce invalid sigs to do some kind of DoS, or worse (with plausible deniability)

I probably miss some of the context, and you may have a good reason to verify sigs that way.

veorq commented 2 years ago

Any thoughts on this?

JameWade commented 4 months ago

Why is there no official reply to this question?I think is a good question