idnits 2.17.1 draft-atkins-suit-cose-walnutdsa-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- 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 (July 24, 2020) is 1372 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 July 24, 2020 5 Expires: January 25, 2021 7 Use of the Walnut Digital Signature Algorithm with CBOR Object Signing 8 and Encryption (COSE) 9 draft-atkins-suit-cose-walnutdsa-05 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 constrained16807 19 environments, 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 January 25, 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 . . . . . . . . . . . . . . . 8 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 . . . . . . . . . 9 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 thie 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 post- 138 quantum secure. 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 and implies working in an NxN matrix. The parameter q 194 defines the size of the finite field (in q elements). Signature 195 verification also requires a set of T-values, which is an ordered 196 list of N entries in the finite field F_q. 198 A WalnutDSA signature is just a string of generators in the infinite 199 group, packed into a byte string. 201 4. WalnutDSA Algorithm Identifiers 203 The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two 204 signature algorithm schemes. This specification makes use of the 205 signature with appendix scheme for WalnutDSA signatures. 207 The signature value is a large byte string. The byte string is 208 designed for easy parsing, and it includes a length (number of 209 generators) and type codes that indirectly provide all of the 210 information that is needed to parse the byte string during signature 211 validation. 213 When using a COSE key for this algorithm, the following checks are 214 made: 216 o The 'kty' field MUST be present, and it MUST be 'WalnutDSA'. 218 o If the 'alg' field is present, and it MUST be 'WalnutDSA'. 220 o If the 'key_ops' field is present, it MUST include 'sign' when 221 creating a WalnutDSA signature. 223 o If the 'key_ops' field is present, it MUST include 'verify' when 224 verifying a WalnutDSA signature. 226 o If the 'kid' field is present, it MAY be used to identify the 227 WalnutDSA Key. 229 5. Security Considerations 231 5.1. Implementation Security Considerations 233 Implementations MUST protect the private keys. Use of a hardware 234 security module (HSM) is one way to protect the private keys. 235 Compromise of the private keys may result in the ability to forge 236 signatures. As a result, when a private key is stored on non- 237 volatile media or stored in a virtual machine environment, care must 238 be taken to preserve confidentiality and integrity. 240 The generation of private keys relies on random numbers. The use of 241 inadequate pseudo-random number generators (PRNGs) to generate these 242 values can result in little or no security. An attacker may find it 243 much easier to reproduce the PRNG environment that produced the keys, 244 searching the resulting small set of possibilities, rather than brute 245 force searching the whole key space. The generation of quality 246 random numbers is difficult, and [RFC4086] offers important guidance 247 in this area. 249 The generation of WalnutDSA signatures also depends on random 250 numbers. While the consequences of an inadequate pseudo-random 251 number generator (PRNG) to generate these values is much less severe 252 than the generation of private keys, the guidance in [RFC4086] 253 remains important. 255 5.2. Method Security Considerations 257 The Walnut Digital Signature Algorithm has undergone significant 258 cryptanalysis since it was first introduced, and several weaknesses 259 were found in early versions of the method, resulting in the 260 description of several exponential attacks. A full writeup of all 261 the analysis can be found in [WalnutDSAAnalysis]. In summary, the 262 original suggested parameters were too small, leading to many of 263 these exponential attacks being practical. However, current 264 parameters render these attacks impractical. The following 265 paragraphs summarize the analysis and how the current parameters 266 defeat all the previous attacks. 268 First, the team of Hart et al found a universal forgery attack based 269 on a group factoring problem that runs in O(q^((N-1)/2)) with a 270 memory complexity of log_2(q) N^2 q^((N-1)/2). With parameters N=10 271 and q=M31 (2^31 - 1), the runtime is 2^139 and memory complexity is 272 2^151. W. Beullens found a modification of this attack but its 273 runtime is even longer. 275 Next, Beullens and Blackburn found several issues with the original 276 method and parameters. First they used a Pollard-Rho attack and 277 discovered the original public key space was too small. Specifically 278 they require that q^(N(N-1)-1) > 2^(2*Security Level). One can 279 clearly see that N=10, q=M31 provides 128-bit security and N=10, 280 q=M61 provides 256-bit security. 282 Beullens and Blackburn also found two issues with the original 283 message encoder of WalnutDSA. First, the original encoder was non- 284 injective, which reduced the available signature space. This was 285 repaired in an update. Second, they pointed out that the dimension 286 of the vector space generated by the encoder was too small. 287 Specifically, they require that q^dimension > 2^(2*Security Level). 289 With N=10, the current encoder produces a dimension of 66 which 290 clearly provides sufficient security. 292 The final issue discovered by Beullens and Blackburn was a process to 293 theoretically "reverse" E-Multiplication. First, their process 294 requires knowing the initial matrix and permutation (which is known 295 for WalnutDSA). But more importantly, their process runs at 296 O(q^((N-1)/2)) which, for N=10, q=M31 is greater than 2^128. 298 A team at Steven's Institute leveraged a length-shortening attack 299 that enabled them to remove the cloaking elements and then solve a 300 conjugacy search problem to derive the private keys. Their attack 301 requires both knowledge of the permutation being cloaked and also 302 that the cloaking elements themselves are conjugates. By adding 303 additional concealed cloaking elements the attack requires an N! 304 search for each cloaking element. By inserting k concealed cloaking 305 elements, this requires the attacker to perform (N!)^k work. This 306 allows k to be set to meet the desired security level. 308 Finally, Merz and Petit discovered that using a Garside Normal Form 309 of a WalnutDSA signature enabled them to find commonalities with the 310 Garside Normal Form of the encoded message. Using those 311 commonalities they were able to splice into a signature and create 312 forgeries. Increasing the number of cloaking elements, specifically 313 within the encoded message, sufficiently obscures the commonalities 314 and blocks this attack. 316 In summary, most of these attacks are exponential in run time and can 317 be shown that current parameters put the runtime beyond the desired 318 security level. The final two attacks are also sufficiently blocked 319 to the desired security level. 321 6. IANA Considerations 323 IANA is requested to add entries for WalnutDSA signatures in the 324 "COSE Algorithms" registry and WalnutDSA public keys in the "COSE Key 325 Types" and "COSE Key Type Parameters" registries. 327 6.1. COSE Algorithms Registry Entry 329 The new entry in the "COSE Algorithms" registry has the following 330 columns: 332 Name: WalnutDSA 334 Value: TBD1 (Value between -256 to 255 to be assigned by IANA) 336 Description: WalnutDSA signature 337 Reference: This document (Number to be assigned by RFC Editor) 339 Recommended: No 341 6.2. COSE Key Types Registry Entry 343 The new entry in the "COSE Key Types" registry has the following 344 columns: 346 Name: WalnutDSA 348 Value: TBD2 (Value to be assigned by IANA) 350 Description: WalnutDSA public key 352 Reference: This document (Number to be assigned by RFC Editor) 354 6.3. COSE Key Type Parameter Registry Entries 356 The following sections detail the additions to the "COSE Key Type 357 Parameters" registry. 359 6.3.1. WalnutDSA Parameter: N 361 The new entry N in the "COSE Key Type Parameters" registry has the 362 following columns: 364 Key Type: TBD2 (Value assigned by IANA above) 366 Name: N 368 Label: TBD (Value to be assigned by IANA) 370 CBOR Type: uint 372 Description: Group and Matrix (NxN) size 374 Reference: This document (Number to be assigned by RFC Editor) 376 6.3.2. WalnutDSA Parameter: q 378 The new entry q in the "COSE Key Type Parameters" registry has the 379 following columns: 381 Key Type: TBD2 (Value assigned by IANA above) 383 Name: q 384 Label: TBD (Value to be assigned by IANA) 386 CBOR Type: uint 388 Description: Finite field F_q 390 Reference: This document (Number to be assigned by RFC Editor) 392 6.3.3. WalnutDSA Parameter: t-values 394 The new entry t-values in the "COSE Key Type Parameters" registry has 395 the following columns: 397 Key Type: TBD2 (Value assigned by IANA above) 399 Name: t-values 401 Label: TBD (Value to be assigned by IANA) 403 CBOR Type: array (of uint) 405 Description: List of T-values, enties in F_q 407 Reference: This document (Number to be assigned by RFC Editor) 409 6.3.4. WalnutDSA Parameter: matrix 1 411 The new entry matrix 1 in the "COSE Key Type Parameters" registry has 412 the following columns: 414 Key Type: TBD2 (Value assigned by IANA above) 416 Name: matrix 1 418 Label: TBD (Value to be assigned by IANA) 420 CBOR Type: array (of array of uint) 422 Description: NxN Matrix of enties in F_q 424 Reference: This document (Number to be assigned by RFC Editor) 426 6.3.5. WalnutDSA Parameter: permutation 1 428 The new entry permutation 1 in the "COSE Key Type Parameters" 429 registry has the following columns: 431 Key Type: TBD2 (Value assigned by IANA above) 432 Name: permutation 1 434 Label: TBD (Value to be assigned by IANA) 436 CBOR Type: array (of uint) 438 Description: Permutation associated with matrix 1 440 Reference: This document (Number to be assigned by RFC Editor) 442 6.3.6. WalnutDSA Parameter: matrix 2 444 The new entry matrix 2 in the "COSE Key Type Parameters" registry has 445 the following columns: 447 Key Type: TBD2 (Value assigned by IANA above) 449 Name: matrix 2 451 Label: TBD (Value to be assigned by IANA) 453 CBOR Type: array (of array of uint) 455 Description: NxN Matrix of enties in F_q 457 Reference: This document (Number to be assigned by RFC Editor) 459 7. References 461 7.1. Normative References 463 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 464 Requirement Levels", BCP 14, RFC 2119, 465 DOI 10.17487/RFC2119, March 1997, . 468 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 469 RFC 8152, DOI 10.17487/RFC8152, July 2017, 470 . 472 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 473 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 474 May 2017, . 476 [SHA2] National Institute of Standards and Technology (NIST), 477 "FIPS Publication 180-3: Secure Hash Standard", October 478 2008. 480 7.2. Informative References 482 [BH2013] Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The 483 Factoring Dead: Preparing for the Cryptopocalypse", August 484 2013, . 487 [GTC] Vasco, M. and R. Steinwandt, "Group Theoretic 488 Cryptography", April 2015, . 492 [NAS2019] National Academies of Sciences, Engineering, and Medicine, 493 "Quantum Computing: Progress and Prospects", 2019, 494 . 496 [PQC] Bernstein, D., "Introduction to post-quantum 497 cryptography", 2009, 498 . 501 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 502 "Randomness Requirements for Security", BCP 106, RFC 4086, 503 DOI 10.17487/RFC4086, June 2005, . 506 [WALNUTDSA] 507 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 508 "WalnutDSA(TM): A Quantum-Resistant Digital Signature 509 Algorithm", January 2017, 510 . 512 [WalnutDSAAnalysis] 513 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 514 "Defeating the Hart et al, Beullens-Blackburn, Kotov- 515 Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)", 516 May 2019, . 518 [WALNUTSPEC] 519 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 520 "The Walnut Digital Signature Algorithm Specification", 521 November 2018, . 524 Appendix A. Acknowledgments 526 A big thank you to Russ Housley for his input on the concepts and 527 text of this document. 529 Author's Address 531 Derek Atkins 532 Veridify Security 533 100 Beard Sawmill Rd, Suite 350 534 Shelton, CT 06484 535 US 537 Phone: +1 617 623 3745 538 Email: datkins@veridify.com