Review c-split vulnerability from TSS Shock

[tmpfs]

As this library was built on top of the ZenGo library I assume it is also vulnerable to the c-split attack documented here:

https://www.verichains.io/tsshock/

Can somebody verify this please?

[drewstone]

I am investigating, could use more eyes too as I'm unsure where to add more iterations as specified @tmpfs.

[drewstone]

@tmpfs curious your thoughts. After investigating these libraries are using zk_pdl_with_slack and not zk_pdl that seems to have the issue described in the tsshock. In the slack based protocol it doesn't seem to contain any challenge here or SHA256 hash as specified in the attack, though I do see the issue in the regular zk_pdl implementation.

[drewstone]

Here's a WIP of the new DLog proof based off BNB tss-lib

https://github.com/webb-tools/cggmp-threshold-ecdsa/blob/drew/dlnproof/src/utilities/dlnproof/mod.rs

Still not working but please take a look if interested. CC @tmpfs @davidsemakula.

Point of confusion

One area I'm confused about is in the generation of these values. It seems that different libraries take different approaches.

Zengo Generates $h1,h2,\tilde{N}$ using safe primes. Then in key generation, generates an entirely separate Paillier key.

pub fn generate_h1_h2_N_tilde() -> (BigInt, BigInt, BigInt, BigInt, BigInt) {
    // note, should be safe primes:
    let (ek_tilde, dk_tilde) = Paillier::keypair_safe_primes().keys();
    // let (ek_tilde, dk_tilde) = Paillier::keypair().keys();
    let one = BigInt::one();
    let phi = (&dk_tilde.p - &one) * (&dk_tilde.q - &one);
    let h1 = BigInt::sample_below(&ek_tilde.n);
    let (mut xhi, mut xhi_inv) = loop {
        let xhi_ = BigInt::sample_below(&phi);
        match BigInt::mod_inv(&xhi_, &phi) {
            Some(inv) => break (xhi_, inv),
            None => continue,
        }
    };
    let h2 = BigInt::mod_pow(&h1, &xhi, &ek_tilde.n);
    xhi = BigInt::sub(&phi, &xhi);
    xhi_inv = BigInt::sub(&phi, &xhi_inv);

    // xhi ~ alpha, xhi_inv ~ beta (as specified in binance tss-lib)
    (ek_tilde.n, h1, h2, xhi, xhi_inv)
}

pub fn create_safe_prime(index: usize) -> Self {
    let u = Scalar::<Secp256k1>::random();
    let y = Point::generator() * &u;

    let (ek, dk) = Paillier::keypair_safe_primes().keys();
    let (N_tilde, h1, h2, xhi, xhi_inv) = generate_h1_h2_N_tilde();

    Self { u_i: u, y_i: y, dk, ek, party_index: index, N_tilde, h1, h2, xhi, xhi_inv }
}

Binance BNB Uses the same primes from what it looks like to generate everything.

P, Q := sgps[0].SafePrime(), sgps[1].SafePrime()
NTildei := new(big.Int).Mul(P, Q)
modNTildeI := common.ModInt(NTildei)

p, q := sgps[0].Prime(), sgps[1].Prime()
modPQ := common.ModInt(new(big.Int).Mul(p, q))
f1 := common.GetRandomPositiveRelativelyPrimeInt(NTildei)
alpha := common.GetRandomPositiveRelativelyPrimeInt(NTildei)
beta := modPQ.ModInverse(alpha)
h1i := modNTildeI.Mul(f1, f1)
h2i := modNTildeI.Exp(h1i, alpha)

preParams := &LocalPreParams{
    PaillierSK: paiSK,
    NTildei:    NTildei,
    H1i:        h1i,
    H2i:        h2i,
    Alpha:      alpha,
    Beta:       beta,
    P:          p,
    Q:          q,
}

[davidsemakula]

@drewstone been a bit too busy elsewhere but will make some time and review this and the PR around the end of the week.

[davidsemakula]

One area I'm confused about is in the generation of these values. It seems that different libraries take different approaches. Zengo Generates $h1$, $h2$, $\tilde N$ using safe primes. Then in key generation, generates an entirely separate Paillier key. ... Binance BNB Uses the same primes from what it looks like to generate everything.

@drewstone ZenGo's approach would be the "correct" one according to GG18 (emphasis is mine)

Therefore our initialization protocol must be augmented with each player $Pi$ generating an additional RSA modulus $\tilde N i$, and values $h1_i$, $h2_i$, together with a proof that they are of the correct form

I haven't reviewed the Binance tss-lib implementation though, so I'm just going by what you've shared here. I also haven't reviewed related papers to understand if reusing these values would make the protocol insecure.

[davidsemakula]

After investigating these libraries are using zk_pdl_with_slack and not zk_pdl that seems to have the issue described in the tsshock. In the slack based protocol it doesn't seem to contain any challenge here or SHA256 hash as specified in the attack, though I do see the issue in the regular zk_pdl implementation.

@drewstone @tmpfs I think zk_pdl was added for Lindel17 (though it doesn't seem to be using it either) not GG18/20 AFAICT.

Focusing on only GG18/20, c-split would be concerned with the discrete log proof for $h_1$ and $h_2$ not zk_pdl_with_slack directly (although zk_pdl_with_slack depends on these parameters being set up correctly). But, since this library only uses GG20 (AFAIK), the rest of my analysis will only focus on GG20.

From GG20 (Section 2.10):

We note that these proofs make use of Fujisaki-Okamoto commitments, and therefore the appropriate setup procedure must be followed. In practice, it suffices for the verifier to generate the parameters, $\tilde N$, $h_1$, $h_2$ and prove the the discrete log between $h_1$ and $h_2$ exist.

From TSSHOCK paper (Section 2.2):

dlnproof is used to verify, in zero-knowledge manner, that a prover knows $\log_g h$ modulo a composite number $N$. At the key generation ceremony, each party is required to generate and broadcast a triple $\tilde N$, $h_1$, $h2$, which is later used in subsequent signing ceremonies, together with a dlnproof proving that the party knows $\log{h_2} h1 \bmod \tilde N$. Some implementations also require an additional dlnproof for $\log{h_1} h_2 \bmod \tilde N$.

From TSSHOCK article (Section 2.2):

2.2 Use a larger challenge space (similar to Schnorr's Protocol - Proof of Knowledge of Discrete Log) and eliminate dlnproof iteration Optimize the scheme without proving its soundness error is negligible. Some TSS libraries optimized the algorithm for dlnproof by choosing the challenge to be 256 bits and running only one time. This is similar to discrete log proof for a group of prime order. But in GG, the group order, phi(N), is not a prime number but a composite number. Hence making our third key extraction attack, c-split, possible.

The above is the section of Verichain's article that lists ZenGo's multi-party-ecdsa as vulnerable to c-split.

However, for the GG20 implementation in ZenGo's multi-party-ecdsa, the dlnproof implementation for $h_1$ and $h_2$ modulo $\tilde N$ uses Pointcheval's "composite discrete logarithm proof" (see here and here) which is specifically built for composite group orders and for a single iteration.

In this paper, we investigate, for the first time, the witness-indistinguishable protocols provided by the discrete logarithm problem with a composite modulus. ... Here, we prove the security of this scheme, even against active attacks, after only one iteration of the protocol, using the witness-indistinguishable property.

I'll note that TSSHOCK makes no mention of Pointcheval's proof and/or its soundness for this use case.

However, it's also notable that the generate_h1_h2_N_tilde function is not using safe primes and that's possibly an attack vector as Pointcheval's proof assumes an RSA modulus. So as it stands, it's not clear if this is the vector exploited by Verichains according to their report.

It's also important to note that the multi-party-ecdsa library implements many protocols (i.e. GG20, GG18, Lindell17 e.t.c) and the Verichains article doesn't explicitly say which protocol it found vulnerable (and the PoC for the attack is not currently publicly available).

I've reached out to Verichains for more info, but it looks to me like the focus (at least for now) should be on the composite discrete log proofs and using safe primes in generate_h1_h2_N_tilde not zk_pdl_with_slack in this particular case.

[drewstone]

Agreed my initial analysis was wrong and you're correct it has more to do with the composite dlog proof that we should focus on.

I tried to reach out to Verichains as well to ask where exactly they identified the vulnerability but haven't heard back. Maybe @ivokub can message his direct contact?

[davidsemakula]

@drewstone FYI, I did get an initial response (rather quickly as well 🙂), I'll share here when we get to a satisfactory/useful conclusion about the use of Pointcheval's proof for this use case.

[davidsemakula]

@drewstone @tmpfs conclusion after reviewing feedback from one of the TSSHOCK authors and having a closer look at both c-split and Pointcheval's proof is that the GG20 implementation is vulnerable.

Feedback from one of the TSSHOCK authors:

The key point to understand why applying the Pointcheval protocol in this case is a disaster: It is intended for proving identity, meaning (N~, h1, h2) are chosen by an honest user or a trusted 3rd party, so an attacker should not be able to forge log(h1, base=h2, mod=N~), while in our case, the attacker is able to choose (N~, h1, h2) in a way that enables her/him to forge proof.

To this, I'll add that the Pointcheval protocol requires that $g$ is an asymmetric basis of $\mathbb{Z}^ \ast _N$ of order greater than $2^k$ during its initialization, and no such check/proof is performed in ZenGo's GG20 implementation to allow for initialization in an adversarial setting.