Use of the Walnut Digital Signature Algorithm with CBOR Object Signing and Encryption (COSE)
draft-atkins-suit-cose-walnutdsa-00

Internet Engineering Task Force                                D. Atkins
Internet-Draft                                      SecureRF Corporation
Intended status: Standards Track                            May 13, 2019
Expires: November 14, 2019

 Use of the Walnut Digital Signature Algorithm with CBOR Object Signing
                         and Encryption (COSE)
                  draft-atkins-suit-cose-walnutdsa-00

Abstract

   This document specifies the conventions for using the Walnut Digital
   Signature Algorithm (WalnutDSA) for digital signatures with the CBOR
   Object Signing and Encryption (COSE) syntax.  WalnutDSA is a
   lightweight, quantum-resistant signature scheme based on Group
   Theoretic Cryptography (see [WALNUTDSA] and [WALNUTSPEC]) with
   implementation and computational efficiency of signature verification
   in constrained environments, even on 8- and 16-bit platforms.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on November 14, 2019.

Copyright Notice

   Copyright (c) 2019 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must

Atkins                  Expires November 14, 2019               [Page 1]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Algorithm Security Considerations . . . . . . . . . . . .   3
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  WalnutDSA Algorithm Overview  . . . . . . . . . . . . . . . .   4
   4.  WalnutDSA Algorithm Identifiers . . . . . . . . . . . . . . .   4
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .   5
     5.1.  Implementation Security Considerations  . . . . . . . . .   5
     5.2.  Method Security Considerations  . . . . . . . . . . . . .   5
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   7
     6.1.  COSE Algorithms Registry Entry  . . . . . . . . . . . . .   7
     6.2.  COSE Key Types Registry Entry . . . . . . . . . . . . . .   7
     6.3.  COSE Key Type Parameter Registry Entries  . . . . . . . .   8
       6.3.1.  WalnutDSA Parameter: N  . . . . . . . . . . . . . . .   8
       6.3.2.  WalnutDSA Parameter: q  . . . . . . . . . . . . . . .   8
       6.3.3.  WalnutDSA Parameter: t-values . . . . . . . . . . . .   8
       6.3.4.  WalnutDSA Parameter: matrix 1 . . . . . . . . . . . .   9
       6.3.5.  WalnutDSA Parameter: permutation 1  . . . . . . . . .   9
       6.3.6.  WalnutDSA Parameter: matrix 2 . . . . . . . . . . . .   9
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .  10
     7.2.  Informative References  . . . . . . . . . . . . . . . . .  10
   Appendix A.  Acknowledgments  . . . . . . . . . . . . . . . . . .  11
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  11

1.  Introduction

   This document specifies the conventions for using the Walnut Digital
   Signature Algorithm (WalnutDSA) [WALNUTDSA] for digital signatures
   with the CBOR Object Signing and Encryption (COSE) [RFC8152] syntax.
   WalnutDSA is a Group-Theoretic [GTC] signature scheme where signature
   validation is both computationally- and space-efficient, even on very
   small processors.  Unlike many hash-based signatures, there is no
   state required and no limit on the number of signatures that can be
   made.  WalnutDSA private and public keys are relatively small;
   however, the signatures are larger than RSA and ECC, but still
   smaller than most all other quantum-resistant schemes (including all
   hash-based schemes).

Atkins                  Expires November 14, 2019               [Page 2]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

1.1.  Algorithm Security Considerations

   There have been recent advances in cryptanalysis and advances in the
   development of quantum computers.  Each of these advances pose a
   threat to widely deployed digital signature algorithms.

   At Black Hat USA 2013, some researchers gave a presentation on the
   current state of public key cryptography.  They said: "Current
   cryptosystems depend on discrete logarithm and factoring which has
   seen some major new developments in the past 6 months" [BH2013].  Due
   to advances in cryptanalysis, they encouraged preparation for a day
   when RSA and DSA cannot be depended upon.

   Peter Shor showed that a large-scale quantum computer could be used
   to factor a number in polynomial time [S1997], effectively breaking
   RSA.  If large-scale quantum computers are ever built, these
   computers will be able to break many of the public-key cryptosystems
   currently in use.  A post-quantum cryptosystem [PQC] is a system that
   is secure against quantum computers that have more than a trivial
   number of quantum bits (qu-bits).  It is open to conjecture when it
   will be feasible to build such a machine; however, RSA, DSA, ECDSA,
   and EdDSA are all vulnerable if large-scale uantum computers come to
   pass.

   WalnutDSA does not depend on the difficulty of discrete logarithm or
   factoring.  As a result this algorithm is considered to be post-
   quantum secure.

   Today, RSA and ECDSA are often used to digitally sign software
   updates.  Unfortunately, implementations of RSA and ECDSA can be
   relatively large, and verification can take a significant amount of
   time on some very small processors.  Therefore, we desire a digital
   signature scheme that verifies faster with less code.  Moreover, in
   preparation for a day when RSA, DSA, and ECDSA cannot be depended
   upon, a digital signature algorithm is needed that will remain secure
   even if there are significant cryptoanalytic advances or a large-
   scale quantum computer is invented.  WalnutDSA, specified in
   [WALNUTSPEC], is one such algorithm.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in BCP
   14 RFC 2119 [RFC2119] RFC 8174 [RFC8174] when, and only when, they
   appear in all capitals, as shown here.

Atkins                  Expires November 14, 2019               [Page 3]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

3.  WalnutDSA Algorithm Overview

   This specification makes use of WalnutDSA signatures as described in
   [WALNUTDSA] and more concretely specified in [WALNUTSPEC].  WalnutDSA
   is a Group-Theoretic cryptographic signature scheme that leverages
   infinite group theory as the basis of its security and maps that to a
   one-way evaluation of a series of matrices over small finite fields
   with permuted multiplicants based on the group input.  WalnutDSA
   leverages the SHA2-256 and SHA2-512 one-way hash algorithms [SHA2] in
   a hash-then-sign process.

   WalnutDSA is based on a one-way function, E-Multiplication, which is
   an action on the infinite group.  A single E-Multiplication step
   takes as input a matrix and permutation, a generator in the group,
   and a set of T-values (entries in the finite field) and outputs a new
   matrix and permutation.  To process a long string of generators (like
   a WalnutDSA signature), E-Multiplication is iterated over each
   generator.  Due to its structure, E-Multiplication is extremely easy
   to implement.

   In addition to being quantum-resistant, the two main benefits of
   using WalnutDSA are that the verification implementation is very
   small and WalnutDSA signature verification is extremely fast, even on
   very small processors (including 16- and even 8-bit MCUs).  This
   lends it well to use in constrained and/or time-sensitive
   environments.

   WalnutDSA has several parameters required to process a signature.
   The main parameters are N and q.  The parameter N defines the size of
   the group and implies working in an NxN matrix.  The parameter q
   defines the size of the finite field (in q elements).  Signature
   verification also requires a set of T-values, which is an ordered
   list of N entries in the finite field F_q.

   A WalnutDSA signature is just a string of generators in the infinite
   group.

4.  WalnutDSA Algorithm Identifiers

   The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two
   signature algorithm schemes.  This specification makes use of the
   signature with appendix scheme for WalnutDSA signatures.

   The signature value is a large byte string.  The byte string is
   designed for easy parsing, and it includes a length (number of
   generators) and type codes that indirectly provide all of the
   information that is needed to parse the byte string during signature
   validation.

Atkins                  Expires November 14, 2019               [Page 4]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

   When using a COSE key for this algorithm, the following checks are
   made:

   o  The 'kty' field MUST be present, and it MUST be 'WalnutDSA'.

   o  If the 'alg' field is present, and it MUST be 'WalnutDSA'.

   o  If the 'key_ops' field is present, it MUST include 'sign' when
      creating a WalnutDSA signature.

   o  If the 'key_ops' field is present, it MUST include 'verify' when
      verifying a WalnutDSA signature.

   o  If the 'kid' field is present, it MAY be used to identify the
      WalnutDSA Key.

5.  Security Considerations

5.1.  Implementation Security Considerations

   Implementations must protect the private keys.  Use of a hardware
   security module (HSM) is one way to protect the private keys.
   Compromise of the private keys may result in the ability to forge
   signatures.  As a result, when a private key is stored on non-
   volatile media or stored in a virtual machine environment, care must
   be taken to preserve confidentiality and integrity.

   The generation of private keys relies on random numbers.  The use of
   inadequate pseudo-random number generators (PRNGs) to generate these
   values can result in little or no security.  An attacker may find it
   much easier to reproduce the PRNG environment that produced the keys,
   searching the resulting small set of possibilities, rather than brute
   force searching the whole key space.  The generation of quality
   random numbers is difficult.  [RFC4086] offers important guidance in
   this area.

   The generation of WalnutDSA signatures also depends on random
   numbers.  While the consequences of an inadequate pseudo-random
   number generator (PRNGs) to generate these values is much less severe
   than the generation of private keys, the guidance in [RFC4086]
   remains important.

5.2.  Method Security Considerations

   The Walnut Digital Signature Algorithm has undergone significant
   cryptanalysis since it was first introduced, and several weaknesses
   were found in early versions of the method, resulting in the
   description of several exponential attacks.  A full writeup of all

Atkins                  Expires November 14, 2019               [Page 5]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

   the analysis can be found in [WalnutDSAAnalysis].  In summary, the
   original suggested parameters were too small, leading to many of
   these exponential attacks being practical.  However, current
   parameters render these attacks impractical.  The following
   paragraphs summarize the analysis and how the current parameters
   defeat all the previous attacks.

   First, the team of Hart et al found a universal forgery attack based
   on a group factoring problem that runs in O(q^((N-1)/2)) with a
   memory complexity of log_2(q) N^2 q^((N-1)/2).  With parameters N=10
   and q=M31 (2^31 - 1), the runtime is 2^139 and memory complexity is
   2^151.  W.  Beullens found a modification of this attack but its
   runtime is even longer.

   Next, Beullens and Blackburn found several issues with the original
   method and parameters.  First they used a Pollard-Rho attack and
   discovered the original public key space was too small.  Specifically
   they require that q^(N(N-1)-1) > 2^(2*Security Level).  One can
   clearly see that N=10, q=M31 provides 128-bit security and N=10,
   q=M61 provides 256-bit security.

   Beullens and Blackburn also found two issues with the original
   message encoder of WalnutDSA.  First, the original encoder was non-
   injective, which reduced the available signature space.  This was
   repaired in an update.  Second, they pointed out that the dimension
   of the vector space generated by the encoder was too small.
   Specifically, they require that q^dimension > 2^(2*Security Level).
   With N=10, the current encoder produces a dimension of 66 which
   clearly provides sufficient security.

   The final issue discovered by Beullens and Blackburn was a process to
   theoretically "reverse" E-Multiplication.  First, their process
   requires knowing the initial matrix and permutation (which is known
   for WalnutDSA).  But more importantly, their process runs at
   O(q^((N-1)/2)) which, for N=10, q=M31 is greater than 2^128.

   A team at Steven's Institute leveraged a length-shortening attack
   that enabled them to remove the cloaking elements and then solve a
   conjugacy search problem to derive the private keys.  Their attack
   requires both knowledge of the permutation being cloaked and also
   that the cloaking elements themselves are conjugates.  By adding
   additional concealed cloaking elements the attack requires an N!
   search for each cloaking element.  By inserting k concealed cloaking
   elements, this requires the attacker to perform (N!)^k work.  This
   allows k to be set to meet the desired security level.

   Finally, Merz and Petit discovered that using a Garside Normal Form
   of a WalnutDSA signature enabled them to find commonalities with the

Atkins                  Expires November 14, 2019               [Page 6]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

   Garside Normal Form of the encoded message.  Using those
   commonalities they were able to splice into a signature and create
   forgeries.  Increasing the number of cloaking elements, specifically
   within the encoded message, sufficiently obscures the commonalities
   and blocks this attack.

   In summary, most of these attacks are exponential in run time and can
   be shown that current parameters put the runtime beyond the desired
   security level.  The final two attacks are also sufficiently blocked
   to the desired security level.

6.  IANA Considerations

   IANA is requested to add entries for WalnutDSA signatures in the
   "COSE Algorithms" registry and WalnutDSA public keys in the "COSE Key
   Types" and "COSE Key Type Parameters" registries.

6.1.  COSE Algorithms Registry Entry

   The new entry in the "COSE Algorithms" registry has the following
   columns:

      Name: WalnutDSA

      Value: TBD1 (Value to be assigned by IANA)

      Description: WalnutDSA signature

      Reference: This document (Number to be assigned by RFC Editor)

      Recommended: Yes

6.2.  COSE Key Types Registry Entry

   The new entry in the "COSE Key Types" registry has the following
   columns:

      Name: WalnutDSA

      Value: TBD2 (Value to be assigned by IANA)

      Description: WalnutDSA public key

      Reference: This document (Number to be assigned by RFC Editor)

Atkins                  Expires November 14, 2019               [Page 7]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

6.3.  COSE Key Type Parameter Registry Entries

   The following sections detail the additions to the "COSE Key Type
   Parameters" registry.

6.3.1.  WalnutDSA Parameter: N

   The new entry N in the "COSE Key Type Parameters" registry has the
   following columns:

      Key Type: TBD2 (Value assigned by IANA above)

      Name: N

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: uint

      Description: Group and Matrix (NxN) size

      Reference: This document (Number to be assigned by RFC Editor)

6.3.2.  WalnutDSA Parameter: q

   The new entry q in the "COSE Key Type Parameters" registry has the
   following columns:

      Key Type: TBD2 (Value assigned by IANA above)

      Name: q

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: uint

      Description: Finite field F_q

      Reference: This document (Number to be assigned by RFC Editor)

6.3.3.  WalnutDSA Parameter: t-values

   The new entry t-values in the "COSE Key Type Parameters" registry has
   the following columns:

      Key Type: TBD2 (Value assigned by IANA above)

      Name: t-values

Atkins                  Expires November 14, 2019               [Page 8]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: array (of uint)

      Description: List of T-values, enties in F_q

      Reference: This document (Number to be assigned by RFC Editor)

6.3.4.  WalnutDSA Parameter: matrix 1

   The new entry matrix 1 in the "COSE Key Type Parameters" registry has
   the following columns:

      Key Type: TBD2 (Value assigned by IANA above)

      Name: matrix 1

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: array (of array of uint)

      Description: NxN Matrix of enties in F_q

      Reference: This document (Number to be assigned by RFC Editor)

6.3.5.  WalnutDSA Parameter: permutation 1

   The new entry permutation 1 in the "COSE Key Type Parameters"
   registry has the following columns:

      Key Type: TBD2 (Value assigned by IANA above)

      Name: permutation 1

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: array (of uint)

      Description: Permutation associated with matrix 1

      Reference: This document (Number to be assigned by RFC Editor)

6.3.6.  WalnutDSA Parameter: matrix 2

   The new entry matrix 2 in the "COSE Key Type Parameters" registry has
   the following columns:

      Key Type: TBD2 (Value assigned by IANA above)

Atkins                  Expires November 14, 2019               [Page 9]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

      Name: matrix 2

      Label: TBD (Value to be assigned by IANA)

      CBOR Type: array (of array of uint)

      Description: NxN Matrix of enties in F_q

      Reference: This document (Number to be assigned by RFC Editor)

7.  References

7.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997, <https://www.rfc-
              editor.org/info/rfc2119>.

   [RFC8152]  Schaad, J., "CBOR Object Signing and Encryption (COSE)",
              RFC 8152, DOI 10.17487/RFC8152, July 2017,
              <https://www.rfc-editor.org/info/rfc8152>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

   [SHA2]     National Institute of Standards and Technology (NIST),
              "FIPS Publication 180-3: Secure Hash Standard", October
              2008.

   [WALNUTSPEC]
              Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
              "The Walnut Digital Signature Algorithm Specification",
              November 2018.

7.2.  Informative References

   [BH2013]   Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The
              Factoring Dead: Preparing for the Cryptopocalypse", August
              2013, <https://media.blackhat.com/us-13/us-13-Stamos-The-
              Factoring-Dead.pdf>.

   [GTC]      Vasco, M. and R. Steinwandt, "Group Theoretic
              Cryptography", April 2015, <https://www.crcpress.com/
              Group-Theoretic-Cryptography/Vasco-Steinwandt/p/
              book/9781584888369>.

Atkins                  Expires November 14, 2019              [Page 10]
Internet-Draft             WalnutDSA COSE Sigs                  May 2019

   [PQC]      Bernstein, D., "Introduction to post-quantum
              cryptography", 2009,
              <http://www.pqcrypto.org/www.springer.com/cda/content/
              document/cda_downloaddocument/9783540887010-c1.pdf>.

   [RFC4086]  Eastlake 3rd, D., Schiller, J., and S. Crocker,
              "Randomness Requirements for Security", BCP 106, RFC 4086,
              DOI 10.17487/RFC4086, June 2005, <https://www.rfc-
              editor.org/info/rfc4086>.

   [S1997]    Shor, P., "Polynomial-time algorithms for prime
              factorization and discrete logarithms on a quantum
              computer", SIAM Journal on Computing 26(5), 1484-26, 1997,
              <http://dx.doi.org/10.1137/S0097539795293172>.

   [WALNUTDSA]
              Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
              "WalnutDSA(TM): A Quantum-Resistant Digital Signature
              Algorithm", January 2017,
              <https://eprint.iacr.org/2017/058>.

   [WalnutDSAAnalysis]
              Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
              "Defeating the Hart et al, Beullens-Blackburn, Kotov-
              Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)",
              May 2019, <https://eprint.iacr.org/2019/472>.

Appendix A.  Acknowledgments

   A big thank you to Russ Housley for his input on the concepts and
   text of this document.

Author's Address

   Derek Atkins
   SecureRF Corporation
   100 Beard Sawmill Rd, Suite 350
   Shelton, CT  06484
   US

   Phone: +1 617 623 3745
   Email: datkins@securerf.com, derek@ihtfp.com

Atkins                  Expires November 14, 2019              [Page 11]