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

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 <X> until <Y> 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 <Y>
to use in "please wait to publish <X> until <Y> is published".

I do note that "please wait to publish <X> until <Y> 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 <X> 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 <X>, 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.