ING (Dutch bank) recently released their own implementation of the popular Gennaro-Goldfeder’18 Threshold ECDSA signature scheme in the form of a library written in Rust. Kudelski Security audited their code, our report is available here. During the audit, we found a potentially serious problem in the protocol itself (not dependent on ING’s implementation, but rather on the need of a security assumption in the original protocol that is not given for granted in many real-world cases.) This problem might allow a single malicious attacker to delete or lock funds and blackmail all other peers.
Threshold signature schemes (TSS) have seen a growing interest and rapid adoption in the last few years, mainly driven by blockchain applications such as Bitcoin. A blockchain transaction (such as the transfer of funds, or the execution of a smart contract) in its basic form is created and verified by the network via a digital signature generated by a private signing key (usually held in a user’s wallet.) This presents a security challenge: anyone with access to the private signing key can issue an (irrevocable) transaction. Clearly an unacceptable risk for highly regulated environments such as large financial institutions, which cannot afford to lose billions of dollars with a single, irreversible transaction executed by a malicious hacker who manages to exfiltrate a high-value key.
TSSs solve this problem by splitting the generation of the signature between N different users, with the possibility of configuring a threshold parameter T such that any subset of T users (among the N authorized ones) is sufficient to generate the signature, but any subset of T-1 or less users is not. This reminds a bit of another similar cryptographic primitive, called “secret sharing schemes” (SSS) but it’s actually different: In a SSS, a subset of T among N users collaborate to have a leader reconstruct a secret (for example, a signing key.) But, after the reconstruction, the leader knows that secret and can further use it however they wish, even without requiring the collaboration of the other users, so it is again a security risk. In a TSS, instead, the signing key is never fully reconstructed! Each one of the T users interact in a complex multi-party computation (MPC) protocol by contributing with a partial signature. Those partial signatures are then recombined by a leader to obtain a single valid signature. The difference is that the leader cannot reuse the data collected to generate a different signature, so the scheme is highly interactive and requires different rounds of complex, interlocking encryption, signatures, and zero-knowledge subprotocols.
The appeal of TSS for many applications is that they are backward-compatible with already deployed signature schemes: the signature generated by a TSS is indistinguishable by a “normal” signature in respect to a certain public key, so at the end the verifying user does not care whether the signature was generated in a “standard” way or in a TSS way, because there is only one single public key to check against, and the verification algorithm is unmodified. So, for example, it is not necessary to modify the Bitcoin protocol to support a new type of signatures, it is just sufficient to add TSS support client-side.
Not all signature schemes are equivalent in respect to “TSS-ization” though. Certain schemes, such as BLS or Schnorr signatures, are much easier to implement in a TSS way. Others, such as ECDSA, are much more complex. It just happens by bad luck that ECDSA is the currently adopted standard in Bitcoin and many other important blockchains. Existing TSS schemes for ECDSA are quite difficult to analyse and implement and they are prone to issues, either in their design or code.
During our audit for ING we stumbled upon one of these issues. ING’s library implements GG18, one of the most popular TSS schemes for ECDSA. One of the features of GG18 is the “key resharing protocol”, which allows an old committee of peers to refresh the shares of the secret key across a new committee (for example, if it is necessary to add new members, or to remove some.) The key resharing protocol is a delicate procedure that has been covered by many recent attacks. One of these attacks, the “forget-and-forgive”, is described as:
The proposed mitigation is:
This mitigation is implemented correctly by ING. However, we found that such mitigation is insufficient – and might actually make things worse – if a robust broadcast channel is not available, by allowing a single malicious attacker to delete or lock funds and blackmail all other peers.
A robust broadcast channel is a reliable way of broadcasting messages in such a way that all parties receive the same broadcast message. This is easily achieved if a trusted third party relay is available, but for the general case of peer-to-peer networks, it is not always trivial. For example, the naive solution of sending a broadcast message as N distinct direct point-to-point connections is clearly not robust, because a malicious sender could transmit a message X to certain peers and a different message Y to other nodes.
This is exactly the scenario that enables a devastating attack in the GG18 resharing protocol. Let’s say a group of 4 peers (A, B, C, D) with threshold value 3 (any 3 of them is necessary and sufficient to sign) wants to add a fifth peer E to the committee (still with threshold value 3). So they start the resharing protocol, and in order to avoid the “forget-and-forgive” attack they conclude the protocol with the final round described in the mitigation above.
However, E is malicious. After the resharing protocol concludes, E crafts different messages for different peers instead of broadcasting a final “ACK”:
- E sends “ACK” to A and B
- E sends “not ACK” to C and D
Now see what happens: A and B think that everything went fine, so they discard the secret key material (their “shares”) that was related to the old committee configuration, and migrate to the shares for the new committee configuration. C and D, however, follow the proposed mitigation to the “forget-and-forgive” attack: they assume that something went wrong and will not save the new shares to disk, falling back to the old shares. And now we have a problem: a single malicious adversary, E, has managed to “segment” the group of peers into two committees, one old and one new, where none of them has enough information to reconstruct the secret without E’s collaboration! So Eve can blackmail the committee, withholding all the funds associated to the wallet being shared.
Under the right circumstances, this attack can be devastating. It is important to notice that this has nothing to do with ING’s implementation, nor with a flaw in the security proof of GG18, but rather with the security model not taking into account real-world implementations of the communication channel. Countermeasures against these kind of attack can only be implemented at an application level, so developers have to be careful when adopting existing GG18 solutions.
We are grateful to ING for the trust they gave us, and found very stimulating working together with their tech team.
Kudelski Security Research 