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