ECDSA Malleability

ECDSA in Ethereum

• Digital Signatures
• Details of ECDSA Signatures
• ECRecover and Signature Verification in Ethereum
• ECDSA Malleability

---

In the previous posts in this series, I introduced the concept of Digital Signatures, the signature scheme ECDSA and how it is implemented in Ethereum. In this post, I explore a feature of ECDSA, called malleability, and whether it could be exploited.

If you’ve read the previous article, you know by now that a valid ECDSA signature (r, s) can easily be transformed into a different valid signature, (r, n - s)for the same data. Is this harmful?

Transaction Malleability in Bitcoin

It could be. There have been exploits before, and some reason to believe the Mt. Gox hack used this technique. You can find some introduction to malleability here and more details here if you wish, but I give a small introduction below.

At its core, the problem is at a higher level than ECDSA. Bitcoin transactions themselves were malleable before Segwit was implemented. You could take a Bitcoin transaction, keep all the same basic data (accounts, transferred amount, etc.) and change just enough auxiliary data that the Transaction Id (aka TxId) would become different.

Now, this TxId is what people use to uniquely identify transactions, just like a cheque has a serial number, for example. The TxId is a hash of all the transaction’s data so if you change anything in the transaction you get a new Identifier.

The problem is that if you can create a new valid signature for your transaction this creates a new TxId of a valid transaction, which is exactly what happens when you change a good signature to something else that is still valid.

Exploiting a Malleable Transaction

People have exploited this flaw by using what is, in essence, a confidence trick applied in a digital scenario. Imagine Alice sends a payment to Bob, in a transaction with the identifier A.

Somehow, Bob manipulates some nodes to change the signature of this transaction and thereby create a new valid transaction with a new identifier A*. These nodes flood the network with this new transaction, which, remember, sends Alice’s payment to Bob.

The trick is to manipulate the network in a way that A* will be accepted into the blockchain before A. If that is the case, Alice’s coins will be transferred, and Bob will receive his payment. And when transaction A is propagated, it will be rejected because the owner of those coins is now Bob.

So all is well, you say?

This is where the con-trick comes in. Alice does not know the new TxId. For all purposes, if she is keeping track of the transactions in the chain to settle her debts in her books, she will never see the payment to Bob.

And Bob will come knocking, oh yes he will, because he engineered all of this to get precisely to this end. He will claim he was never paid, and that Alice made a mistake.

She will check the blockchain and conclude her transaction was lost, and if she does not suspect foul-play, she will send it again. Bob just received a double payment, and he can go on with this trick until Alice suspects something.

Fixes to ECDSA Malleability

The above scenario leaves an exploit open, and so Bitcoin developers tried to address it. I will not go into the complicated history of Bitcoin, and focus on Ethereum instead, that I understand better.

In Ethereum, likewise, the guys at Ethereum Foundation considered this problem worthy of a fix in EIP-2, although the write up says:

This is not a serious security flaw, especially since Ethereum uses addresses and not transaction hashes as the input to an ether value transfer or other transaction, but it nevertheless creates a UI inconvenience as an attacker can cause the transaction that gets confirmed in a block to have a different hash from the transaction that any user sends, interfering with user interfaces that use transaction hashes as tracking IDs.

Avoiding ECDSA Malleability

EIP-2 changed the calculation of signatures, to disallow values of s above n/2. Remember a signature has two values that fall in the range [1; n) (the strange bracketing in this expression means that 1 is part of the set, but n is not — there are n-1 elements in this range).

Because all operations are done modulo n, the value n/2 divides the interval [0; n) into a low-half and a high-half. A little thought should convince you that if s falls in one half, n - s falls in the other.

By restricting the valid range in half, EIP2 effectively removes half the points from the group, ensuring there is at most one valid point at each x coordinate.

Open Zeppelin

Although Solidity offers a native ecrecover operation, which invokes a suitable precompiled contract, there is an EVM library by Open Zeppelin that introduces further checks.

This offers a convenient API, since ecrecover expects to receive its arguments in too much of a low-level format: the hash of the message to check, and each of the 3 parts of the signature as a 4-byte integer.

Open Zeppelin’s library allows you to invoke the Key Recovery operation by simply passing the signature as a sequence of bytes, as generated by web3.eth.sign().

This must be 65 bytes in length, with the first 32 bytes for r, then 32 bytes for s and a final byte for v. It specifically implements EIP2 by checking s against the restricted range and also checks vis either 27 or 28.

If you go back to the last post, you’ll see that the recovery identifier can only be 29 or 30 when the value of s is too large. This meant s > n, but since now s is restricted to the first half of the set, it can never be that large anymore.

Public Keys for Invalid Cases:

The promise of Public Key Recovery is that a message and a signature are enough to recover a valid public key. Is this true?

Let’s see. Let’s fix a message with hash e, a random point X = (xR, yR) = kG, a private key d, a public key (xQ, yQ)= Q = dG and a resulting signature:

r = xR mod n
s = (e + rd) / k (mod n/2)

You can check the previous post of this series to see how one can compute the correct point X from the values r and v.

Briefly, recall that r is strongly related to the x-coordinate of X. And in fact, with EIP-2 in place, r is the x-coordinate of X. From this value, and applying the curve’s equation, we can obtain the y-coordinate and therefore the point X.

So, given a signature (r, s) and a message m, we can compute the corresponding hash e and the random point X.

Now, recall that in the vanilla ECDSA verification, we compute X by:

X = (eG + rQ) / s (mod n)

To obtain the public key Q, we turn this around and get

Q = (sX - eG) / r

1. For a Different Message

Next, let’s see what happens if we pass a different message, represented by its hash e', to the recovery process, keeping the original signature (r, s).

We recover the same point X, as outlined above.

Q' = (sX - e'G) / r

We get a valid elliptic curve point, and in the end, that is exactly what a public key is. If we now apply the original verification algorithm with this public key to the mismatched message, in the step where we compute the point X, we get unsurprisingly

X' = (e'G + rQ') / s = 
   = e'G / s + (sX - e'G) / s
   = e'G / s - e'G / s + X
   = X

This is exactly the same point computed in the original case, which means we have recovered a public key Q' that accepts the signature as valid, although for a different message than the one it was authenticating.

2. For a Different Signature

Now let’s try using a different, formally correct, signature (r', s') and keep the same original message, with hash e.
This time, the reconstruction obtains a very different point X' whose x-coordinate is r', and then:

Q'' = (s'X' - eG) / r'. 

Once again, the verification algorithm accepts this signature, since:

X = (eG + r' Q'') / s' = X'
v = x-coordinate of X
which implies v = r'

So What is the Meaning of This?

We can summarize the last two section in a few words. If we take some signature sig for a given message e (under a public key Q), it is always possible (except for eventual edge cases) to find a new public key Q' under which:

• this signature remains valid for a different message, or
• this message can be verified by a new forged signature

It may just be cryptographer’s paranoia, but this always felt icky to me.

In other words, given a publicly known signature, stored for the sake of example on a blockchain, we can always create a new fact, out of the blue, that some random public key authenticated any message we want.

Is that serious?

From the viewpoint of an attacker trying to forge any signature, not really. They can obtain an essentially random new key, and so it’s only by chance that they could produce a specific target public key.

But if the attacker can engineer the message and signature to generate a specific key, then they would have effectively forged a signature. How could they do it?

Let the attacker fix a target key Q. The attacker must find (r, s, m) such that:

• X = (r, y(r)) is the unique point with x-coordinate r;
• e = Hash(m) where m is some useful “authenticated” message
• rQ + eG - sX = 0

Notice that each of the three variables the attack can manipulate appears as the logarithm of an elliptic curve point in the sum above.

Any two of these variables can be freely chosen by the attacker, but to make the third consistent with them, the attacker must solve a discrete logarithm on the elliptic curve, for example:

Fix r and s:
--- X is fully determined by r or vice-versa
--- s can be independently chosen from r
==> e must be the discrete log of rQ - sX

Fix r and e:
--- X is fully determined by r or vice-versa
--- e can be independently chosen from r
==> s must be the discrete log of rQ + eG with respect to X.

Concluding Thoughts

The discrete log is the backbone of current public-key cryptography, and barring the use of a general quantum computer, no one knows how to solve them.

So there you go, although you can always compute some public key that validates a message/signature pair, it seems you can’t really turn that into a meaningful attack, and we can all go back to sleeping easy at night.

This has been a long series, exploring the depths of ECDSA and the key recovery mechanism. We covered a lot of ground, from basic definitions to esoteric attacks.

I hope it has given you some new insight or made you think about the many assumptions we make when using secure systems.

In any case, if you enjoyed reading this post, please like it and share it, and let me know your thoughts in the comments below.

Have fun, stay safe, and see you soon.