idnits 2.17.1 draft-hallambaker-threshold-sigs-02.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 (9 March 2020) is 1509 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'TBS' is mentioned on line 1267, 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 9 March 2020 5 Expires: 10 September 2020 7 Threshold Signatures in Elliptic Curves 8 draft-hallambaker-threshold-sigs-02 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 10 September 2020. 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 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 . . . . . . . . . . . . . . . . . . 5 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 . . . . . . . . . . . . . . . . . . . . 11 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 . . . . . . . . . . . . 18 78 6.3. Shamir Threshold Signature Ed25519 . . . . . . . . . . . 21 79 6.4. Shamir Threshold Signature Ed448 . . . . . . . . . . . . 24 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 81 7.1. Rogue Key attack . . . . . . . . . . . . . . . . . . . . 27 82 7.2. Disclosure or reuse of the value r . . . . . . . . . . . 27 83 7.3. Resource exhaustion attack . . . . . . . . . . . . . . . 27 84 7.4. Signature Uniqueness . . . . . . . . . . . . . . . . . . 27 85 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 86 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 87 10. Normative References . . . . . . . . . . . . . . . . . . . . 28 88 11. Informative References . . . . . . . . . . . . . . . . . . . 28 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 278 _L_ is the order of the elliptic curve group. 280 To verify the signature, the verifier checks that: 282 _S.B_ = _R_ + _k.A_ 284 This equality must hold for a valid signature since: 286 _S.B_ = (_r_ + _k.s_)._B_ 288 = _r.B_ +_k_.(_s.B_) 290 = _R_ + _k.A_ 292 The value _r_ plays a critical role in the signature scheme as it 293 serves to prevent disclosure of the secret scalar. If the value _r_ 294 is known, _s_ can be calculated as _s_ = (_S-r_)._k_^(-1) mod _L_. It 295 is therefore essential that the value _r_ be unguessable. 297 Furthermore, if the same value of _r_ is used to sign two different 298 documents, this results two signatures with the same value _R_ and 299 different values of _k_ and _S_. Thus 301 _S_(1)_ = _r_ + _k_(1)_._s_ mod _L_ 303 S_(2) = _r_ + _k_(2).s mod L_ 305 s = (_S_(1)_ - _S_(2)_)(_k_(1)_ - _k_(2)_)^(-1) mod _L_ 307 The method of constructing _r_ MUST ensure that it is unique and 308 unguessable. 310 3.1. Direct shared threshold signature 312 A threshold signature R, S is constructed by summing a set of 313 signature contributions from two or more signers. For the case that 314 the composite private key is the sum of the key shares (_n_ = _t_), 315 each signer _i_ provides a contribution as follows: 317 A_(i) = s_(i).B 319 R_(i) = r_(i).B 321 S_(i) = r_(i) + k.s_(i) mod L 323 Where s_(i) and r_(i) are the secret scalar and unguessable value for 324 the individual signer. 326 The contributions of signers {1, 2, ... n} are then combined as 327 follows: 329 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_ 419 It is convenient to combine the derivation of _S_(i)_ for the 420 additive and Shamir shared threshold signatures by introducing a key 421 multiplier coefficient _c_(i)_: 423 _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: 56271244081186130980636545017945156580516101894352492 728 459594967614223399428880 729 Encoded Private 730 33 40 0E 22 D8 67 17 F4 8A 9F 6A 46 61 B4 0E AD 731 8C D0 DD C3 79 CD 85 BD 95 5C 90 B9 6C CB 8C 23 732 X: 11116793672970427161790264469280294507189044728140547954071022 733 7976454124042406369344932655633664630560242213431409139866940 734 284702002648469365756492647970 735 Y: 61655404171611396573021808119108664749574235125343680206454285 736 6299141386615046548323087409388548650272224487089895079970526 737 0143544115364878870129761259200 738 Encoded Public 739 E2 AB 8F 37 62 C8 7B F9 E9 BC 59 0C 2E 99 A5 58 740 0C C3 19 D5 CD DA 53 DF 3E C1 F0 C0 FE D3 55 5E 741 ED25519Bob's Key (ED25519) 742 UDF: ZAAA-GTSI-G2ED-255X-XBOB-XSXK-EY 743 Scalar: 54940772670153459146152925564198105262971485730889818 744 986727608573229799020168 745 Encoded Private 746 68 9A 68 92 8A 06 17 84 35 3C B7 08 F8 56 00 3F 747 BA 31 8C 42 B0 42 FE 2D 18 F2 7F AB CD 10 49 F1 748 X: 14271495069349838216379540196263140964032393512903842206168182 749 5518850827098876289800868735522232908519794251130907125878675 750 6343411484065706313568410880015 751 Y: 28094328948004112428189466223757440886388684291254605355859923 752 6240968229706795825282419594219442074647093851302547452470435 753 9438513477629978601366725015573 754 Encoded Public 755 32 E5 8D 5E 66 B2 F9 E9 14 79 08 71 96 3B 9A 75 756 A2 31 59 4B 8E ED 18 EF BD FF 11 D4 47 2A 8C F4 758 The composite Signature Key A = A_(a) + A_(b) 760 Aggregate Key = Alice + Bob () 761 UDF: TBS 762 Scalar: 26569330913556569171916721364983482306308422345436973 763 56293312113171384684213 764 Encoded Private 765 B5 CE 0E B3 9C CF 18 99 CF 8D 4C BB AE 81 79 1F 766 CE 13 AA 3E 63 59 5B AC 8D 2C EB A4 55 C5 DF 05 767 X: 67872685043898469012456949773240814121645904736114813455820339 768 8688906486811443744733724675994181258029547346985079901494367 769 752381127781166234556148580090 770 Y: 36481740058369645484420180976004932062085375941522344052907594 771 0118552792158551197107484892204562290802810655253510302448455 772 4128548992118101415797909250954 773 Encoded Public 774 29 65 63 86 4F FB 10 8D BA 7A 0A 68 04 6D 00 DA 775 9B 1D C3 A4 AF BA 95 B4 5D 27 B4 35 00 2F DF 32 777 To sign the text "This is a test", Alice first generates her value r 778 and multiplies it by the base point to obtain the value R_(a): 780 Alice: 781 r_a = 47498736868184230171598682949552850028048129926454476046383202 782 22101432831360 783 R_a = 784 37 4D BC B2 FC 26 43 69 DA B7 DF 78 F7 05 63 1D 785 C4 96 FB FB D6 CC 6A 9E 92 ED E7 35 93 44 B8 14 787 Alice passes her value R_(A) to Bob along with the other parameters 788 required to calculate i. Bob then calculates his value R_(A) and 789 multiplies it by the base point to obtain the value R_(b): 791 Bob: 792 r_b = 52485056662860498129500187267044856221580824276836907703860095 793 4226327269184 794 R_b = 795 AB A1 A8 28 11 6E FC A0 E9 8B CF 53 A2 4C AF F8 796 66 59 69 4B 2F 37 93 77 92 3A 70 95 33 DE 5B 54 798 Bob can now calculate the composite value R = R_(a) + R_(b) and thus 799 the value k. 801 R = 802 5B 68 76 8C CA 23 E6 84 36 92 76 F1 9E FF 08 8F 803 0A 16 A9 55 E3 96 9C 84 36 28 89 DB 06 16 43 44 804 k = 2386567530061545624821866403866306492890802298065266303263411446 805 38069188344 807 Bob calculates his signature scalar contribution and returns the 808 value to Alice: 810 Bob: 811 S_b = 28944981827334439860137457106479900995796126061421325490732808 812 17601718529025 814 Alice can now calculate her signature scalar contribution and thus 815 the signature scalar S. 817 Alice: 818 S_a = 42757354096062105044904298703340896803929542552166792901005683 819 43184517117786 820 S = 7170233592339654490504175580982079779972566861358811839173849160 821 786235646811 823 Alice checks to see that the signature verifies: 825 S.B = R + kA = 826 X: 40361643976948744971992641065784582623361456745859092512349846 827 75625733276535 828 Y: 41192378513331957483774498173296750751876504986403840969777850 829 360997558579289 831 6.2. Direct Threshold Signature Ed448 833 The signers are Alice and Bob's Threshold Signature Service 'Bob'. 834 Each creates a key pair: 836 ED448Alice's Key (ED448) 837 UDF: ZAAA-ITSI-GXED-44XA-LICE-XSXK-EY 838 Scalar: 63495803583658817688110446314786076976347236361354035 839 5597788771064742993095132758589292255654895141583596922516472 840 738879360490167934280 841 Encoded Private 842 A0 53 4C 93 3C 34 00 76 AE 5D B5 4A C2 71 5F 43 843 E1 D6 63 2C 5C 56 53 C8 98 A0 8F 03 FF F5 22 96 844 91 45 8C 2B CF E3 FD 7E 2A 9E 0B D6 F4 CC 66 61 845 43 62 72 7B 34 B4 79 92 846 X: 24743197509267833262111449556527285120868167712209919570838426 847 3466168536901525943558973091346360088759980994772668117646359 848 614426660579 849 Y: 21342899120576770537664462049685258390853729788303428349051130 850 8752175233505795318243164692156369495328007220135137156078814 851 081547431302 852 Encoded Public 853 0A 3B F3 27 E7 E1 67 63 2C 59 E2 1C D1 84 C7 83 854 E8 1E D1 68 9F 32 A1 16 99 00 5C DA 29 B9 6C 08 855 E4 15 57 7E E5 63 C2 32 08 23 41 68 5F 49 1F FF 856 BC 4D CD 3A 4E A6 85 49 00 857 ED448Bob's Key (ED448) 858 UDF: ZAAA-ITSI-G2ED-44XB-OBXS-XKEY 859 Scalar: 72649803773199751564998543891898904839718409312910780 860 0262041941160989643727331987658132182181970054245587322070535 861 846720571414845714224 862 Encoded Private 863 BC 53 B4 74 3E A7 A7 FA 9F 05 9A BC 8C 22 26 15 864 A1 4E BB 10 0E B5 59 6B DE 9C 1B E9 F2 3C 65 42 865 E7 B4 47 18 60 AC 18 A6 D2 78 B8 BC CE F5 F4 28 866 B2 3A FF 08 61 EF 6B 7C 867 X: 58235851934808640621920816872959059172692411187640950432203039 868 8116748997750134460231406698091317008063030408798536634284207 869 667468558264 870 Y: 34390767697909283892495761259186538632120422458392131201372282 871 6056455656591826216381185634080685718154852726725624178995827 872 091591132128 873 Encoded Public 874 93 63 5A 45 2D 4C 94 32 45 23 CD E2 A8 46 E4 78 875 A0 80 59 DA 36 CB 6B 0C 06 64 6F BE 51 AB C0 BF 876 1E DB A8 3F 2B 3B 80 0F BF 00 E6 78 DD E0 83 E9 877 AC 20 02 55 87 07 39 38 00 879 The composite Signature Key A = A_(a) + A_(b) 880 Aggregate Key = Alice + Bob () 881 UDF: TBS 882 Scalar: 89488306051273634069773238262841883041784075539841550 883 3672228636597106090916876462340541507950185640860121886233669 884 49466515613996100051 885 Encoded Private 886 D3 29 DD AB F6 0D 99 8B 75 65 B8 06 36 C9 3A 2C 887 D4 08 C3 9B 7C F9 77 8C 68 29 0E 3D 5D C7 3E 00 888 92 8B DC AE 26 FB 16 39 CD 25 1B 23 4A 5A 05 61 889 1D 5C C4 70 0A C9 84 1F 890 X: 17985659098670117617173315763082238685735647626871251468000984 891 2080317111091696183607307614171726960576308774975742249260532 892 199160570999 893 Y: 31506323224859159594386181995639405170623657273945727288760063 894 1624406694682617334725040181287905351066763414658543828623841 895 509161975864 896 Encoded Public 897 9B 3E DF 49 55 40 9F 7B EA 0B AA 40 B7 3D 15 82 898 60 9F 7C 40 CF 67 DE 56 56 0D 03 87 63 3B 15 F2 899 45 33 FE 48 BD 2D A0 A2 8B CC 74 DA 94 0F 39 00 900 AC 39 CB 0A 9F A4 EB B0 00 902 To sign the text "This is a test", Alice first generates her value r 903 and multiplies it by the base point to obtain the value R_(a): 905 Alice: 906 r_a = 68686103432614286085087961100697733989779035076023642515818127 907 98858367044290553184740969706908768491109520568381137474912463623 908 0094998 909 R_a = 910 84 D1 68 50 1E BB 9D 40 17 52 C5 D2 96 41 DE FC 911 22 D9 04 02 82 27 1B 32 CD 1D 8C 53 85 AB 40 79 912 F5 00 C2 4C 89 A6 71 0A 39 08 A6 98 4C 2A FE FD 913 B9 F7 66 FC E9 F2 20 B9 80 915 Alice passes her value R_(A) to Bob along with the other parameters 916 required to calculate i. Bob then calculates his value R_(A) and 917 multiplies it by the base point to obtain the value R_(b): 919 Bob: 920 r_b = 76096557183484521564781984661044762292570684233728343619181213 921 42816465520852868086783053490696058232580309131924136177891398775 922 9613091 923 R_b = 924 F3 60 25 C5 13 CE AA A9 B2 7E 9D 05 5B B1 F5 6B 925 4F 5B A5 EC 49 3F 39 A4 B5 C3 3C 7F 80 17 44 5B 926 02 83 FD 12 06 A2 DF E8 C6 46 1D 2A 6C 8E 75 70 927 02 53 71 3F 95 C2 71 A8 00 929 Bob can now calculate the composite value R = R_(a) + R_(b) and thus 930 the value k. 932 R = 933 25 F2 BA FD D1 BB 3F 38 7B 4F 26 63 47 9A 78 81 934 4F CB 1F 82 8D F9 84 D4 34 96 E1 5A 4A 52 46 2C 935 13 EF 67 37 E0 61 13 9F B2 1F 7E C5 B9 56 7F B6 936 CA 88 D7 0B CC BC 96 C5 00 937 k = 1280456290623708148598382410642762981433750669722496871781111755 938 77910741520269875312421999840786826452062625868870120134096187323 939 572465 941 Bob calculates his signature scalar contribution and returns the 942 value to Alice: 944 Bob: 945 S_b = 13468720239873188337021798218509333541110080817756031277945581 946 40664081463680336638329881442786750747115016847691428033880365372 947 48950911 949 Alice can now calculate her signature scalar contribution and thus 950 the signature scalar S. 952 Alice: 953 S_a = 11878333834477344997625309702086496132606331016796170754366862 954 41133668758758146277756495968716749041239572075324760597254347275 955 98536495 956 S = 7176085966960361070914012723395716314875377817369250525275188838 957 46290182823087058924419858586576028721485985925272008086975089878 958 37627 960 Alice checks to see that the signature verifies: 962 S.B = R + kA = 963 X: 16291004486439090147776612791895755846785064919509905636229908 964 328194692798396 965 Y: 46841527536088411435030533441004631079380726947860208328057908 966 29635735834402 968 6.3. Shamir Threshold Signature Ed25519 970 The administrator creates the composite key pair 971 ED25519Aggregate Key (ED25519) 972 UDF: ZAAA-GTSI-GQED-255X-XAGG-REGA-TEXK-EY 973 Scalar: 39348647608109113656999806950437958090469802387424444 974 589375066079861075223816 975 Encoded Private 976 37 39 5E 7A 8B A5 A0 19 46 4B 58 22 EA 24 A5 71 977 45 2C 2A AC 7A 3E FB CA CE 3F D4 12 9A BA EB 70 978 X: 14198837758377867455716504277518729070915183249890461230792115 979 9904969716778427995951234766002164511738587575257530388758374 980 7824906047250057721855068523970 981 Y: 20211025649802071998810413948266748565975140520947927724517956 982 2067625505077751598018629551746824533726709810990193455662385 983 6152736116303441031851305458040 984 Encoded Public 985 6E 13 79 B4 39 DA 97 9C 5A 34 CE 79 CD 1B 50 DF 986 A0 76 AD 49 81 6D 52 59 A4 2C DB CE 44 FF 3E F5 988 Three key shares are required for Alice, Bob and Carol with a 989 threshold of two. The parameters of the Shamir Secret Sharing 990 polynomial are: 992 a0 = 3934864760810911365699980695043795809046980238742444458937506607 993 9861075223816 994 a1 = 4447543804183276703367140352869026105461853047473514285943821414 995 241349264676 997 The key share values for the participants are 999 xa = 1 1000 ya = 3741579482988170765278279250490187507889572786185132393071818643 1001 89698982558 1003 xb = 2 1004 yb = 4821701752482093779894968277918044856250810326092027525251003278 1005 631048247234 1007 xc = 3 1008 yc = 2032239979333108269288922067744076720855547014185634205192873754 1009 586943260921 1011 Alice and Carol are selected to sign the message "This is another 1012 test" 1014 The Lagrange coefficients are: 1016 la = 3618502788666131106986593281521497120428558179689953803000975469 1017 142727125496 1018 lc = 3618502788666131106986593281521497120428558179689953803000975469 1019 142727125494 1021 Alice and Carol select their values ra, rc 1023 ra = 5377248352669516780549162073457874087773506582785629831437934867 1024 461127075879 1025 Ra = 1026 2F 0E 76 87 F3 98 84 41 03 29 5F 5A 84 7D 62 34 1027 A3 9B 64 8C 34 11 99 F1 D5 A9 63 0E 8E 3D 6C C9 1029 rc = 4232465617601402201287633784079511069602658258584839658166776648 1030 89765437047 1031 Rc = 1032 53 7C 5B 73 DE 10 64 82 3C CF CF 19 5F E8 83 24 1033 A0 14 A3 F2 FF 7E 4D 0D 42 42 8E B3 03 66 49 04 1035 The composite value R = R_(a) + R_(c) 1037 R = 1038 5E BA 21 F2 87 4E C8 4E B8 4B E9 5C 1E 3A B2 67 1039 B8 D0 E3 B3 98 C8 DB E0 E6 50 35 8D 47 9B C1 E1 1041 The value k is 1043 k = 31647328596154272207177743411362878636270581278391351236822318404 1044 2871610589 1046 The values R and k (or the document to be signed) and the Lagrange 1047 coefficients are passed to Alice and Carol who use them to calculate 1048 their secret scalar values: 1050 sa = 5612369224482256147917418875735281261834359179277698589607727965 1051 84548473837; 1052 sc = 2602382798999576972342132247649458760000784672597136700404538591 1053 849255495034 1055 The signature contributions can now be calulated: 1057 Sa = 6873614337238287985974631938614575791975512646788133685349814447 1058 956390424246 1059 Sc = 6734965213168676845758127805874268408589146808656626354387236455 1060 007092488600 1062 The dealer calculates the composite value S = S_(a) + S_(b) 1063 S = 6371573973074702617759573181445849959707543096064852433735099964 1064 678028661857 1066 The dealer checks to see that the signature verifies: 1068 S.B = R + kA = 1069 X: 50976148565709102066754003035356376378566475226930883450768310 1070 75625019906058 1071 Y: 74629887867177957343114045996705864971381351024041289421281109 1072 60605559633693 1074 6.4. Shamir Threshold Signature Ed448 1076 The administrator creates the composite key pair 1078 ED448Aggregate Key (ED448) 1079 UDF: ZAAA-ITSI-GQED-44XA-GGRE-GATE-XKEY 1080 Scalar: 50890460656419721531273587958284096015810982760541575 1081 4207268050539683337837216003977228732536078674802149039736292 1082 653681850024283019712 1083 Encoded Private 1084 78 22 7E 3B 89 95 80 5D 04 19 DC 27 F1 7F 9B E4 1085 86 2B 0B DD 55 64 EE 04 19 49 4D DE B9 04 3B 9E 1086 8B 7D DC EC EC 8F DD 1D E7 88 86 FD 11 FD 78 EF 1087 1A 8B 84 8F 77 00 73 65 1088 X: 44109173355278142669484438370724914685176368933547176239809629 1089 7503768465595321590690311221269514682222687386378631457535068 1090 446135118173 1091 Y: 53219402718535721212460981200104434180077825188675868294070079 1092 5084662920552823356888138706016038637934794839496624474125511 1093 419755284720 1094 Encoded Public 1095 43 61 20 A0 B1 DF AA BD 6B 55 00 97 A3 BE CB B8 1096 09 57 20 88 16 69 E4 B9 E1 7E 9C 13 C0 41 5B CB 1097 4D 3E E4 99 2E 2D 48 89 1C C0 FB 26 58 C2 DD 5C 1098 C1 DC 17 82 D7 A0 43 EE 80 1100 Three key shares are required for Alice, Bob and Carol with a 1101 threshold of two. The parameters of the Shamir Secret Sharing 1102 polynomial are: 1104 a0 = 5089046065641972153127358795828409601581098276054157542072680505 1105 39683337837216003977228732536078674802149039736292653681850024283 1106 019712 1107 a1 = 3934291191212650584059669841203896874838912563882890929786754329 1108 01065050103930671683138406271792350963735688973370364434513108789 1109 92904 1111 The key share values for the participants are 1113 xa = 1 1114 ya = 3118475254618553241339722078876528141267932728756118294017944444 1115 35183096299031399695530728818078200859172750635470321098006758306 1116 3279 1118 xb = 2 1119 yb = 4246138716674505908193642049091549688965705836758502759188548773 1120 44583359733833811652691479153600171049652964036917396544313784620 1121 56183 1123 xc = 3 1124 yc = 8180429907887156492253311890295446563804618400641393688975303102 1125 45648409837764483335829885425392522013388653010287760978826893410 1126 49087 1128 Alice and Carol are selected to sign the message "This is another 1129 test" 1131 The Lagrange coefficients are: 1133 la = 9085484053695086131866547598600056679420517008591475753518627489 1134 75730019807697928580978776458461879816551468545458311523868779298 1135 24891 1136 lc = 9085484053695086131866547598600056679420517008591475753518627489 1137 75730019807697928580978776458461879816551468545458311523868779298 1138 24889 1140 Alice and Carol select their values ra, rc 1142 ra = 1610705867304076392921723072340177274788014288395871190735371844 1143 45304821479265411365593663429368194644596000340187951474891649791 1144 38278 1145 Ra = 1146 CF 97 83 F4 16 2D EF A1 85 95 8F 65 68 BC 59 56 1147 94 9F 51 61 A7 F9 95 27 81 E6 83 7F 0A E6 16 C0 1148 50 8D 8A D5 B6 47 3C 64 E0 34 1B AB F3 BF 89 96 1149 41 5D A8 29 06 04 F9 D3 00 1151 rc = 1513721922038322665004883340036457345550315134561588659560214983 1152 90578815745979201541151452164958584639864068264575123975657731927 1153 908051 1154 Rc = 1155 7A 5A E9 4E 9B E9 9E 66 C1 E2 CE 3A B5 CD 73 FA 1156 4C C7 9E E9 C3 59 37 46 11 55 62 6A DC 69 8D 7F 1157 63 20 CF B0 30 6D 77 5E B4 5F 09 B3 8A ED C6 36 1158 64 8F 6B 70 02 DE AB 45 00 1160 The composite value R = R_(a) + R_(c) 1162 R = 1163 D0 51 EC 22 5C 8A 25 9E E7 B6 0B 1E 26 54 0F 51 1164 4C 65 1C B5 24 B1 89 91 FA 63 32 39 89 89 24 9B 1165 03 3E E6 83 1A 74 FA 79 0D E5 90 D7 C2 7C 3B FF 1166 22 D5 B2 7F B7 14 C8 F0 80 1168 The value k is 1170 k = 11205778835971090763459400118127617086725238194171737531994098751 1171 92020469089993225609677938158558606382862723600565685005808743888 1172 1311 1174 The values R and k (or the document to be signed) and the Lagrange 1175 coefficients are passed to Alice and Carol who use them to calculate 1176 their secret scalar values: 1178 sa = 9553255341887869118067505910431535900610706917904893497621319156 1179 41007484252552638535308385781173609945427381140778859688569793044 1180 19808; 1181 sc = 4995269099751507885739891653452333397518207808270778909030975938 1182 52905814888815686913063833745765618809857142040314431034455332593 1183 00346 1185 The signature contributions can now be calulated: 1187 Sa = 1288724802012784524546710951030879127642885816514372129177355341 1188 52388852607084448690299630591486640562077067211721300969711457389 1189 734384 1190 Sc = 9245427182572705582371845728508254342708120847149751739704864321 1191 05098990035212645834079206651328626851538428963929848345208375317 1192 71245 1194 The dealer calculates the composite value S = S_(a) + S_(b) 1196 S = 3961707095310378564105860041616932260295944995110521524441162756 1197 77527476490661275575117959649271272839206163990226234994585390618 1198 55850 1200 The dealer checks to see that the signature verifies: 1202 S.B = R + kA = 1203 X: 89820587157297640914878146420868301420919058721019003413415111 1204 40349053172466 1205 Y: 29679650828270530327946891692133348611591938177520550739646498 1206 568569373309365 1208 7. Security Considerations 1210 All the security considerations of [RFC7748], [RFC8032] and 1211 [draft-hallambaker-threshold] apply and are hereby incorporated by 1212 reference. 1214 7.1. Rogue Key attack 1216 The rogue key attack described in [draft-hallambaker-threshold] is of 1217 particular concern to generation of threshold signatures. 1219 If _A_ and _B_ are public keys, the intrinsic degree of trust in the 1220 composite keypair _A_ + _B_ is that of the lesser of _A_ and _B_. 1222 7.2. Disclosure or reuse of the value r 1224 As in any Schnorr signature scheme, compromise of the value _r_ 1225 results in compromise of the private key. The base signature 1226 specification [RFC8032] describes a deterministic construction of _r_ 1227 that ensures confidentiality and uniqueness for a given value of _k_. 1229 As described above, this approach is not applicable to the generation 1230 of values of _r_(i)_ to compute threshold signature contributions. 1231 Accordingly the requirements of [RFC4086] regarding requirements for 1232 randomness MUST be observed. 1234 Implementations MUST NOT use a deterministic generation of the value 1235 _r_(i)_ for any threshold contribution except for calculating the 1236 final contribution when all the other parameters required to 1237 calculate _k_ are known. 1239 7.3. Resource exhaustion attack 1241 Implementation of the general two stage signing algorithm requires 1242 that signers track generation and use of the values _r_(i)_ to avoid 1243 reuse for different values of _R_(i)_. Implementations MUST ensure 1244 that exhaustion of this resource by one party does not cause other 1245 parties to be denied service. 1247 7.4. Signature Uniqueness 1249 Signatures generated in strict conformance with [RFC8032] are 1250 guaranteed to be unique such that signing the same document with the 1251 same key will always result in the same signature value. 1253 The signature modes described in this document are computationally 1254 indistinguishable from those created in accordance with [RFC8032] but 1255 are not unique. 1257 Implementations MUST not use threshold signatures in applications 1258 where signature values are used in place of cryptographic digests as 1259 unique content identifiers. 1261 8. IANA Considerations 1263 This document requires no IANA actions. 1265 9. Acknowledgements 1267 [TBS] 1269 10. Normative References 1271 [draft-hallambaker-mesh-udf] 1272 Hallam-Baker, P., "Mathematical Mesh 3.0 Part II: Uniform 1273 Data Fingerprint.", Work in Progress, Internet-Draft, 1274 draft-hallambaker-mesh-udf-08, 6 January 2020, 1275 . 1278 [draft-hallambaker-threshold] 1279 Hallam-Baker, P., "Threshold Key Generation and Decryption 1280 in Ed25519 and Ed448", Work in Progress, Internet-Draft, 1281 draft-hallambaker-threshold-00, 5 January 2020, 1282 . 1285 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1286 Requirement Levels", BCP 14, RFC 2119, 1287 DOI 10.17487/RFC2119, March 1997, 1288 . 1290 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 1291 "Randomness Requirements for Security", BCP 106, RFC 4086, 1292 DOI 10.17487/RFC4086, June 2005, 1293 . 1295 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1296 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1297 2016, . 1299 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1300 Signature Algorithm (EdDSA)", RFC 8032, 1301 DOI 10.17487/RFC8032, January 2017, 1302 . 1304 11. Informative References 1306 [draft-hallambaker-mesh-developer] 1307 Hallam-Baker, P., "Mathematical Mesh: Reference 1308 Implementation", Work in Progress, Internet-Draft, draft- 1309 hallambaker-mesh-developer-09, 23 October 2019, 1310 . 1313 [Komlo] Komlo, C. and I. Goldberg, "FROST: Flexible Round- 1314 Optimized Schnorr Threshold Signatures", 2020. 1316 [RFC5860] Vigoureux, M., Ward, D., and M. Betts, "Requirements for 1317 Operations, Administration, and Maintenance (OAM) in MPLS 1318 Transport Networks", RFC 5860, DOI 10.17487/RFC5860, May 1319 2010, . 1321 [Shamir79] Shamir, A., "How to share a secret.", 1979.