idnits 2.17.1 draft-atkins-suit-cose-walnutdsa-01.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 abstract seems to contain references ([WALNUTDSA], [WALNUTSPEC]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (November 20, 2019) is 1616 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: 2 errors (**), 0 flaws (~~), 2 warnings (==), 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 SecureRF Corporation 4 Intended status: Informational November 20, 2019 5 Expires: May 23, 2020 7 Use of the Walnut Digital Signature Algorithm with CBOR Object Signing 8 and Encryption (COSE) 9 draft-atkins-suit-cose-walnutdsa-01 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 (see [WALNUTDSA] and [WALNUTSPEC]) with 18 implementation and computational efficiency of signature verification 19 in constrained environments, even on 8- and 16-bit platforms. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on May 23, 2020. 38 Copyright Notice 40 Copyright (c) 2019 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 57 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 3. WalnutDSA Algorithm Overview . . . . . . . . . . . . . . . . 4 59 4. WalnutDSA Algorithm Identifiers . . . . . . . . . . . . . . . 4 60 5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 61 5.1. Implementation Security Considerations . . . . . . . . . 5 62 5.2. Method Security Considerations . . . . . . . . . . . . . 5 63 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 64 6.1. COSE Algorithms Registry Entry . . . . . . . . . . . . . 7 65 6.2. COSE Key Types Registry Entry . . . . . . . . . . . . . . 7 66 6.3. COSE Key Type Parameter Registry Entries . . . . . . . . 8 67 6.3.1. WalnutDSA Parameter: N . . . . . . . . . . . . . . . 8 68 6.3.2. WalnutDSA Parameter: q . . . . . . . . . . . . . . . 8 69 6.3.3. WalnutDSA Parameter: t-values . . . . . . . . . . . . 8 70 6.3.4. WalnutDSA Parameter: matrix 1 . . . . . . . . . . . . 9 71 6.3.5. WalnutDSA Parameter: permutation 1 . . . . . . . . . 9 72 6.3.6. WalnutDSA Parameter: matrix 2 . . . . . . . . . . . . 9 73 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 74 7.1. Normative References . . . . . . . . . . . . . . . . . . 10 75 7.2. Informative References . . . . . . . . . . . . . . . . . 10 76 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 11 77 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11 79 1. Introduction 81 This document specifies the conventions for using the Walnut Digital 82 Signature Algorithm (WalnutDSA) [WALNUTDSA] for digital signatures 83 with the CBOR Object Signing and Encryption (COSE) [RFC8152] syntax. 84 WalnutDSA is a Group-Theoretic [GTC] signature scheme where signature 85 validation is both computationally- and space-efficient, even on very 86 small processors. Unlike many hash-based signatures, there is no 87 state required and no limit on the number of signatures that can be 88 made. WalnutDSA private and public keys are relatively small; 89 however, the signatures are larger than RSA and ECC, but still 90 smaller than most all other quantum-resistant schemes (including all 91 hash-based schemes). 93 1.1. Motivation 95 There have been recent advances in cryptanalysis and advances in the 96 development of quantum computers. Each of these advances pose a 97 threat to widely deployed digital signature algorithms. 99 At Black Hat USA 2013, some researchers gave a presentation on the 100 current state of public key cryptography. They said: "Current 101 cryptosystems depend on discrete logarithm and factoring which has 102 seen some major new developments in the past 6 months" [BH2013]. Due 103 to advances in cryptanalysis, they encouraged preparation for a day 104 when RSA and DSA cannot be depended upon. 106 Peter Shor showed that a large-scale quantum computer could be used 107 to factor a number in polynomial time [S1997], effectively breaking 108 RSA. If large-scale quantum computers are ever built, these 109 computers will be able to break many of the public-key cryptosystems 110 currently in use. A post-quantum cryptosystem [PQC] is a system that 111 is secure against quantum computers that have more than a trivial 112 number of quantum bits (qu-bits). It is open to conjecture when it 113 will be feasible to build such a machine; however, RSA, DSA, ECDSA, 114 and EdDSA are all vulnerable if large-scale uantum computers come to 115 pass. 117 WalnutDSA does not depend on the difficulty of discrete logarithm or 118 factoring. As a result this algorithm is considered to be post- 119 quantum secure. 121 Today, RSA and ECDSA are often used to digitally sign software 122 updates. Unfortunately, implementations of RSA and ECDSA can be 123 relatively large, and verification can take a significant amount of 124 time on some very small processors. Therefore, we desire a digital 125 signature scheme that verifies faster with less code. Moreover, in 126 preparation for a day when RSA, DSA, and ECDSA cannot be depended 127 upon, a digital signature algorithm is needed that will remain secure 128 even if there are significant cryptoanalytic advances or a large- 129 scale quantum computer is invented. WalnutDSA, specified in 130 [WALNUTSPEC], is one such algorithm. 132 2. Terminology 134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 136 "OPTIONAL" in this document are to be interpreted as described in BCP 137 14 RFC 2119 [RFC2119] RFC 8174 [RFC8174] when, and only when, they 138 appear in all capitals, as shown here. 140 3. WalnutDSA Algorithm Overview 142 This specification makes use of WalnutDSA signatures as described in 143 [WALNUTDSA] and more concretely specified in [WALNUTSPEC]. WalnutDSA 144 is a Group-Theoretic cryptographic signature scheme that leverages 145 infinite group theory as the basis of its security and maps that to a 146 one-way evaluation of a series of matrices over small finite fields 147 with permuted multiplicants based on the group input. WalnutDSA 148 leverages the SHA2-256 and SHA2-512 one-way hash algorithms [SHA2] in 149 a hash-then-sign process. 151 WalnutDSA is based on a one-way function, E-Multiplication, which is 152 an action on the infinite group. A single E-Multiplication step 153 takes as input a matrix and permutation, a generator in the group, 154 and a set of T-values (entries in the finite field) and outputs a new 155 matrix and permutation. To process a long string of generators (like 156 a WalnutDSA signature), E-Multiplication is iterated over each 157 generator. Due to its structure, E-Multiplication is extremely easy 158 to implement. 160 In addition to being quantum-resistant, the two main benefits of 161 using WalnutDSA are that the verification implementation is very 162 small and WalnutDSA signature verification is extremely fast, even on 163 very small processors (including 16- and even 8-bit MCUs). This 164 lends it well to use in constrained and/or time-sensitive 165 environments. 167 WalnutDSA has several parameters required to process a signature. 168 The main parameters are N and q. The parameter N defines the size of 169 the group and implies working in an NxN matrix. The parameter q 170 defines the size of the finite field (in q elements). Signature 171 verification also requires a set of T-values, which is an ordered 172 list of N entries in the finite field F_q. 174 A WalnutDSA signature is just a string of generators in the infinite 175 group. 177 4. WalnutDSA Algorithm Identifiers 179 The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two 180 signature algorithm schemes. This specification makes use of the 181 signature with appendix scheme for WalnutDSA signatures. 183 The signature value is a large byte string. The byte string is 184 designed for easy parsing, and it includes a length (number of 185 generators) and type codes that indirectly provide all of the 186 information that is needed to parse the byte string during signature 187 validation. 189 When using a COSE key for this algorithm, the following checks are 190 made: 192 o The 'kty' field MUST be present, and it MUST be 'WalnutDSA'. 194 o If the 'alg' field is present, and it MUST be 'WalnutDSA'. 196 o If the 'key_ops' field is present, it MUST include 'sign' when 197 creating a WalnutDSA signature. 199 o If the 'key_ops' field is present, it MUST include 'verify' when 200 verifying a WalnutDSA signature. 202 o If the 'kid' field is present, it MAY be used to identify the 203 WalnutDSA Key. 205 5. Security Considerations 207 5.1. Implementation Security Considerations 209 Implementations must protect the private keys. Use of a hardware 210 security module (HSM) is one way to protect the private keys. 211 Compromise of the private keys may result in the ability to forge 212 signatures. As a result, when a private key is stored on non- 213 volatile media or stored in a virtual machine environment, care must 214 be taken to preserve confidentiality and integrity. 216 The generation of private keys relies on random numbers. The use of 217 inadequate pseudo-random number generators (PRNGs) to generate these 218 values can result in little or no security. An attacker may find it 219 much easier to reproduce the PRNG environment that produced the keys, 220 searching the resulting small set of possibilities, rather than brute 221 force searching the whole key space. The generation of quality 222 random numbers is difficult. [RFC4086] offers important guidance in 223 this area. 225 The generation of WalnutDSA signatures also depends on random 226 numbers. While the consequences of an inadequate pseudo-random 227 number generator (PRNGs) to generate these values is much less severe 228 than the generation of private keys, the guidance in [RFC4086] 229 remains important. 231 5.2. Method Security Considerations 233 The Walnut Digital Signature Algorithm has undergone significant 234 cryptanalysis since it was first introduced, and several weaknesses 235 were found in early versions of the method, resulting in the 236 description of several exponential attacks. A full writeup of all 237 the analysis can be found in [WalnutDSAAnalysis]. In summary, the 238 original suggested parameters were too small, leading to many of 239 these exponential attacks being practical. However, current 240 parameters render these attacks impractical. The following 241 paragraphs summarize the analysis and how the current parameters 242 defeat all the previous attacks. 244 First, the team of Hart et al found a universal forgery attack based 245 on a group factoring problem that runs in O(q^((N-1)/2)) with a 246 memory complexity of log_2(q) N^2 q^((N-1)/2). With parameters N=10 247 and q=M31 (2^31 - 1), the runtime is 2^139 and memory complexity is 248 2^151. W. Beullens found a modification of this attack but its 249 runtime is even longer. 251 Next, Beullens and Blackburn found several issues with the original 252 method and parameters. First they used a Pollard-Rho attack and 253 discovered the original public key space was too small. Specifically 254 they require that q^(N(N-1)-1) > 2^(2*Security Level). One can 255 clearly see that N=10, q=M31 provides 128-bit security and N=10, 256 q=M61 provides 256-bit security. 258 Beullens and Blackburn also found two issues with the original 259 message encoder of WalnutDSA. First, the original encoder was non- 260 injective, which reduced the available signature space. This was 261 repaired in an update. Second, they pointed out that the dimension 262 of the vector space generated by the encoder was too small. 263 Specifically, they require that q^dimension > 2^(2*Security Level). 264 With N=10, the current encoder produces a dimension of 66 which 265 clearly provides sufficient security. 267 The final issue discovered by Beullens and Blackburn was a process to 268 theoretically "reverse" E-Multiplication. First, their process 269 requires knowing the initial matrix and permutation (which is known 270 for WalnutDSA). But more importantly, their process runs at 271 O(q^((N-1)/2)) which, for N=10, q=M31 is greater than 2^128. 273 A team at Steven's Institute leveraged a length-shortening attack 274 that enabled them to remove the cloaking elements and then solve a 275 conjugacy search problem to derive the private keys. Their attack 276 requires both knowledge of the permutation being cloaked and also 277 that the cloaking elements themselves are conjugates. By adding 278 additional concealed cloaking elements the attack requires an N! 279 search for each cloaking element. By inserting k concealed cloaking 280 elements, this requires the attacker to perform (N!)^k work. This 281 allows k to be set to meet the desired security level. 283 Finally, Merz and Petit discovered that using a Garside Normal Form 284 of a WalnutDSA signature enabled them to find commonalities with the 285 Garside Normal Form of the encoded message. Using those 286 commonalities they were able to splice into a signature and create 287 forgeries. Increasing the number of cloaking elements, specifically 288 within the encoded message, sufficiently obscures the commonalities 289 and blocks this attack. 291 In summary, most of these attacks are exponential in run time and can 292 be shown that current parameters put the runtime beyond the desired 293 security level. The final two attacks are also sufficiently blocked 294 to the desired security level. 296 6. IANA Considerations 298 IANA is requested to add entries for WalnutDSA signatures in the 299 "COSE Algorithms" registry and WalnutDSA public keys in the "COSE Key 300 Types" and "COSE Key Type Parameters" registries. 302 6.1. COSE Algorithms Registry Entry 304 The new entry in the "COSE Algorithms" registry has the following 305 columns: 307 Name: WalnutDSA 309 Value: TBD1 (Value to be assigned by IANA) 311 Description: WalnutDSA signature 313 Reference: This document (Number to be assigned by RFC Editor) 315 Recommended: Yes 317 6.2. COSE Key Types Registry Entry 319 The new entry in the "COSE Key Types" registry has the following 320 columns: 322 Name: WalnutDSA 324 Value: TBD2 (Value to be assigned by IANA) 326 Description: WalnutDSA public key 328 Reference: This document (Number to be assigned by RFC Editor) 330 6.3. COSE Key Type Parameter Registry Entries 332 The following sections detail the additions to the "COSE Key Type 333 Parameters" registry. 335 6.3.1. WalnutDSA Parameter: N 337 The new entry N in the "COSE Key Type Parameters" registry has the 338 following columns: 340 Key Type: TBD2 (Value assigned by IANA above) 342 Name: N 344 Label: TBD (Value to be assigned by IANA) 346 CBOR Type: uint 348 Description: Group and Matrix (NxN) size 350 Reference: This document (Number to be assigned by RFC Editor) 352 6.3.2. WalnutDSA Parameter: q 354 The new entry q in the "COSE Key Type Parameters" registry has the 355 following columns: 357 Key Type: TBD2 (Value assigned by IANA above) 359 Name: q 361 Label: TBD (Value to be assigned by IANA) 363 CBOR Type: uint 365 Description: Finite field F_q 367 Reference: This document (Number to be assigned by RFC Editor) 369 6.3.3. WalnutDSA Parameter: t-values 371 The new entry t-values in the "COSE Key Type Parameters" registry has 372 the following columns: 374 Key Type: TBD2 (Value assigned by IANA above) 376 Name: t-values 377 Label: TBD (Value to be assigned by IANA) 379 CBOR Type: array (of uint) 381 Description: List of T-values, enties in F_q 383 Reference: This document (Number to be assigned by RFC Editor) 385 6.3.4. WalnutDSA Parameter: matrix 1 387 The new entry matrix 1 in the "COSE Key Type Parameters" registry has 388 the following columns: 390 Key Type: TBD2 (Value assigned by IANA above) 392 Name: matrix 1 394 Label: TBD (Value to be assigned by IANA) 396 CBOR Type: array (of array of uint) 398 Description: NxN Matrix of enties in F_q 400 Reference: This document (Number to be assigned by RFC Editor) 402 6.3.5. WalnutDSA Parameter: permutation 1 404 The new entry permutation 1 in the "COSE Key Type Parameters" 405 registry has the following columns: 407 Key Type: TBD2 (Value assigned by IANA above) 409 Name: permutation 1 411 Label: TBD (Value to be assigned by IANA) 413 CBOR Type: array (of uint) 415 Description: Permutation associated with matrix 1 417 Reference: This document (Number to be assigned by RFC Editor) 419 6.3.6. WalnutDSA Parameter: matrix 2 421 The new entry matrix 2 in the "COSE Key Type Parameters" registry has 422 the following columns: 424 Key Type: TBD2 (Value assigned by IANA above) 425 Name: matrix 2 427 Label: TBD (Value to be assigned by IANA) 429 CBOR Type: array (of array of uint) 431 Description: NxN Matrix of enties in F_q 433 Reference: This document (Number to be assigned by RFC Editor) 435 7. References 437 7.1. Normative References 439 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 440 Requirement Levels", BCP 14, RFC 2119, 441 DOI 10.17487/RFC2119, March 1997, . 444 [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", 445 RFC 8152, DOI 10.17487/RFC8152, July 2017, 446 . 448 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 449 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 450 May 2017, . 452 [SHA2] National Institute of Standards and Technology (NIST), 453 "FIPS Publication 180-3: Secure Hash Standard", October 454 2008. 456 [WALNUTSPEC] 457 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 458 "The Walnut Digital Signature Algorithm Specification", 459 November 2018. 461 7.2. Informative References 463 [BH2013] Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The 464 Factoring Dead: Preparing for the Cryptopocalypse", August 465 2013, . 468 [GTC] Vasco, M. and R. Steinwandt, "Group Theoretic 469 Cryptography", April 2015, . 473 [PQC] Bernstein, D., "Introduction to post-quantum 474 cryptography", 2009, 475 . 478 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 479 "Randomness Requirements for Security", BCP 106, RFC 4086, 480 DOI 10.17487/RFC4086, June 2005, . 483 [S1997] Shor, P., "Polynomial-time algorithms for prime 484 factorization and discrete logarithms on a quantum 485 computer", SIAM Journal on Computing 26(5), 1484-26, 1997, 486 . 488 [WALNUTDSA] 489 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 490 "WalnutDSA(TM): A Quantum-Resistant Digital Signature 491 Algorithm", January 2017, 492 . 494 [WalnutDSAAnalysis] 495 Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, 496 "Defeating the Hart et al, Beullens-Blackburn, Kotov- 497 Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)", 498 May 2019, . 500 Appendix A. Acknowledgments 502 A big thank you to Russ Housley for his input on the concepts and 503 text of this document. 505 Author's Address 507 Derek Atkins 508 SecureRF Corporation 509 100 Beard Sawmill Rd, Suite 350 510 Shelton, CT 06484 511 US 513 Phone: +1 617 623 3745 514 Email: datkins@securerf.com