Summary

In the threshold signature scheme, participants start by dividing secrets into shares using a secret sharing scheme. The Verifiable Secret Sharing scheme generates shares from the user’s IDs but does not properly validate them. Using a malicious ID will make other users reveal their secrets during the secret-sharing procedure. In addition, a second issue resulting from lack of validation could cause nodes to crash when sent maliciously formed user IDs.

Details

The creation of Parties IDs does not properly validate for maliciously chosen IDs. Parties generate the secret shares in binance-chain/tss-lib codebase that keep-network/keep-ecdsa uses by evaluating the polynomial with the other parties’ IDs. It is critical that these party ids are non-zero because evaluating the polynomial at point 0 reveals the secret.

There is a check that these ids are not zero, but this is insufficient since it is not performed modulo the curve order. Therefore, one can set their ID equal to the order of the elliptic curve, which equals 0 during the polynomial evaluation modulo the curve order.

    shares := make(Shares, num)
    for i := 0; i < num; i++ {
        if indexes[i].Cmp(big.NewInt(0)) == 0 {
            return nil, nil, fmt.Errorf("party index should not be 0")
        }
        share := evaluatePolynomial(ec, threshold, poly, indexes[i])
        shares[i] = &Share{Threshold: threshold, ID: indexes[i], Share: share}
    }

(https://github.com/binance-chain/tss-lib/blob/73560daec7f83d7355107ea9b5e59d16de8765be/crypto/vss/feldman_vss.go#L64-L70)

Thus, a party with an ID equal to the order of the curve will receive the secret key as its share.

Another issue with the tss-lib implementation was the lack of verification for modularly equal user IDs that can cause nodes to crash during key generation or resharing.

Timeline

6 December 2021, 20:28 CET

The team is informed by Trail of Bits about the issue in binance-chain/tss-lib. The vulnerability was already disclosed with Binance and they have implemented fixes in their recent commits. We are advised to update our dependency to the most recent binance-chain/tss-lib version.

7 December 2021, 9:10 CET

The team confirms with Trail of Bits we started the work on a fix.

7 December 2021, 20:03 CET

The team informs Trail of Bits that we found a potential problem in Binance's fix that may lead to the signing code failing with Go panic. We identified the problematic line and suggested its removal.

To address the vulnerability in the protocol, it is required to ensure that:

• all indexes are non-zero,
• all indexes are non-zero modulo the curve order,
• all indexes are unique modulo the curve order.

The first two are guarded in CheckIndexes function by:

vMod := new(big.Int).Mod(v, ec.Params().N)
if vMod.Cmp(zero) == 0 {
  return nil, errors.New("party index should not be 0")
}

The last one is guarded by:

if sortutil.Dedupe(sortutil.BigIntSlice(dup)) < len(indexes) {
  return nil, errors.New("duplicate in indexes")
}

However, CheckIndexes was additionally modified to update values of passed indexes by doing indexes[i] = vMod.

This line was not backward-compatible and caused signatures to fail with panic: runtime error: invalid memory address or nil pointer dereference in case the signing group was generated with at least one PartyID.Key higher than ec.Params().N. This would also be problematic for new code that constructs such PartyID - we tested that key generation completed successfully but signing failed with the mentioned panic.

8 December 2021, 12:49 CET

Trail of Bits confirmed the line we flagged is not critical to the security of the protocol.

8 December 2021, 15:29 CET

The team informed Trail of Bits we are planning to open a PR to binance-chain/tss-lib with a fix and we suggest extending the embargo for communicating this issue for one more week, until Friday, Dec 17h to give everyone more time update their code given the problem was found. We also ask Trail of Bits to get in touch with Binance to review our fix given that we are not going to provide a sufficient explanation in the commit and PR description to do not threaten the security of projects that have already upgraded their dependency.

8 December 2021, 18:17 CET

The team informs Trail of Bits about opening a PR bnb-chain/tss-lib#155 and explains all the details of the issue.

The problematic scenario is:

1. We start the keygen by creating PartyID for each member. The PartyID struct has Id and Key fields. We set PartyID.Key that is higher than the elliptic curve's N.
2. This goes to tss-lib which starts the round 1 code (ecdsa/keygen/round_1.go). It takes PartyID.Key of each member and assembles the ids slice. This slice is thrown into CheckIndexes which overwrites each element by doing the modulo N.
3. After returning from CheckIndexes the modified ids slice is used to set the Ks slice in the final LocalPartySaveData which is received by each group member as keygen final result.
4. Each member takes this LocalPartySaveData and saves it on disk.
5. Upon signing, we do the same as in point 1, so we construct PartyIDs in the same way and start the protocol. At this point, PartyID.Key is higher than curve's N.
6. Before starting round 1 of signing, LocalPartySaveData obtained at keygen and our PartyIDs built at point 5 are used in BuildLocalSaveDataSubset to build a new LocalPartySaveData instance.
7. BuildLocalSaveDataSubset is the place where things go wrong because Key field of each PartyID from point 5 doesn't correspond to encoded Ks elements of LocalPartySaveData obtained after keygen, the final LocalPartySaveData is corrupted, and cause panic upon validation before signing round 1.

8 December 2021, 21:50 CET

Trail of Bits confirms they are going to followup with Binance and they agree to extend the embargo by a week.

8 December 2021, 15:16 CET

Trail of Bits validates the problematic scenario we described and our fix. Trail of Bits reaches to Binance and recommends merging our fix and in addition to some other fixes that would secure the code to do not panic even if LocalPartySaveData has corrupted data.

10 December 2021, 8:16 CET

Binance merges our fix bnb-chain/tss-lib@cd95cee

13 December 2021, 8:35 CET

Binance applies more fixes so that even in case of LocalPartySaveData corrupted, the code is not going to panic.

15 December 2021

The team releases a new version of the client, v1.8.1, and announces the need for an upgrade.
https://github.com/keep-network/keep-ecdsa/releases/tag/v1.8.1