Baby Sharks

Injecting small order points to threshold EdDSA

Background

Curve25519 has the following group structure: P = bB + tT , where B is a generator of a subgroup of prime order L, and T is a small torsion point which generates a small subgroup of order 8. Curve25519 has a complete twisted Edwards addition which makes Elliptic Curve Cryptography atop Curve25519 very efficient.

A known fact, proven time and time again is that for ECC applications to be secure it is important to only work with points P such that t=0:

1. Ed25519, or EdDSA over curve25519 is designed to eliminate any group element from the small subgroup. However, recent publications showed that by deliberately injecting such elements as part of the public key, a discrepancy can be created between different verification implementations, which in theory can put consensus algorithm into a halt, breaking liveness (i.e if half the validators think a signature is valid and half think its invalid)
2. Monero blockchain had a double spend bug because a “tag” point intended to signal that a specific private key was already used, had a malleability induced by the small subgroup which the Monero verification code could not detect
3. In simple two party protocols such as ECDH (key exchange) it is known that a counterparty must check that a received point is in the subgroup of prime order, otherwise, some bits of its secret will get leaked. One of our favorite examples is the Simplest OT paper that handles communication of group elements by eliminating the torsion point.

Higher level protocols based on Curve25519

There is not yet a systematic study on how to handle the co-factor in a higher level protocols such as MPC, ZK proofs etc.. There is no standard for those, however, we start to see implementations of involved protocols that use curves with co-factors :

• MPC: Threshold EdDSA (here, here and here)
• ZK: Zcash zk-snark with BLS12–381 or Concordium Bulletproofs on top of BLS12–381

In a multiparty protocol, all honest parties will use valid points and an adversary might try to inject some small subgroup elements.

Bypassing Security in tss-lib

We showcase one example of how an attacker can inject a low order subgroup group element in threshold EdDSA protocol secure against malicious adversaries, bypassing existing protections.

Tss-lib is Binance’s threshold signatures library, which includes threshold ECDSA and threshold EdDSA implementations. It is a production grade library, used by many projects in the blockchain space.

The code for threshold EdDSA includes three parts: distributed key generation (DKG), distributed signing and secret re-sharing. Let us describe the protocols in high level:

DKG: Each party samples a random secret and uses it as a 0-coefficient in a Feldman VSS (verifiable secret sharing) scheme. As a result each party generates a commitment vector of group elements that hides and binds the coefficients.

• In the first round the parties send commitments to their VSS coefficient commitment vector
• In the next round each party sends a commitment to the vector (revealing the VSS commitment vector) and a EC-DLog proof of knowledge for x ᵢ : that party’s secret, with respect to the first coefficient in the commitment (X ᵢ = x ᵢ B). Each party Pᵢ will also send a p2p message to each other party with a secret share of xᵢ
• In the third and final round, each party checks the decommitments and proofs of knowledge from all other parties and sums the secret shares it received and outputs the public key as the sum X₁+ X₂ +… +Xn

Signing: An ephemeral point R is generated by a round of commitments to Rᵢ followed by a round of decommitments and EC-DLog proof of knowledge of rᵢ such that R ᵢ = rᵢ B

Re-sharing: Same as DKG but the 0-coefficient of each party is its old secret share

The attack

The attacker goal is to inject a small group element into the joint public key:

X = X₁ +X₂+…+Xn + T

This will cause some verification implementations to accept any signature generated by the protocol while other implementations will reject (The verification protocol used in tss-lib will accept with probability 1/8). However, since tss-lib threshold EdDSA protocol is secure against malicious adversaries,this injection should not be possible; To see why, remember that the parties must prove knowledge (using ZK DLog proof of knowledge) of the DLog of X ᵢ + T in base B (the generator of the prime order group). Since this DLog does not exist and the proofs are sound, an attacker shouldn’t be able to inject T into the public key.

Bypassing the DLog proof of knowledge

Let’s start with a honest Schnorr proof of knowledge, as implemented in tss-lib:

• Prover knows Q=x ᵢ B
• Prover picks random point A = r B
• Prover computes e = Hash(Q, B, A) (Fiat Shamir)
• Prover computes z = ex ᵢ + r
• Verifier receives (Q,A,z), computes e and checks zB = eQ + A

Now let’s assume the prover is our attacker and it chooses Q = x ᵢB + T. Repeating the proof and subtracting the honest part we are left with 0 =? eT which will work if eT=0 which happens with probability ⅛.

In total, it seems that with probability (⅛)² the attacker will be able to inject T into the public key and pass a given signature verification¹.

Mitigation and future research

The result above is actually not surprising, because a Schnorr proof can be viewed as a Schnorr signature. We do believe that more complex zk proofs will have similar pitfalls and hope that our example and other existing implementations using curves with co-factors will ignite research in this direction.

To mitigate the attack in our example there are few well known techniques. Since higher level protocols usually don’t try to optimize for microseconds or even milliseconds we suggest to simply multiply each received group element with 8, followed by a multiplication by inverse of 8. This is a costly yet effective and intuitive way to sanitize low order group elements².

The bug was responsibly disclosed to Binance and was fixed according to our recommendation.

Acknowledgments

We would like to thank Claudio Orlandi for his help discovering the bug and insightful comments

Appendix : Polychain labs threshold validator

Recently, Polychain labs open-sourced their code for threshold EdDSA Tendermint validator. For convenience, this commit highlights the changes from the single party validator. The threshold scheme is said to be based on Stinson&Strobl threshold Schnorr paper. The protocol from the paper is similar in spirit to the tss-lib protocol we analyzed above, by means of security against malicious adversary using the same cryptographic building blocks. This in turn requires parties to receive EdDSA points from untrusted counter parties.

As with tss-lib, we found no protection against injecting small group elements. We note that in the use case of a validator — a rejected validation signature might result in punishing the validator.

To be fair, Polychain labs code seems to operate in the semi-honest adversary model in which our attack do not work. However this model is no good fit for real world applications.

¹ In fact, the attacker can also control the point A and bias it with a low order element : A’ = A + T₂.

² Multiplying the point under test by the order of the prime subgroup L and check equality to zero is another way. It is comparable in cost to our preferred method stated above but it is less intuitive because although the point at infinity is well defined, implementations tend to interpret it differently.