GHSA-gp6j-vx54-5pmf: Github.com/keep network/keep ecdsa Incorrect Validation Of Parties IDs Vulnerability

{
  "schema_version" : "1.4.0",
  "id" : "GHSA-gp6j-vx54-5pmf",
  "modified" : "2022-01-04T22:41:52Z",
  "published" : "2022-01-06T18:30:26Z",
  "aliases" : [ ],
  "summary" : "Incorrect validation of parties IDs leaks secret keys in Secret-sharing scheme",
  "details" : "# Summary\n\nIn 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.\n\n# Details\n\nThe 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.\n\nThere 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.\n```\n    shares := make(Shares, num)\n    for i := 0; i < num; i++ {\n        if indexes[i].Cmp(big.NewInt(0)) == 0 {\n            return nil, nil, fmt.Errorf(\"party index should not be 0\")\n        }\n        share := evaluatePolynomial(ec, threshold, poly, indexes[i])\n        shares[i] = &Share{Threshold: threshold, ID: indexes[i], Share: share}\n    }\n```\n(https://github.com/binance-chain/tss-lib/blob/73560daec7f83d7355107ea9b5e59d16de8765be/crypto/vss/feldman_vss.go#L64-L70)\n\nThus, a party with an ID equal to the order of the curve will receive the secret key as its share.\n\nAnother 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.\n\n# Timeline\n\n### 6 December 2021, 20:28 CET\nThe 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.\n\n### 7 December 2021, 9:10 CET\nThe team confirms with Trail of Bits we started the work on a fix.\n\n### 7 December 2021, 20:03 CET\nThe 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.\n\nTo address the vulnerability in the protocol, it is required to ensure that:\n- all indexes are non-zero,\n- all indexes are non-zero modulo the curve order,\n- all indexes are unique modulo the curve order.\n\nThe first two are guarded in `CheckIndexes` function by:\n```\nvMod := new(big.Int).Mod(v, ec.Params().N)\nif vMod.Cmp(zero) == 0 {\n  return nil, errors.New(\"party index should not be 0\")\n}\n```\nThe last one is guarded by:\n```\nif sortutil.Dedupe(sortutil.BigIntSlice(dup)) < len(indexes) {\n  return nil, errors.New(\"duplicate in indexes\")\n}\n```\nHowever, `CheckIndexes` was additionally modified to update values of passed indexes by doing `indexes[i] = vMod`.\n\nThis 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.\n\n### 8 December 2021, 12:49 CET\nTrail of Bits confirmed the line we flagged is not critical to the security of the protocol.\n\n### 8 December 2021, 15:29 CET\nThe 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.\n\n### 8 December 2021, 18:17 CET\n\nThe team informs Trail of Bits about opening a PR https://github.com/binance-chain/tss-lib/pull/155 and explains all the details of the issue.\n\nThe problematic scenario is:\n\n1. 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`.\n2. 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`.\n3. 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.\n4. Each member takes this `LocalPartySaveData` and saves it on disk.\n5. Upon signing, we do the same as in point 1, so we construct `PartyID`s in the same way and start the protocol. At this point, `PartyID.Key` is higher than curve's `N`.\n6. Before starting round 1 of signing, `LocalPartySaveData` obtained at keygen and our `PartyID`s built at point 5 are used in `BuildLocalSaveDataSubset` to build a new `LocalPartySaveData` instance.\n7. `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.\n\n### 8 December 2021, 21:50 CET\n\nTrail of Bits confirms they are going to followup with Binance and they agree to extend the embargo by a week.\n\n### 8 December 2021, 15:16 CET\n\nTrail 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.\n\n### 10 December 2021, 8:16 CET\n\nBinance merges our fix https://github.com/binance-chain/tss-lib/commit/cd95cee01ea2af6d4aa8316612803be944d5369a\n\n### 13 December 2021, 8:35 CET\n\nBinance applies more fixes so that even in case of `LocalPartySaveData` corrupted, the code is not going to panic.\n\n### 15 December 2021\n\nThe team releases a new version of the client, v1.8.1, and announces the need for an upgrade.\nhttps://github.com/keep-network/keep-ecdsa/releases/tag/v1.8.1",
  "severity" : [ ],
  "affected" : [ {
    "package" : {
      "ecosystem" : "Go",
      "name" : "github.com/keep-network/keep-ecdsa"
    },
    "ranges" : [ {
      "type" : "ECOSYSTEM",
      "events" : [ {
        "introduced" : "0"
      }, {
        "fixed" : "1.8.1"
      } ]
    } ]
  } ],
  "references" : [ {
    "type" : "WEB",
    "url" : "https://github.com/keep-network/keep-ecdsa/security/advisories/GHSA-gp6j-vx54-5pmf"
  }, {
    "type" : "PACKAGE",
    "url" : "https://github.com/keep-network/keep-ecdsa"
  }, {
    "type" : "WEB",
    "url" : "https://github.com/keep-network/keep-ecdsa/releases/tag/v1.8.1"
  } ],
  "database_specific" : {
    "cwe_ids" : [ ],
    "severity" : "CRITICAL",
    "github_reviewed" : true,
    "github_reviewed_at" : "2022-01-04T22:41:52Z",
    "nvd_published_at" : null
  }
}