This is a suggestion only. Given that structure fields are only private on a
package level in golang, this may not make sense to implement. In particular
if consuming packages are free to modify the internal fields of the structure
at any point, then IsOnCurve may need to be called to check the structure
has not been altered into an invalid state.

The structure ECPoint represents a point on a given curve. Currently a method
exists such that one can:

    point := NewECPoint(P256(), x, y)
    if !point.IsOnCurve() {
        // report error
    }

This relies on the programmer remembering to call IsOnCurve. We see such checks
in the code:

https://github.com/binance-chain/tss-lib/blob/f90989ed35aa3f016ea35623c6faa697d9fb64a7/crypto/schnorr/schnorr_proof_test.go#L20

https://github.com/binance-chain/tss-lib/blob/f90989ed35aa3f016ea35623c6faa697d9fb64a7/crypto/mta/proofs.go#L173

https://github.com/binance-chain/tss-lib/blob/f90989ed35aa3f016ea35623c6faa697d9fb64a7/crypto/vss/feldman_vss_test.go#L36

https://github.com/binance-chain/tss-lib/blob/f90989ed35aa3f016ea35623c6faa697d9fb64a7/ecdsa/keygen/round_3.go#L127

but for defensive coding purposes we recommend not allowing the construction
of an invalid curve point. This can be done by changing NewECPoint to validate
and return an error:

func isOnCurve(c Curve, x, y *big.Int) bool {
  if x == nil || y == nil {
    return false
  }
  return c.IsOnCurve(x,y)
}

func (p *ECPoint) IsOnCurve() bool {
    return isOnCurve(p, p.coords[0], p.coords[1])
}

func NewECPoint(curve elliptic.Curve, X, Y *big.Int) *ECPoint, error {
  if !isOnCurve(curve, X, Y) {
        return nil, fmt.Errorf("Your error message here")
    }
    return &ECPoint{curve, [2]*big.Int{X, Y}}, nil
}

The unmarshal function UnmarshalJSON can likewise call isOnCurve to
validate the point.

threshold = 2, full = 3
After signing by user A, the signing result is sent to user B, and user B completes the final signature.
Can tss-lib achieve this function?

In hash.go, int is used as an identifier in for i, int := range in. Although int is not a reserved keyword in the Go language, such a mix between type and variable identifier can be confusing.

Here the for loop depends on the condition zero.Cmp(q) == -1, however neither q nor zero are modified
inside the loop, so this check can be moved out of the loop:

func RejectionSample(q *big.Int, eHash *big.Int) *big.Int { // e' = eHash
	qBits := q.BitLen()
	// e = the first |q| bits of e'
	e := firstBitsOf(qBits, eHash)
	// while e is not between 0-q
	for !(e.Cmp(q) == -1 && zero.Cmp(q) == -1) {
		eHash := SHA512_256i(eHash)
		e = firstBitsOf(qBits, eHash)
	}
	return e
}

Steven has informed us that we might be able to pre-compute the primes and re-use them per player across multiple keygens.

This would solve two issues: the fact that we are not using proper safe primes, and the computational cost of calculating them from scratch on each keygen round.

Initial audit feedback:

GetRandomGeneratorOfTheQuadraticResidue() assumes safe primes

It seems the function GetRandomGeneratorOfTheQuadraticResidue() used in GenerateNTildei() works only if its input
is the product of two safe primes, that is primes of the form p = 2q+1 for q another prime.

But the primes used in GenerateNTildei() are coming from its arguments and in
keygen/round_1.go, it appears the primes are generated using rsa.GenerateMultiPrimeKey() are not safe primes.

可以提供带网络的demo吗？

sev: mid

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/common/random/random.go#L35

If the lessThan argument is negative, then GetRandomPositiveInt() will
loop forever, as the condition try.Cmp(lessThan) < 0 will never be
satisfied.

See PoC at https://play.golang.org/p/sqxDsvzM944

We recommend to check that lessThan is positive.

Some minor work has already been done in the wasm branch but it would be great to finish this

tss-lib BIP-32 integration

There are different cases in terms of integrating BIP-32 into tss-lib.

One is, we keep the keygen process as previous, but we can provide "path" when we are signing. The signature will be corresponding to the derived child key.

Another one is, we can derive the "child key_share"s from the "parent key_share"s, so that we can distribute the "child key_share"s to other people.

Here I would just briefly explain the first one as follows.

Clarification

We omit the details of BIP32 and GG18 here. But since

• to derive hardened children keys, we will need to know the parent private key
• in TSS use cases, we usually won't re-construct the full private key

So this document only works for non-hardened derived keys.

Basic Idea

Let $G$ be the base point of the curve, $P$ be the parent public key,

$I$ be as described in https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#private-parent-key--private-child-key,

$I_r$ is the right half of $I$, $I_l$ is the left half of $I$.

Then $I_r$ is the chaincode for each depth;

$I_l$, i.e, $\delta$, is the shift introducded by hierarchy levels, then

$$P_{child} = P + \delta * G$$

child private key: $$x_{child} = x + \delta = sum(u_i) + \delta$$

That means we will need one of the parties to change his $u_i$ to $u_i + \delta$. We call such a party as the leader.

Moreover, the VSS commitment to the polynomial should also be changed from

$$p(x) = a_0 + a_1 * x + a_2 * x^2 + ... + a_t * x^t \mod q$$

to

$$p'(x) = (a_0 + \delta) + a_1 * x + a_2 * x^2 + ... + a_t * x^t \mod q$$

Implementation Example

Can refer to:

• https://github.com/cryptochill/tss-ecdsa-cli
• https://github.com/trepca/multi-party-ecdsa/tree/hd-support

As aforementioned, we would need a leader.

• we can derive the derived_public_key from the master_public_key using path, see https://github.com/cryptochill/tss-ecdsa-cli/blob/master/src/common/hd_keys.rs, f_l_new is useful later
• we will need to replace leader's VSS as in https://github.com/cryptochill/tss-ecdsa-cli/blob/master/src/common/signer.rs#L89-L118
• we would need to update u_i and x_i for leader, but we only need to update x_i for non-leaders, as in https://github.com/cryptochill/tss-ecdsa-cli/blob/master/src/common/signer.rs#L123-L130
  • some of these values in binance's tss-lib are not stored permanently, but discarded after keygen. May need to make some changes and store them.

In the signing round 1, the value round.temp.point is stored, but in round 4 and in round 5, the bigGamma value and the RX, RY values respectively are re-computed from the round.temp.gamma value, instead of being retrieved from the round.temp.point variable from round 1.

Since this implies modular exponentiations, performances could be improved by using the stored value.

Implement initial version of Dynamic Group.

currently this library doesn't support
https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki key derivation directly

I understand that this lib only severs as the purpose of TSS, but it will be awesome if adding such a support
e.g.,
each party using their own derived secret can also perform DKG & TSS
and the consequent commitment corresponds to the derivation of the original commitment.

Original scenario:

secrect A -------------------
                            |
secrect B --------------- keygen ------------- commitment X
                            |
secrect C -------------------

Derived:

child secrect A' ------------------
                                  |
child secrect B' --------------- keygen ------------- commitment X'
                                  |
child secrect C' ------------------

if A' & B' & C' are derived from A, B, C respectively, using the same derivation path, the X' is expected as the derived from X using the same path.

An ECPoint struct is defined as:

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/crypto/ecpoint.go#L16-L19

Hence the coords array will always be of size 2, as enforced by the Go language. The condition len(p.coords) == 2 below is therefore always true, thus can be omitted:

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/crypto/ecpoint.go#L62-L64

In crypto/mta/proofs.go, on lines 93 and 161 you compute:

eHash = common.SHA512_256i(append(pk.AsInts(), X.X(), X.Y(), c1, c2, pf.Z, pf.ZPrm, pf.T, pf.V, pf.W)...)

But it is missing one component in that hash: namely u = g^alpha (notice the Full Spec has a typo in Figure 10 line 1 of VerifyMtA_Bob, as it's including u in the verification, even though it has no u in the MtA case. But Fig. 11 clearly and correctly includes the u in both case)

This effectively "unlinks" the consistency from the MtAwc, but maybe not in a dramatic way.
However, this should be fixed.

sev: mid

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/common/random/random.go#L64

If the n argument is negative, then
GetRandomPositiveRelativelyPrimeInt will loop forever, as the
condition v.Cmp(n) < 0 in IsNumberInMultiplicativeGroup() is never
satisfied.

We recommend to check that n is positive, and also that
IsNumberInMultiplicativeGroup checks the validity of its argument
(being a method visible outside of the package).

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/common/random/random.go#L73

See PoC at https://play.golang.org/p/NeejDhqUWOb

tss-lib points to the github.com/golang/protobuf v1.3.2 dependency in the go.mod file. However, according to Go modules version selection policy all versions of protobuf >= v1.3.2 and < v2 can be picked if present in the module list.

This can be a problem because tss-lib protobuf messages are registered twice which causes a registration conflict. The first registration occurs in the generated *.pb.go files and then the second registration is performed in messages.go files.

Example for the ecdsa/keygen package:

• First registration: https://github.com/binance-chain/tss-lib/blob/abd66f888438ead112891bc3d74d04d09b94446f/ecdsa/keygen/ecdsa-keygen.pb.go#L235
• Second registration: https://github.com/binance-chain/tss-lib/blob/abd66f888438ead112891bc3d74d04d09b94446f/ecdsa/keygen/messages.go#L35

The github.com/golang/protobuf v1.3.2 doesn't complain but the newer github.com/golang/protobuf v1.4.0 displays a warning:

2020/08/05 14:43:02 WARNING: proto: message KGRound1Message is already registered
A future release will panic on registration conflicts. See:
https://developers.google.com/protocol-buffers/docs/reference/go/faq#namespace-conflict

sev: intended behavior?

The SHA512_256() function takes of list of byte arrays as arguments and creates the data to be hashed by separating these data blocks with a $ character.

Since the byte arrays can also include this character, different sets of inputs can hash to the same value.

For example, is in is the single array [a,$,b,$]*, then the hash result will be the same as when in is the two arrays [a] and [b].

A non-ambiguous encoding should be used to prevent this, for example by adding an encoding of the block length for each of the blocks processed.

Including a prefix containing the block count would be a great preventative measure.

sk:01d62035da1803bc0520da4158ca1a118d685a5b2d7ec054ad0ed603537ad5df67
pk:f024efe7d7c1ac5f22dd45a4778a804f37bfd313e9ca6bc9071f304047143a18

Why the generated private key is 33 bytes，the private key has 01 bytes in front of it. I don't understand why. thanks

why
https://github.com/binance-chain/tss-lib/blob/4fcd04b0ce5527ece51afa70c7852b5fd03b120c/ecdsa/signing/finalize.go#L59

instead of

sig := btcec.Signature{
	R: new(big.Int).SetBytes(round.data.R),
	S: new(big.Int).SetBytes(round.data.S),
}
round.data.Signature = sig.Serialize()

such serialization also passes the test case in local_party_test.go

signature, err := btcec.ParseSignature(sig.Serialize(), btcec.S256())
if err != nil {
	t.Log("parse secp256k1 signature failed")
}

if !signature.Verify(big.NewInt(42).Bytes(), pubKey) {
	t.Log("errVerifyFail")
}

pubKey is

pkX, pkY := keys[0].ECDSAPub.X(), keys[0].ECDSAPub.Y()
pk := ecdsa.PublicKey{
	Curve: tss.EC(),
	X:     pkX,
	Y:     pkY,
}

pubKey, err := btcec.ParsePubKey((*btcec.PublicKey)(&pk).SerializeCompressed(), btcec.S256())
if err != nil {
	t.Log("parse secp256k1 public key failed")
}

I read the doc here,

and there are tss client:

./tss describe

> please set vault of this party:
[input vault name]
> Password to sign with this vault:
[input password]
address of this vault: bnb1
config of this vault:

And how should I do to get the tss?

4.1 Key generation protocol in GG18spec is as below.
  values Xi = g ^ xi are public.
But is the code only modulo?
round.save.Xi = new (big.Int) .Mod (xi, tss.EC (). Params (). N)

https://github.com/binance-chain/tss-lib/blob/1e5e2dd5ed1da5f0ad67665f0fedd08e555b00ff/ecdsa/keygen/round_3.go#L44

On line 38, the err value is not checked, but if EncryptAndReturnRandomness returns with the ErrMessageTooLong error, then both cBetaPrm and cRand would be nil, which it turns would make pkA.HomoAdd(cB, cBetaPrm) panic on nil pointer dereference.

https://github.com/binance-chain/tss-lib/blob/master/crypto/mta/share_protocol.go#L38

As a user of the library has to store the key generation output keygen.LocalPartySaveData it would be helpful to expose functions to marshal and unmarshal this struct.

What are your thoughts on adding such functions?

sev: mid

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/common/random/random.go#L23

The bits argument should be checked for acceptable value:

• Upon negative value, rand.Int() will panic
• Upon very long value rand.Int will take a long time

See PoC at https://play.golang.org/p/y-wjDiIK374

We recommend to check that bits is strictly positive and below a certain
bound defined as a constant

In ecpoint.go, there are unhandled errors on Read, Write and (*Int) GobDecode. This should not be a security concern, but it would be better to handle them. Especially for the GobDecode one, as the encoding version can change, causing it to be incompatible.

If an attacker's goal is to find the hash corresponding to some (unknown) secret parts, they may leverage the variable-time comparator in Verify().
The execution time of Verify() can also leak the result of the function to an observer.

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/crypto/commitments/commitment.go#L47-L58

Here hash.Cmp(C) calls big/nat.go's cmp(), which compares bigInt's value Word per Word.
This is unlikely to be a security issue though.

First Version of TSS Signing

Thank you for open sourcing this library.

Is there a bug bounty program for this library?
What would be a proper channel to communicate vulnerabilities?

mta.BobMid and mta.BobMidWC share a couple of lines of codes, I guess we can actually combine them?

i.e.
https://github.com/binance-chain/tss-lib/blob/e860e36eaaa63afcaf1e5a0ed79b6f56362e88c8/crypto/mta/share_protocol.go#L36-L54

and
https://github.com/binance-chain/tss-lib/blob/e860e36eaaa63afcaf1e5a0ed79b6f56362e88c8/crypto/mta/share_protocol.go#L65-L83

Something like a check like this at the start of Create in feldman_vss.go

if threshold < 1 {
    return nil, nil, errors.New("vss threshold < 1")
}

The verification function checks that arguments are not nil:

func (pf *RangeProofAlice) Verify(pk *paillier.PublicKey, NTilde, h1, h2, c *big.Int) bool {
  if pf == nil || pk == nil || NTilde == nil || h1 == nil || h2 == nil || c == nil {
    return false
  }
...

However the proof creation does not perform any such checks (and might fail upon nil values when performing arithmetic operations):

func ProveRangeAlice(pk *paillier.PublicKey, c, NTilde, h1, h2, m, r *big.Int) *RangeProofAlice {
  q := tss.EC().Params().N
  q3 := new(big.Int).Mul(q, q)
  q3 = new(big.Int).Mul(q, q3)
  ...

We recommend to add nil checks for extra safety.

Golang's big package provides multiprecision integer arithmetic similar to
libgmp or libmpir. However, big.Int does not operate in constant time.

All big.Int.Exp() implementations
thus potentially leak timing information.

Recommendations: Golang's RSA package is similarly vulnerable and in order to
mitigate it, applies blinding
in decryption operations. Decrypt functionality in the Paillier cryptosystem
may apply similar techniques. An issue is open in the golang repository to
support constant-time arithmetic
but there is little progress.

When running GeneratePreParams on machines with less than 3 CPUs the process timeouts as the generation goroutines are not being started.
It happens when optionalConcurrency is not provided so the runtime.NumCPU() is invoked, or when optionalConcurrency is less than 3.

A number of concurrent execution is taken from runtime.NumCPU():
https://github.com/binance-chain/tss-lib/blob/efd7f5ab41d31ade2dbc274371d07fb1b0dd2512/ecdsa/keygen/prepare.go#L39

Next, this value is divided by 3, which gives us 0 and passed to generate functions:
https://github.com/binance-chain/tss-lib/blob/efd7f5ab41d31ade2dbc274371d07fb1b0dd2512/ecdsa/keygen/prepare.go#L51
https://github.com/binance-chain/tss-lib/blob/efd7f5ab41d31ade2dbc274371d07fb1b0dd2512/ecdsa/keygen/prepare.go#L65

As a result, prime generation routines are not started:
https://github.com/binance-chain/tss-lib/blob/efd7f5ab41d31ade2dbc274371d07fb1b0dd2512/common/safe_prime.go#L144-L149

#108, #109, #112 and #113 fail the github CI.

However, tests pass if I run make test_unit and test_unit_race locally.

$make test_unit
--> Running Unit Tests
!!! WARNING: This will take a long time :)
go test -timeout 20m github.com/binance-chain/tss-lib/common github.com/binance-chain/tss-lib/crypto github.com/binance-chain/tss-lib/crypto/commitments github.com/binance-chain/tss-lib/crypto/dlnproof github.com/binance-chain/tss-lib/crypto/mta github.com/binance-chain/tss-lib/crypto/paillier github.com/binance-chain/tss-lib/crypto/schnorr github.com/binance-chain/tss-lib/crypto/vss github.com/binance-chain/tss-lib/ecdsa/keygen github.com/binance-chain/tss-lib/ecdsa/resharing github.com/binance-chain/tss-lib/ecdsa/signing github.com/binance-chain/tss-lib/eddsa/keygen github.com/binance-chain/tss-lib/eddsa/resharing github.com/binance-chain/tss-lib/eddsa/signing github.com/binance-chain/tss-lib/test github.com/binance-chain/tss-lib/tss
ok    github.com/binance-chain/tss-lib/common  56.981s
ok    github.com/binance-chain/tss-lib/crypto  0.099s
ok    github.com/binance-chain/tss-lib/crypto/commitments  0.015s
?     github.com/binance-chain/tss-lib/crypto/dlnproof  [no test files]
ok    github.com/binance-chain/tss-lib/crypto/mta  134.237s
ok    github.com/binance-chain/tss-lib/crypto/paillier  82.473s
ok    github.com/binance-chain/tss-lib/crypto/schnorr  0.173s
ok    github.com/binance-chain/tss-lib/crypto/vss  0.269s
ok    github.com/binance-chain/tss-lib/ecdsa/keygen  457.716s
ok    github.com/binance-chain/tss-lib/ecdsa/resharing  511.729s
ok    github.com/binance-chain/tss-lib/ecdsa/signing  103.261s
ok    github.com/binance-chain/tss-lib/eddsa/keygen  193.417s
ok    github.com/binance-chain/tss-lib/eddsa/resharing  169.153s
ok    github.com/binance-chain/tss-lib/eddsa/signing  8.254s
?     github.com/binance-chain/tss-lib/test  [no test files]
?     github.com/binance-chain/tss-lib/tss  [no test files]

$make test_unit_race
--> Running Unit Tests (with Race Detection)
!!! WARNING: This will take a long time :)
go test -timeout 30m -race github.com/binance-chain/tss-lib/common github.com/binance-chain/tss-lib/crypto github.com/binance-chain/tss-lib/crypto/commitments github.com/binance-chain/tss-lib/crypto/dlnproof github.com/binance-chain/tss-lib/crypto/mta github.com/binance-chain/tss-lib/crypto/paillier github.com/binance-chain/tss-lib/crypto/schnorr github.com/binance-chain/tss-lib/crypto/vss github.com/binance-chain/tss-lib/ecdsa/keygen github.com/binance-chain/tss-lib/ecdsa/resharing github.com/binance-chain/tss-lib/ecdsa/signing github.com/binance-chain/tss-lib/eddsa/keygen github.com/binance-chain/tss-lib/eddsa/resharing github.com/binance-chain/tss-lib/eddsa/signing github.com/binance-chain/tss-lib/test github.com/binance-chain/tss-lib/tss
ok    github.com/binance-chain/tss-lib/common  109.241s
ok    github.com/binance-chain/tss-lib/crypto  3.057s
ok    github.com/binance-chain/tss-lib/crypto/commitments  0.042s
?     github.com/binance-chain/tss-lib/crypto/dlnproof  [no test files]
ok    github.com/binance-chain/tss-lib/crypto/mta  560.327s
ok    github.com/binance-chain/tss-lib/crypto/paillier  323.040s
ok    github.com/binance-chain/tss-lib/crypto/schnorr  3.184s
ok    github.com/binance-chain/tss-lib/crypto/vss  3.489s
ok    github.com/binance-chain/tss-lib/ecdsa/keygen  1607.806s
ok    github.com/binance-chain/tss-lib/ecdsa/resharing  1756.956s
ok    github.com/binance-chain/tss-lib/ecdsa/signing  236.149s
ok    github.com/binance-chain/tss-lib/eddsa/keygen  1719.769s
ok    github.com/binance-chain/tss-lib/eddsa/resharing  1535.071s
ok    github.com/binance-chain/tss-lib/eddsa/signing  90.409s
?     github.com/binance-chain/tss-lib/test  [no test files]
?     github.com/binance-chain/tss-lib/tss  [no test files]

It seems that it's because the test jobs were killed if it takes too long.

The modular arithmetic defined on top of big.Int does a lot of new(big.Int) in order to use big.Int methods, however these incur superfluous memory allocations, which may have an impact on performance when many operations are done. For example in:

func (mi *modInt) Add(x, y *big.Int) *big.Int {
  i := new(big.Int).Add(x, y)
  return new(big.Int).Mod(i, mi.i())
}

Here, three big.Int structs are allocated whereas one would be sufficient, for example by doing:

func (mi *modInt) Add(x, y *big.Int) *big.Int {
  i := new(big.Int)
  i.Add(x, y)
  return i.Mod(i, mi.i())
}

The allocation issue may be benign, but at scale if you're on a server with a lot of requests and CPU usage this makes a difference (encountered similar issues with byte arrays to string conversions and comparisons)

The signed message is not hashed

Currently the message is not hashed in round_1.go (this is even explicitely written in the comments on lines 21-22),
instead it is simply passed as a big.Int, without even checking it's in Z_q.
This means it is trivial to forge messages that match a signature for a previous message,
as it allows to find collisions easily.

Not hashed: I deliberately leave it to tss repo because different blockchain has different hash function. i.e. Ethereum Keccak-256 and Bitcoin sha256. The reason is to make tss-lib as much as flexible and doesn't need to cope with different hashing strategy for different blockchains.
Checking in Z_q: I will check it's in Z_q in the fix.
Find collisions: What do you mean?

Discrepancy in Finalize

In the last part of the signature generation protocol, each party is supposed to verify the final signature it computed
verifies under the group public key.
This is not the case currently, as such, any malicious party could make the group reconstruct invalid signatures.
Notice that also the reference paper states this check as necessary, as the signing procedure can potentially produce invalid signatures.

Sorry, I will add.
[UPDATED 2019-10-17] Added: 9f398c9

Wrong value gets saved in round 2

In the loop at the end of round 2 responsible for sending the messages, it appears only the latest message meant for
the last party is saved in the local temp variable :

// create and send messages
for j, Pj := range round.Parties().IDs() {
if j == round.PartyID().Index { // <--- notice this is already defined as being i
continue
}
r2msg := NewSignRound2MtAMidMessage(
Pj, round.PartyID(), round.temp.c1jis[j], round.temp.pi1jis[j], round.temp.c2jis[j], round.temp.pi2jis[j])
round.temp.signRound2MtAMidMessages[round.PartyID().Index] = &r2msg // <--- This seems wrong.
round.out <- r2msg
}

Also notice that round.PartyID().Index is actually i.

As a consequence, in the Update() function, message on index i is the one meant to be sent to the latest party.
This seems wrong as there is no need to store the latest message sent on index i of that table.
If the goal is simply to have a valid message on index i, so that the Update() still verifies, it seems a bit too
much to ove

Thanks, this line round.temp.signRound2MtAMidMessages[round.PartyID().Index] = &r2msg // <--- This seems wrong. is not needed as local party only need store messages peers sent to him.
I will delete it.

The PrepareForSigning() function is not checking its input

The input to PrepareForSigning() could be so that pax > len(ks) || pax > len(Xs), which would lead to a panic
in the loops.

func PrepareForSigning(i, pax int, xi *big.Int, ks []*big.Int, bigXs []*crypto.ECPoint) (wi *big.Int, bigWs []*crypto.ECPoint) {
modQ := common.ModInt(tss.EC().Params().N)

// 2-4.
wi = xi
for j := 0; j < pax; j++ {
if j == i {
continue
}
kj, ki := ks[j], ks[i] // would panic if j > len(ks)
...
Recommendation: add sanity checks on the input.

Also, if kj == ki, notice the function will panic as it tries to compute the modular inverse of (kj-ki) on the next line.
A little bit further on line 36, if ks[c]==ks[j], the ModInverse would panic.

Notice these should never happen, but this is an exported function, which means it is best to check from a defensive coding point of view.

Thanks. Fixed!

Variable named after package

In Keygen/round_1.go, L88, the variable cmt is named like the package cmt, which hurts readability and maintainability.

cmt := cmt.NewHashCommitment(pGFlat...)

Renamed into commitment`

Extra big int allocation done in Proofs

In mta/proofs.go, there are extra allocation of big.Int that could be spared:

// 14.
s1 := new(big.Int).Mul(e, x)
s1 = new(big.Int).Add(s1, alpha)

// 15.
s2 := new(big.Int).Mul(e, rho)
s2 = new(big.Int).Add(s2, rhoPrm)

// 16.
t1 := new(big.Int).Mul(e, y)
t1 = new(big.Int).Add(t1, gamma)

// 17.
t2 := new(big.Int).Mul(e, sigma)
t2 = new(big.Int).Add(t2, tau)

This could be instead:

s1 := new(big.Int).Mul(e, x)
s1.Add(s1, alpha)

Thanks. Fixed

Round 1 CanAccept function only rejects if both messages are wrong

If msg1 is corrupted but msg2 is not corrupted, then the function would still return true.

func (round *round1) CanAccept(msg tss.Message) bool {
if msg1, ok := msg.(*SignRound1MtAInitMessage); !ok || msg1 == nil {
if msg2, ok := msg.(*SignRound1CommitMessage); !ok || msg2 == nil {
return false
}
}
return true
}
While this is unlikely to be the case, it is probably something we want to check here.

The checking against message is type assertion. If the msg is second type, then the msg must not be first type.
So the checking is actually saying "is this message neither type1 nor type2"?

Unnecessary computations in round 1

In round 1, in the case where j == i, the mta.AliceInit() function is still called, and the message is even stored in
round.temp.signRound1MtAInitMessages[i], whereas it is always skipped in the next rounds.

This could be skipped completely in round 1 as well as per the specification.

for j, Pj := range round.Parties().IDs() {
c, pi, err := mta.AliceInit(round.key.PaillierPks[i], k, round.key.NTildej[j], round.key.H1j[j], round.key.H2j[j])
if err != nil {
return round.WrapError(fmt.Errorf("failed to init mta: %v", err))
}
r1msg1 := NewSignRound1MtAInitMessage(Pj, round.PartyID(), c, pi)
if j == i { // this could be at the start of the loop to spare us the AliceInit computations
round.temp.signRound1MtAInitMessages[j] = &r1msg1 // unnecessary
continue
}
round.temp.signRound1SentMtaInitMessages[j] = &r1msg1
round.out <- r1msg1
}

Fixed, thanks!

GetRandomGeneratorOfTheQuadraticResidue() assumes safe primes

It seems the function GetRandomGeneratorOfTheQuadraticResidue() used in GenerateNTildei() works only if its input
is the product of two safe primes, that is primes of the form p = 2q+1 for q another prime.

But the primes used in GenerateNTildei() are coming from its arguments and in
keygen/round_1.go, it appears the primes are generated using rsa.GenerateMultiPrimeKey() are not safe primes.

// Return a random generator of RQn with high probability. THIS METHOD
// ONLY WORKS IF N IS THE PRODUCT OF TWO SAFE PRIMES!
// https://github.com/didiercrunch/paillier/blob/d03e8850a8e4c53d04e8016a2ce8762af3278b71/utils.go#L39
func GetRandomGeneratorOfTheQuadraticResidue(n *big.Int) *big.Int {
r := GetRandomPositiveRelativelyPrimeInt(n)
return new(big.Int).Mod(new(big.Int).Mul(r, r), n) // YRO: could be simplified to r.Mod(r.Mul(r, r), n)
}

Unnecessary usage of multiple channels in concurrency situation

In the ecdsa signing rounds, there are multiple instances of 2n channels being created for n parties:

// it's concurrency time...
errChs1 := make([]chan *tss.Error, len(round.Parties().IDs()))
for j := range errChs1 {
if j == i {
errChs1[j] = nil
continue
}
errChs1[j] = make(chan *tss.Error)
}
errChs2 := make([]chan *tss.Error, len(round.Parties().IDs()))
for j := range errChs2 {
if j == i {
errChs2[j] = nil
continue
}
errChs2[j] = make(chan *tss.Error)
}

But one channel should be enough to gather all errors from all go routines.

Valid point! Fixed!

Unecessary initiliazation in loop.

In signing/prepare.go, L21, the value ki := ks[i] is initialized in every loop iteration, whereas it could be
initialized just once outside of the loop.

func PrepareForSigning(i, pax int, xi *big.Int, ks []*big.Int, bigXs []*crypto.ECPoint) (wi *big.Int, bigWs []*crypto.ECPoint) {
modQ := common.ModInt(tss.EC().Params().N)

// 2-4.
wi = xi // ki could be initialized here
for j := 0; j < pax; j++ {
if j == i {
continue
}
kj, ki := ks[j], ks[i] // ki doesn't need to be initialized every time
...

Furthermore, copying ks[j] into kj is not useful, as it is only used twice on the line just after it.

Thanks fixed.

Implementation does not support more parties than the threshold

It seems the current signing algorithm is assuming as many parties as required by the threshold, and if there are more parties,
with indexes larger than Threshold+1, they would panic during signing.

See for instance, how pax and len(bigWs) are not related in PrepareForSigning() (see lines 28, 29 and 39 in prepare.go),
which means bigWs[pax:] is containing null pointers that would be used by the parties with indexes > pax in
round_2's Start().

ks (which bigWs computed from) is filtered in tss client, it's a subset of ks generated during keygen. So its client's response to make sure len(ks) == len(bigXs) == pax.

Currently in tss client we support no more signer than t+1 because there is no centralized server coordinate the signers. So its an offline agreement for each signing session. (For example due to network speed, if 3 clients started at the same time for signing (t = 1), A may regard B as its signer, but B may regard C as its signer) then all is messed up.

I added some check because this function is exported:

	if len(ks) != len(bigXs) {
		panic(fmt.Errorf("indices and bigX are not same length"))
	}
	if len(ks) != pax {
		panic(fmt.Errorf("indices is not in pax size"))
	}

Notice that this is consistent with the spec that says on page 16 "We assume that [the set of player participating] = t+1",
however this does not seem to be check within the library, instead it is assumed and could lead to panics if someone
where to run the protocol with more players than the threshold+1.

Variable could be initialized outside of the loop

In prepare.go, line 36, the value ks[c] is accessed at each iteration, it could be copied to a local variable
in the outer loop:

bigWj := bigXs[j]
for c := 0; c < pax; c++ {
if j == c {
continue
}
// big.Int Div is calculated as: a/b = a * modInv(b,q)
iota := modQ.Mul(ks[c], modQ.ModInverse(new(big.Int).Sub(ks[c], ks[j])))
bigWj = bigWj.ScalarMult(iota)
}

Thanks, Fixed

Right now the curve that the library uses is set through a call to tss.SetCurve(...) and a reference to the given curve is stored globally, applying to all active Party instances.

It would be better for the curve to be a member of the BaseParty, set through a call to a new SetCurve function on an individual Party.

Here try == nil can only be true if err != nil, so it suffices to
check for err != nil.

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/common/random/random.go#L43-L46

We've noticed a bug where it appears that the binance lib hangs forever.

We seem to start the 2nd round of keygen, and it just gets stuck there...

I initialized a keygen party but haven't started the process yet. When I call WaitingFor() for this party, I get panic runtime error.

In such a case I would expect WaitingFor() function to return either an error or a list of parties (empty or containing all parties).

Stack trace:

panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x50 pc=0x4407f56]

goroutine 10 [running]:
testing.tRunner.func1(0xc0000fe300)
	/usr/local/Cellar/go/1.13.4/libexec/src/testing/testing.go:874 +0x3a3
panic(0x45aff80, 0x4bef630)
	/usr/local/Cellar/go/1.13.4/libexec/src/runtime/panic.go:679 +0x1b2
github.com/binance-chain/tss-lib/tss.(*BaseParty).WaitingFor(0xc00048f290, 0x0, 0x0, 0x0)
	/Users/(...)/binance-chain/[email protected]/tss/party.go:49 +0x86
github.com/(...)/tss.TestWaitingFor(0xc0000fe300)
	/Users/(...)/tss_test.go:46 +0x329
testing.tRunner(0xc0000fe300, 0x4795300)
	/usr/local/Cellar/go/1.13.4/libexec/src/testing/testing.go:909 +0xc9
created by testing.(*T).Run
	/usr/local/Cellar/go/1.13.4/libexec/src/testing/testing.go:960 +0x350

Test:

func TestWaitingFor(t *testing.T) {
	groupPartiesIDs := []*tss.PartyID{
		tss.NewPartyID("party-1", "", big.NewInt(1)),
		tss.NewPartyID("party-2", "", big.NewInt(2)),
		tss.NewPartyID("party-3", "", big.NewInt(3)),
	}

	params := tss.NewParameters(
		tss.NewPeerContext(tss.SortPartyIDs(groupPartiesIDs)),
		groupPartiesIDs[0],
		len(groupPartiesIDs),
		len(groupPartiesIDs)-1,
	)

	tssMessageChan := make(chan tss.Message, len(groupPartiesIDs))
	endChan := make(chan keygen.LocalPartySaveData)

	party := keygen.NewLocalParty(params, tssMessageChan, endChan)

	waitingFor := party.WaitingFor()

	t.Logf("waiting for: %v", waitingFor)
}

Implement Negative test cases to ensure 100% code coverage

In addition to the below audit feedback, the Paillier modulus N should be computed from two safe primes. Moreover, the primes P, Q should be safe primes with “large” difference (at least 1020-bit P-Q) to prevent square-root attacks.

GetRandomGeneratorOfTheQuadraticResidue() assumes safe primes

It seems the function GetRandomGeneratorOfTheQuadraticResidue() used in GenerateNTildei() works only if its input
is the product of two safe primes, that is primes of the form p = 2q+1 for q another prime.

But the primes used in GenerateNTildei() are coming from its arguments and in
keygen/round_1.go, it appears the primes are generated using rsa.GenerateMultiPrimeKey() are not safe primes.

The function requires a slice with exactly two *big.Ints however the function will not reject slices with three or more values:

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/crypto/utils.go#L10-L18

Such a behavior typically contributes to hiding bugs or misbehavior in the callers.

We have 3 nodes, A,B,C that involved in the keygen.

after successfully run the first keygen , node A saved the wiredBytes from the previous keygen for the round binance.tss-lib.ecdsa.keygen.KGRound2Message2.

They run the keygen with same parties again.

in the round "binance.tss-lib.ecdsa.keygen.KGRound2Message2" node A broadcasts the wiredBytes that from the previous keygen request to the peers, and the peers accept this incorrect wiredBytes as partyInfo.Party.UpdateFromBytes return nil error. Since the peers applied the incorrect share, their outChannel cannot produce the wiredMsg for the round "binance.tss-lib.ecdsa.keygen.KGRound3Message", finally, the Tss process stuck there.

In round_1_old_step_1.go, the "big Xjs" are included in the commitments made using
the Com() function, whereas in the specification itself, only commitments for the v_ij from the Feldman's VSS scheme are included.

Similarly, the use of X_j is omitted from the decommitment in NewCommitteeStep2 step 6, but unwrapped in the code and stored in round.temp.OldBigXj and round.temp.OldKs in round_4_new_step_2.go.

They both do not appear to be reused after that, and take no further part in the specification document.

In the feldman_vss.go file, in the evaluatePolynomial() function, instead of computing
modQ.Exp(id, big.NewInt(int64(i))) at each iteration, it could be faster to accumulate the value of x^i

https://github.com/binance-chain/tss-lib/blob/fea73dc96d6e7b0a94b42aa5074bf0e1c2296aae/crypto/vss/feldman_vss.go#L137-L147

Proposed fix:

func evaluatePolynomial(threshold int, v []*big.Int, id *big.Int) (result *big.Int) {
    	q := tss.EC().Params().N
    	modQ := common.ModInt(q)
    	result = new(big.Int).Set(v[0])
    	X := big.NewInt(int64(1))  // YRO : we need to have our accumulator outside of the loop
    	for i := 1; i <= threshold; i++ {
    		ai := v[i]
    		X = modQ.Mul(X, id)    // YRO: so we have that X = 1*id*id*...*id = id^i 
    		aiXi := new(big.Int).Mul(ai, X)
    		result = modQ.Add(result, aiXi)
    	}
    	return
    }

The same holds for the verify() function:
https://github.com/binance-chain/tss-lib/blob/master/crypto/vss/feldman_vss.go#L75

func (share *Share) Verify(threshold int, vs Vs) bool {
	if share.Threshold != threshold {
		return false
	}
	modN := common.ModInt(tss.EC().Params().N)
	v := vs[0]
	t := new(big.Int).SetInt64(int64(1)) // YRO : we need to have our accumulator outside of the loop
	for j := 1; j <= threshold; j++ {
		// t = ki^j
		t = modN.Mul(t, share.ID)  // YRO : here we can use just Mul instead of Exp.
		// v = v * vj^t
		vjt := vs[j].SetCurve(tss.EC()).ScalarMult(t)
		v = v.SetCurve(tss.EC()).Add(vjt)
	}
	sigmaGi := crypto.ScalarBaseMult(tss.EC(), share.Share)
	if sigmaGi.Equals(v) { 	//YRO: could be simplified to "return sigmaGi.Equals(v)"
		return true	 // *
	}			// *
	return false		// *
}

Also notice the above function could directly return the value of sigmaGi.Equals(v) instead of having a conditional return statement.

The same holds for the Start() function in round_4_new_step_2.go.
https://github.com/binance-chain/tss-lib/blob/master/ecdsa/regroup/round_4_new_step_2.go#L138

for c := 1; c <= round.NewThreshold(); c++ {
    z := modQ.Exp(kj, big.NewInt(int64(c))) // YRO : Here.
    newBigXj = newBigXj.Add(Vc[c].ScalarMult(z))
}
NewBigXj[j] = newBigXj

And the same holds for keygen/round_3.go :
https://github.com/binance-chain/tss-lib/blob/master/ecdsa/keygen/round_3.go#L136

z := new(big.Int).SetInt64(int64(1))
for c := 1; c <= round.Threshold(); c++ {
    z = z.Mod(z.Mul(z, kj), tss.EC().Params().N)
    BigXj = BigXj.Add(Vc[c].ScalarMult(z))
}
bigXj[j] = BigXj

For instance, using 512 bits values for q and id, here are some benchmark results that show a 5x speed increase using an accumulator:

BenchmarkModMul-4     1000      2188456 ns/op   1135169 B/op   8996 allocs/op
BenchmarkExpMod-4      100     10746285 ns/op   1987063 B/op  13186 allocs/op

There are a handful of hardware acceleration features in arm architectures that we could be making use of. armv8 has a PMULL instruction (polynomial multiplication) and there are dedicated instructions for hashing (sha256h, sha256h2, sha256su0 sha256su1, sha512h, sha512h2, sha512su0, sha512su1).

First action item would be to check that we're using these accelerated instructions and then use them if not.

• dlnproof.Verify
• ProofBobWC.Verify
• RangeProofAlice.Verify

are not constant-time.

On L96, it is deadcode:

https://github.com/binance-chain/tss-lib/blob/31c67c55cf30e314d2640e71b632917a932b57f6/ecdsa/signing/round_5.go#L94-L97

Since it will already have returned on the previous line.