Around six days ago (2021/12/12) Dmytro Tymokhanov and Omer Shlomovits published a paper titled “Key Extraction Attacks on Threshold ECDSA Implementation,” in which they described two attacks against the Multi-Party Computation (MPC) based ECDSA implementations proposed in the GG18 and GG20 papers. Almost all state-of-the-art MPCs on today’s market of cryptocurrency custody solutions are based on ideas from these two papers, e.g., Binance’s (open-sourced) TSS MPC (GG18), as well as Coinbase’s recently released, open-sourced Kryptologo MPC (GG20). As a result, this new eprint paper by Tymokhanov and Shlomovits may potentially have a very wide impact on systems deployed in the real world, in addition to its significant contributions in MPC theory, namely, concrete attacks demonstrating the absolute necessity of incorporating zero-knowledge proofs in the protocol design, which the authors of GG18 and GG20 have long acknowledged but was unable to give any explicit attacks.
More specifically, this new paper describes an attack on the key Multiplicative-to-Additive (MtA) subroutine. Once successfully launched, all private key fragments required to generate a legitimate signature can be obtained in a very small (single-digit) number of attempts.
Tymokhanov and Shlomovits gave two specific attacks. The first attack works if your MPC does not use zero-knowledge proofs by simply assuming all signers are trustworthy. The attacker can guess the private key fragments with just 8 signatures. As we have mentioned, this new attack gives an accurate explanation why zero-knowledge proofs are absolutely essential in GG18/20-style MPC, which the original authors have long known but did not give any explicit attacks.
The second attack works if your MPC adopts the Paillier encryption to implement MtA, as suggested in the GG18/20 papers, but does not correctly check whether the exponents in the received public keys are large enough, then an attacker can easily recover honest partys' secret shares with just 1 single signature. According to the authors, this is more serious and practical threat, as Binance’s TSS MPC and all its forks did not implement their Paillier encryption correctly.
As CYBAVO’s customers, however, you do not need to worry about these attacks when using your CYBAVO system. After rounds of verification and testing, we are happy to report that these attacks described in the new e-print paper do not work against out MPC architecture and implementation.