How Not to Use ECDSA

For many developers, digital signatures (and most cryptographic primitives for that matter) are black boxes that “just work”. Developers can usually expect to be able to leverage open source implementations for signature generation and verification either in a programming language’s standard library or in a third party library. Oftentimes, all it takes is a quick skim through the API documentation and within minutes a developers can drop signature generation and verification into their systems.

While easier to use digital signatures can be a blessing, it is not necessarily always the case that digital signatures are easy to securely use. Furthermore, not all documentation is created equal and in some cases documentation might lack the proper guidance to ensure developers can use digital signatures in a secure manner. As a result, understanding how digital signatures can be incorrectly used is valuable knowledge for developers.

In this post, we will explore incorrect usage of the Elliptic Curve Digital Signature Algorithm (ECDSA). If you are unfamiliar with ECDSA, Andrea Corbellini has written a great introductory primer.

Pitfall #1: Signature Malleability

Recall that a ECDSA signature $(r, s)$ is valid for a public key $H$ and hash $z$ if $r$ is the x coordinate of the following point calculated by the verifier:

$P = s^{-1}zG + s^{-1}rH$

Notice that signature verification will pass as long as $r$ is correct – $s$ is used in the calculation of point $P$ , but as long as the x coordinate of $P$ is equal to $r$ , the actual value for $s$ does not matter. Thus, if there is more than one value for $s$ that can result in a point $P$ with an x coordinate equal to $r$ then there can be more than one valid signature for a given public key and hash. In fact, since $P$ is a point on an elliptic curve, there is also a point $-P$ on the curve with the same x coordinate as $P$ , but a negated y coordinate [1]. Since $P = kG$ [7] and $s$ is an input into the calculation of $k$ , a negated $s$ results in $-P$ which has the same x coordinate as $P$ . As a result, both $(r, s)$ and $(r, -s \mod n)$ are valid signatures for the public key $H$ and hash $z$ . We refer to $(r, s)$ as a “malleable” signature because a third party can use it to compute another valid signature for a public key and hash without access to the signing private key.

This malleability property of ECDSA signatures can introduce security vulnerabilities into systems if:

Replay defense mechanisms use the signatures themselves as unique identifiers (i.e. a verifier should only allow a signature to be used once).
Software relies on signatures as identifiers to query for additional information. See Bitcoin transaction malleability [2].

Avoiding Pitfall #1

One solution to defend against signature malleability based attacks is to enforce a single canonical signature for a given public key and hash which is the approach taken by Bitcoin. More specifically, the Bitcoin core client software will only accept “low s-value” ECDSA signatures where a signature has a low s-value if $s$ is less or equal to half the curve order [3]. The secp256k1 curve library used by the client will always generate signatures in low s-value form and the verifier expects provided signatures to also be in low s-value form [4].

Another solution is to avoid using signatures in identifiers or at the very least making sure to use unique values in the identifier creation process i.e. a nonce in the signed message. Unless there is a single canonical signature for a given public key and hash, signatures cannot be relied upon as unique identifiers.

Example Code for Pitfall #1

Example code for creating malleable signatures can be found here.

The program first generates the original signature and then TrickSig1() is used to create another valid signature. In the first attempt, the signature generated by TrickSig1() passes verification. However, in the second attempt, the ECDSA verification implementation from go-ethereum is used which implements the low s-value requirement thus causing verification to fail.

 original sig: (0xe742ff452d41413616a5bf43fe15dd88294e983d3d36206c2712f39083d638bd, 0xe0a0fc89be718fbc1033e1d30d78be1c68081562ed2e97af876f286f3453231d)
 original sig verification with message hash 0xb94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9: SUCCESS
 
 
 trick sig 1: (0xe742ff452d41413616a5bf43fe15dd88294e983d3d36206c2712f39083d638bd, 0x1f5f0376418e7043efcc1e2cf28741e252a6c783c21a088c3863361d9be31e24)
 NO MALLEABILITY CHECK
 trick sig 1 verification with message hash 0xb94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9: SUCCESS
 
 
 WITH MALLEABILITY CHECK
 HALF CURVE ORDER = 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
 trick sig 1 s-value <= half curve order!
 normalizing sig by negating s-value
 trick sig 1 verification with message hash 0xb94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9: FAILED

Pitfall #2: Verification Without Hash Pre-Image

Many ECDSA verification implementations expect the hash of the signed message as input, but the the verifier should always be the one to hash the message and should never accept a hash without knowledge of its pre-image [5]. Otherwise, an attacker is able to pick the hash that will used for verification. If the attacker does not need to know the pre-image of the hash, he/she can pick a hash that he/she can always produce valid signatures for [6].

The point $P$ calculated during verification can be expressed as $P = aG + bH$ where $a = s^{-1}z$ and $b = s^{-1}r$ .

We can express $s$ in terms of $b$ and $P$ :

$s = b^{-1}r = b^{-1}P_{x}$

We can express $z$ in terms of $a$ , $b$ and $s$ :

$z = as = ab^{-1}r = ab^{-1}P_{x}$

We can express a valid signature $(r, s)$ as:

$(r, s) = (P_{x}, P_{x}b^{-1})$

Thus, if an attacker has the freedom to choose the value for hash $z$ , then it can set $a$ and $b$ to arbitrary non-zero values and then derive values for hash $z$ and signature $(r, s)$ that would always pass verification for a public key $H$ .

Avoiding Pitfall #2

The solution to defend against this type of attack is to implement verifiers to always use the result of hashing a received message (that another party is claiming to have signed) for ECDSA verification.

Example Code for Pitfall #2

Example code for exploiting ECDSA verifiers that do not know the pre-image of a hash can be found here.

The program uses TrickSig2() to create a valid signature and hash pair given a public key. The verifier just accepts the hash so it has no knowledge of the pre-image (in contrast to if the verifier instead hashed the input before running the verification algorithm).

 trick sig 2: (0x41b5201d06acaafb67785a8e8aa89626e79c2117acce468196c1c5074ec9c274, 0x4f28c5a75abedce19cacba086282632f175abb635bd633465f6763a250eea629)
 trick sig 2 verification with message hash 0x8bcbdc44c5ba50680f5fa229ec8befecba16cc0a1be660241d32939ec472fd8c: SUCCESS

Conclusion

Both of the described pitfalls are examples of instances where a developer that has access to an easy to use cryptographic primitive library (both code examples import widely used open source implementations either from a standard or third party library) could still incorrectly use the library thereby losing some of the security properties of the primitive. Especially when creating systems that require cryptographic guarantees, developers stand to benefit a lot from not only a larger breadth of tools, but also a better understanding of what correct (or incorrect) usage of those tools looks like.