One of the most important challenges within cybersecurity is key management. This is a way that organisations store encryption keys and can recall them when required. We also need a way to back up these keys, in case we lose them. One method of achieving this is to centralise our key management into a trusted server. This, though, can centralise our infrastructure, and it can become a target for attack. An alternative is to use a Distributed Key Generation (DKG) infrastructure, and where we split the keys into a number of Shamir shares, and then distribute these to a number of stored key stores. This is more secure and also resilient, and where we can create \(n\) shares and with a \(t\) threshold, and where we can rebuild our data with at least \(t\) shares. It should not be possible to reconstruct the key without gathering \(t\) shares. In this way, we can either cope with a malicious key store or can cope with an outage on one or more of these.
Distributed key generation (DKG) using FROST threshold Schnorr signature protocol in Kryptology |
Background
One of the most important challenges within cybersecurity is key management. This is a way that organisations store encryption keys and can recall them when required. We also need a way to back up these keys, in case we lose them. One method of achieving this is to centralise our key management into a trusted server. This, though, can centralise our infrastructure, and it can become a target for attack.
An alternative is to use a Distributed Key Generation (DKG) infrastructure, and where we split the keys into a number of Shamir shares, and then distribute these to a number of stored key stores. This is more secure and also resilient, and where we can create \(n\) shares and with a \(t\) threshold, and where we can rebuild our data with at least \(t\) shares. It should not be possible to reconstruct the key without gathering \(t\) shares. In this way, we can either cope with a malicious key store or can cope with an outage on one or more of these.
In this case, we will use the FROST method defined by Komlo and Goldberg [1]. With this, we use a share of a Schnorr signature across trusted parties, and where each of the key shares can be signed by each of the parties, and where the validation signature can only be rebuilt when a given threshold is reached. Essentially there are two core elements to the FROST method. The first is that n parties run a distributed key generation (DKG) service, and then agree on a verification key, and where each party has their own secret key. Then any one of the parties involved can collaboratively generate a Schnorr signature. In the following diagram we see that Bob, Alice and Carol have their own secret key. They then create a round where the create a verification key which is the aggregation of their public keys. This uses the Schnorr signature method, and where we can easily agreegate public keys together. The verification key will then be used to verify signatures. Each party will tehn hold a secret key (\(i,sk_i\)) and which is there long term secret key, and also a verification key (\(vk_i=sk_i G\)). This verification key (\(vk_i\)) is then used to define the correctness of their signature signing shares, whereas the main verification (\(vk\)) checks the signed message for the group.
Next we decide the signing threshold, and how many signers are allowed to verify a message. In this case, we will do an any 2-from-3, and where Bob and Carol can come together and sign for a message:
For a Schnorr signature we first perform a key generation phase. Each party (\(i\)) create a random secret key (\(sk\)) and generators a validation key of:
\(vk = sk \cdot G\)
For the signing process we take the secret key (\(sk\)) and a message (\(M\)). Each party select a random nonce (\(r\)), and then computes:
\(R = r \cdot G\)
\(c = H(M,R)\)
\(z= r + sk \cdot c \pmod p\)
\(Sig = (z,c)\)
To check the signature:
\(R' = z \cdot G - c \cdot vk\)
\(c' = H(M,R')\)
We then check that \(c'\) is equal to \(c\). This works because:
\(c' = H(M,R') = H(M,z \cdot G - c \cdot vk) = H(M,(r + sk \cdot c) \cdot G - c \cdot vk) = H(M, r \cdot G + c \cdot sk \cdot G - c \cdot vk) = H(M,r \cdot G + c \cdot vk - c \cdot vk) = H(M,R) = c\)
and where \(H()\) is a hash on the content, \(G\) is the base point on the curve, \(sk\) is the secret key as a scalar value, and \(vk\) is the public verifier point.
Coding
In the following, we will add two new participants to a share: p1 (ID=1) and p2 (ID=2), and where we define an additional participant for p1 as p2 (ID-2), and vice verse. The first argument of NewDkgParticipant is the ID. This is followed by the threshold required to rebuild the shares. The next is the context of the message, and which avoids a replay attack. Finally, we have the curve type (Ed25519), and the last argument is the ID of the other share participant:
Ctx := "Stop reply attack" testCurve := curves.ED25519() p1, _ := frost.NewDkgParticipant(1, 2, Ctx, testCurve, 2) p2, _ := frost.NewDkgParticipant(2, 2, Ctx, testCurve, 1)
After the first round, we have a broadcast value, and a p2p share:
bcast1, p2psend1, _ := p1.Round1(nil) bcast2, p2psend2, _ := p2.Round1(nil)
The ID value of p2psend1 will contain the share (p2psend1 and p2psend2) for the given ID. For example, p2psend1[2] will contain the share for ID=2, and p2psend2[1] will contain the share for ID=1. We can then pass the shares:
bcast := make(map[uint32]*frost.Round1Bcast) p2p1 := make(map[uint32]*sharing.ShamirShare) p2p2 := make(map[uint32]*sharing.ShamirShare) bcast[1] = bcast1 bcast[2] = bcast2 p2p1[2] = p2psend2[1] p2p2[1] = p2psend1[2]
For this, we exchange the shares, and where the first participant receives the share the second participant:
p1.Round2(bcast, p2p1) p2.Round2(bcast, p2p2) fmt.Printf("\nSkShare P1: %x\n", p1.SkShare.Bytes()) fmt.Printf("SkShare P2: %x\n", p2.SkShare.Bytes()) fmt.Printf("\nVerification key P1: %x\n", p1.VerificationKey.ToAffineCompressed()) fmt.Printf("Verification key P2: %x\n", p2.VerificationKey.ToAffineCompressed())
P1 will have a secret key (p1.SkShare), and P2 will also have its own secret key (p2.SkShare). We will now have two verification keys on P1 and P2. These should be the same for each participant. Next, we will split the verification key into any two from three shares:
s, _ := sharing.NewShamir(2, 3, myCurve)
These shares can then be distributed to participants. When we need to rebuilt them we:
sk, _ := s.Combine(&sharing.ShamirShare{Id: p1.Id, Value: p1.SkShare.Bytes()},&sharing.ShamirShare{Id: p2.Id, Value: p2.SkShare.Bytes()})
The value of sk will rebuild the secret back. We can then recreate the verification key with:
vk := myCurve.ScalarBaseMult(sk) rtn := vk.Equal(p1.VerificationKey) if rtn { fmt.Printf("Verification keys are the same.\n") fmt.Printf("Verification key Round 2: %x\n", vk.ToAffineCompressed()) }
Coding
The outline coding using the library from the Krytology library:
package main import ( "fmt" "github.com/coinbase/kryptology/pkg/core/curves" "github.com/coinbase/kryptology/pkg/dkg/frost" "github.com/coinbase/kryptology/pkg/sharing" ) // Test dkg round1 works for 2 participants func main() { // Round 1 Ctx := "string to prevent replay attack" myCurve := curves.ED25519() fmt.Printf("=== Round 1 let's generate secret keys ===\n") p1, _ := frost.NewDkgParticipant(1, 2, Ctx, myCurve, 2) p2, _ := frost.NewDkgParticipant(2, 2, Ctx, myCurve, 1) bcast1, p2psend1, _ := p1.Round1(nil) bcast2, p2psend2, _ := p2.Round1(nil) fmt.Printf("\n=== Round 2 let's generate the verification key ===\n") bcast := make(map[uint32]*frost.Round1Bcast) p2p1 := make(map[uint32]*sharing.ShamirShare) p2p2 := make(map[uint32]*sharing.ShamirShare) bcast[1] = bcast1 bcast[2] = bcast2 p2p1[2] = p2psend2[1] p2p2[1] = p2psend1[2] // Running round 2 p1.Round2(bcast, p2p1) p2.Round2(bcast, p2p2) fmt.Printf("\nSkShare P1: %x\n", p1.SkShare.Bytes()) fmt.Printf("SkShare P2: %x\n", p2.SkShare.Bytes()) fmt.Printf("\nVerification key P1: %x\n", p1.VerificationKey.ToAffineCompressed()) fmt.Printf("Verification key P2: %x\n", p2.VerificationKey.ToAffineCompressed()) fmt.Printf("\n=== Round 3 split those secret keys and rebuild verification key ===\n") s, _ := sharing.NewShamir(2, 3, myCurve) sk, _ := s.Combine(&sharing.ShamirShare{Id: p1.Id, Value: p1.SkShare.Bytes()}, &sharing.ShamirShare{Id: p2.Id, Value: p2.SkShare.Bytes()}) vk := myCurve.ScalarBaseMult(sk) rtn := vk.Equal(p1.VerificationKey) if rtn { fmt.Printf("Verification keys are the same.\n") fmt.Printf("Verification key Round 2: %x\n", vk.ToAffineCompressed()) } }
A sample run is:
=== Round 1 let's generate secret keys === === Round 2 let's generate the verification key === SkShare P1: ce265892e28d85248a2b84e5d0f8d8cb1d913ff2b56c2bb10abf773db5d71806 SkShare P2: edf456335be5535a58cb20ac91ef953890d8fab07e1adac48a273a4ecc96470d Verification key P1: 041a152cb05f02ebb1573bae9d1ff9d0909f787f05c5a825d8560ce6d9f463db Verification key P2: 041a152cb05f02ebb1573bae9d1ff9d0909f787f05c5a825d8560ce6d9f463db === Round 3 split those secret keys and rebuild verification key === Verification keys are the same. Verification key Round 2: 041a152cb05f02ebb1573bae9d1ff9d0909f787f05c5a825d8560ce6d9f463db
Coding
Reference
[1] Komlo, C., & Goldberg, I. (2020). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. IACR Cryptol. ePrint Arch., 2020, 852.