idnits 2.17.1 draft-hallambaker-threshold-sigs-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: Implementations MUST not use threshold signatures in applications where signature values are used in place of cryptographic digests as unique content identifiers. -- The document date (2 November 2020) is 1270 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBS' is mentioned on line 1266, but not defined Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. M. Hallam-Baker 3 Internet-Draft ThresholdSecrets.com 4 Intended status: Informational 2 November 2020 5 Expires: 6 May 2021 7 Threshold Signatures in Elliptic Curves 8 draft-hallambaker-threshold-sigs-05 10 Abstract 12 A Threshold signature scheme is described. The signatures created 13 are computationally indistinguishable from those produced using the 14 Ed25519 and Ed448 curves as specified in RFC8032 except in that they 15 are non-deterministic. Threshold signatures are a form of digital 16 signature whose creation requires two or more parties to interact but 17 does not disclose the number or identities of the parties involved. 19 https://mailarchive.ietf.org/arch/browse/cfrg/ 20 (http://whatever)Discussion of this draft should take place on the 21 CFRG mailing list (cfrg@irtf.org), which is archived at . 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at https://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on 6 May 2021. 40 Copyright Notice 42 Copyright (c) 2020 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 47 license-info) in effect on the date of publication of this document. 48 Please review these documents carefully, as they describe your rights 49 and restrictions with respect to this document. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.1. Applications . . . . . . . . . . . . . . . . . . . . . . 4 55 1.1.1. HSM Binding . . . . . . . . . . . . . . . . . . . . . 4 56 1.1.2. Code Signing . . . . . . . . . . . . . . . . . . . . 4 57 1.1.3. Signing by Redundant Services . . . . . . . . . . . . 5 58 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 5 59 2.1. Requirements Language . . . . . . . . . . . . . . . . . . 5 60 2.2. Defined Terms . . . . . . . . . . . . . . . . . . . . . . 5 61 2.3. Related Specifications . . . . . . . . . . . . . . . . . 5 62 2.4. Implementation Status . . . . . . . . . . . . . . . . . . 6 63 3. Principles . . . . . . . . . . . . . . . . . . . . . . . . . 6 64 3.1. Direct shared threshold signature . . . . . . . . . . . . 7 65 3.2. Shamir shared threshold signature . . . . . . . . . . . . 9 66 3.3. Stateless computation of final share . . . . . . . . . . 10 67 3.3.1. Side channel resistance . . . . . . . . . . . . . . . 11 68 3.4. Security Analysis . . . . . . . . . . . . . . . . . . . . 12 69 3.4.1. Calculation of r values . . . . . . . . . . . . . . . 12 70 3.4.2. Replay Attack . . . . . . . . . . . . . . . . . . . . 13 71 3.4.3. Malicious Contribution Attack . . . . . . . . . . . . 13 72 3.4.4. Rogue Key Attack . . . . . . . . . . . . . . . . . . 13 73 4. Ed2519 Signature . . . . . . . . . . . . . . . . . . . . . . 14 74 5. Ed448 Signature . . . . . . . . . . . . . . . . . . . . . . . 15 75 6. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 16 76 6.1. Direct Threshold Signature Ed25519 . . . . . . . . . . . 16 77 6.2. Direct Threshold Signature Ed448 . . . . . . . . . . . . 19 78 6.3. Shamir Threshold Signature Ed25519 . . . . . . . . . . . 22 79 6.4. Shamir Threshold Signature Ed448 . . . . . . . . . . . . 25 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 28 81 7.1. Rogue Key attack . . . . . . . . . . . . . . . . . . . . 28 82 7.2. Disclosure or reuse of the value r . . . . . . . . . . . 28 83 7.3. Resource exhaustion attack . . . . . . . . . . . . . . . 28 84 7.4. Signature Uniqueness . . . . . . . . . . . . . . . . . . 28 85 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 29 86 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 29 87 10. Normative References . . . . . . . . . . . . . . . . . . . . 29 88 11. Informative References . . . . . . . . . . . . . . . . . . . 29 90 1. Introduction 92 Threshold encryption and key generation provide compelling advantages 93 over single private key approaches because splitting the private key 94 permits the use of that key to be divided between two or more roles. 96 All existing digital signatures allow the signer role to be divided 97 between multiple parties by attaching multiple signatures to the 98 signed document. This approach, known as multi-signatures, is 99 distinguished from a threshold signature scheme in that the identity 100 and roles of the individual signers is exposed. In a threshold 101 signature scheme, the creation of a single signature requires the 102 participation of multiple signers and the signature itself does not 103 reveal the means by which it was constructed. 105 Rather than considering multi-signatures or threshold signatures to 106 be inherently superior, it is more useful to regard both as two 107 points on a continuum of choices: 109 Multi-signatures Multiple digital signatures on the same document. 110 Multi-signatures are simple to create and provide the verifier 111 with more information but require the acceptance criteria to be 112 specified independently of the signature itself. This requires 113 that the application logic or PKI provide some means of describing 114 the criteria to be applied. 116 Multi-party key release A single signature created using a single 117 private key stored in an encrypted form whose use requires 118 participation of multiple key decryption shares. 120 Threshold signatures A single signature created using multiple 121 signature key shares. Signature creation may be subject to 122 complex criteria such as requiring an (n,t) quorum of signers but 123 these criteria are fixed at the time the signature is created 125 Aggregate Signatures A single signature created using multiple 126 signature key shares such that validation of the aggregate 127 signature serves to validate the participation of each of the 128 individual signers. 130 This document builds on the approach described in 131 [draft-hallambaker-threshold] to define a scheme that creates 132 threshold signatures that are computationally indistinguishable from 133 those produced according to the algorithm specified in [RFC8032]. 134 The scheme does not support the creation of aggregate signatures. 136 The approach used is based on that developed in FROST [Komlo]. This 137 document describes the signature scheme itself. The techniques used 138 to generate keys are described separately in 139 [draft-hallambaker-threshold]. 141 As in the base document, we first describe signature generation for 142 the case that _n_ = _t_ using 'direct' coefficients, that is the 143 secret scalar is the sum of the secret shares. We then show how the 144 scheme is modified using Shamir secret sharing [Shamir79] and 145 Lagrange coefficients for the case that _n_ > _t_. 147 1.1. Applications 149 Threshold signatures have application in any situation where it is 150 desired to have finer grain control of signing operations without 151 this control structure being visible to external applications. It is 152 of particular interest in situations where legacy applications do not 153 support multi-signatures. 155 1.1.1. HSM Binding 157 Hardware Security Modules (HSMs) prevent accidental disclosures of 158 signature keys by binding private keys to a hardware device from 159 which it cannot be extracted without substantial effort. This 160 provides effective mitigation of the chief causes of key disclosure 161 but requires the signer to rely on the trustworthiness of a device 162 that represents a black box they have no means of auditing. 164 Threshold signatures allow the signer to take advantage of the key 165 binding control provided by an HSM without trusting it. The HSM only 166 contributes one of the key shares used to create the signature. The 167 other is provided by the application code (or possibly an additional 168 HSM). 170 1.1.2. Code Signing 172 Code signing is an important security control used to enable rapid 173 detection of malware by demonstrating the source of authorized code 174 distributions but places a critical reliance on the security of the 175 signer's private key. Inadvertent disclosure of code signing keys is 176 commonplace as they are typically stored in a form that allows them 177 to be used in automatic build processes. Popular source code 178 repositories are regularly scanned by attackers seeking to discover 179 private signature keys and passwords embedded in scripts. 181 Threshold signatures allow the code signing operation to be divided 182 between a developer key and an HSM held locally or by a signature 183 service. The threshold shares required to create the signature can 184 be mapped onto the process roles and personnel responsible for 185 authorizing code release. This last concern might be of particular 186 advantage in open source projects where the concentration of control 187 embodied in a single code signing key has proved to be difficult to 188 reconcile with community principles. 190 1.1.3. Signing by Redundant Services 192 Redundancy is as desirable for trusted services as for any other 193 service. But in the case that multiple hosts are tasked with 194 compiling a data set and signing the result, there is a risk of 195 different hosts obtaining a different view of the data set due to 196 timing or other concerns. This presents the risk of the hosts 197 signing inconsistent views of the data set. 199 Use of threshold signatures allows the criteria for agreeing on the 200 data set to be signed to be mapped directly onto the requirement for 201 creating a signature. So if there are three hosts and two must agree 202 to create a signature, three signature shares are created and with a 203 threshold of two. 205 2. Definitions 207 This section presents the related specifications and standard, the 208 terms that are used as terms of art within the documents and the 209 terms used as requirements language. 211 2.1. Requirements Language 213 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 214 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 215 document are to be interpreted as described in [RFC2119]. 217 2.2. Defined Terms 219 See [draft-hallambaker-threshold]. 221 2.3. Related Specifications 223 This document extends the approach described in 224 [draft-hallambaker-threshold] to support threshold signatures. The 225 deterministic mechanism described in specification 226 [draft-hallambaker-mesh-udf] is used to generate the private keys 227 used in the test vectors. 229 2.4. Implementation Status 231 The implementation status of the reference code base is described in 232 the companion document [draft-hallambaker-mesh-developer]. 234 3. Principles 236 The threshold signatures created according to the algorithms 237 described in this document are compatible with but not identical to 238 the signatures created according to the scheme described in 239 [RFC8032]. In particular: 241 * The signature verification algorithm is unchanged. 243 * The unanimous threshold scheme produces values of _R_ and _S_ that 244 are deterministic but different from the values that would be 245 obtained by using the aggregate private key to sign the same 246 document. 248 * The deterministic quorate threshold scheme produces values of _R_ 249 and _S_ that are deterministic for a given set of signers but will 250 change for a different set of signers or if the aggregate private 251 key was used to sign the same document. 253 * ?The non-deterministic quorate threshold scheme produces values of 254 _R_ and _S_ that will be different each time the document is 255 signed. 257 Recall that a digital signature as specified by [RFC8032] consists of 258 a pair of values _S_, _R_ calculated as follows: 260 _R_ = _r.B_ 262 S = _r_ + _k.s_ mod _L_ 264 Where _B_ is the base point of the elliptic curve. 266 _r_ is an unique, unpredictable integer value such that 0 r L 268 _k_ is the result of applying a message digest function determined 269 by the curve (Ed25519, Ed448) to a set of parameters known to the 270 verifier which include the values _R_, _A_ and PH(_M_). 272 _A_ is the public key of the signer, _A_ = _s.B_ 274 PH(_M_) is the prehash function of the message value. 276 _s_ is the secret scalar value 277 _L_ is the order of the elliptic curve group. 279 To verify the signature, the verifier checks that: 281 _S.B_ = _R_ + _k.A_ 283 This equality must hold for a valid signature since: 285 _S.B_ = (_r_ + _k.s_)._B_ 287 = _r.B_ +_k_.(_s.B_) 289 = _R_ + _k.A_ 291 The value _r_ plays a critical role in the signature scheme as it 292 serves to prevent disclosure of the secret scalar. If the value _r_ 293 is known, _s_ can be calculated as _s_ = (_S-r_)._k_^(-1) mod _L_. It 294 is therefore essential that the value _r_ be unguessable. 296 Furthermore, if the same value of _r_ is used to sign two different 297 documents, this results two signatures with the same value _R_ and 298 different values of _k_ and _S_. Thus 300 _S_(1)_ = _r_ + _k_(1)_._s_ mod _L_ 302 S_(2) = _r_ + _k_(2).s mod L_ 304 s = (_S_(1)_ - _S_(2)_)(_k_(1)_ - _k_(2)_)^(-1) mod _L_ 306 The method of constructing _r_ MUST ensure that it is unique and 307 unguessable. 309 3.1. Direct shared threshold signature 311 A threshold signature R, S is constructed by summing a set of 312 signature contributions from two or more signers. For the case that 313 the composite private key is the sum of the key shares (_n_ = _t_), 314 each signer _i_ provides a contribution as follows: 316 A_(i) = s_(i).B 318 R_(i) = r_(i).B 320 S_(i) = r_(i) + k.s_(i) mod L 322 Where s_(i) and r_(i) are the secret scalar and unguessable value for 323 the individual signer. 325 The contributions of signers {1, 2, ... n} are then combined as 326 follows: 328 R = R_(1) + R_(2) + ... + R_(n) 330 S = S_(1) + S_(2) + ... + S_(n) 332 A = s.B 334 Where s = (s_(1) + s_(2) + ... + s_(n)) mod L 336 The threshold signature is verified in the same manner as before: 338 S.B = R + k.A 340 Substituting for S.B we get: 342 = (S_(1) + S_(2) + ... + S_(n)).B 344 = S_(1).B + S_(2).B + ... + S_(n).B 346 = (r_(1) + k.s_(1)).B + (r_(2) + k.s_(2)).B + ... + (r_(n) + 347 k.s_(n)).B 349 = (r_(1).B + k.s_(1).B) + (r_(2).B + k.s_(2).B) + ... + (r_(n).B + 350 k.s_(n).B) 352 = (R1 + k.A1) + (R1 + k.A1) + ... + (Rn + k.An) 354 Substituting for R + k.A we get: 356 = R_(1) + R_(2) + ... + R_(n) + k.(A_(1) + A_(2) + ... + A_(n)) 358 = R_(1) + R_(2) + ... + R_(n) + k.A_(1) + k.A_(2) + ... + k.A_(n) 360 = (R_(1) + k.A_(1)) + (R_(1) + k.A_(1)) + ... + (R_(n) + k.A_(n)) 362 As expected, the operation of threshold signature makes use of the 363 same approach as threshold key generation and threshold decryption as 364 described in [draft-hallambaker-threshold]. As with threshold 365 decryption it is not necessary for each key share holder to have a 366 public key corresponding to their key share. All that is required is 367 that the sum of the secret scalar values used in calculation of the 368 signature modulo the group order be the value of the aggregate secret 369 scalar corresponding to the aggregate secret key. 371 While verification of [RFC8032] signatures is unchanged, the use of 372 threshold signatures requires a different approach to signing. In 373 particular, the fact that the value k is bound to the value R means 374 that the participants in the threshold signature scheme must agree on 375 the value R before the value k can be calculated. Since k is 376 required to calculate the signature contributions S_(i) can be 377 calculated, it is thus necessary to calculate the values R_(i) and 378 S_(i) in separate phases. The process of using a threshold signature 379 to sign a document thus has the following stages orchestrated by a 380 dealer as follows: 382 0. The dealer determines the values F, C and PH(M) as specified in 383 [RFC8032] and transmits them to the signers {1, 2, ... n}. 385 1. Each signer generates a random value r_(i) such that 1 r_(i) L, 386 calculates the value R_(i) = r_(i).B and returns R to the dealer 387 . 389 2. The dealer calculates the value R = R_(1) + R_(2) + ... + R_(n) 390 and transmits R and A to the signers {1, 2, ... n}. 392 3. Each signer uses the suppled data to determine the value k and 393 hence S_(i) = r_(i) + k.s_(i) mod L and transmits it to the 394 dealer . 396 4. The dealer calculates the value S = S_(1) + S_(2) + ... + S_(n) 397 and verifies that the resulting signature R, S verifies according 398 to the mechanism specified in [RFC8032]. If the signature is 399 correct, the dealer publishes it. Otherwise, the dealer MAY 400 identify the signer(s) that provided incorrect contributions by 401 verifying the values R_(i) and S_(i) for each. 403 For clarity, the dealer role is presented here as being implemented 404 by a single party. 406 3.2. Shamir shared threshold signature 408 To construct a threshold signature using shares created using Shamir 409 Secret Sharing, each private key value _s_(i)_ is multiplied by the 410 Lagrange coefficient _l_(i)_ corresponding to the set of shares used 411 to construct the signature: 413 A_(i) = s_(i)l_(i).B 415 R_(i) = r_(i).B 417 _S_(i) = ri + klisi mod L_ 418 It is convenient to combine the derivation of _S_(i)_ for the 419 additive and Shamir shared threshold signatures by introducing a key 420 multiplier coefficient _c_(i)_: 422 _S_(i) = ri + kcisi mod L_ 424 Where _c_(i)_ = 1 for the additive shared threshold signature 426 _c_(i)_ = _l_(i)_ for the Shamir shared threshold signature 428 3.3. Stateless computation of final share 430 One of the chief drawbacks to the algorithm described above is that 431 it requires signers to perform two steps with state carried over from 432 the first to the second to avoid reuse of the value _r_(i)_. This 433 raises particular concern for implementations such as signature 434 services or HSMs where maintaining state imposes a significant cost. 436 Fortunately, it is possible to modify the algorithm so that the final 437 signer does not need to maintain state between steps: 439 0. All the signers except the final signer _F_ generate their value 440 _r_(i)_ and submit the corresponding value _R_(i)_ to the dealer 442 1. Dealer calculates the value _R_ - _R_(F)_ and sends it to the 443 final signer together with the all the other parameters required 444 to calculate _k_ and the final signer's key multiplier 445 coefficient _c_(F)_. 447 2. The final signer generates its value _r_(F)_ 449 3. The final signer calculates the value _R_(F)_ from which the 450 values _R_ and _k_ can now be determined. 452 4. The final signer calculates its key share contribution _S_(F) = 453 rF + kcFsF mod L._ 455 5. The final signer returns the values _S_(F)_ and _R_ to the 456 dealer. 458 6. The dealer reports the value R to the other signers and continues 459 the signature process as before. 461 While this approach to stateless computation of the signature 462 contributions is limited to the final share, this is sufficient to 463 cover the overwhelming majority of real-world applications where _n_ 464 = _t_ = 2. 466 Note that the final signer MAY calculate its value _r_(F)_ 467 deterministically provided that the parameters _R_ - _R_(F)_ and 468 _c_(F)_ are used in its determination. Other signers MUST NOT use a 469 deterministic means of generating their value _r_(i)_ since the 470 information known to them at the time this parameter is generated is 471 not sufficient to fix the value of _R_. 473 3.3.1. Side channel resistance 475 The use of Kocher side channel resistance as described in 476 [draft-hallambaker-threshold] entails randomly splitting the private 477 key into two shares and performing the private key operation 478 separately on each share to avoid repeated operations using the same 479 private key value at the cost of performing each operation twice. 481 This additional overhead MAY be eliminated when threshold approaches 482 are used by applying blinding factors whose sum is zero to each of 483 the threshold shares. 485 For example, if generation of the threshold signature is divided 486 between an application program A and an HSM B using the final share 487 approach to avoid maintaining state in the HSM, we might generate a 488 blinding factor thus: 490 0. A generates a random nonce _n_(A)_ and sends it to B with the 491 other parameters required to generate the signature. 493 1. B generates a random nonce _n_(B)_ 495 2. B calculates the blinding factor _x_ by calculating 496 _H_(_n_(A,)nB) where H is a strong cryptographic digest function 497 and converting the result to an integer in the range 1 x L._ 499 3. B calculates the signature parameters as before except that the 500 threshold signature contribution is now _S_(B) = rB + k(cBsB + x) 501 mod L._ 503 4. B returns the nonce _n_(B)_ to A with the other parameters. 505 5. A calculates the blinding factor _x_ using the same approach as B 507 6. A calculates the signature parameters as before except that the 508 threshold signature contribution is now _S_(A) = rA + k(cAsA - x) 509 mod L._ 511 This approach MAY be extended to the case that _t_ > 2 by 512 substituting a Key Derivation Function (e.g. [RFC5860]) for the 513 digest function. 515 3.4. Security Analysis 517 We consider a successful breach of the threshold signature scheme to 518 be any attack that allows the attacker to create a valid signature 519 for any message without the participation of the required threshold 520 of signers. 522 Potential breaches include: 524 * Disclosure of the signature key or signature key share. 526 * Modification of signature data relating to message M to allow 527 creation of a signature for message M'. 529 * Ability of one of the signers to choose the value of the aggregate 530 public key. 532 * Access control attacks inducing a signer to create a signature 533 contribution that was not properly authenticated or authorized. 535 We regard attacks on the access control channel to be out of scope 536 for the threshold signature algorithm, though they are certainly a 537 concern for any system in which a threshold signature algorithm is 538 employed. 540 We do not consider the ability of a signer to cause creation of an 541 invalid signature to represent a breach. 543 3.4.1. Calculation of r values 545 The method of constructing the values _r_(i)_ MUST ensure that each 546 is unique and unguessable both to external parties, the signers and 547 the dealer. The deterministic method specified in [RFC8032] cannot 548 be applied to generation of the values r_(i) as it allows the dealer 549 to cause signers to reveal their key shares by requesting multiple 550 signature contributions for the same message but with different 551 values of _k_. In particular, requesting signature contributions for 552 the same message: 554 With different Lagrange coefficients. 556 With a false value of _R_ 558 To avoid these attacks, the value r_(i) is generated using a secure 559 random number generator. This approach requires the signer to ensure 560 that values are never reused requiring that the signing API maintain 561 state between the first and second rounds of the algorithm. 563 While there are many approaches to deterministic generation of r_(i) 564 that appear to be sound, closer inspection has demonstrated these to 565 be vulnerable to rogue key and rogue contribution attacks. 567 3.4.2. Replay Attack 569 The most serious concern in the implementation of any Schnorr type 570 signature scheme is the need to ensure that the value r_(i) is never 571 revealed to any other party and is never used to create signatures 572 for two different values of k.s_(i). 574 Ensuring this does not occur imposes significant design constraints 575 as creating a correct signature contribution requires that the signer 576 use the same value of r_(i) to construct its value or R_(i) and 577 S_(i). 579 For example, a HSM device may be required to perform multiple 580 signature operations simultaneously. Since the storage capabilities 581 of an HSM device are typically constrained, it is tempting to attempt 582 to avoid the need to track the value of r_(i) within the device 583 itself using an appropriately authenticated and encrypted opaque 584 state token. Such mechanisms provide the HSM with the value of r_(i) 585 but do not and cannot provide protection against a replay attack in 586 which the same state token is presented with a request to sign 587 different values of k. 589 3.4.3. Malicious Contribution Attack 591 In a malicious contribution attack, one or more parties present a 592 signature contribution that does not meet the criteria R_(i) = 593 r_(i).B and S_(i) = r_(i) + ks_(i). 595 Such an attack is not considered to be a breach as it merely causes 596 the signature process to fail. 598 3.4.4. Rogue Key Attack 600 A threshold signature scheme that allows the participants to 'bring 601 their own key' may be vulnerable to a rogue key attack in which a 602 signer is able to select the value of the aggregate public signature 603 key by selecting a malicious public signature key value. 605 The scheme described in this document is a threshold signature scheme 606 and does not support this feature. Consequently, this attack is not 607 relevant. It is described here for illustrative purposes only. 609 This particular attack only applies when the individual signers 610 create their own signature shares. It is not a concern when the 611 signature shares are created by splitting a master signature private 612 key. 614 Consider the case where the aggregate public key signature is 615 calculated from the sum of public signature key share values 616 presented by the signers: 618 A = A_(1) + A_(2) + ... + A_(n) 620 If the public key values are presented in turn, the last signer 621 presenting their key share can force the selection of any value of A 622 that they choose by selecting A_(n) = A_(m) - (A_(1) + A_(2) + ... + 623 A_(n-1)) 625 The attacker can thus gain control of the aggregate signature key by 626 choosing A_(m) = s_(m).B where s_(m) is a secret scalar known only to 627 the attacker. But does so at the cost of not knowing the value s_(n) 628 and so the signer cannot participate in the signature protocol. 630 This attack allows the attacker and the attacker alone to create 631 signatures which are validated under the aggregate signature key. 633 The attack is a consequence of the mistaken assumption that a 634 signature created under the signature key A_(1) + A_(2) + ... + A_(n) 635 provides evidence of the individual participation of the 636 corresponding key holders without separate validation of the 637 aggregate key. 639 Enabling the use of threshold signature techniques by ad-hoc groups 640 of signers using their existing signature keys as signature key 641 shares presents serious technical challenges that are outside the 642 scope of this specification. 644 4. Ed2519 Signature 646 The means by which threshold shares are created is described in 647 [draft-hallambaker-threshold]. 649 The dealer selects the signers who are to construct the signature. 650 Each signer then computes the value R_(i): 652 0. Randomly generate an integer r_(i) such that 1 r_(i) L. 654 1. Compute the point R_(i) = r_(i)B. For efficiency, do this by 655 first reducing r_(i) modulo L, the group order of B. Let the 656 string R_(i) be the encoding of this point. 658 2. Transmit the value R_(i) to the dealer 660 3. At some later point, the dealer MAY complete the signature by 661 returning the values F, C, A and R as specified in [RFC8032] 662 together with the key multiplier coefficient c_(i). The signers 663 MAY then complete their signature contributions: 665 4. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the 666 64-octet digest as a little-endian integer k. 668 5. Compute S_(i) = (r_(i) + kc_(i)s_(i)) mod L. For efficiency, 669 again reduce k modulo L first. 671 6. Return the values R_(i), S_(i) to the dealer . 673 The dealer then completes the signature by: 675 0. Computing the composite value S = S_(1) + S_(2) + ... + S_(n) 677 1. Verifying that the signature R, S is valid. 679 2. Publishing the signature. 681 5. Ed448 Signature 683 The means by which threshold shares are created is described in 684 [draft-hallambaker-threshold]. 686 The dealer selects the signers who are to construct the signature. 687 Each signer then computes the value R_(i): 689 0. Randomly generate an integer r_(i) such that 1 r_(i) L. 691 1. Compute the point R_(i) = r_(i)B. For efficiency, do this by 692 first reducing r_(i) modulo L, the group order of B. Let the 693 string R_(i) be the encoding of this point. 695 Transmit the value R_(i) to the dealer 697 0. At some later point, the dealer MAY complete the signature by 698 returning the values F, C, A and R as specified in [RFC8032] 699 together with the key multiplier coefficient c_(i). The signers 700 MAY then complete the signature contributions: 702 1. Compute SHAKE256(dom4(F, C) || R || A || PH(M), 114), and 703 interpret the 114-octet digest as a little-endian integer k. 705 2. Compute S_(i) = (r_(i) + kc_(i)s_(i)) mod L. For efficiency, 706 again reduce k modulo L first. 708 3. Return the values R_(i), S_(i) to the dealer. 710 The dealer then completes the signature by: 712 0. Computing the composite value S = S_(1) + S_(2) + ... + S_(n) 714 1. Verifying that the signature R, S is valid. 716 2. Publishing the signature. 718 6. Test Vectors 720 6.1. Direct Threshold Signature Ed25519 722 The signers are Alice and Bob's Threshold Signature Service 'Bob'. 723 Each creates a key pair: 725 ED25519Alice's Key (ED25519) 726 UDF: ZAAA-GTSI-GXED-255X-XALI-CEXS-XKEY 727 Scalar: 312191303806394376947696888962276115420485359001 728 34467943432016761653342335248 729 Encoded Private 730 10 AE C0 C2 16 65 9B 4F 7C 9D DE 82 3E 49 7F D4 731 9B 14 BB F8 2D 9F 0C 11 24 D7 15 E3 43 79 57 20 732 X: -13697699435406080999251131063344049965140553452 733 752305353714819106646919347160064793506327635954342719144289 734 2305566686088586980395284289746495530409889930 735 Y: 278793875610616080844162800185864399625503938157 736 569374174700414845758479331294424147393776831767266487579098 737 7675375777043504113387553916769515911310193558 738 Encoded Public 739 45 16 53 7C 26 50 CF DA F1 A4 DF 4C 45 DC 3D 95 740 4E B6 8E EB A6 5A 27 D6 CD 5B 43 C5 F4 06 53 ED 741 ED25519Bob's Key (ED25519) 742 UDF: ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY 743 Scalar: 567212843891509414800308620158891720685508995620 744 72140666211075925337851277632 745 Encoded Private 746 E5 CD 34 01 FD 8C 0E 27 81 4B 11 DD 12 68 50 A1 747 4B 5A D5 E1 E1 41 D7 68 5F 51 ED B4 3A 84 58 5C 748 X: -13809282472298084436735987888897423507149580966 749 952791761446670884044433963975178482398144657564565223270588 750 5322459642470946347570575475534141406285323257 751 Y: 263684226342871984706317411760423095947068088366 752 393546798602378437432707482089806653755881399592963068751759 753 9645362525866308283171284327931970404321458677 754 Encoded Public 755 F1 5F C0 78 F8 32 49 2C D9 64 CC 2B CF 90 5C 4F 756 23 EA BB F8 38 99 C5 FE F3 AA 67 BE AB EC D2 5E 758 The composite Signature Key A = A_(a) + A_(b) 759 Aggregate Key = Alice + Bob () 760 UDF: TBS 761 Scalar: 109634784180323260712231215560085272031403914964 762 7717337619681427565742601012 763 Encoded Private 764 34 33 AB 10 9A 09 A9 61 65 8B 3A EC 58 21 FB 2D 765 0D 45 74 49 45 BA E2 CF A8 98 C2 94 C9 82 6C 02 766 X: -83837675294300852842901121613445594296352372347 767 711317409367737761568353629718805151940195325485285476438422 768 923698718220652243749390297055882388709313280 769 Y: 160553422944358144751060009820735322036903773802 770 361117046457476895165059738086663330972263850675453249990301 771 0398473811263196653225446124160025082144761534 772 Encoded Public 773 48 1A 27 66 06 AF 4E 3C 20 A4 02 CD 8A 13 46 99 774 02 B7 75 F8 AC D4 7E 89 68 FB 68 EB D8 EF 4A C7 776 To sign the text "This is a test", Alice first generates her value r 777 and multiplies it by the base point to obtain the value R_(a): 779 Alice: 780 r_a: 304554767184319354570910632330847275245170925807 781 471005852065308719163006873 782 R_a = 783 4D D3 35 87 4D D2 A9 35 79 CF 33 11 4E 3C 4C 86 784 A3 46 83 F8 77 2B 69 B9 BE 8A D0 03 5B 07 1B 3D 786 Alice passes her value R_(A) to Bob along with the other parameters 787 required to calculate i. Bob then calculates his value R_(A) and 788 multiplies it by the base point to obtain the value R_(b): 790 Bob: 791 r_b: 211453017009495036941255861540216441186480571963 792 4308458833747992420728606380 793 R_b = 794 9E 92 BB 50 CD DA 6A 97 70 83 54 82 4A C5 A2 5E 795 CF 0C 53 65 19 55 74 E0 66 F7 49 0B F1 9E 42 C1 797 Bob can now calculate the composite value R = R_(a) + R_(b) and thus 798 the value k. 800 R = 801 6D 04 0A 15 D3 26 95 7E 60 4B 31 B9 40 03 34 24 802 C1 E2 94 CE 4C 2D 67 AC 23 F9 09 EB 01 35 27 BC 803 k: 141815370378674010309754096097287620917810351837 804 8705827473796209228380712742 806 Bob calculates his signature scalar contribution and returns the 807 value to Alice: 809 Bob: 810 S_b: 536363782415883723339410938370364298390876250983 811 1717008575694722457748759583 813 Alice can now calculate her signature scalar contribution and thus 814 the signature scalar S. 816 Alice: 817 S_a: 268700124091647466934677864874812484315783329013 818 4699034602004495702143596514 819 S: 813633487743049688767701469408773586209479440586 820 508437175748279874438105108 822 Alice checks to see that the signature verifies: 824 S.B = R + kA = 825 X: 303888032885010422619559054491601097433934565460 826 00461769461185182044799973523 827 Y: 242312166466765598632540958273647355363821360549 828 75658447998613064394185428840 830 6.2. Direct Threshold Signature Ed448 832 The signers are Alice and Bob's Threshold Signature Service 'Bob'. 833 Each creates a key pair: 835 ED448Alice's Key (ED448) 836 UDF: ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY 837 Scalar: 672286477331130983513039743350616227864346753924 838 962787860729757222511999618443513569403793186398096717924945 839 854846544396984088344823264 840 Encoded Private 841 6F 85 B1 91 9A 37 06 A6 B2 15 79 AD 5B 69 16 6A 842 5A CD C8 17 D4 14 1F 68 DA 97 C5 B4 44 79 CE EA 843 3C 17 7B E1 29 44 70 DF 41 C8 98 38 1E 7C 9B 3B 844 03 63 6F 85 E8 39 31 91 845 X: 526046019655043632868470952286947529492283092344 846 122476077151423645243648974512182548405702873560533846673262 847 767064019365470830861106049 848 Y: 145374550785380850812934424757986866673485237047 849 938554544492694946608060986459495807055455048208713991919477 850 720250115717234689256856152 851 Encoded Public 852 59 55 F4 7A 66 08 91 35 F8 15 63 F4 90 91 7F 38 853 12 E3 49 22 51 F8 BC 4A 41 C9 44 59 5A 64 9B 40 854 0B C5 7E 53 48 0F 32 12 90 32 69 38 47 28 94 BB 855 99 D1 16 6F 2D D5 3D 4F 80 856 ED448Bob's Key (ED448) 857 UDF: ZAAA-ITSI-G2ED-44XB-OBXS-XKEY 858 Scalar: 455052626698262385397736547727159423941520792904 859 908612603542850909167215987713902322619933929404455741806848 860 064294945283113799683261212 861 Encoded Private 862 CA 15 22 BD F4 0F 9E 0A EC A7 61 79 BE 9E E3 38 863 BF 93 D3 5B B3 E6 FC F0 A7 5B 7C F0 E7 B5 89 F6 864 2E F6 D1 0E 72 49 4D DF 34 5E 2F 7C 9E 42 1D 85 865 AB AB 30 BD 68 C6 3E 35 866 X: 752024108200272710832187535557164455078689734595 867 171189993383259892607253027500878543439908750525763880661232 868 171322059854852522782265 869 Y: 619329873102159676791326142073166790594683111409 870 729383584199833441028484525583699421181422168190856074786324 871 020492214873796495570056511 872 Encoded Public 873 76 2B FC F8 AC 96 79 DE 1C 72 07 65 DD 49 5B 28 874 C7 04 CB A8 A5 96 3D D9 9E 23 FA 05 83 15 33 95 875 85 82 F8 CF A3 7A 2F 24 F8 EB D6 AE 20 0A 25 D0 876 44 1A F9 C0 86 D7 87 B7 00 878 The composite Signature Key A = A_(a) + A_(b) 879 Aggregate Key = Alice + Bob () 880 UDF: TBS 881 Scalar: 370810175859830330867905792457688502754055057988 882 943100420373093608031918369199015948491953656482966798700316 883 64591515851455352870185802 884 Encoded Private 885 4A AB 7A BB 2D 95 72 75 B1 3A 1D 22 24 17 76 2D 886 A1 D5 55 94 67 35 8C E7 A1 A0 ED 0C E7 88 FF 9F 887 6E 2F 70 80 89 F5 01 2A C0 AD 4C 4E 7B 90 68 6C 888 F4 53 BA 32 9B 70 0F 0D 889 X: 583249553407699999284154112964835446252412293188 890 857058051552519639906663406776316984154017062023869075790536 891 30514579317017660114474427 892 Y: 518040437562811181169413740718290938351269168888 893 257124107164689245721852001077758864406412789756149699111633 894 051823234569886260996269341 895 Encoded Public 896 34 70 8D 08 DE 63 0B A6 49 2A 33 D8 B7 15 A9 84 897 A4 87 F6 B6 C7 4B 1C AE 5A 1F 7C 4B 12 70 FB CF 898 5A A9 3C 20 31 BA 9A 53 A0 FE 2A 43 24 97 06 F8 899 DA 40 0D 88 E3 D9 DE 2E 00 901 To sign the text "This is a test", Alice first generates her value r 902 and multiplies it by the base point to obtain the value R_(a): 904 Alice: 905 r_a: 177274411620382331885613075298112943809338383162 906 174753240420771790910425395072244220798681166866026098695507 907 899343208324484682831848544 908 R_a = 909 EC 4E A5 8E BE 3E DC C4 AA DC 67 65 D9 0D B1 24 910 82 97 7E 57 83 4C BC CA D0 68 98 72 B8 1A F2 61 911 E2 CC 2C AF AE F3 A9 8A 16 DF F1 1E 91 EC E2 FC 912 3C 09 DD 25 AB 6E 7D 02 00 914 Alice passes her value R_(A) to Bob along with the other parameters 915 required to calculate i. Bob then calculates his value R_(A) and 916 multiplies it by the base point to obtain the value R_(b): 918 Bob: 919 r_b: 914384096261894497392108217856312041404007433725 920 737987383860198449871749775140845071471047786135423317371867 921 85115509488719418941845277 922 R_b = 923 7E 8C 1C B1 EA 5F 9E 58 F4 E1 4C AB 9D CF C9 4B 924 42 8E 01 F4 B4 27 AA 74 D8 66 E8 5B D5 8C 23 10 925 31 A7 99 FC 69 3D 4A 81 56 9B 31 07 A4 7C 3B 83 926 9D 79 6B 12 08 D0 2C CC 80 928 Bob can now calculate the composite value R = R_(a) + R_(b) and thus 929 the value k. 931 R = 932 AE 82 1A 7D A9 B6 35 7A 3E CF 58 95 9E 97 3A 45 933 62 77 E5 DB F6 B5 B7 5F 5A 27 A0 29 0A 4D D4 2C 934 9F 39 97 BB A3 55 DC C8 BF 02 C1 8F CE 8E 92 D9 935 97 38 19 6B 73 07 19 FE 00 936 k: 120812996308912938173796275547209139305812356493 937 218326541177300961108122972500434047109753132978603955927000 938 049579948492518627324723657 940 Bob calculates his signature scalar contribution and returns the 941 value to Alice: 943 Bob: 944 S_b: 131642872805495450312819108720996394951179966909 945 422047047106195752645599694599197550402234644818088495417690 946 338344590538474713569000455 948 Alice can now calculate her signature scalar contribution and thus 949 the signature scalar S. 951 Alice: 952 S_a: 135660088492295551401234992018778138767930165450 953 263985669170229118586124164862063605687569508563259045492355 954 878328728103423148386029682 955 S: 855932802238892790767231487677734001306997921878 956 565176459038750760857198979216754398940488616889715775997525 957 07581656337124106095380358 959 Alice checks to see that the signature verifies: 961 S.B = R + kA = 962 X: 225696302738968030426017676274023389357161605713 963 77841610835599611770420843463 964 Y: 366869559370146495596698412318900310141515842791 965 80057095036770676314039224332 967 6.3. Shamir Threshold Signature Ed25519 969 The administrator creates the composite key pair 970 ED25519Aggregate Key (ED25519) 971 UDF: ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY 972 Scalar: 367238470592488326468789252109412889361910680229 973 03089760692844779165588879504 974 Encoded Private 975 FE 48 94 1F EB 3D 28 E1 61 81 E2 1E E1 CF F2 1E 976 1E 70 91 30 DF 98 9F 1C 34 EB BB 74 C5 C8 07 EB 977 X: 143576564277195758046684172284175869008525477709 978 640743490221115123376609940386394888392330104965579307772627 979 313244177612005636942740116142030215202393600 980 Y: 844838272625277895849027219595751726665225134917 981 547580682441821283235675507225396641352769322822815561632929 982 543097074319051436285787045255908364074589900 983 Encoded Public 984 DF E8 0A 2B E9 6C 53 C0 AB 9B BC BC 39 95 9A 61 985 9C 33 2E 22 24 A7 F7 F2 21 06 AC 6D 01 5D 0B E2 987 Three key shares are required for Alice, Bob and Carol with a 988 threshold of two. The parameters of the Shamir Secret Sharing 989 polynomial are: 991 a0 = 367238470592488326468789252109412889361910680229030897606928 992 44779165588879504 993 a1 = 338318986010852412366041291642398977925879116179901190258252 994 3043521639876163 996 The key share values for the participants are 998 xa = 1 999 ya = 392200903269604570067340531215030751116427738780256363326561 1000 3131259957500722 1002 xb = 2 1003 yb = 681933154723076103606316655313030495659521902216679298461852 1004 36496143125896 1006 xc = 3 1007 yc = 345138317558083173402104458195529282882474335202067983242870 1008 8280017783002059 1010 Alice and Carol are selected to sign the message "This is another 1011 test" 1013 The Lagrange coefficients are: 1015 la = 361850278866613110698659328152149712042855817968995380300097 1016 5469142727125496 1017 lc = 361850278866613110698659328152149712042855817968995380300097 1018 5469142727125494 1020 Alice and Carol select their values ra, rc 1022 ra = 183324669043432475889177343290874841197580255869543278119963 1023 6861783584446189 1024 Ra = 1025 54 9B F7 DF F9 4E FA 95 DE D8 27 4E 0D AD A4 81 1026 4B D7 1F CA 21 B4 B2 7D D6 06 4F 59 28 41 87 92 1028 rc = 161475617387612449161820030097871350703159449773365674965881 1029 1083650872383824 1030 Rc = 1031 95 25 84 AA B3 F7 39 14 10 67 E8 45 21 68 67 76 1032 11 73 88 28 D6 50 71 0F D4 21 67 12 98 CC 80 C7 1034 The composite value R = R_(a) + R_(c) 1036 R = 1037 22 B8 67 CA 63 65 00 7D AD 85 96 83 FD 86 CB 92 1038 88 E7 E7 73 F9 3E 48 8D AE 7E 43 E3 2D AC 5F 7F 1040 The value k is 1042 k = 300461162806835024067835386157211645931753120888211250552921 1043 1847964183554048 1045 The values R and k (or the document to be signed) and the Lagrange 1046 coefficients are passed to Alice and Carol who use them to calculate 1047 their secret scalar values: 1049 sa = 588301354904406855101010796822546126674641608170384544989841 1050 9696889936251083 1051 sc = 189281120087571523997607099054385070601618650367961388678662 1052 1329133835624465 1054 The signature contributions can now be calulated: 1056 Sa = 128238145780800590303153436041482532412837879827391619588852 1057 5270458485017264 1058 Sc = 425392829290723185011341307483608802636424146029130066221513 1059 8481933637068796 1061 The dealer calculates the composite value S = S_(a) + S_(b) 1062 S = 553630975071523775314494743525091335049262025856521685810366 1063 3752392122086060 1065 The dealer checks to see that the signature verifies: 1067 S.B = R + kA = 1068 X: 386656916198500913898974718482142916932478347228 1069 53747339220827400653000735042 1070 X: 272627300420736046999889168909581852465293124122 1071 69338237353604076047710443564 1073 6.4. Shamir Threshold Signature Ed448 1075 The administrator creates the composite key pair 1077 ED448Aggregate Key (ED448) 1078 UDF: ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY 1079 Scalar: 723088510822916843359337925516642493307623385482 1080 113107480846498794254549074097051759295396782499503452909258 1081 978468506553055366989547456 1082 Encoded Private 1083 59 DC 8A 5F 5E AF 8C FA 96 19 F8 EE 78 13 00 12 1084 33 0E 12 80 2D 25 E6 EF E8 E2 56 B5 83 6A 0C CF 1085 DC 11 96 A5 A5 D1 39 AA 34 25 0B 52 ED 9F 38 92 1086 5D 9F 7B BC B9 BC 86 45 1087 X: 600163199260212879671026282440221570752543874569 1088 276531213297382365938924845597497264583528185273760383031589 1089 25167107013312482098672476 1090 Y: 568007995844826855892481230051783440873263817862 1091 016100095069663100696528804467952219402043387612562057320585 1092 561865068046226655443122582 1093 Encoded Public 1094 ED C3 90 99 38 0B 8F CD 60 29 24 04 6C DE 52 33 1095 A2 07 3E 56 8D 27 B5 B9 21 60 CF E9 E7 9D D6 4A 1096 11 47 20 E6 9D FE 75 C7 04 14 70 18 B4 52 10 83 1097 D0 EC 98 BD F5 E6 E3 D5 80 1099 Three key shares are required for Alice, Bob and Carol with a 1100 threshold of two. The parameters of the Shamir Secret Sharing 1101 polynomial are: 1103 a0 = 723088510822916843359337925516642493307623385482113107480846 1104 49879425454907409705175929539678249950345290925897846850 1105 6553055366989547456 1106 a1 = 253947292459661473537056525563228503335644586909535883819036 1107 29593189848969312285942082195525418378983878506351793852 1108 012228645407360825 1110 The key share values for the participants are 1112 xa = 1 1113 ya = 216445157732761001637197701849608092875464834857486355812599 1114 29206860382197250994836594571141148378583546590493895709 1115 346188988958309165 1117 xb = 2 1118 yb = 470392450192422475174254227412836596211109421767022239631635 1119 58800050231166563280778676766666566757567425096845689561 1120 358417634365669990 1122 xc = 3 1123 yc = 724339742652083948711310752976065099546754008676558123450671 1124 88393240080135875566720758962191985136551303603197483413 1125 370646279773030815 1127 Alice and Carol are selected to sign the message "This is another 1128 test" 1130 The Lagrange coefficients are: 1132 la = 908548405369508613186654759860005667942051700859147575351862 1133 74897573001980769792858097877645846187981655146854545831 1134 152386877929824891 1135 lc = 908548405369508613186654759860005667942051700859147575351862 1136 74897573001980769792858097877645846187981655146854545831 1137 152386877929824889 1139 Alice and Carol select their values ra, rc 1141 ra = 597061760142011172791892795402895896258128262343360777519356 1142 25449868368724094466154383697912358541824000038036669052 1143 993742082445345445 1144 Ra = 1145 35 E5 61 55 78 E7 27 24 55 2D C9 76 4B 49 2B 46 1146 16 E3 FA 97 2F 9A E6 47 1B 22 CD 2D 54 F5 1A 1C 1147 7A A7 67 B0 CE 65 84 05 39 33 0E A6 33 5E 67 BD 1148 58 CA ED 7E F3 EE DD 59 00 1150 rc = 134782448747121628062621888359149856538463227176060814858572 1151 40759552504564125328966600869858667833252205589918638910 1152 3286110005426517374 1153 Rc = 1154 3C 7B 81 57 A9 C9 23 90 E2 1D 82 42 7B 0C D9 88 1155 E7 E5 98 81 DB 52 76 E3 77 67 E8 34 DC D7 DC 81 1156 20 B6 3A 6F EC E8 0C D9 0E BC C5 5A A0 E6 91 D5 1157 D9 14 0B 60 C2 A4 D0 A8 80 1159 The composite value R = R_(a) + R_(c) 1161 R = 1162 00 27 F8 F7 A7 39 F7 AE B6 8F E4 0F A8 4E 3A 71 1163 45 87 6A 1E C4 C3 29 52 CC 8A C7 6C 36 47 4B A6 1164 04 F8 55 03 7B 49 86 87 E4 91 AB 73 E0 AF 3F 12 1165 AB 7F 09 2D 4E 06 4A 71 00 1167 The value k is 1169 k = 111997156629233344141251678175691985810414419806912701822160 1170 03679477455027316936425566511876628316232490805931954430 1171 9467825781335347270 1173 The values R and k (or the document to be signed) and the Lagrange 1174 coefficients are passed to Alice and Carol who use them to calculate 1175 their secret scalar values: 1177 sa = 123321614196865011564245131263441780725524895314537710907076 1178 16870786357527664628511298973435756875585697503259538939 1179 5171670361367288637 1180 sc = 546378534043466638830999383371973118168674696520868513626526 1181 80700952961912832009497718396549853619706003345255804124 1182 467063738043309482 1184 The signature contributions can now be calulated: 1186 Sa = 458780069801903308724659679047126206540023727016859370284301 1187 27448209487257982695731719827860225173821194895861101407 1188 212569594681924953 1189 Sc = 401983114222685811776093088236307108408769238787937252473320 1190 58598217288865359359764076141664751937484813828720687591 1191 206436379246811336 1193 The dealer calculates the composite value S = S_(a) + S_(b) 1195 S = 860763184024589120500752767283433314948792965804796622757621 1196 86046426776123342055495795969524977111306008724581788998 1197 419005973928736289 1199 The dealer checks to see that the signature verifies: 1201 S.B = R + kA = 1202 X: 565863868058207644748379075787643375969163605886 1203 69329263413068616160478393570 1204 X: 150478297775841135131577263700053908124463098444 1205 5517859016637728894764938481 1207 7. Security Considerations 1209 All the security considerations of [RFC7748], [RFC8032] and 1210 [draft-hallambaker-threshold] apply and are hereby incorporated by 1211 reference. 1213 7.1. Rogue Key attack 1215 The rogue key attack described in [draft-hallambaker-threshold] is of 1216 particular concern to generation of threshold signatures. 1218 If _A_ and _B_ are public keys, the intrinsic degree of trust in the 1219 composite keypair _A_ + _B_ is that of the lesser of _A_ and _B_. 1221 7.2. Disclosure or reuse of the value r 1223 As in any Schnorr signature scheme, compromise of the value _r_ 1224 results in compromise of the private key. The base signature 1225 specification [RFC8032] describes a deterministic construction of _r_ 1226 that ensures confidentiality and uniqueness for a given value of _k_. 1228 As described above, this approach is not applicable to the generation 1229 of values of _r_(i)_ to compute threshold signature contributions. 1230 Accordingly the requirements of [RFC4086] regarding requirements for 1231 randomness MUST be observed. 1233 Implementations MUST NOT use a deterministic generation of the value 1234 _r_(i)_ for any threshold contribution except for calculating the 1235 final contribution when all the other parameters required to 1236 calculate _k_ are known. 1238 7.3. Resource exhaustion attack 1240 Implementation of the general two stage signing algorithm requires 1241 that signers track generation and use of the values _r_(i)_ to avoid 1242 reuse for different values of _R_(i)_. Implementations MUST ensure 1243 that exhaustion of this resource by one party does not cause other 1244 parties to be denied service. 1246 7.4. Signature Uniqueness 1248 Signatures generated in strict conformance with [RFC8032] are 1249 guaranteed to be unique such that signing the same document with the 1250 same key will always result in the same signature value. 1252 The signature modes described in this document are computationally 1253 indistinguishable from those created in accordance with [RFC8032] but 1254 are not unique. 1256 Implementations MUST not use threshold signatures in applications 1257 where signature values are used in place of cryptographic digests as 1258 unique content identifiers. 1260 8. IANA Considerations 1262 This document requires no IANA actions. 1264 9. Acknowledgements 1266 [TBS] 1268 10. Normative References 1270 [draft-hallambaker-mesh-udf] 1271 Hallam-Baker, P., "Mathematical Mesh 3.0 Part II: Uniform 1272 Data Fingerprint.", Work in Progress, Internet-Draft, 1273 draft-hallambaker-mesh-udf-10, 27 July 2020, 1274 . 1277 [draft-hallambaker-threshold] 1278 Hallam-Baker, P., "Threshold Modes in Elliptic Curves", 1279 Work in Progress, Internet-Draft, draft-hallambaker- 1280 threshold-03, 3 September 2020, 1281 . 1284 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1285 Requirement Levels", BCP 14, RFC 2119, 1286 DOI 10.17487/RFC2119, March 1997, 1287 . 1289 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 1290 "Randomness Requirements for Security", BCP 106, RFC 4086, 1291 DOI 10.17487/RFC4086, June 2005, 1292 . 1294 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1295 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1296 2016, . 1298 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1299 Signature Algorithm (EdDSA)", RFC 8032, 1300 DOI 10.17487/RFC8032, January 2017, 1301 . 1303 11. Informative References 1305 [draft-hallambaker-mesh-developer] 1306 Hallam-Baker, P., "Mathematical Mesh: Reference 1307 Implementation", Work in Progress, Internet-Draft, draft- 1308 hallambaker-mesh-developer-10, 27 July 2020, 1309 . 1312 [Komlo] Komlo, C. and I. Goldberg, "FROST: Flexible Round- 1313 Optimized Schnorr Threshold Signatures", 2020. 1315 [RFC5860] Vigoureux, M., Ward, D., and M. Betts, "Requirements for 1316 Operations, Administration, and Maintenance (OAM) in MPLS 1317 Transport Networks", RFC 5860, DOI 10.17487/RFC5860, May 1318 2010, . 1320 [Shamir79] Shamir, A., "How to share a secret.", 1979.