Subject: Re: [COSE] draft-ietf-lwig-curve-representations-13

From: Rene Struik <[email-masked]>
Date: Wed, 13 Jan 2021 09:26:15 -0500

Hi Goran, John:

Please let me know if my response to the COSE mailing list (Dec 19th) 
works for you. If you have comments, please suggest constructive 
improvements.

I really would like to get closure on this.

I value your feedback, even though you brought up your points more than 
two months after the IETF Last-Call. I hope we can move forward without 
undue delays.

Thanks for your help, Rene

On 2020-12-19 11:01 a.m., Rene Struik wrote:
>
> Dear John:
>
> Based on your review and other feedback received, I slightly updated 
> the draft and posted the latest revision as [1].
>
> Your review below (of Nov 6, 2020) seems to bring up three topics, 
> viz.: (1) definition of Wei25519 and Wei448 vs. verbiage in NIST docs; 
> (2) need for iana registrations for ECDSA25519 and ECDSA448; (3) need 
> for iana registrations ECDH25519 and ECDH448.
>
> Please find below some feedback.
>
> General feedback:
>
> Please bear in mind that the specifications of ECDSA25519 and 
> ECDH25519 in the lwig curve document aim to yield schemes that are 
> strictly NIST-compliant (i.e., these would allow FIPS 140-2 
> accreditation if the curves would be in the "NIST recommended" set). 
> See also Note 2 of Section 4.1 of [1]. A similar remark applies to 
> ECDSA448 and ECDH448.
>
> Detailed feedback:
>
> (1) Definition of Wei25519 and Wei448 vs. verbiage in NIST docs.
>
> Draft NIST SP 800-186 indeed defines a short-Weierstrass version of 
> Curve25519 [dubbed W-25519] and FIPS 186-5 allows its use; similar for 
> Curve448 [dubbed W-448 there]). I have now added references to these 
> draft specifications in the lwig-curve draft. I have double-checked 
> all domain parameters, mappings between curve models, tables of 
> isogeny details in the lwig draft and provided Sage scripts for the 
> CFRG crypto panel review at the time. I do anticipate that NIST will 
> arrive at the same values in their final publication when they decide 
> to publish this. (I am happy to share Sage scripts for this purpose.)
>
> (2) Need for iana registrations for ECDSA25519 and ECDSA448.
>
> ECDSA is determined by an instantiation of hash function, curves, and 
> representation conventions for inputs and outputs (i.e., message 
> representation, curve point representation, and signature 
> representation).
> a) ECDSA448 uses SHAKE256 under the hood, which is currently not 
> defined with COSE. Hence, my request to register ECDSA w/ SHAKE256 and 
> Wei448 as "ECDSA448".
> b) ECSA25519 uses SHA256 and Wei25519 under the hood. I thought to 
> request to register "ECDSA25519" since this would allow referencing 
> the quite careful write-up (Section 4.3), including bit/byte ordering, 
> checks, and nondeterministic behavior (and, thereby, keeping this 
> concise). Please note that this is very similar to the COSE IANA 
> registry for "ES256k1" (ECDSA w/ SHA256 and Bitcoin curve secp256k1).
>
> (3) Need for iana registrations ECDH25519 and ECDH448.
>
> ECDH25519 and ECDH448 are co-factor Diffie-Hellman key establishment 
> schemes and can, therefore, not be based on (cofactorless) 
> Diffie-Hellman, as defined in RFC 8152. (Please note that there is no 
> difference for the NIST curves, which all of co-factor h=1, but in our 
> case one has h=8 and h=4, respectively). Here, one should note that 
> the ECDH25519 and ECDH448 write-ups (Section 4.1 and 4.3) quite 
> carefully cross-reference co-factor ECDH in a NIST-compliant way. 
> Apart from the co-factor ECDH vs. ECDH issue and objective to comply 
> with all strict NIST validation checks, the objective was also to make 
> sure that ECDH25519 and ECDH448 can be used in settings where either 
> or both parties uses ephemeral keys (which is more flexible than what 
> RFC 8152 allows).  Hence, the request to register "ECDH25519" and 
> "ECDH448", to make sure this covers the intent of these schemes 
> accurately and with precise description.
>
> It is possible that I overlooked something in this assessment. If so, 
> any constructive suggestions are welcome.
>
> Ref: [1] 
> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-19
>
> Best regards, Rene
>
> On 2020-11-06 5:04 p.m., John Mattsson wrote:
>>
>> Hi,
>>
>> I looked through this draft again. I think it is a very good draft 
>> and I think it will be a solution to some of the problems IoT devices 
>> have with Ed25519. I will bring up this draft for discussion in the 
>> LAKE WG at IETF 109.
>>
>> I find it strange that the IANA registration has not been coordinated 
>> with COSE WG at all. I am a bit surprised to see IANA registrations 
>> for COSE/JOSE/PKIX/CMS at all in a LWIG draft (is that in charter?). 
>> If LWIG wants to register new algorithms, I think LWIG at a minimum 
>> should coordinate with COSE WG and other groups. I think this draft 
>> should be presented at the next COSE WG meeting.
>>
>> I support registration of W-25519 and W-448 curves as long they agree 
>> with NIST. I would like answers to the questions why ECDSA25519 and 
>> ECDH25519 are needed at all. There is no ECDSAP256 and no ECDHP256, 
>> so why are specific algorithm registration needed for W-25519?  It 
>> makes no sense to me that a special signature registration is needed 
>> for COSE but not for PKIX? If PKIX can use ecdsa-with-SHA256 why 
>> cannot COSE use ES256?
>>
>> I don't think ANSI X9.62 is an acceptable normative reference. NIST 
>> just removed the normative reference to ANSI X9.62 in SP 186-5.
>>
>> Cheers,
>>
>> John
>>
>> *From: *COSE <[email-masked]> on behalf of Rene Struik 
>> <[email-masked]>
>> *Date: *Friday, 6 November 2020 at 20:37
>> *To: *Göran Selander <goran.selander=[email-masked]>, 
>> "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
>> *Subject: *Re: [COSE] draft-ietf-lwig-curve-representations-13
>>
>> Hi Goran:
>>
>> Please find below some brief feedback on your note:
>>
>> - the naming wei25519 has been around since the first draft (Nov 13, 
>> 2017, i.e., 3 years minus 1 week ago), see [1]. NIST indeed produced 
>> two draft documents, viz. Draft NIST SP 800-186 and Draft FIPS Pub 
>> 186-5 (on October 31, 2019), which generated lots of (to my knowledge 
>> still unresolved) comments during public review. It is hard to refer 
>> to that document, since it is only a draft and unfortunately has 
>> quite a few errors.
>>
>> - earlier versions of the lwig draft have received reviews by the 
>> crypto review panel (Stanislavslav Smyshlyaev), iotdir early-review 
>> (Daniel Migault); the sections on COSE/JOSE code point assignments 
>> resulted from a phone call and various email exchanges with Jim 
>> Schaad; the section on PKIX/CMS was suggested during IETF Last-Call 
>> secdir-review (Russ Housley) and reviewed by him. The document had 
>> IETF Last-Call Aug 24, 2020. See, e.g., the status pages [1].
>>
>> - ECDSA has been around since 1999, has been widely standardized, and 
>> has seen lots of analysis, where ECDSA25519 is simply yet another 
>> instantiation. Signature generation and verification times for 
>> ECDSA25519 should be similar to those of Ed25519 (since timing is 
>> dominated by scalar multiplication, where one could simply use 
>> Montgomery arithmetic [3]). In my personal view, ECDSA25519 may be 
>> more secure than Ed25519 (if only because it is non-deterministic, 
>> see Security section [6]); similar side-channel care has to be taken 
>> in either case.
>>
>>  - As mentioned in the draft, one can easily switch between Wei25519 
>> and Curve25519 (which requires a single field addition or subtraction 
>> only, i.e., <.01%, see Appendix E.2 [7]). As mentioned in the draft, 
>> one could use Wei25519.-3 with an existing generic implementation 
>> that hardcodes the domain parameter a=-3, but needs to compute an 
>> isogeny and dual isogeny for this (adding 5-10% cost, see Appendix 
>> G.2 [8]]) and a ~9.5kB table (see Section 5.3 [4]). However, if one 
>> already has generic hardware support, one may still have a 
>> significant win (see Section 6 [5]).
>>
>> - The isogeny for Wei25519.-3 has odd degree l=47, which is co-prime 
>> with the order of the curve, so is in fact invertible. With 
>> Wei448.-3, the isogeny has degree l=2, so is not invertible; however, 
>> this does not really matter, since it is invertible with correctly 
>> generated public-private key pairs (which have prime/odd order) and 
>> the factor two is absorbed with co-factor ECDH, where h=4 then.
>>
>> I hope this helps.
>>
>> (*) For ease of tracking, it would help if iana related comments are 
>> flagged in the subject line (e.g., include (iana) in the beginning 
>> hereof).
>>
>> Best regards, Rene
>>
>> Ref with hyperlinks:
>>
>> [1] 
>> https://datatracker.ietf.org/doc/html/draft-struik-lwig-curve-representations-00 
>> <https://datatracker.ietf.org/doc/html/draft-struik-lwig-curve-representations-00>
>>
>> [2] 
>> https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ 
>> <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/>
>>
>> [3] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-4.3 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-4.3>
>>
>> [4] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-5.3 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-5.3>
>>
>> [5] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-6 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-6>
>>
>> [6] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-8 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#section-8>
>>
>> [7] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-E.2 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-E.2>
>>
>> [8] 
>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-G.2 
>> <https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-13#appendix-G.2>
>>
>> On 2020-11-06 11:19 a.m., Göran Selander wrote:
>>
>>     Hi,
>>
>>     Apologies for cross-posting LWIG and COSE. I had a brief look at
>>     draft-ietf-lwig-curve-representations-13 and noticed it registers
>>     a lot of new COSE(andJOSE, PKIX, and CMS)algorithms. Has this
>>     draft been discussed in COSE(JOSE/CURDLE)? If not, perhaps it
>>     should be before being progressed?
>>
>>     1.The draft needs to manage the overlap with NIST SP 800-186,
>>     which should be referenced and mappings, name of curves, etc.
>>     aligned. The draft defines Wei25519 and Wei448. It is unclear if
>>     these are identical to W-25519, W-448 as defined in NIST SP
>>     800-186. We probably would not want two slightly different
>>     definitions and/or names, multiple COSE code points, etc.
>>
>>     1.The draft registers the COSE algorithm "ECDSA25519" as "ECDSA
>>     with SHA-256 and curve Wei25519". That is not how the other COSE
>>     signature algorithms work. They work like PKIX where the curve is
>>     given by the public key. Also, why cannot W-25519 be used with
>>     the existing ES256 signature algorithm?
>>
>>     2.The draft registers the COSE algorithm "ECDH25519". There are
>>     no COSE ECDH algorithms for P-256, why is anECDH algorithm for
>>     W-25519 be needed?
>>
>>     Other questions. I may have missed it, but
>>
>>     2.is it described what are the expected security properties of
>>     ECDSA25519(including mapping) compared to Ed25519? For example
>>     w.r.t. side channel attacks?
>>
>>     3.has any performance measurements been made comparing ECDSA25519
>>     (including mapping) and Ed25519?
>>
>>     4.similar questions on security and performance with Wei25519.-3
>>     instead of Wei25519. If I understand right, the former mapping is
>>     not reversible, but could benefit from optimized code with
>>     hardcoded domain parameters.
>>
>>     5.ANSI X9.62-2005 was withdrawn in 2015 and is behind a paywall,
>>     is this reference necessary?
>>
>>     Göran
>>
>>
>>
>>     _______________________________________________
>>
>>     COSE mailing list
>>
>>     [email-masked]  <mailto:[email-masked]>
>>
>>     https://www.ietf.org/mailman/listinfo/cose  <https://www.ietf.org/mailman/listinfo/cose>
>>
>> -- 
>> email:[email-masked]  <mailto:[email-masked]>  | Skype: rstruik
>> cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
>>
>> -->
>>
>
> -- 
> email:[email-masked]  | Skype: rstruik
> cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 14 Jan 2021 15:12:10 +0200

On Wed, Jan 13, 2021 at 09:26:15AM -0500, Rene Struik wrote:
> Hi Goran, John:
> 
> Please let me know if my response to the COSE mailing list (Dec 19th) works
> for you. If you have comments, please suggest constructive improvements.
> 
> I value your feedback, even though you brought up your points more than two
> months after the IETF Last-Call. I hope we can move forward without undue
> delays.
> 
> > Based on your review and other feedback received, I slightly updated the
> > draft and posted the latest revision as [1].
> > 
> > Your review below (of Nov 6, 2020) seems to bring up three topics, viz.:
> > (1) definition of Wei25519 and Wei448 vs. verbiage in NIST docs; (2)
> > need for iana registrations for ECDSA25519 and ECDSA448; (3) need for
> > iana registrations ECDH25519 and ECDH448.
> > 
> > Please bear in mind that the specifications of ECDSA25519 and ECDH25519
> > in the lwig curve document aim to yield schemes that are strictly
> > NIST-compliant (i.e., these would allow FIPS 140-2 accreditation if the
> > curves would be in the "NIST recommended" set). See also Note 2 of
> > Section 4.1 of [1]. A similar remark applies to ECDSA448 and ECDH448.

I think the spec should call out the odd way hash truncation in ECDSA
works with these curves, as it is unlikely implementations have
encountered that kind of special case before.

As far as I understand (z is the integer value representing the message
in both signing and verification... I have not actually tested these, so
there might be bugs):

1) Wei25519:

C = 31;
if len(hash) > C:
  z = int.from_bytes(hash[:C],byteorder="big");
  y = hash[C];
  if is_sha2(hashfunc):
    z += y // 8 << 8*C;
  elif is_sha3_or_shake(hashfunc):
    z += y % 32 << 8*C;
  else:
    raise ValueError("Unsupported hash");
else:
    z = int.from_bytes(hash,byteorder="big");

2) Wei448:

C = 55;
if len(hash) > C:
  z = int.from_bytes(hash[:C],byteorder="big");
  y = hash[C];
  if is_sha2(hashfunc):
    z += y // 4 << 8*C;
  elif is_sha3_or_shake(hashfunc):
    z += y % 64 << 8*C;
  else:
    raise ValueError("Unsupported hash");
else:
    z = int.from_bytes(hash,byteorder="big");

Where is_sha2 and is_sha3_or_shake are predicates for the hash function
that check if the hash function used is one from SHA-2 or from
SHA-3/SHAKE respectively. The dependence on these predicates cause major
issues with traditional signhash-style ECDSA implementations.

If the above is wrong (beyond just bugs or typos), it would be
especially necressary to write how the case is handled, as even trying
to carefully work out how it works leads to wrong result.

(For comparision, here is what truncation looks for P-256:

if len(hash) > 32: hash = hash[:32];
z = int.from_bytes(hash,byteorder="big");

There is no reference to hash function used.
)

> > a) ECDSA448 uses SHAKE256 under the hood, which is currently not defined
> > with COSE. Hence, my request to register ECDSA w/ SHAKE256 and Wei448 as
> > "ECDSA448".
> > request to register "ECDSA25519" since this would allow referencing the
> > quite careful write-up (Section 4.3), including bit/byte ordering,

This is not how ECDSA is usually used (and this goes to a lot of other
things besides COSE and JOSE, e.g. to TLSv1.2 and PKIX). Usually in ECDSA,
the algorithm determines the hash function, and key determines the curve.
This would presumably still hold if doing agility-by-key (not that either
COSE nor JOSE have the necressary means for that). 

IMO, ES256k1 was a mistake. That should have had alg ES256 and 
crv secp256k1.

(TLSv1.3 mixes hash and curve, but seemingly only to simplify
negotiation, which is not applicable here, since COSE/JOSE are not
interactive. Many implementations probably do not check that the curve
is correct. Mine certainly does not.)

> > case one has h=8 and h=4, respectively). Here, one should note that the
> > ECDH25519 and ECDH448 write-ups (Section 4.1 and 4.3) quite carefully
> > cross-reference co-factor ECDH in a NIST-compliant way. Apart from the
> > co-factor ECDH vs. ECDH issue and objective to comply with all strict
> > NIST validation checks, the objective was also to make sure that
> > ECDH25519 and ECDH448 can be used in settings where either or both
> > parties uses ephemeral keys (which is more flexible than what RFC 8152
> > allows).  Hence, the request to register "ECDH25519" and "ECDH448", to
> > make sure this covers the intent of these schemes accurately and with
> > precise description.

COSE does not just have ECDH, it has many different variants of ECDH.
It would probably be easier to define cofactor ECDH by performing the
cofactor multiplication (which seems to be the only difference between
cofactor and non-cofactor ECDH) in output shared secret conversion.
Otherwise one would need at least 8 new algorithms (SS/ES times KW/KDF
times 128/256).

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Thu, 14 Jan 2021 09:29:24 -0500

Hi Ilari:

I do not understand your posting, which is full of hearsay and 
ill-defined terms, such as "odd way", "usually", "have not tested this" 
(which are subjective terms). Can we please stick to facts?

ECDSA has been introduced in 1999 [1]. The specification of ECDSA25519 
[2] and that of ECDSA448 [3] uses the description in FIPS Pub 186-4, 
which is unambiguous.

If you nevertheless believe there are ambiguities in the specification, 
please point those out succinctly and in a technical matter, with 
detailed reference to the alleged substep where this "mishap" occurs.

Best regards, Rene

Ref:
[1] Don Johnson, Alfred Menezes, "The Elliptic Curve Digital Signature 
Algorithm (ECDSA)", CACR Corr 99-34.
[2] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-19#section-4.3 

[3] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-19#section-4.4