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