B002: Solidity EC Signature Pitfalls
Although many people are intimidated by cryptography, it is a commonly utilized thing in almost all our daily interactions ranging from certificate handshakes for accessing websites over HTTPS to hardware-based signature validation for IoT devices.
Today’s topic will attempt to explain the inner workings of cryptography (the relevant ones, at least) in straightforward but technical terms aiming to educate on how to properly utilize the cryptographic signature system readily available within Solidity; a very powerful feature that allows multiple second layer abstractions to be applied such as EIP-712, EIP-1271 and more.
This article goes into quite some technical depth so if one is interested in solely how to prevent these pitfalls, I advise heading straight to the conclusion chapter.
Cryptographic System
The cryptographic system available within Solidity is Elliptic Curve based and in particular utilizes the same curve as Ethereum, secp256k1. For those unfamiliar with cryptography, there are two main methods of cryptography: one based on prime factorization (such as RSA) and one based on the discrete logarithm problem (such as ECDSA).
Within Solidity, an ECDSA signature is represented by its r, s and v values. Users familiar with ECDSA will immediately deduce that the v value out of the three is relatively non-standard as the r and s are sufficient to provide a valid “point” in the curve. The v value is actually an optimization step as the r and s values can point to multiple different points in the same elliptic curve (four for secp256k1) and as such, one would need to compute all points to identify the one that validates the signature.
The v argument is detailed in the Ethereum Yellow Paper in Appendix F and was originally meant to support all four points by holding a value of either 27, 28, (chainid * 2) + 35 and (chainid * 2) + 36. In the latest iteration of the Yellow Paper, however, either 27 or 28 are expected and the other two points are invalidated due to signature malleability which we will cover in the next chapter.
Signature Malleability
The first EIP that was introduced as a hard-fork of Ethereum was EIP-2 which, among other things, sought to prevent signature malleability by restricting valid signatures to boast a low s value or otherwise be considered invalid. This change was also what brought the update to the Yellow Paper with regards to valid v values.
In order to better understand why signature malleability is possible within the Elliptic Curve cryptographic system, one must first visualize how an elliptic curve works.
As seen above, an Elliptic Curve is symmetric on the X-axis, meaning two points can exist with the same X value. In the r, s and v representation this permits us to carefully adjust s to produce a second valid signature for the same r, thus breaking the assumption that a signature cannot be replayed in what is known as a replay-attack.
The adjustment that needs to be done on s is dependent on the Elliptic Curve utilized and can be generalized as follows: for a given (r, s) signature pair, the complementary signature (r, -s mod n) is also considered valid where n represents the curve’s integer order.
Given the generalization above, one can deduce that a sensible way to prevent malleable signatures is to simply ensure the s value is low enough that the modulo operation with n will yield an equivalent s value. Although the n value of secp256k1 is 0xFF..FEBAAEDCE6AF48A03BBFD25E8CD0364141, Ethereum (as Bitcoin before it) chose to restrict the valid s values to the lower half order of the elliptic curve the upper bound of which is equal to (n / 2) + 1, or 0x7F..FF5D576E7357A4501DDFE92F46681B20A1.
As seen in the above segment, the limit imposed for s is the same as (n / 2) given that the upper bound value we calculated above is non-inclusive. The lower half order of the Elliptic Curve for valid s values was ultimately chosen because small s values can lead to a smaller signature size when variable-length encodings are utilized in addition to protecting against replay attacks.
An important thing to note is that signature malleability is of no concern if the payload that was signed utilizes a nonce system or similar information that is consumed upon signature validation. This is indeed the case for most use cases of ecrecover in smart contracts today and this trait also rendered Ethereum inherently secure even before EIP-2 was assimilated as it uses a nonce-based system in contrast to Bitcoin.
In any case, malleable signatures should be prohibited under all circumstances as a matter of best practice.
Implementation Misbehaviour
The above chapter summarized the potential pitfall with regards to the cryptographic system itself, however, the software implementation can also misbehave as is the case of Ethereum. The EC recovery mechanism is available within Solidity via the ecrecover primitive operation which in turn invokes a pre-compiled contract within the EVM to validate the signatures.
As detailed above, the EIP-2 hardfork does invalidate signatures with a high s value but the precompiled contract ecrecover points to was left as is, meaning that individuals need to properly account for malleable signatures and sanitize them.
Another pitfall of the ecrecover precompiled contract is that it does not halt execution when invalid signatures are supplied to it instead yielding the address of 0. If this edge case is not properly accounted for and the signature is not validated against the caller of the function, one may be able to impersonate the 0 address which in most contracts has a special meaning (i.e. burn address) and could have devastating consequences to its operation.
Conclusion
To summarize, code that utilizes the ecrecover mechanism directly should primarily validate that the resulting address is not equal to the 0 address and secondarily validate that the v value is either 27 or 28 and that the s value of the signature is lower-than-or-equal-to the value of (n / 2) of the secp256k1 bonding curve, the value of which can be found here.
