idnits 2.17.1 draft-atkins-suit-cose-walnutdsa-06.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 17, 2020) is 1249 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 8152 (Obsoleted by RFC 9052, RFC 9053) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force D. Atkins 3 Internet-Draft Veridify Security 4 Intended status: Informational November 17, 2020 5 Expires: May 21, 2021 7 Use of the Walnut Digital Signature Algorithm with CBOR Object Signing 8 and Encryption (COSE) 9 draft-atkins-suit-cose-walnutdsa-06 11 Abstract 13 This document specifies the conventions for using the Walnut Digital 14 Signature Algorithm (WalnutDSA) for digital signatures with the CBOR 15 Object Signing and Encryption (COSE) syntax. WalnutDSA is a 16 lightweight, quantum-resistant signature scheme based on Group 17 Theoretic Cryptography with implementation and computational 18 efficiency of signature verification in constrained environments, 19 even on 8- and 16-bit platforms. 21 The goal of this publication is to document a way to use the 22 lightweight, quantum-resistant WalnutDSA signature algorithm in COSE 23 in a way that would allow multiple developers to build compatible 24 implementations. As of this publication, WalnutDSA has not been 25 endorsed by the IETF. 27 WalnutDSA(TM) and Walnut Digital Signature Algorithm(TM) are 28 trademarks of Veridify Security Inc.. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on May 21, 2021. 47 Copyright Notice 49 Copyright (c) 2020 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 65 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.2. Trademark Notice . . . . . . . . . . . . . . . . . . . . 4 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 68 3. WalnutDSA Algorithm Overview . . . . . . . . . . . . . . . . 4 69 4. WalnutDSA Algorithm Identifiers . . . . . . . . . . . . . . . 5 70 5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 71 5.1. Implementation Security Considerations . . . . . . . . . 5 72 5.2. Method Security Considerations . . . . . . . . . . . . . 6 73 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 74 6.1. COSE Algorithms Registry Entry . . . . . . . . . . . . . 7 75 6.2. COSE Key Types Registry Entry . . . . . . . . . . . . . . 8 76 6.3. COSE Key Type Parameter Registry Entries . . . . . . . . 8 77 6.3.1. WalnutDSA Parameter: N . . . . . . . . . . . . . . . 8 78 6.3.2. WalnutDSA Parameter: q . . . . . . . . . . . . . . . 9 79 6.3.3. WalnutDSA Parameter: t-values . . . . . . . . . . . . 9 80 6.3.4. WalnutDSA Parameter: matrix 1 . . . . . . . . . . . . 9 81 6.3.5. WalnutDSA Parameter: permutation 1 . . . . . . . . . 10 82 6.3.6. WalnutDSA Parameter: matrix 2 . . . . . . . . . . . . 10 83 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 84 7.1. Normative References . . . . . . . . . . . . . . . . . . 10 85 7.2. Informative References . . . . . . . . . . . . . . . . . 11 86 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 12 87 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 12 89 1. Introduction 91 This document specifies the conventions for using the Walnut Digital 92 Signature Algorithm (WalnutDSA) [WALNUTDSA] for digital signatures 93 with the CBOR Object Signing and Encryption (COSE) [RFC8152] syntax. 94 WalnutDSA is a Group-Theoretic [GTC] signature scheme where signature 95 validation is both computationally- and space-efficient, even on very 96 small processors. Unlike many hash-based signatures, there is no 97 state required and no limit on the number of signatures that can be 98 made. WalnutDSA private and public keys are relatively small; 99 however, the signatures are larger than RSA and ECC, but still 100 smaller than most all other quantum-resistant schemes (including all 101 hash-based schemes). 103 COSE provides a lightweight method to encode structured data. 104 WalnutDSA is a lightweight, quantum-resistant WalnutDSA signature 105 algorithm. The goal of this specification is to document a method to 106 leverage WalnutDSA in COSE in a way that would allow multiple 107 developers to build compatible implementations. 109 As with all cryptosystems, the initial versions of WalnutDSA 110 underwent significant cryptanalysis, and in some cases, identified 111 potential issues. For more discussion on this topic, a summary of 112 all published cryptanalysis can be found in Section 5.2. Validated 113 issues were addressed by reparameterization in updated versions of 114 WalnutDSA. Although the IETF has not endorsed WalnutDSA as of this 115 publication, this document provides a method to use WalnutDSA in 116 conjunction with IETF protocols. As always, users of any security 117 algorithm are advised to research the security properties of the 118 algorithm and make their own judgment about the risks involved. 120 1.1. Motivation 122 Recent advances in cryptanalysis [BH2013] and progress in the 123 development of quantum computers [NAS2019] pose a threat to widely 124 deployed digital signature algorithms. As a result, there is a need 125 to prepare for a day that cryptosystems such as RSA and DSA that 126 depend on discrete logarithm and factoring cannot be depended upon. 128 If large-scale quantum computers are ever built, these computers will 129 be able to break many of the public-key cryptosystems currently in 130 use. A post-quantum cryptosystem [PQC] is a system that is secure 131 against quantum computers that have more than a trivial number of 132 quantum bits (qubits). It is open to conjecture when it will be 133 feasible to build such computers; however, RSA, DSA, ECDSA, and EdDSA 134 are all vulnerable if large-scale quantum computers come to pass. 136 WalnutDSA does not depend on the difficulty of discrete logarithm or 137 factoring. As a result this algorithm is considered to be resistant 138 to post-quantum attacks. 140 Today, RSA and ECDSA are often used to digitally sign software 141 updates. Unfortunately, implementations of RSA and ECDSA can be 142 relatively large, and verification can take a significant amount of 143 time on some very small processors. Therefore, we desire a digital 144 signature scheme that verifies faster with less code. Moreover, in 145 preparation for a day when RSA, DSA, and ECDSA cannot be depended 146 upon, a digital signature algorithm is needed that will remain secure 147 even if there are significant cryptoanalytic advances or a large- 148 scale quantum computer is invented. WalnutDSA, specified in 149 [WALNUTSPEC], is one such algorithm. 151 1.2. Trademark Notice 153 WalnutDSA(TM) and Walnut Digital Signature Algorithm(TM) are 154 trademarks of Veridify Security Inc.. 156 2. Terminology 158 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 159 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 160 "OPTIONAL" in this document are to be interpreted as described in BCP 161 14 [RFC2119] [RFC8174] when, and only when, they appear in all 162 capitals, as shown here. 164 3. WalnutDSA Algorithm Overview 166 This specification makes use of WalnutDSA signatures as described in 167 [WALNUTDSA] and more concretely specified in [WALNUTSPEC]. WalnutDSA 168 is a Group-Theoretic cryptographic signature scheme that leverages 169 infinite group theory as the basis of its security and maps that to a 170 one-way evaluation of a series of matrices over small finite fields 171 with permuted multiplicants based on the group input. WalnutDSA 172 leverages the SHA2-256 and SHA2-512 one-way hash algorithms [SHA2] in 173 a hash-then-sign process. 175 WalnutDSA is based on a one-way function, E-Multiplication, which is 176 an action on the infinite group. A single E-Multiplication step 177 takes as input a matrix and permutation, a generator in the group, 178 and a set of T-values (entries in the finite field) and outputs a new 179 matrix and permutation. To process a long string of generators (like 180 a WalnutDSA signature), E-Multiplication is iterated over each 181 generator. Due to its structure, E-Multiplication is extremely easy 182 to implement. 184 In addition to being quantum-resistant, the two main benefits of 185 using WalnutDSA are that the verification implementation is very 186 small and WalnutDSA signature verification is extremely fast, even on 187 very small processors (including 16- and even 8-bit MCUs). This 188 lends it well to use in constrained and/or time-sensitive 189 environments. 191 WalnutDSA has several parameters required to process a signature. 192 The main parameters are N and q. The parameter N defines the size of 193 the group by defining the number of strands in use, and implies 194 working in an NxN matrix. The parameter q defines the number of 195 elements in the finite field. Signature verification also requires a 196 set of T-values, which is an ordered list of N entries in the finite 197 field F_q. 199 A WalnutDSA signature is just a string of generators in the infinite 200 group, packed into a byte string. 202 4. WalnutDSA Algorithm Identifiers 204 The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two 205 signature algorithm schemes. This specification makes use of the 206 signature with appendix scheme for WalnutDSA signatures. 208 The signature value is a large byte string. The byte string is 209 designed for easy parsing, and it includes a length (number of 210 generators) and type codes that indirectly provide all of the 211 information that is needed to parse the byte string during signature 212 validation. 214 When using a COSE key for this algorithm, the following checks are 215 made: 217 o The 'kty' field MUST be present, and it MUST be 'WalnutDSA'. 219 o If the 'alg' field is present, and it MUST be 'WalnutDSA'. 221 o If the 'key_ops' field is present, it MUST include 'sign' when 222 creating a WalnutDSA signature. 224 o If the 'key_ops' field is present, it MUST include 'verify' when 225 verifying a WalnutDSA signature. 227 o If the 'kid' field is present, it MAY be used to identify the 228 WalnutDSA Key. 230 5. Security Considerations 232 5.1. Implementation Security Considerations 234 Implementations MUST protect the private keys. Use of a hardware 235 security module (HSM) is one way to protect the private keys. 236 Compromise of the private keys may result in the ability to forge 237 signatures. As a result, when a private key is stored on non- 238 volatile media or stored in a virtual machine environment, care must 239 be taken to preserve confidentiality and integrity. 241 The generation of private keys relies on random numbers. The use of 242 inadequate pseudo-random number generators (PRNGs) to generate these 243 values can result in little or no security. An attacker may find it 244 much easier to reproduce the PRNG environment that produced the keys, 245 searching the resulting small set of possibilities, rather than brute 246 force searching the whole key space. The generation of quality 247 random numbers is difficult, and [RFC4086] offers important guidance 248 in this area. 250 The generation of WalnutDSA signatures also depends on random 251 numbers. While the consequences of an inadequate pseudo-random 252 number generator (PRNG) to generate these values is much less severe 253 than the generation of private keys, the guidance in [RFC4086] 254 remains important. 256 5.2. Method Security Considerations 258 The Walnut Digital Signature Algorithm has undergone significant 259 cryptanalysis since it was first introduced, and several weaknesses 260 were found in early versions of the method, resulting in the 261 description of several attacks with exponential computational 262 complexity. A full writeup of all the analysis can be found in 263 [WalnutDSAAnalysis]. In summary, the original suggested parameters 264 (N=8, q=32) were too small, leading to many of these exponential- 265 growth attacks being practical. However, current parameters render 266 these attacks impractical. The following paragraphs summarize the 267 analysis and how the current parameters defeat all the previous 268 attacks. 270 First, the team of Hart et al found a universal forgery attack based 271 on a group factoring problem that runs in O(q^((N-1)/2)) with a 272 memory complexity of log_2(q) N^2 q^((N-1)/2). With parameters N=10 273 and q=M31 (the Mersenne prime 2^31 - 1), the runtime is 2^139 and 274 memory complexity is 2^151. W. Beullens found a modification of 275 this attack but its runtime is even longer. 277 Next, Beullens and Blackburn found several issues with the original 278 method and parameters. First they used a Pollard-Rho attack and 279 discovered the original public key space was too small. Specifically 280 they require that q^(N(N-1)-1) > 2^(2*Security Level). One can 281 clearly see that N=10, q=M31 provides 128-bit security and N=10, 282 q=M61 provides 256-bit security. 284 Beullens and Blackburn also found two issues with the original 285 message encoder of WalnutDSA. First, the original encoder was non- 286 injective, which reduced the available signature space. This was 287 repaired in an update. Second, they pointed out that the dimension 288 of the vector space generated by the encoder was too small. 289 Specifically, they require that q^dimension > 2^(2*Security Level). 290 With N=10, the current encoder produces a dimension of 66 which 291 clearly provides sufficient security with q=M31 or q=M61. 293 The final issue discovered by Beullens and Blackburn was a process to 294 theoretically "reverse" E-Multiplication. First, their process 295 requires knowing the initial matrix and permutation (which is known 296 for WalnutDSA). But more importantly, their process runs at 297 O(q^((N-1)/2)) which, for N=10, q=M31 is greater than 2^128. 299 A team at Steven's Institute leveraged a length-shortening attack 300 that enabled them to remove the cloaking elements and then solve a 301 conjugacy search problem to derive the private keys. Their attack 302 requires both knowledge of the permutation being cloaked and also 303 that the cloaking elements themselves are conjugates. By adding 304 additional concealed cloaking elements the attack requires an N! 305 search for each cloaking element. By inserting k concealed cloaking 306 elements, this requires the attacker to perform (N!)^k work. This 307 allows k to be set to meet the desired security level. 309 Finally, Merz and Petit discovered that using a Garside Normal Form 310 of a WalnutDSA signature enabled them to find commonalities with the 311 Garside Normal Form of the encoded message. Using those 312 commonalities they were able to splice into a signature and create 313 forgeries. Increasing the number of cloaking elements, specifically 314 within the encoded message, sufficiently obscures the commonalities 315 and blocks this attack. 317 In summary, most of these attacks are exponential in run time and can 318 be shown that current parameters put the runtime beyond the desired 319 security level. The final two attacks are also sufficiently blocked 320 to the desired security level. 322 6. IANA Considerations 324 IANA is requested to add entries for WalnutDSA signatures in the 325 "COSE Algorithms" registry and WalnutDSA public keys in the "COSE Key 326 Types" and "COSE Key Type Parameters" registries. 328 6.1. COSE Algorithms Registry Entry 330 The new entry in the "COSE Algorithms" registry has the following 331 columns: 333 Name: WalnutDSA 334 Value: TBD1 (Value between -65536 to -257 or 256-65535 to be 335 assigned by IANA) 337 Description: WalnutDSA signature 339 Reference: This document (Number to be assigned by RFC Editor) 341 Recommended: No 343 6.2. COSE Key Types Registry Entry 345 The new entry in the "COSE Key Types" registry has the following 346 columns: 348 Name: WalnutDSA 350 Value: TBD2 (Value to be assigned by IANA) 352 Description: WalnutDSA public key 354 Reference: This document (Number to be assigned by RFC Editor) 356 6.3. COSE Key Type Parameter Registry Entries 358 The following sections detail the additions to the "COSE Key Type 359 Parameters" registry. 361 6.3.1. WalnutDSA Parameter: N 363 The new entry N in the "COSE Key Type Parameters" registry has the 364 following columns: 366 Key Type: TBD2 (Value assigned by IANA above) 368 Name: N 370 Label: TBD (Value to be assigned by IANA) 372 CBOR Type: uint 374 Description: Group and Matrix (NxN) size 376 Reference: This document (Number to be assigned by RFC Editor) 378 6.3.2. WalnutDSA Parameter: q 380 The new entry q in the "COSE Key Type Parameters" registry has the 381 following columns: 383 Key Type: TBD2 (Value assigned by IANA above) 385 Name: q 387 Label: TBD (Value to be assigned by IANA) 389 CBOR Type: uint 391 Description: Finite field F_q 393 Reference: This document (Number to be assigned by RFC Editor) 395 6.3.3. WalnutDSA Parameter: t-values 397 The new entry t-values in the "COSE Key Type Parameters" registry has 398 the following columns: 400 Key Type: TBD2 (Value assigned by IANA above) 402 Name: t-values 404 Label: TBD (Value to be assigned by IANA) 406 CBOR Type: array (of uint) 408 Description: List of T-values, enties in F_q 410 Reference: This document (Number to be assigned by RFC Editor) 412 6.3.4. WalnutDSA Parameter: matrix 1 414 The new entry matrix 1 in the "COSE Key Type Parameters" registry has 415 the following columns: 417 Key Type: TBD2 (Value assigned by IANA above) 419 Name: matrix 1 421 Label: TBD (Value to be assigned by IANA) 423 CBOR Type: array (of array of uint) 425 Description: NxN Matrix of enties in F_q in column-major form 426 Reference: This document (Number to be assigned by RFC Editor) 428 6.3.5. WalnutDSA Parameter: permutation 1 430 The new entry permutation 1 in the "COSE Key Type Parameters" 431 registry has the following columns: 433 Key Type: TBD2 (Value assigned by IANA above) 435 Name: permutation 1 437 Label: TBD (Value to be assigned by IANA) 439 CBOR Type: array (of uint) 441 Description: Permutation associated with matrix 1 443 Reference: This document (Number to be assigned by RFC Editor) 445 6.3.6. WalnutDSA Parameter: matrix 2 447 The new entry matrix 2 in the "COSE Key Type Parameters" registry has 448 the following columns: 450 Key Type: TBD2 (Value assigned by IANA above) 452 Name: matrix 2 454 Label: TBD (Value to be assigned by IANA) 456 CBOR Type: array (of array of uint) 458 Description: NxN Matrix of enties in F_q in column-major form 460 Reference: This document (Number to be assigned by RFC Editor) 462 7. References 464 7.1. Normative References 466 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 467 Requirement Levels", BCP 14, RFC 2119, 468 DOI 10.17487/RFC2119, March 1997, . 471 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 472 RFC 8152, DOI 10.17487/RFC8152, July 2017, 473 . 475 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 476 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 477 May 2017, . 479 [SHA2] National Institute of Standards and Technology (NIST), 480 "FIPS Publication 180-3: Secure Hash Standard", October 481 2008. 483 [WALNUTDSA] 484 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 485 "WalnutDSA(TM): A group-theoretic digital signature 486 algorithm", November 2020, 487 . 489 7.2. Informative References 491 [BH2013] Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The 492 Factoring Dead: Preparing for the Cryptopocalypse", August 493 2013, . 496 [GTC] Vasco, M. and R. Steinwandt, "Group Theoretic 497 Cryptography", April 2015, . 501 [NAS2019] National Academies of Sciences, Engineering, and Medicine, 502 "Quantum Computing: Progress and Prospects", 2019, 503 . 505 [PQC] Bernstein, D., "Introduction to post-quantum 506 cryptography", 2009, 507 . 510 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 511 "Randomness Requirements for Security", BCP 106, RFC 4086, 512 DOI 10.17487/RFC4086, June 2005, . 515 [WalnutDSAAnalysis] 516 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 517 "Defeating the Hart et al, Beullens-Blackburn, Kotov- 518 Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)", 519 May 2019, . 521 [WALNUTSPEC] 522 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 523 "The Walnut Digital Signature Algorithm Specification", 524 November 2018, . 527 Appendix A. Acknowledgments 529 A big thank you to Russ Housley for his input on the concepts and 530 text of this document. 532 Author's Address 534 Derek Atkins 535 Veridify Security 536 100 Beard Sawmill Rd, Suite 350 537 Shelton, CT 06484 538 US 540 Phone: +1 617 623 3745 541 Email: datkins@veridify.com