rfc9021.original   rfc9021.txt 
Internet Engineering Task Force D. Atkins Independent Submission D. Atkins
Internet-Draft Veridify Security Request for Comments: 9021 Veridify Security
Intended status: Informational January 26, 2021 Category: Informational May 2021
Expires: July 30, 2021 ISSN: 2070-1721
Use of the Walnut Digital Signature Algorithm with CBOR Object Signing Use of the Walnut Digital Signature Algorithm with CBOR Object Signing
and Encryption (COSE) and Encryption (COSE)
draft-atkins-suit-cose-walnutdsa-07
Abstract Abstract
This document specifies the conventions for using the Walnut Digital This document specifies the conventions for using the Walnut Digital
Signature Algorithm (WalnutDSA) for digital signatures with the CBOR Signature Algorithm (WalnutDSA) for digital signatures with the CBOR
Object Signing and Encryption (COSE) syntax. WalnutDSA is a Object Signing and Encryption (COSE) syntax. WalnutDSA is a
lightweight, quantum-resistant signature scheme based on Group lightweight, quantum-resistant signature scheme based on Group
Theoretic Cryptography with implementation and computational Theoretic Cryptography with implementation and computational
efficiency of signature verification in constrained environments, efficiency of signature verification in constrained environments,
even on 8- and 16-bit platforms. even on 8- and 16-bit platforms.
The goal of this publication is to document a way to use the The goal of this publication is to document a way to use the
lightweight, quantum-resistant WalnutDSA signature algorithm in COSE lightweight, quantum-resistant WalnutDSA signature algorithm in COSE
in a way that would allow multiple developers to build compatible in a way that would allow multiple developers to build compatible
implementations. As of this publication, the security properties of implementations. As of this publication, the security properties of
WalnutDSA have not been evaluated by the IETF and its use has not WalnutDSA have not been evaluated by the IETF and its use has not
been endorsed by the IETF. been endorsed by the IETF.
WalnutDSA(TM) and Walnut Digital Signature Algorithm(TM) are WalnutDSA and the Walnut Digital Signature Algorithm are trademarks
trademarks of Veridify Security Inc.. of Veridify Security Inc.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
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 https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This is a contribution to the RFC Series, independently of any other
and may be updated, replaced, or obsoleted by other documents at any RFC stream. The RFC Editor has chosen to publish this document at
time. It is inappropriate to use Internet-Drafts as reference its discretion and makes no statement about its value for
material or to cite them other than as "work in progress." implementation or deployment. Documents approved for publication by
the RFC Editor are not candidates for any level of Internet Standard;
see Section 2 of RFC 7841.
This Internet-Draft will expire on July 30, 2021. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc9021.
Copyright Notice Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document.
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 Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction
1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Motivation
1.2. Trademark Notice . . . . . . . . . . . . . . . . . . . . 4 1.2. Trademark Notice
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology
3. WalnutDSA Algorithm Overview . . . . . . . . . . . . . . . . 4 3. WalnutDSA Algorithm Overview
4. WalnutDSA Algorithm Identifiers . . . . . . . . . . . . . . . 5 4. WalnutDSA Algorithm Identifiers
5. Security Considerations . . . . . . . . . . . . . . . . . . . 5 5. Security Considerations
5.1. Implementation Security Considerations . . . . . . . . . 6 5.1. Implementation Security Considerations
5.2. Method Security Considerations . . . . . . . . . . . . . 6 5.2. Method Security Considerations
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 6. IANA Considerations
6.1. COSE Algorithms Registry Entry . . . . . . . . . . . . . 8 6.1. COSE Algorithms Registry Entry
6.2. COSE Key Types Registry Entry . . . . . . . . . . . . . . 8 6.2. COSE Key Types Registry Entry
6.3. COSE Key Type Parameter Registry Entries . . . . . . . . 8 6.3. COSE Key Type Parameters Registry Entries
6.3.1. WalnutDSA Parameter: N . . . . . . . . . . . . . . . 8 6.3.1. WalnutDSA Parameter: N
6.3.2. WalnutDSA Parameter: q . . . . . . . . . . . . . . . 9 6.3.2. WalnutDSA Parameter: q
6.3.3. WalnutDSA Parameter: t-values . . . . . . . . . . . . 9 6.3.3. WalnutDSA Parameter: t-values
6.3.4. WalnutDSA Parameter: matrix 1 . . . . . . . . . . . . 9 6.3.4. WalnutDSA Parameter: matrix 1
6.3.5. WalnutDSA Parameter: permutation 1 . . . . . . . . . 10 6.3.5. WalnutDSA Parameter: permutation 1
6.3.6. WalnutDSA Parameter: matrix 2 . . . . . . . . . . . . 10 6.3.6. WalnutDSA Parameter: matrix 2
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. References
7.1. Normative References . . . . . . . . . . . . . . . . . . 10 7.1. Normative References
7.2. Informative References . . . . . . . . . . . . . . . . . 11 7.2. Informative References
Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . 12 Acknowledgments
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 12 Author's Address
1. Introduction 1. Introduction
This document specifies the conventions for using the Walnut Digital This document specifies the conventions for using the Walnut Digital
Signature Algorithm (WalnutDSA) [WALNUTDSA] for digital signatures Signature Algorithm (WalnutDSA) [WALNUTDSA] for digital signatures
with the CBOR Object Signing and Encryption (COSE) [RFC8152] syntax. with the CBOR Object Signing and Encryption (COSE) syntax [RFC8152].
WalnutDSA is a Group-Theoretic [GTC] signature scheme where signature WalnutDSA is a Group Theoretic signature scheme [GTC] where signature
validation is both computationally- and space-efficient, even on very validation is both computationally and space efficient, even on very
small processors. Unlike many hash-based signatures, there is no small processors. Unlike many hash-based signatures, there is no
state required and no limit on the number of signatures that can be state required and no limit on the number of signatures that can be
made. WalnutDSA private and public keys are relatively small; made. WalnutDSA private and public keys are relatively small;
however, the signatures are larger than RSA and ECC, but still however, the signatures are larger than RSA and Elliptic Curve
smaller than most all other quantum-resistant schemes (including all Cryptography (ECC), but still smaller than most all other quantum-
hash-based schemes). resistant schemes (including all hash-based schemes).
COSE provides a lightweight method to encode structured data. COSE provides a lightweight method to encode structured data.
WalnutDSA is a lightweight, quantum-resistant digital signature WalnutDSA is a lightweight, quantum-resistant digital signature
algorithm. The goal of this specification is to document a method to algorithm. The goal of this specification is to document a method to
leverage WalnutDSA in COSE in a way that would allow multiple leverage WalnutDSA in COSE in a way that would allow multiple
developers to build compatible implementations. developers to build compatible implementations.
As with all cryptosystems, the initial versions of WalnutDSA As with all cryptosystems, the initial versions of WalnutDSA
underwent significant cryptanalysis, and in some cases, identified underwent significant cryptanalysis, and, in some cases, identified
potential issues. For more discussion on this topic, a summary of potential issues. For more discussion on this topic, a summary of
all published cryptanalysis can be found in Section 5.2. Validated all published cryptanalysis can be found in Section 5.2. Validated
issues were addressed by reparameterization in updated versions of issues were addressed by reparameterization in updated versions of
WalnutDSA. Although the IETF has neither evaluated the security WalnutDSA. Although the IETF has neither evaluated the security
properties of WalnutDSA nor has the IETF endorsed WalnutDSA as of properties of WalnutDSA nor endorsed WalnutDSA as of this
this publication, this document provides a method to use WalnutDSA in publication, this document provides a method to use WalnutDSA in
conjunction with IETF protocols. As always, users of any security conjunction with IETF protocols. As always, users of any security
algorithm are advised to research the security properties of the algorithm are advised to research the security properties of the
algorithm and make their own judgment about the risks involved. algorithm and make their own judgment about the risks involved.
1.1. Motivation 1.1. Motivation
Recent advances in cryptanalysis [BH2013] and progress in the Recent advances in cryptanalysis [BH2013] and progress in the
development of quantum computers [NAS2019] pose a threat to widely development of quantum computers [NAS2019] pose a threat to widely
deployed digital signature algorithms. As a result, there is a need deployed digital signature algorithms. As a result, there is a need
to prepare for a day that cryptosystems such as RSA and DSA that to prepare for a day that cryptosystems such as RSA and DSA, which
depend on discrete logarithm and factoring cannot be depended upon. depend on discrete logarithm and factoring, cannot be depended upon.
If large-scale quantum computers are ever built, these computers will If large-scale quantum computers are ever built, these computers will
be able to break many of the public-key cryptosystems currently in be able to break many of the public key cryptosystems currently in
use. A post-quantum cryptosystem [PQC] is a system that is secure use. A post-quantum cryptosystem [PQC] is a system that is secure
against quantum computers that have more than a trivial number of against quantum computers that have more than a trivial number of
quantum bits (qubits). It is open to conjecture when it will be quantum bits (qubits). It is open to conjecture when it will be
feasible to build such computers; however, RSA, DSA, ECDSA, and EdDSA feasible to build such computers; however, RSA, DSA, the Elliptic
are all vulnerable if large-scale quantum computers come to pass. Curve Digital Signature Algorithm (ECDSA), and the Edwards-Curve
Digital Signature Algorithm (EdDSA) are all vulnerable if large-scale
quantum computers come to pass.
WalnutDSA does not depend on the difficulty of discrete logarithm or WalnutDSA does not depend on the difficulty of discrete logarithms or
factoring. As a result this algorithm is considered to be resistant factoring. As a result, this algorithm is considered to be resistant
to post-quantum attacks. to post-quantum attacks.
Today, RSA and ECDSA are often used to digitally sign software Today, RSA and ECDSA are often used to digitally sign software
updates. Unfortunately, implementations of RSA and ECDSA can be updates. Unfortunately, implementations of RSA and ECDSA can be
relatively large, and verification can take a significant amount of relatively large, and verification can take a significant amount of
time on some very small processors. Therefore, we desire a digital time on some very small processors. Therefore, we desire a digital
signature scheme that verifies faster with less code. Moreover, in signature scheme that verifies faster with less code. Moreover, in
preparation for a day when RSA, DSA, and ECDSA cannot be depended preparation for a day when RSA, DSA, and ECDSA cannot be depended
upon, a digital signature algorithm is needed that will remain secure upon, a digital signature algorithm is needed that will remain secure
even if there are significant cryptoanalytic advances or a large- even if there are significant cryptanalytic advances or a large-scale
scale quantum computer is invented. WalnutDSA, specified in quantum computer is invented. WalnutDSA, specified in [WALNUTSPEC],
[WALNUTSPEC], is a quantum-resistant algorithm that addresses these is a quantum-resistant algorithm that addresses these requirements.
requirements.
1.2. Trademark Notice 1.2. Trademark Notice
WalnutDSA(TM) and Walnut Digital Signature Algorithm(TM) are WalnutDSA and the Walnut Digital Signature Algorithm are trademarks
trademarks of Veridify Security Inc.. of Veridify Security Inc.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP "OPTIONAL" in this document are to be interpreted as described in
14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
3. WalnutDSA Algorithm Overview 3. WalnutDSA Algorithm Overview
This specification makes use of WalnutDSA signatures as described in This specification makes use of WalnutDSA signatures as described in
[WALNUTDSA] and more concretely specified in [WALNUTSPEC]. WalnutDSA [WALNUTDSA] and more concretely specified in [WALNUTSPEC]. WalnutDSA
is a Group-Theoretic cryptographic signature scheme that leverages is a Group Theoretic cryptographic signature scheme that leverages
infinite group theory as the basis of its security and maps that to a 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 one-way evaluation of a series of matrices over small finite fields
with permuted multiplicants based on the group input. WalnutDSA with permuted multiplicants based on the group input. WalnutDSA
leverages the SHA2-256 and SHA2-512 one-way hash algorithms [SHA2] in leverages the SHA2-256 and SHA2-512 one-way hash algorithms [SHA2] in
a hash-then-sign process. a hash-then-sign process.
WalnutDSA is based on a one-way function, E-Multiplication, which is WalnutDSA is based on a one-way function, E-multiplication, which is
an action on the infinite group. A single E-Multiplication step an action on the infinite group. A single E-multiplication step
takes as input a matrix and permutation, a generator in the group, 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 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 matrix and permutation. To process a long string of generators (like
a WalnutDSA signature), E-Multiplication is iterated over each a WalnutDSA signature), E-multiplication is iterated over each
generator. Due to its structure, E-Multiplication is extremely easy generator. Due to its structure, E-multiplication is extremely easy
to implement. to implement.
In addition to being quantum-resistant, the two main benefits of In addition to being quantum resistant, the two main benefits of
using WalnutDSA are that the verification implementation is very using WalnutDSA are that the verification implementation is very
small and WalnutDSA signature verification is extremely fast, even on small and WalnutDSA signature verification is extremely fast, even on
very small processors (including 16- and even 8-bit MCUs). This very small processors (including 16- and even 8-bit
lends it well to use in constrained and/or time-sensitive microcontrollers). This lends it well to use in constrained and/or
environments. time-sensitive environments.
WalnutDSA has several parameters required to process a signature. WalnutDSA has several parameters required to process a signature.
The main parameters are N and q. The parameter N defines the size of The main parameters are N and q. The parameter N defines the size of
the group by defining the number of strands in use, and implies the group by defining the number of strands in use and implies
working in an NxN matrix. The parameter q defines the number of working in an NxN matrix. The parameter q defines the number of
elements in the finite field. Signature verification also requires a elements in the finite field. Signature verification also requires a
set of T-values, which is an ordered list of N entries in the finite set of T-values, which is an ordered list of N entries in the finite
field F_q. field F_q.
A WalnutDSA signature is just a string of generators in the infinite A WalnutDSA signature is just a string of generators in the infinite
group, packed into a byte string. group, packed into a byte string.
4. WalnutDSA Algorithm Identifiers 4. WalnutDSA Algorithm Identifiers
The CBOR Object Signing and Encryption (COSE) [RFC8152] supports two The CBOR Object Signing and Encryption (COSE) syntax [RFC8152]
signature algorithm schemes. This specification makes use of the supports two signature algorithm schemes. This specification makes
signature with appendix scheme for WalnutDSA signatures. use of the signature with appendix scheme for WalnutDSA signatures.
The signature value is a large byte string. The byte string is The signature value is a large byte string. The byte string is
designed for easy parsing, and it includes a length (number of designed for easy parsing, and it includes a length (number of
generators) and type codes that indirectly provide all of the generators) and type codes that indirectly provide all of the
information that is needed to parse the byte string during signature information that is needed to parse the byte string during signature
validation. validation.
When using a COSE key for this algorithm, the following checks are When using a COSE key for this algorithm, the following checks are
made: made:
o The 'kty' field MUST be present, and it MUST be 'WalnutDSA'. * The "kty" field MUST be present, and it MUST be "WalnutDSA".
o If the 'alg' field is present, and it MUST be 'WalnutDSA'. * If the "alg" field is present, it MUST be "WalnutDSA".
o If the 'key_ops' field is present, it MUST include 'sign' when * If the "key_ops" field is present, it MUST include "sign" when
creating a WalnutDSA signature. creating a WalnutDSA signature.
o If the 'key_ops' field is present, it MUST include 'verify' when * If the "key_ops" field is present, it MUST include "verify" when
verifying a WalnutDSA signature. verifying a WalnutDSA signature.
o If the 'kid' field is present, it MAY be used to identify the * If the "kid" field is present, it MAY be used to identify the
WalnutDSA Key. WalnutDSA Key.
5. Security Considerations 5. Security Considerations
5.1. Implementation Security Considerations 5.1. Implementation Security Considerations
Implementations MUST protect the private keys. Use of a hardware Implementations MUST protect the private keys. Use of a hardware
security module (HSM) is one way to protect the private keys. security module (HSM) is one way to protect the private keys.
Compromise of the private keys may result in the ability to forge Compromising the private keys may result in the ability to forge
signatures. As a result, when a private key is stored on non- signatures. As a result, when a private key is stored on non-
volatile media or stored in a virtual machine environment, care must volatile media or stored in a virtual machine environment, care must
be taken to preserve confidentiality and integrity. be taken to preserve confidentiality and integrity.
The generation of private keys relies on random numbers. The use of The generation of private keys relies on random numbers. The use of
inadequate pseudo-random number generators (PRNGs) to generate these inadequate pseudorandom number generators (PRNGs) to generate these
values can result in little or no security. An attacker may find it values can result in little or no security. An attacker may find it
much easier to reproduce the PRNG environment that produced the keys, much easier to reproduce the PRNG environment that produced the keys,
searching the resulting small set of possibilities, rather than brute searching the resulting small set of possibilities, rather than brute
force searching the whole key space. The generation of quality force searching the whole key space. The generation of quality
random numbers is difficult, and [RFC4086] offers important guidance random numbers is difficult, and [RFC4086] offers important guidance
in this area. in this area.
The generation of WalnutDSA signatures also depends on random The generation of WalnutDSA signatures also depends on random
numbers. While the consequences of an inadequate pseudo-random numbers. While the consequences of an inadequate PRNG to generate
number generator (PRNG) to generate these values is much less severe these values are much less severe than the generation of private
than the generation of private keys, the guidance in [RFC4086] keys, the guidance in [RFC4086] remains important.
remains important.
5.2. Method Security Considerations 5.2. Method Security Considerations
The Walnut Digital Signature Algorithm has undergone significant The Walnut Digital Signature Algorithm has undergone significant
cryptanalysis since it was first introduced, and several weaknesses cryptanalysis since it was first introduced, and several weaknesses
were found in early versions of the method, resulting in the were found in early versions of the method, resulting in the
description of several attacks with exponential computational description of several attacks with exponential computational
complexity. A full writeup of all the analysis can be found in complexity. A full writeup of all the analysis can be found in
[WalnutDSAAnalysis]. In summary, the original suggested parameters [WalnutDSAAnalysis]. In summary, the original suggested parameters
(N=8, q=32) were too small, leading to many of these exponential- (N=8, q=32) were too small, leading to many of these exponential-
growth attacks being practical. However, current parameters render growth attacks being practical. However, current parameters render
these attacks impractical. The following paragraphs summarize the these attacks impractical. The following paragraphs summarize the
analysis and how the current parameters defeat all the previous analysis and how the current parameters defeat all the previous
attacks. attacks.
First, the team of Hart et al found a universal forgery attack based 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 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 memory complexity of log_2(q) N^2 q^((N-1)/2). With parameters N=10
and q=M31 (the Mersenne prime 2^31 - 1), the runtime is 2^139 and and q=M31 (the Mersenne prime 2^31 - 1), the runtime is 2^139 and
memory complexity is 2^151. W. Beullens found a modification of memory complexity is 2^151. W. Beullens found a modification of this
this attack but its runtime is even longer. attack but its runtime is even longer.
Next, Beullens and Blackburn found several issues with the original Next, Beullens and Blackburn found several issues with the original
method and parameters. First they used a Pollard-Rho attack and method and parameters. First, they used a Pollard-Rho attack and
discovered the original public key space was too small. Specifically discovered the original public key space was too small.
they require that q^(N(N-1)-1) > 2^(2*Security Level). One can Specifically, they require that q^(N(N-1)-1) > 2^(2*Security Level).
clearly see that N=10, q=M31 provides 128-bit security and N=10, One can clearly see that (N=10, q=M31) provides 128-bit security and
q=M61 provides 256-bit security. (N=10, q=M61) provides 256-bit security.
Beullens and Blackburn also found two issues with the original Beullens and Blackburn also found two issues with the original
message encoder of WalnutDSA. First, the original encoder was non- message encoder of WalnutDSA. First, the original encoder was non-
injective, which reduced the available signature space. This was injective, which reduced the available signature space. This was
repaired in an update. Second, they pointed out that the dimension repaired in an update. Second, they pointed out that the dimension
of the vector space generated by the encoder was too small. of the vector space generated by the encoder was too small.
Specifically, they require that q^dimension > 2^(2*Security Level). Specifically, they require that q^dimension > 2^(2*Security Level).
With N=10, the current encoder produces a dimension of 66 which With N=10, the current encoder produces a dimension of 66, which
clearly provides sufficient security with q=M31 or q=M61. clearly provides sufficient security with q=M31 or q=M61.
The final issue discovered by Beullens and Blackburn was a process to The final issue discovered by Beullens and Blackburn was a process to
theoretically "reverse" E-Multiplication. First, their process theoretically "reverse" E-multiplication. First, their process
requires knowing the initial matrix and permutation (which is known requires knowing the initial matrix and permutation (which are known
for WalnutDSA). But more importantly, their process runs at 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. 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 A team at Steven's Institute leveraged a length-shortening attack
that enabled them to remove the cloaking elements and then solve a that enabled them to remove the cloaking elements and then solve a
conjugacy search problem to derive the private keys. Their attack conjugacy search problem to derive the private keys. Their attack
requires both knowledge of the permutation being cloaked and also requires both knowledge of the permutation being cloaked and also
that the cloaking elements themselves are conjugates. By adding that the cloaking elements themselves are conjugates. By adding
additional concealed cloaking elements the attack requires an N! additional concealed cloaking elements, the attack requires an N!
search for each cloaking element. By inserting k concealed cloaking search for each cloaking element. By inserting k concealed cloaking
elements, this requires the attacker to perform (N!)^k work. This elements, this requires the attacker to perform (N!)^k work. This
allows k to be set to meet the desired security level. allows k to be set to meet the desired security level.
Finally, Merz and Petit discovered that using a Garside Normal Form Finally, Merz and Petit discovered that using a Garside Normal Form
of a WalnutDSA signature enabled them to find commonalities with the of a WalnutDSA signature enabled them to find commonalities with the
Garside Normal Form of the encoded message. Using those Garside Normal Form of the encoded message. Using those
commonalities they were able to splice into a signature and create commonalities, they were able to splice into a signature and create
forgeries. Increasing the number of cloaking elements, specifically forgeries. Increasing the number of cloaking elements, specifically
within the encoded message, sufficiently obscures the commonalities within the encoded message, sufficiently obscures the commonalities
and blocks this attack. and blocks this attack.
In summary, most of these attacks are exponential in run time and can In summary, most of these attacks are exponential in runtime and it
be shown that current parameters put the runtime beyond the desired can be shown that current parameters put the runtime beyond the
security level. The final two attacks are also sufficiently blocked desired security level. The final two attacks are also sufficiently
to the desired security level. blocked to the desired security level.
6. IANA Considerations 6. IANA Considerations
IANA is requested to add entries for WalnutDSA signatures in the IANA has added entries for WalnutDSA signatures in the "COSE
"COSE Algorithms" registry and WalnutDSA public keys in the "COSE Key Algorithms" registry and WalnutDSA public keys in the "COSE Key
Types" and "COSE Key Type Parameters" registries. Types" and "COSE Key Type Parameters" registries.
6.1. COSE Algorithms Registry Entry 6.1. COSE Algorithms Registry Entry
The new entry in the "COSE Algorithms" registry has the following The following new entry has been registered in the "COSE Algorithms"
columns: registry:
Name: WalnutDSA Name: WalnutDSA
Value: TBD1 (Value between -65536 to -257 or 256-65535 to be Value: -260
assigned by IANA)
Description: WalnutDSA signature Description: WalnutDSA signature
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
Recommended: No Recommended: No
6.2. COSE Key Types Registry Entry 6.2. COSE Key Types Registry Entry
The new entry in the "COSE Key Types" registry has the following The following new entry has been registered in the "COSE Key Types"
columns: registry:
Name: WalnutDSA Name: WalnutDSA
Value: TBD2 (Value to be assigned by IANA) Value: 6
Description: WalnutDSA public key Description: WalnutDSA public key
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
6.3. COSE Key Type Parameter Registry Entries 6.3. COSE Key Type Parameters Registry Entries
The following sections detail the additions to the "COSE Key Type The following sections detail the additions to the "COSE Key Type
Parameters" registry. Parameters" registry.
6.3.1. WalnutDSA Parameter: N 6.3.1. WalnutDSA Parameter: N
The new entry N in the "COSE Key Type Parameters" registry has the The new entry, N, has been registered in the "COSE Key Type
following columns: Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: N Name: N
Label: TBD (Value to be assigned by IANA) Label: -1
CBOR Type: uint CBOR Type: uint
Description: Group and Matrix (NxN) size Description: Group and Matrix (NxN) size
Reference: This document (Number to be assigned by RFC Editor)
Reference: RFC 9021
6.3.2. WalnutDSA Parameter: q 6.3.2. WalnutDSA Parameter: q
The new entry q in the "COSE Key Type Parameters" registry has the The new entry, q, has been registered in the "COSE Key Type
following columns: Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: q Name: q
Label: TBD (Value to be assigned by IANA) Label: -2
CBOR Type: uint CBOR Type: uint
Description: Finite field F_q Description: Finite field F_q
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
6.3.3. WalnutDSA Parameter: t-values 6.3.3. WalnutDSA Parameter: t-values
The new entry t-values in the "COSE Key Type Parameters" registry has The new entry, t-values, has been registered in the "COSE Key Type
the following columns: Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: t-values Name: t-values
Label: TBD (Value to be assigned by IANA) Label: -3
CBOR Type: array (of uint) CBOR Type: array (of uint)
Description: List of T-values, enties in F_q Description: List of T-values, entries in F_q
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
6.3.4. WalnutDSA Parameter: matrix 1 6.3.4. WalnutDSA Parameter: matrix 1
The new entry matrix 1 in the "COSE Key Type Parameters" registry has The new entry, matrix 1, has been registered in the "COSE Key Type
the following columns: Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: matrix 1 Name: matrix 1
Label: TBD (Value to be assigned by IANA) Label: -4
CBOR Type: array (of array of uint) CBOR Type: array (of array of uint)
Description: NxN Matrix of enties in F_q in column-major form
Reference: This document (Number to be assigned by RFC Editor) Description: NxN Matrix of entries in F_q in column-major form
Reference: RFC 9021
6.3.5. WalnutDSA Parameter: permutation 1 6.3.5. WalnutDSA Parameter: permutation 1
The new entry permutation 1 in the "COSE Key Type Parameters" The new entry, permutation 1, has been registered in the "COSE Key
registry has the following columns: Type Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: permutation 1 Name: permutation 1
Label: TBD (Value to be assigned by IANA) Label: -5
CBOR Type: array (of uint) CBOR Type: array (of uint)
Description: Permutation associated with matrix 1 Description: Permutation associated with matrix 1
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
6.3.6. WalnutDSA Parameter: matrix 2 6.3.6. WalnutDSA Parameter: matrix 2
The new entry matrix 2 in the "COSE Key Type Parameters" registry has The new entry, matrix 2, has been registered in the "COSE Key Type
the following columns: Parameters" registry as follows:
Key Type: TBD2 (Value assigned by IANA above) Key Type: 6
Name: matrix 2 Name: matrix 2
Label: TBD (Value to be assigned by IANA) Label: -6
CBOR Type: array (of array of uint) CBOR Type: array (of array of uint)
Description: NxN Matrix of enties in F_q in column-major form Description: NxN Matrix of entries in F_q in column-major form
Reference: This document (Number to be assigned by RFC Editor) Reference: RFC 9021
7. References 7. References
7.1. Normative References 7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)", [RFC8152] Schaad, J., "CBOR Object Signing and Encryption (COSE)",
RFC 8152, DOI 10.17487/RFC8152, July 2017, RFC 8152, DOI 10.17487/RFC8152, July 2017,
<https://www.rfc-editor.org/info/rfc8152>. <https://www.rfc-editor.org/info/rfc8152>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[SHA2] National Institute of Standards and Technology (NIST), [SHA2] National Institute of Standards and Technology (NIST),
"FIPS Publication 180-3: Secure Hash Standard", October "Secure Hash Standard (SHS)", DOI 10.6028/NIST.FIPS.180-4,
2008. August 2015, <https://doi.org/10.6028/NIST.FIPS.180-4>.
[WALNUTDSA] [WALNUTDSA]
Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
"WalnutDSA(TM): A group-theoretic digital signature "WalnutDSA(TM): A group theoretic digital signature
algorithm", November 2020, algorithm", DOI 10.1080/23799927.2020.1831613, November
<https://doi.org/10.1080/23799927.2020.1831613>. 2020, <https://doi.org/10.1080/23799927.2020.1831613>.
7.2. Informative References 7.2. Informative References
[BH2013] Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The [BH2013] Ptacek, T., Ritter, J., Samuel, J., and A. Stamos, "The
Factoring Dead: Preparing for the Cryptopocalypse", August Factoring Dead: Preparing for the Cryptopocalypse", August
2013, <https://media.blackhat.com/us-13/us-13-Stamos-The- 2013, <https://www.slideshare.net/astamos/bh-slides>.
Factoring-Dead.pdf>.
[GTC] Vasco, M. and R. Steinwandt, "Group Theoretic [GTC] Vasco, M. and R. Steinwandt, "Group Theoretic
Cryptography", April 2015, <https://www.crcpress.com/ Cryptography", ISBN 9781584888369, April 2015,
Group-Theoretic-Cryptography/Vasco-Steinwandt/p/ <https://www.crcpress.com/Group-Theoretic-Cryptography/
book/9781584888369>. Vasco-Steinwandt/p/book/9781584888369>.
[NAS2019] National Academies of Sciences, Engineering, and Medicine, [NAS2019] National Academies of Sciences, Engineering, and Medicine,
"Quantum Computing: Progress and Prospects", 2019, "Quantum Computing: Progress and Prospects",
<http://dx.doi.org/10.17226/25196>. DOI 10.17226/25196, 2019,
<https://doi.org/10.17226/25196>.
[PQC] Bernstein, D., "Introduction to post-quantum [PQC] Bernstein, D., "Introduction to post-quantum
cryptography", 2009, cryptography", DOI 10.1007/978-3-540-88702-7, 2009,
<http://www.pqcrypto.org/www.springer.com/cda/content/ <https://doi.org/10.1007/978-3-540-88702-7>.
document/cda_downloaddocument/9783540887010-c1.pdf>.
[RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker,
"Randomness Requirements for Security", BCP 106, RFC 4086, "Randomness Requirements for Security", BCP 106, RFC 4086,
DOI 10.17487/RFC4086, June 2005, DOI 10.17487/RFC4086, June 2005,
<https://www.rfc-editor.org/info/rfc4086>. <https://www.rfc-editor.org/info/rfc4086>.
[WalnutDSAAnalysis] [WalnutDSAAnalysis]
Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
"Defeating the Hart et al, Beullens-Blackburn, Kotov- "Defeating the Hart et al, Beullens-Blackburn, Kotov-
Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)", Menshov-Ushakov, and Merz-Petit Attacks on WalnutDSA(TM)",
May 2019, <https://eprint.iacr.org/2019/472>. May 2019, <https://eprint.iacr.org/2019/472>.
[WALNUTSPEC] [WALNUTSPEC]
Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells, Anshel, I., Atkins, D., Goldfeld, D., and P. Gunnells,
"The Walnut Digital Signature Algorithm Specification", "The Walnut Digital Signature Algorithm Specification",
November 2018, <https://csrc.nist.gov/projects/post- Post-Quantum Cryptography, November 2018,
quantum-cryptography/round-1-submissions>. <https://csrc.nist.gov/projects/post-quantum-cryptography/
round-1-submissions>.
Appendix A. Acknowledgments Acknowledgments
A big thank you to Russ Housley for his input on the concepts and A big thank you to Russ Housley for his input on the concepts and
text of this document. text of this document.
Author's Address Author's Address
Derek Atkins Derek Atkins
Veridify Security Veridify Security
100 Beard Sawmill Rd, Suite 350 100 Beard Sawmill Rd, Suite 350
Shelton, CT 06484 Shelton, CT 06484
US United States of America
Phone: +1 617 623 3745 Phone: +1 617 623 3745
Email: datkins@veridify.com Email: datkins@veridify.com
 End of changes. 106 change blocks. 
199 lines changed or deleted 196 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/