Small Leaks, Billions of Dollars

I love using Shamir’s secret shares — and is one of the few provable methods that enhance resiliance. And, so the drive has been on MPC…

Small Leaks, Billions of Dollars

I love using Shamir’s secret shares — and it is one of the few provable methods that enhance resilience. And, so, the drive has been on MPC (Multiparty Computation) methods to integrate Shamir’s approach to DKG (Distributed Key Generation) and distributed signing. For this, we see work where many hosts can generate a secret — such as a private key — without the need for a dealer. The dream is to build a world where no one ever needs the secret, but you can still prove it.

Why? Because what happens when the dealer goes bad? For this, we have integrated Byzantian fault tolerance and have moved towards distributed digital signing. This is where each trusted entity with a share of the secret can sign their part of a digital signature, and which is then aggregated together to give the final signature. The target for this, of course, is the mighty ECDSA signature — as this is used in the Ethereum Virtual Machine (EVM). All sounds wonderful — and if you want your grant or company funded — just add MPC to the description.

But, the ECDSA signature doesn’t scale that well to MPC, and that’s where the problem comes in. In fact, life would be a whole lot simplier if we could only use EdDSA for our signatures [here].

Now, a new Black Hat presentation from a team at Fireblocks casts some light on the many problems that MPC has brought the area, and which may have cost billions of dollars [here]:

Their work shows that the discovery of the private key can be gained from a couple of hundred signatures. Overall they found four novel attacks and three zero-day threats, and which affect around 16 different wallet vendors. The three core attacks are:

  • Two-party signing protocol: Lindell17 [2]. PoC: [here]. The attack is defined as Broken Record and results 256 signatures (see Table 1).
  • Multi-party signing protocols: GG18 and 20 [1]. PoC: [here]. The attack is defined a “6ix1een” for GG20 (New) and “Death by 1M Cuts” for GG20 (Old). With 6ix1een, only 16 signatures are required, but “Death by 1M Cuts” requires at least one million signatures.
  • Crypto custodian: BitGo TSS (low interactivity). PoC: [here]. The is defined by “Zero Proof” and requires one signature.

The results are:

Table 1

The paper is published as a whitepaper [here]:

So, let’s look at one of the methods: GG20.

GG20

The GG20 (Gennaro, R., & Goldfeder, S. (2020) [1]) method implements an ECDSA signing algorithm using threshold protocols. In this case we define that at least t shares are required to rebuild the signature, for n parties. With this, we generate a private key that will be used to sign our data. This private key is then split into a number of shares (n) and then t or more parties can come together to generate a valid ECDSA signature.

The focus of the paper [1] is to create an ECDSA signature using secret shares of a private key. In this way we can create an ECDSA signature using multiple Shamir shares, and where the private is never actually revealed, but split over two or more parties.

So, let’s use the Coinbase Kryptology library to implement a t-from-n theshold ECDSA scheme using GG20 (Gennaro and Goldfeder, 2020). Initially we will use the secp256k1 curve and then generate a new private key (ikm):

k256 := btcec.S256()ikm, _ := dealer.NewSecret(k256)

This private key will not be stored on the parties which receive the shares, and can be deleted afer the shares have been distributed. We can then generate the associated public key (pk) and split the key into a number of shares (sharesMap):

pk, sharesMap, _ := dealer.NewDealerShares(k256, tshare, nshare, ikm)
fmt.Printf("Message: %s\n", msg)fmt.Printf("Sharing scheme: Any %d from %d\n", tshare, nshare)
fmt.Printf("Random secret: (%x)\n\n", ikm)fmt.Printf("Public key: (%s %s)\n\n", pk.X, pk.Y)

This public key will be used to check that the signature that the parties create. We also create public shares which can be used to verify the shares created. We then create Paillier keys which will be used to distribute the key signing:

for len(sharesMap) > int(tshare) {
		delete(sharesMap, uint32(len(sharesMap)))
	}
	pubSharesMap, _ := dealer.PreparePublicShares(sharesMap)
	keysMap := make(map[uint32]*paillier.SecretKey, tshare)
	pubKeys := make(map[uint32]*paillier.PublicKey, tshare)
	keyPrimesArray := genPrimesArray(int(tshare))
	for i := range sharesMap {
		keysMap[i], _ = paillier.NewSecretKey(keyPrimesArray[i-1].p, keyPrimesArray[i-1].q)
		pubKeys[i] = &keysMap[i].PublicKey
		fmt.Printf("Share: %x\n", sharesMap[i].Bytes())
	}
	proofParams := &dealer.TrustedDealerKeyGenType{
		ProofParams: dealerParams,
	}

The dealer of the shares is now setup. What we need now is two parties to receive the shares, and for them to sign for a message (msg). We can create a hash of the message with:

m := []byte(msg)msgHash := sha256.Sum256(m)

Next we will create two participants (p1 and p2), and where p1 gets the first set of shares (sharesMap1), and the ID for these, and p2 gets the second set of shares (sharesMap2), and the required ID for these:

p1 := Participant{*setup.sharesMap[1], setup.privkeys[1]}
p2 := Participant{*setup.sharesMap[2], setup.privkeys[2]}

And then set them up for split the share. These will be run of either of the parties:

s1, _ := p1.PrepareToSign(setup.pk,k256Verifier,setup.curve,setup.proofParams,setup.pubSharesMap,setup.pubkeys)
s2, _ := p2.PrepareToSign(setup.pk,k256Verifier,setup.curve,setup.proofParams,setup.pubSharesMap,
setup.pubkeys)

We then go into a number of rounds, and where s1 is run on one party, and s2 on another party:

// Run signing rounds
	// Sign Round 1
	var err error
	signerOut := make(map[uint32]*Round1Bcast, tshare)
	for i, s := range signersMap {
		signerOut[i], _, err = s.SignRound1()
		if err != nil {
			return
		}
	}
// Sign Round 2
 p2p := make(map[uint32]map[uint32]*P2PSend)
 for i, s := range signersMap {
  in := make(map[uint32]*Round1Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = signerOut[j]
  }
  p2p[i], err = s.SignRound2(in, nil) // TODO: fix me later
  if err != nil {
   return
  }
 }
 // Sign Round 3
 r3Bcast := make(map[uint32]*Round3Bcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*P2PSend, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = p2p[j][i]
  }
  r3Bcast[i], err = s.SignRound3(in)
  if err != nil {
   return
  }
 }
 // Sign Round 4
 r4Bcast := make(map[uint32]*Round4Bcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round3Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r3Bcast[j]
  }
  r4Bcast[i], err = s.SignRound4(in)
  if err != nil {
   return
  }
 }
 // Sign Round 5
 r5Bcast := make(map[uint32]*Round5Bcast, tshare)
 r5P2p := make(map[uint32]map[uint32]*Round5P2PSend, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round4Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r4Bcast[j]
  }
  r5Bcast[i], r5P2p[i], err = s.SignRound5(in)
  if err != nil {
   return
  }
 }
 // Sign Round 6
 r6Bcast := make(map[uint32]*Round6FullBcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round5Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r5Bcast[j]
  }
  r6Bcast[i], err = s.SignRound6Full(msgHash[:], in, r5P2p[i])
  if err != nil {
   return
  }
 }

Now each party can generate the shared signature:

var sig *curves.EcdsaSignature
	for i, s := range signersMap {
		in := make(map[uint32]*Round6FullBcast, tshare-1)
		for j := range signersMap {
			if i == j {
				continue
			}
			in[j] = r6Bcast[j]
		}
sig, _ = s.SignOutput(in)
 }

We can then check the signature that has been generated against the public key:

fmt.Printf("\nOverall signature: (%d %d)\n", sig.R, sig.S)
publicKey := ecdsa.PublicKey{
  Curve: ecc.P256k1(), //secp256k1
  X:     pk.X,
  Y:     pk.Y,
 }
 rtn := ecdsa.Verify(&publicKey, msgHash[:], sig.R, sig.S)
 fmt.Printf("\nSignature Verified: %v", rtn)

A sample run is:

Message: hello
Sharing scheme: Any 2 from 2
Random secret: (4ba8a796f32ec45a1197de6089fa236e50801928ad24fecac8c1ab09e531a166)Public key: (26312696491752052329024843181188922148239837748725137580407874797348180244367 15363854046934109047334192976294337901992160667810868208924200646181218876027)Node 1 signature: (58831626654799325138549587498198878137267315963404497589755928522155537172377 52424895795438944536339814184633346175739904425137488476336337801850504274550)
Node 2 signature: (58831626654799325138549587498198878137267315963404497589755928522155537172377 52424895795438944536339814184633346175739904425137488476336337801850504274550)Signature Verified: true

Coding

In this case we will define t for the threshold and n for the number of shares:

package main
import (
 "crypto/ecdsa"
 "crypto/sha256"
 "fmt"
 "math/big"
 "github.com/dustinxie/ecc"
 "os"
 "strconv"
 "github.com/btcsuite/btcd/btcec"
 "github.com/coinbase/kryptology/pkg/core/curves"
 "github.com/coinbase/kryptology/pkg/paillier"
 "github.com/coinbase/kryptology/pkg/tecdsa/gg20/dealer"
)
var (
 testPrimes = []*big.Int{
  B10("186141419611617071752010179586510154515933389116254425631491755419216243670159714804545944298892950871169229878325987039840135057969555324774918895952900547869933648175107076399993833724447909579697857041081987997463765989497319509683575289675966710007879762972723174353568113668226442698275449371212397561567"),
  B10("94210786053667323206442523040419729883258172350738703980637961803118626748668924192069593010365236618255120977661397310932923345291377692570649198560048403943687994859423283474169530971418656709749020402756179383990602363122039939937953514870699284906666247063852187255623958659551404494107714695311474384687"),
  B10("62028909880050184794454820320289487394141550306616974968340908736543032782344593292214952852576535830823991093496498970213686040280098908204236051130358424961175634703281821899530101130244725435470475135483879784963475148975313832483400747421265545413510460046067002322131902159892876739088034507063542087523"),
  B10("321804071508183671133831207712462079740282619152225438240259877528712344129467977098976100894625335474509551113902455258582802291330071887726188174124352664849954838358973904505681968878957681630941310372231688127901147200937955329324769631743029415035218057960201863908173045670622969475867077447909836936523"),
  B10("52495647838749571441531580865340679598533348873590977282663145916368795913408897399822291638579504238082829052094508345857857144973446573810004060341650816108578548997792700057865473467391946766537119012441105169305106247003867011741811274367120479722991749924616247396514197345075177297436299446651331187067"),
  B10("118753381771703394804894143450628876988609300829627946826004421079000316402854210786451078221445575185505001470635997217855372731401976507648597119694813440063429052266569380936671291883364036649087788968029662592370202444662489071262833666489940296758935970249316300642591963940296755031586580445184253416139"),
 }
 dealerParams = &dealer.ProofParams{
  N:  B10("135817986946410153263607521492868157288929876347703239389804036854326452848342067707805833332721355089496671444901101084429868705550525577068432132709786157994652561102559125256427177197007418406633665154772412807319781659630513167839812152507439439445572264448924538846645935065905728327076331348468251587961"),
  H1: B10("130372793360787914947629694846841279927281520987029701609177523587189885120190605946568222485341643012763305061268138793179515860485547361500345083617939280336315872961605437911597699438598556875524679018909165548046362772751058504008161659270331468227764192850055032058007664070200355866555886402826731196521"),
  H2: B10("44244046835929503435200723089247234648450309906417041731862368762294548874401406999952605461193318451278897748111402857920811242015075045913904246368542432908791195758912278843108225743582704689703680577207804641185952235173475863508072754204128218500376538767731592009803034641269409627751217232043111126391"),
 }
 k256Verifier = func(pubKey *curves.EcPoint, hash []byte, sig *curves.EcdsaSignature) bool {
  btcPk := &btcec.PublicKey{
   Curve: btcec.S256(),
   X:     pubKey.X,
   Y:     pubKey.Y,
  }
  btcSig := btcec.Signature{
   R: sig.R,
   S: sig.S,
  }
  return btcSig.Verify(hash, btcPk)
 }
)
func getParams(msg *string, t, n *uint32) {
 argCount := len(os.Args[1:])
 if argCount > 0 {
  *msg = os.Args[1]
 }
 if argCount > 1 {
  val, _ := strconv.Atoi(os.Args[2])
  *t = uint32(val)
 }
 if argCount > 2 {
  val, _ := strconv.Atoi(os.Args[3])
  *n = uint32(val)
 }
}
func genPrimesArray(count int) []struct{ p, q *big.Int } {
 primesArray := make([]struct{ p, q *big.Int }, 0, count)
 for len(primesArray) < count {
  for i := 0; i < len(testPrimes) && len(primesArray) < count; i++ {
   for j := 0; j < len(testPrimes) && len(primesArray) < count; j++ {
    if i == j {
     continue
    }
    keyPrime := struct {
     p, q *big.Int
    }{
     testPrimes[i], testPrimes[j],
    }
    primesArray = append(primesArray, keyPrime)
   }
  }
 }
 return primesArray
}
func B10(s string) *big.Int {
 x, ok := new(big.Int).SetString(s, 10)
 if !ok {
  panic("Couldn't derive big.Int from string")
 }
 return x
}

func main() {
 tshare := uint32(2)
 nshare := uint32(3)
 msg := "Hello"
 m := []byte(msg)
 msgHash := sha256.Sum256(m)
 getParams(&msg, &tshare, &nshare)
 k256 := btcec.S256()
 ikm, _ := dealer.NewSecret(k256)
 pk, sharesMap, _ := dealer.NewDealerShares(k256, tshare, nshare, ikm)
 fmt.Printf("Message: %s\n", msg)
 fmt.Printf("Sharing scheme: Any %d from %d\n", tshare, nshare)
 fmt.Printf("Random secret: (%x)\n\n", ikm)
 fmt.Printf("Public key: (%s %s)\n\n", pk.X, pk.Y)
 for len(sharesMap) > int(tshare) {
  delete(sharesMap, uint32(len(sharesMap)))
 }
 pubSharesMap, _ := dealer.PreparePublicShares(sharesMap)
 keysMap := make(map[uint32]*paillier.SecretKey, tshare)
 pubKeys := make(map[uint32]*paillier.PublicKey, tshare)
 keyPrimesArray := genPrimesArray(int(tshare))
 for i := range sharesMap {
  keysMap[i], _ = paillier.NewSecretKey(keyPrimesArray[i-1].p, keyPrimesArray[i-1].q)
  pubKeys[i] = &keysMap[i].PublicKey
  fmt.Printf("Share: %x\n", sharesMap[i].Bytes())
 }
 proofParams := &dealer.TrustedDealerKeyGenType{
  ProofParams: dealerParams,
 }
 signersMap := make(map[uint32]*Signer, tshare)
 for i, k := range keysMap {
  p := Participant{*sharesMap[i], k}
  signersMap[i], _ = p.PrepareToSign(pk, k256Verifier, k256, proofParams, pubSharesMap, pubKeys)
 }
 // Run signing rounds
 // Sign Round 1
 var err error
 signerOut := make(map[uint32]*Round1Bcast, tshare)
 for i, s := range signersMap {
  signerOut[i], _, err = s.SignRound1()
  if err != nil {
   return
  }
 }
 // Sign Round 2
 p2p := make(map[uint32]map[uint32]*P2PSend)
 for i, s := range signersMap {
  in := make(map[uint32]*Round1Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = signerOut[j]
  }
  p2p[i], err = s.SignRound2(in, nil) // TODO: fix me later
  if err != nil {
   return
  }
 }
 // Sign Round 3
 r3Bcast := make(map[uint32]*Round3Bcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*P2PSend, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = p2p[j][i]
  }
  r3Bcast[i], err = s.SignRound3(in)
  if err != nil {
   return
  }
 }
 // Sign Round 4
 r4Bcast := make(map[uint32]*Round4Bcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round3Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r3Bcast[j]
  }
  r4Bcast[i], err = s.SignRound4(in)
  if err != nil {
   return
  }
 }
 // Sign Round 5
 r5Bcast := make(map[uint32]*Round5Bcast, tshare)
 r5P2p := make(map[uint32]map[uint32]*Round5P2PSend, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round4Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r4Bcast[j]
  }
  r5Bcast[i], r5P2p[i], err = s.SignRound5(in)
  if err != nil {
   return
  }
 }
 // Sign Round 6
 r6Bcast := make(map[uint32]*Round6FullBcast, tshare)
 for i, s := range signersMap {
  in := make(map[uint32]*Round5Bcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r5Bcast[j]
  }
  r6Bcast[i], err = s.SignRound6Full(msgHash[:], in, r5P2p[i])
  if err != nil {
   return
  }
 }
 // Signature output
 var sig *curves.EcdsaSignature
 for i, s := range signersMap {
  in := make(map[uint32]*Round6FullBcast, tshare-1)
  for j := range signersMap {
   if i == j {
    continue
   }
   in[j] = r6Bcast[j]
  }
  sig, _ = s.SignOutput(in)
 }
 fmt.Printf("\nOverall signature: (%d %d)\n", sig.R, sig.S)
 publicKey := ecdsa.PublicKey{
  Curve: ecc.P256k1(), //secp256k1
  X:     pk.X,
  Y:     pk.Y,
 }
 rtn := ecdsa.Verify(&publicKey, msgHash[:], sig.R, sig.S)
 fmt.Printf("\nSignature Verified: %v", rtn)
}

A sample run:

Message: Hello
Sharing scheme: Any 3 from 3
Random secret: (c271efce18143d061fc038520bf237d54bc1bae30102a6865415469395c828e9)
Public key: (57755611822377136447302262937396184048650892670209379601281857181998065978443 44413617945939969186822341967546876716017422443472796955428443139294461366744)
Share: 00000001d626949296c762aed6b05487089a1e8427eab17517b1cbf50452c20d721ee6d0
Share: 00000002101c511c26b51045ee6bd4d9b765dca488a724408d2b612bc40e59804b3a40f0
Share: 000000037053256ac7dd45cb66f2b94a18557233e354cd12c000a6a212ecca05c186b9cb
Overall signature: (41380358919718061219799007246292506717162956461936762477573221474876405792049 38097776260715345652427955489175480176251297451389595674385725752408498422410)
Signature Verified: true

References

[1] Gennaro, R., & Goldfeder, S. (2020). One Round Threshold ECDSA with Identifiable Abort. IACR Cryptol. ePrint Arch., 2020, 540 [here].

[2] Lindell, Y. (2017). Fast secure two-party ECDSA signing. In Advances in Cryptology–CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II 37 (pp. 613–644). Springer International Publishing.