IETF conflict review for draft-atkins-suit-cose-walnutdsa
conflict-review-atkins-suit-cose-walnutdsa-01

The following approval message was sent
From: The IESG
To: Adrian Farrel ,
    draft-atkins-suit-cose-walnutdsa@ietf.org,
    rfc-ise@rfc-editor.org
Cc: IETF-Announce ,
    The IESG ,
    iana@iana.org
Subject: Results of IETF-conflict review for draft-atkins-suit-cose-walnutdsa-07

The IESG has completed a review of draft-atkins-suit-cose-walnutdsa-07
consistent with RFC5742.

The IESG has no problem with the publication of 'Use of the Walnut Digital
Signature Algorithm with CBOR Object Signing and Encryption (COSE)'
as an Informational RFC.

The IESG has concluded that this work is related to IETF work done in WG
COSE, but this relationship does not prevent publishing.

Additionally, the IESG requests the following note be added to the document
if it is published:

This document proposes a cryptographic signature algorithm that is claimed to
be "post-quantum secure". The IETF takes no position on these claims.
Development of such algorithms is an active topic of great interest to the
Internet community, but the IETF has chosen to defer selection and
publication of "post-quantum secure" algorithms until after the conclusion of
the NIST "Post-Quantum Cryptography" Project
(https://csrc.nist.gov/projects/post-quantum-cryptography). The
NIST-sponsored endeavor (whose participants include cryptographic experts
from around the world) provides substantially more cryptographic expertise
than is available solely within the IETF, and the IESG believes it is in the
best interest of the Internet community to take advantage of the in-depth
cryptographic reviews performed during the NIST project before selecting
"post-quantum secure" algorithms for standardization.

The IESG would also like the Independent Submissions Editor to review the
comments in the datatracker related to this document and determine whether or
not they merit incorporation into the document. Comments may exist in both
the ballot and the history log.

The IESG review is documented at:
https://datatracker.ietf.org/doc/conflict-review-atkins-suit-cose-walnutdsa/

A URL of the reviewed Internet Draft is:
https://datatracker.ietf.org/doc/draft-atkins-suit-cose-walnutdsa/

The process for such documents is described at
https://www.rfc-editor.org/indsubs.html

Thank you,

The IESG Secretary

[Ballot comment]
Thanks for incorporating my DISCUSS feedback into note. 

----

I concur with the conflict review conclusion.

For the IESG
==========
As background for the IESG, the NIST Post-Quantum Cryptography initiative is an iterative, multi-round (multi-year) selection process for algorithms:

Round 3 = https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions

Round 2 = https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

Round 1 = https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

WalnutDSA was part of only Round 1 (no judgement implied)

A similar process was used to select what we currently know as AES and SHA2.

[Ballot discuss]
As noted below, I agree with the conflict review conclusion.  Let's discuss on whether we should make a slightly stronger IESG note:

OLD
This document proposes a cryptographic signature algorithm that is claimed to be "post-quantum secure". Development of such algorithms is an active topic ...,

NEW
This document proposes a cryptographic signature algorithm that is claimed to be "post-quantum secure". The IETF takes no position on these claims.  Development of such algorithms is an active topic ...

[Ballot comment]
I concur with the conflict review conclusion.

For the IESG
==========
As background for the IESG, the NIST Post-Quantum Cryptography initiative is an iterative, multi-round (multi-year) selection process for algorithms:

Round 3 = https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions

Round 2 = https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

Round 1 = https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

WalnutDSA was part of only Round 1 (no judgement implied)

A similar process was used to select what we currently know as AES and SHA2.

[Ballot comment]
To the IESG
===========
The -05 has text requesting a codepoint allocation from a "Standards
Action" range, but the authors and ISE have confirmed that this was a
copy/paste issue from a different draft and will be addressed prior to
publication.

There is also a bit of related work in flight whereby
draft-ietf-cose-rfc8152bis-algs is introducing "COSE Capabilities" (see
Section 4 comments) that would need to be defined for the key type and
algorithm specified by this document.  However, my opinion is that the
"capabilities" concept is not fundamentally changing the operation of
COSE, and thus that defining capabilities for WalnutDSA could be done in
a separate document after -algs is published; as such, it does not seem
to merit a "please wait to publish  until  is published" type
response.  (That said, I still encourage the authors to specify what the
capabilities should be at this time, instead of waiting.)

More worrisome is that this document claims to provide a "post-quantum
secure" algorithm at a time when the IETF consensus is to wait for the
outcome of the NIST contest before specifying post-quantum algorithms.
In some sense this constitutes a case where publication is harmful, akin
to the example in Section 5 of RFC 5742, whereby the "rejected
alternative" gets published before the WG solution.  However, there is
not currently a WG solution under consideration, and thus no clear
to use in "please wait to publish  until  is published".

I do note that "please wait to publish  until  is published" is
not one of the enumerated classes of response in RFC 5742, rather, we
would be expected to use:

  3. The IESG has concluded that publication could potentially disrupt
      the IETF work done in WG  and recommends not publishing the
      document at this time.

to achieve such an effect.  However, the COSE Algorithms registry does
have a separation of codepoint ranges into the "anyone can get one" and
"IETF approved" (paraphrasing) ranges, so my expectation is that the
codepoint range would be more useful to an implementor/user looking at
what algorithm to use than the "lower RFC number" metric.  As such, I
don't have a clear justification for how publication would "disrupt IETF
work in the COSE WG".  My proposal is therefore to use the "type 2"
response:

  2. The IESG has concluded that this work is related to IETF work done
      in WG , but this relationship does not prevent publishing.

with an IESG Note indicating that the IETF is waiting for external
events (NIST) before undertaking work on post-quantum secure algorithms.

To the Authors/IESG
===================

Please find below some review comments on the draft, based on notes I
made while reviewing the document.

Abstract

What are "constrained16807 environments"?

Section 1

  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.

(There is an 8152bis effort underway to get Internet Standard status
that even made it as far as IESG evaluation, but got pulled back because
a flaw in how countersignatures are specified.  There probably is not a
reason to sequence publication of this document after those documents,
though.)

  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;

I'm not sure if this statement is intended to place WalnutDSA as
belonging to the category of "hash-based signatures".  (I would argue
that it does not; the hash seems to just be used to digest the message
to a form smaller than the native input size for the "main" algorithm.)

  algorithm.  The goal of thie specification is to document a method to

nit: s/thie/the/ or s/thie/this/ (probably the latter)

Section 1.1

  Recent advances in cryptanalysis [BH2013] and progress in the

(Does 2013 still count as "recent"?)

  deployed digital signature algorithms.  As a result, there is a need
  to prepare for a day that cryptosystems such as RSA and DSA that
  depend on discrete logarithm and factoring cannot be depended upon.

nit(?): maybe "the discrete logarithm problem or factorization"?
(Also when it appears later on.)

I also note that draft-hoffman-c2pq is adopted in the CFRG and attempts
to go into a fair bit more detail on "the need to prepare", so might be
worth considering a reference to.

Section 3

Some disambiguation about "the infinite group" and "N defines the size
of the group" might be in order (but it's not material to the actual
content of the draft, so it might not, too).

  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

nit(?): the "in" in the parenthetical feels weird to me.  It's just
clarifying that "defines the size of the field" is "the size is the
value of the parameter" (vs. some more complicated function), right?  So
maybe "The parameter q specifies the number of elements in the finite
field" directly?

Section 4

draft-ietf-cose-rfc8152bis-algs (part of the 8152bis effort mentioned
previously, now in the RFC Editor queue) introduces the concept of "COSE
Capabilities".  It may be worth investigating now what capabilities (if
any) would be specified for these key types to avoid the need for a
follow-up specification.

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

This is not quite true -- recall that "[t]here may be more than one key
with the same 'kid' value", and as such 'kid' cannot (in general) serve
as a unique key identifier.

Section 5.1

(I note that RFC 4086 is BCP 106.)

Section 5.2

  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

nit(?): my understanding is that "exponential attack" is not a term of
art, so an alternate phrasing like "attacks of exponential computational
complexity" might be appropriate.  (Also occurs later.)

  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

I would suggest calling out the original proposed parameter sets (e.g.,
N=8, q=32 IIUC?) to contrast against the modifications needed to achieve
the desired security level as a result of the security reviews.

  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.

If you're going to use the "M31" (and "M61", later) notation, it's
probably worth mentioning the phrase "Mersenne number" somehow.

  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 new q of M31 or M61 is also required; q=32, N=10 wouldn't cut it.)

  Finally, Merz and Petit discovered that using a Garside Normal Form
  of a WalnutDSA signature enabled them to find commonalities with the
  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.

The previous paragraphs had numerical formulae that even a
non-cryptographer can verify are satisfied; is there not such a formula
for the ability of cloaking elements to obscure commonalities between
message and signature that could be listed?

  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.

Earlier we implied that *all* (not just "most of") the attacks were
exponential.  The formulae I see are exponential, which seems to just
leve the Garside Normal Form/commonalities forgery attack as potentially
non-exponential.  Is it, or is it not exponential?

Section 6.3

In IETF protocols we have been seeing a recent trend to, essentially,
have only "one joint" for describing how the protocol/algorithm varies,
as opposed to a cornucopia of parameters that allows for the user to
produce unsafe configurations (among other things).  Having fewer
parameters to encode also produces a shorter encoding, of course.  Given
that the rest of the recent literature has been showing parameters with
N=1 and either q=M31 or q=M1, perhaps some reduction in the number of
key parameters could be considered.

Section 6.3.4, 6.3.6

Are the matrices encoded in row-major or column-major form?

Also, given that [WALNUTDSA] just talks about a public key being "two
matrix and permutation pairs", it's not clear how much value we get from
splitting them into separate key parameters and labeling them "one" and
"two".

Also^2, doesn't that imply that we need a "permutation 2" key parameter?

Section 7.2

I feel like at least one of [WALNUTDSA] and [WALNUTSPEC] should be
classified as normative, as you will need to read those quite carefully
in order to actually generate a COSE signature for this key/algorithm
type.