Subject: [COSE] (request for presentation slot) Re: (question) Re: IETF 112 Call for Agenda Items

From: Rene Struik <[email-masked]>
Date: Fri, 5 Nov 2021 14:01:51 -0400

Dear Ivaylo:

I would like to ask for a presentation slot for the COSE/JOSE meeting 
Wednesday next week.

    Title: code points for fast-verification friendly ECDSA
    Presenter: Rene Struik

For context, please see my email of Tue Nov 2, 2021 below.

Best regards, Rene

On 2021-11-02 12:36 p.m., Rene Struik wrote:
> Dear Ivaylo:
>
> I presented a mechanism for putting ECDSA signatures into a format 
> that facilitates verification speed-ups, both in single-verify and 
> batch verification settings [1]. While this technique (known for more 
> than 1 1/2 decades) is generally applicable, I believe this would be 
> especially useful to implement with JOSE and perhaps COSE right now, 
> given Covid-vaccination records using ES256 in the smart healthcard 
> specifications [3] (proposed with IATA, etc.). For the main idea, see 
> [1]. For a JSON Web signature example, see [2].
>
> Do you think I could briefly present? I would like to ask for a code 
> point for JOSE and others down the road.
>
> I think I could simply present the example of [2] and some applications.
>
> Best regards, Rene
>
> ref: [1] 
> https://datatracker.ietf.org/doc/html/draft-struik-secdispatch-verify-friendly-ecdsa-00#section-9.3
> [2]https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.3.4 
>
> [3]https://smarthealth.cards/
>
> On 2021-10-31 10:06 a.m., Ivaylo Petrov wrote:
>> Hello all,
>>
>> This is a call for agenda items for our session at IETF 112. Please
>> send them to the chairs and/or this list.
>>
>> We have a slot for Wednesday, November 10, 2021 Session II 
>> (14:30-15:30 UTC).
>>
>> Thank you,
>>
>> -- 
>> COSE WG Chairs
>> Matthew, Mike and Ivaylo
>>
>> _______________________________________________
>> COSE mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/cose
>
>

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

---

From: Ivaylo Petrov <[email-masked]>
Date: Sat, 6 Nov 2021 23:13:18 +0100

Hello Rene,

Thank you for your email! It was brought to my attention that during IETF
111 secdispatch (
https://datatracker.ietf.org/meeting/111/materials/minutes-111-secdispatch-00)
it was decided no code points to be assigned before the CFRG reviews the
document. Could you clarify if that has already concluded and if not, what
will be the purpose of the presentation?

Thanks,
Ivaylo

*Ivaylo Petrov*

CONFIDENTIALITY NOTICE: This email may contain confidential and privileged
material for the sole use of the intended recipient(s).

It is strictly forbidden to share any part of this message with any third
party, without the written consent of the sender.

If you have received this message by mistake, please notify the sender
immediately by email and delete the message and any file attached to it.
Thank you!

On Fri, Nov 5, 2021 at 7:03 PM Rene Struik <[email-masked]> wrote:

> I presented a mechanism for putting ECDSA signatures into a format that
> facilitates verification speed-ups, both in single-verify and batch
> verification settings [1]. While this technique (known for more than 1 1/2
> decades) is generally applicable, I believe this would be especially useful
> to implement with JOSE and perhaps COSE right now, given Covid-vaccination
> records using ES256 in the smart healthcard specifications [3] (proposed
> with IATA, etc.). For the main idea, see [1]. For a JSON Web signature
> example, see [2].
>
> Do you think I could briefly present? I would like to ask for a code point
> for JOSE and others down the road.
>
> [2]
> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.3.4
> We have a slot for Wednesday, November 10, 2021 Session II (14:30-15:30
> UTC).
>
> Thank you,
>
> --
> COSE WG Chairs
> Matthew, Mike and Ivaylo
>
> email: [email-masked] | Skype: rstruik

---

From: Rene Struik <[email-masked]>
Date: Sun, 7 Nov 2021 10:38:22 -0500

Hi Ivaylo:

I do not understand what the role of the CFRG is with this: should they 
confirm that if (r,s) is a valid ECDSA signature for message m with 
signing key Q, then so is (r,-s)? Or, is there more to this?

FYI - the ECDSA signing equation is e:=h(m)=s*k-d*r (mod n), where 
r:=x(R) (mod n), R:=k*G, Q:=d*G, so r=x(R)=x(-R) and e=s*k-d*r (mod n) = 
(-s)*(-k) - d*r (mod n). QED.

Is the idea to have this one-line verification being blessed by someone 
from CFRG (which I consider myself also part of), Scott Fluhrer or 
anyone who can do modular arithmetic could do this one-line check. As I 
already indicated in my email of July 27, 2021 [2],

    As already indicated in the email below (July 21st), the draft does not contain new crypto and only uses a public and reversible (r,s) to (r,-s) signature transformation, if need be. This should therefore allow for a very quick start-to-finish project, where enabling this simply depends on defining code points or another unique cross-reference and getting this out of the door.

This was published in the peer-reviewed SAC 2005 conference, used in SAC 
2010 again, presented at IETF-78 (July 2010, i.e., 11 years ago!), 
presented at NIST in 2009 [1]. What more does one need?

I think the time is there to move forward on this extremely simple 
suggestion and get this done. IETF should be able to move fast if there 
is no reason to let things linger forever.

Rene

Ref: [1] 
https://csrc.nist.gov/csrc/media/events/cryptographic-key-management-workshop-2009/documents/rene_struik_kmwjune09_5min.pdf
[2] 
https://mailarchive.ietf.org/arch/msg/secdispatch/FXnznttsnNvlYcu_PX70itFJO_A/

On 2021-11-06 6:13 p.m., Ivaylo Petrov wrote:
> Hello Rene,
>
> Thank you for your email! It was brought to my attention that during 
> IETF 111 secdispatch 
> (https://datatracker.ietf.org/meeting/111/materials/minutes-111-secdispatch-00) 
> it was decided no code points to be assigned before the CFRG reviews 
> the document. Could you clarify if that has already concluded and if 
> not, what will be the purpose of the presentation?
>
> Thanks,
> Ivaylo
>
>
> *Ivaylo Petrov*
>
>
> CONFIDENTIALITY NOTICE: This email may contain confidential and 
> privileged material for the sole use of the intended recipient(s).
>
> It is strictly forbidden to share any part of this message with any 
> third party, without the written consent of the sender.
>
> immediately by email and delete the message and any file attached to 
> it. Thank you!
>
>
>
>     I would like to ask for a presentation slot for the COSE/JOSE
>     meeting Wednesday next week.
>
>>     I presented a mechanism for putting ECDSA signatures into a
>>     format that facilitates verification speed-ups, both in
>>     single-verify and batch verification settings [1]. While this
>>     technique (known for more than 1 1/2 decades) is generally
>>     applicable, I believe this would be especially useful to
>>     implement with JOSE and perhaps COSE right now, given
>>     Covid-vaccination records using ES256 in the smart healthcard
>>     specifications [3] (proposed with IATA, etc.). For the main idea,
>>     see [1]. For a JSON Web signature example, see [2].
>>
>>     Do you think I could briefly present? I would like to ask for a
>>     code point for JOSE and others down the road.
>>

---

From: Rene Struik <[email-masked]>
Date: Sun, 7 Nov 2021 11:53:45 -0500

Hi Ivylo:

As to your question "what will be the purpose of the presentation?", the 
answer is that one would like to have a simple code point to facilitate 
fast verification, both in single- and batch-settings.

As an example, with [1], one would like to have "ES256fv" 
(ECDSA/P-256/SHA-256 in fast-verify friendly way) in the "alg" field, 
where currently batch verification and single verification speed-ups are 
not possible. So, almost 17 years after this technique was introduced it 
is about time to switch this on for those who (optionally) wish to get 
~1.3x (single) to ~3x speed-ups (those who do not want to, can still 
simply not use this but should not be spoke-in-the-wheelers for those 
who do). This is just a single example (with JOSE); speed-ups apply 
across the (universe) board, for all ECDSA deployments (passports, TLS, 
SSH, etc.).

Ref: [1] https://spec.smarthealth.cards/#signing-health-cards

Each public key used to verify signatures is represented as a JSON Web 
Key (seeRFC 7517 <https://tools.ietf.org/html/rfc7517>):

  * SHALL have|"kty": "EC"|,|"use": "sig"|, and|"alg": "ES256"|

On 2021-11-07 10:38 a.m., Rene Struik wrote:
> Hi Ivaylo:
>
> I do not understand what the role of the CFRG is with this: should 
> they confirm that if (r,s) is a valid ECDSA signature for message m 
> with signing key Q, then so is (r,-s)? Or, is there more to this?
>
> r:=x(R) (mod n), R:=k*G, Q:=d*G, so r=x(R)=x(-R) and e=s*k-d*r (mod n) 
> = (-s)*(-k) - d*r (mod n). QED.
>
> Is the idea to have this one-line verification being blessed by 
> someone from CFRG (which I consider myself also part of), Scott 
> Fluhrer or anyone who can do modular arithmetic could do this one-line 
> check. As I already indicated in my email of July 27, 2021 [2],
>
> This was published in the peer-reviewed SAC 2005 conference, used in 
> SAC 2010 again, presented at IETF-78 (July 2010, i.e., 11 years ago!), 
> suggestion and get this done. IETF should be able to move fast if 
> there is no reason to let things linger forever.
>
> Rene
>
>
> Ref: [1] 
>> If you have received this message by mistake, please notify the 
>> sender immediately by email and delete the message and any file 
>> attached to it. Thank you!
>>
>>
>>
>>>     specifications [3] (proposed with IATA, etc.). For the main
>>>     idea, see [1]. For a JSON Web signature example, see [2].
>>>

---

From: Benjamin Kaduk <[email-masked]>
Date: Sun, 7 Nov 2021 09:44:43 -0800

Hi Rene,

While you may be an experienced enough cryptographer to be comfortable
asserting that there is "no new crypto" in these procedures, I contend that
being able to make that assessment does actually require some
cryptographic knowledge.  In particular, the question is not just that
(r,s) and (r,-s) are either both valid solutions to the ECDSA signing
equation or both not solutions; rather, it is whether making use of this
property has any interaction with the ECDSA assumptions that must be taken
into account for use in a protocol scenario.  While the fact that it is a
transform solely on public data suggests that there should not be any risk,
I, for one, am not willing to risk the reputation of the IETF on just my
own personal analysis of this case.

Furthermore, for a WG-consensus decision we never rely on just one
individual's analysis and review, and I lack confidence that the COSE WG
has sufficient cryptographic expertise to form a consensus assessment that
aligns with your individual assessment.  Likewise, the SECDISPATCH session
at IETF 111 produced a conclusion that the IETF security area as a whole is
unlikely to have that expertise, and suggested that CFRG would be an
appropriate place to reach a consensus conclusion in an open and public
forum that these techniques do not require any special handling in order to
be safely used in protocols designed to use regular ECDSA.

Is there anything blocking you from raising this question at the CFRG
yourself?  If it's just a matter of how to frame the question that is
believed to be relevant for IETF usage of the technique, I think we can
assist with that.  The previous publication at SAC would, of course, be a
useful input for the CFRG discussion (are there more specific
links/references available?), though the IETF-78 presentation may be less
so -- lots of things can get presented at an IETF session, including those
which end up being a bad idea.

> fast verification, both in single- and batch-settings.

If the goal is solely to have *a* codepoint, there does not seem to be a
need to involve the WG at all, at least initially.  It appears that the
relevant IANA registries have ranges available for allocation based solely
on the "Expert Review" procedure, which is something you can request
directly from IANA without any IETF WG involvement.

There may be other reasons to present to the WG, such as gaining visibility
of the technique to the broader community, getting a codepoint from the
"standards action" ranges, etc., but just having a codepoint does not
require a presentation to the WG.

Thanks,

Ben

---

From: Rene Struik <[email-masked]>
Date: Sun, 7 Nov 2021 12:51:48 -0500

Hi Ben:

If only for raising awareness of progress since ECDSA was first 
introduced, I think a presentation would be useful.

"Be liberal about what you accept..." should also apply to presentations 
that, for the first time in a very long time, have something with 
significant performance potential to offer.

BTW - I presented all pointers to one-line proofs in my previous email, 
including presentations in peer-reviewed conferences (2005, 2010), at 
NIST (2009), etc.

What question do you need to get answered (please be precise, so that 
this can be a one-round solicitation request), and I will get a 2nd 
opinion on that before Wednesday.

Rene

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 7 Nov 2021 21:20:52 +0200

> own personal analysis of this case.

What I think are more relevant properties:

While this does not prove that batch verification is safe (e.g., it
relies on random numbers and if those are predictable, it is not safe).
However, since everything is easily computable and all parameters are
considered public (e.g, the private key appears nowhere), these two
theorems establish that ECDSA and ECDSA* are of strictly equal security
in single verification.

Theorem 1: If (r,s) is valid ECDSA signature for message m with key Q,
then ((H(m)/s)*G+(r/s)*Q),s) is valid ECDSA* signature for message m
with key Q.

Proof:

Since (r,s) is valid ECDSA signature for message m with key Q, by
assumption it holds that:

r = x((H(m)/s)*G+(r/s)*Q)

Now, let R = (H(m)/s)*G+(r/s)*Q)

Substituting latter to former gives r = x(R).

Therefore:

R = (H(m)/s)*G+(x(R)/s)*Q)

Which is impiles that (R,s) = ((H(m)/s)*G+(r/s)*Q),s) is a valid ECDSA*
signature. Q.E.D.

Theorem 2: If (R,s) is valid ECDSA* signature for message m with key Q,
then (x(R),s) is valid ECDSA signature for message m with key Q.

Proof:

Since (R,s) is valid ECDSA* signature for message m with key Q, by
assumption it holds that:

R = (H(m)/s)*G+(x(R)/s)*Q)

Now, let r = x(R). Substituting latter to former gives:

R = (H(m)/s)*G+(r/s)*Q

Taking x() of both sides gives:

x(R) = x(H(m)/s)*G+(r/s)*Q)

Which by definition equals:

r = x(H(m)/s)*G+(r/s)*Q)

Which impiles that (x(R),s) is a valid ECDSA signature. Q.E.D.

-Ilari

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 8 Nov 2021 08:45:37 -0800

Hi Rene,

I'm not opposed to a presentation; what I'm opposed to is setting up
unrealistic expectations that are doomed to disappoint.

If you are specifically asking the WG for a WG-consensus-document
allocating codepoints, the answer is "sorry, we can't do that right now --
go to CFRG first".  If you are coming to the WG with a message "I know that
the WG will not accept work items using something that the WG can't tell
from 'new crypto' until there's external signoff, e.g., from the CFRG, on
the crypto, but I think the WG might be interested in this functionality
and I would like the WG's help ensuring that the CFRG answers the questions
the WG needs answered", that is a great thing to do and I'd support
spending meeting time on it (assuming that there is time after what is
needed for covering adopted WG items).

To clarify, when I asked about "more specific links/references" I was
thinking of, e.g., an http URL to an entry in the conference proceedings,
or perhaps a bibliography-entry-style reference.  I am not confident that I
would find the items you are referring to, otherwise (versus some other
entry from the same conference).  The only URLs I see in your previous
posting are to a 2009 NIST workshop
(https://csrc.nist.gov/csrc/media/events/cryptographic-key-management-workshop-2009/documents/rene_struik_kmwjune09_5min.pdf)
and a secdispatch posting
(https://mailarchive.ietf.org/arch/msg/secdispatch/FXnznttsnNvlYcu_PX70itFJO_A/);
in particular I do not see any links to the peer-reviewed SAC proceedings
of 2005 and 2010 that you mentioned.

I am not confident that I can frame a specific precise question during the
hustle of the IETF meeting week.  I should also reiterate that I am not
looking for a "second opinion", but rather the consensus conclusion of an
open and public body qualified to assess the work.  It may well be that
posting a link to Ilari's follow-up and a couple "+1" in reply would
suffice (I haven't read Ilari's message in detail yet), but if I were to
make a de novo request to CFRG, it would look something like this:

  I am proposing to the COSE WG that they make use of
  "verification-friendly ECDSA" [link] that adjusts the outputted signature
  in order to convey parity information about the ephemeral signing key R
  (which is what facilitates the efficiency gains in verification).  COSE
  currently has codepoints and associated processing procedures for
  unmodified ECDSA.  If verification-friendly ECDSA is to be used with
  COSE, new codepoints will be needed so as to indicate to recipients that
  the more efficient verification procedures are usable.  Other than having
  the new codepoints to indicate that the feature is available, are there
  any other changes to the COSE protocol (and the constituent ECDSA
  verification procedures) that are needed in order to retain a secure
  system while using the new functionality?  In particular (but not
  exclusively), is it safe to allow both the regular ECDSA verification
  procedures and the optimized ones to be used with these new codepoints?
  Is there any additional information that would need to be conveyed in the
  protocol that was not previously needed?  Are there any new security
  considerations that would need to be documented?

Thanks,

Ben

---

From: Rene Struik <[email-masked]>
Date: Mon, 8 Nov 2021 12:35:03 -0500

Hi Ben:

The conference papers (for which the titles and all other details are 
spelled out in the internet draft) are available online, via a single 
mouse click:
SAC 2005. https://link.springer.com/content/pdf/10.1007%2F11693383_21.pdf
A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, S.A. Vanstone, 
“Accelerated Verification of ECDSA Signatures,” in /Proceedings of 
Selected Areas of Cryptography – SAC 2005/, B. Preneel, S. Tavares, 
Eds., Lecture Notes in Computer Science, Vol. 3897, pp. 307-318, Berlin: 
Springer, 2006.

SAC 2010. 
https://link.springer.com/content/pdf/10.1007%2F978-3-642-19574-7_9.pdf
R. Struik, “Batch Computations Revisited: Combining Key Computations and 
Batch Verifications,” in/Proceedings of Selected Areas of Cryptography – 
SAC 2010/, A. Biryukov, G. Gong, D.R. Stinson, Eds., Lecture Notes in 
Computer Science, Vol. 6544, pp. 130-142, Berlin-Heidelberg: Springer, 2011

For equivalence of ECDSA and ECDSA* signature validity criteria, see p. 
2 of the SAC 2005 paper (Theorem 2); QED
For putting ECDSA* into ECDSA form via (r,s) to (r,-s) change, if need 
be, see, e.g., Section 4.3 of the SAC 2010 paper. QED

Since the suggested Fast-Verify friendly ECDSA format is also a valid 
ECDSA signature, any forgery of ECDSA Fast Verify would constitute a 
forgery of ECDSA (i.e., if the suggested speed-up would break things, 
then ECDSA would be bad too). QED

For experimenting with ECDSA in JWS format, simply try and validate the 
RFC 7515 example (Appendix A.3) and do the same with (r,s) replaced by 
(r,-s):
a) Example with (r,s) signature:
eyJhbGciOiJFUzI1NiJ9.eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ.DtEhU3ljbEg8L38VWAfUAqOyKAM6-Xx-F4GawxaepmXFCgfTjDxw5djxLa8ISlSApmWQxfKTUJqPP3-Kg6NU1Q
b) Same, but now with (r,-s) signature
eyJhbGciOiJFUzI1NiJ9.eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ.DtEhU3ljbEg8L38VWAfUAqOyKAM6-Xx-F4GawxaepmU69fgrc8OPGycO0lD3tat_FoFp57SETepkeks4eL_QfA

The full details (step-by-step) are also in Appendix Q.3.4 of the lwig 
curve draft: 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.3.4

I hope this helps, Rene

On 2021-11-08 11:45 a.m., Benjamin Kaduk wrote:
>>>>> On Fri, Nov 5, 2021 at 7:03 PM Rene Struik<[email-masked]>  wrote:
>>>>>
>>>>>       Dear Ivaylo:
>>>>>

---

From: Ivaylo Petrov <[email-masked]>
Date: Mon, 8 Nov 2021 21:49:26 +0100

Dear Rene,

Thank you for all the details you provided! I believe they will be
very helpful for anyone interested in learning more about the topic.
>From the discussion it appears to me that raising awareness of this
work with the COSE WG will be of benefit for the participants. Looking
at the current items in the agenda, I believe we can have 5 minutes
for presenting this topic (and 5 minutes for questions if there are
any). Please provide the slides by Tuesday 17:00 UTC and please
respect the spirit of raising awareness.

Best regards,
Ivaylo

On Mon, Nov 8, 2021 at 6:35 PM Rene Struik <[email-masked]> wrote:
>
> Hi Ben:
>
> The conference papers (for which the titles and all other details are spelled out in the internet draft) are available online, via a single mouse click:
> A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, S.A. Vanstone, “Accelerated Verification of ECDSA Signatures,” in Proceedings of Selected Areas of Cryptography – SAC 2005, B. Preneel, S. Tavares, Eds., Lecture Notes in Computer Science, Vol. 3897, pp. 307-318, Berlin: Springer, 2006.
>
> SAC 2010. https://link.springer.com/content/pdf/10.1007%2F978-3-642-19574-7_9.pdf
> R. Struik, “Batch Computations Revisited: Combining Key Computations and Batch Verifications,” in Proceedings of Selected Areas of Cryptography – SAC 2010, A. Biryukov, G. Gong, D.R. Stinson, Eds., Lecture Notes in Computer Science, Vol. 6544, pp. 130-142, Berlin-Heidelberg: Springer, 2011
>
> For equivalence of ECDSA and ECDSA* signature validity criteria, see p. 2 of the SAC 2005 paper (Theorem 2); QED
> For putting ECDSA* into ECDSA form via (r,s) to (r,-s) change, if need be, see, e.g., Section 4.3 of the SAC 2010 paper. QED
>
> Since the suggested Fast-Verify friendly ECDSA format is also a valid ECDSA signature, any forgery of ECDSA Fast Verify would constitute a forgery of ECDSA (i.e., if the suggested speed-up would break things, then ECDSA would be bad too). QED
>
> For experimenting with ECDSA in JWS format, simply try and validate the RFC 7515 example (Appendix A.3) and do the same with (r,s) replaced by (r,-s):
> The full details (step-by-step) are also in Appendix Q.3.4 of the lwig curve draft: https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.3.4
>
> I hope this helps, Rene
>

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 10 Nov 2021 05:28:09 -0800

Hi Rene,

Many thanks for the direct links -- for what it's worth, I would have been
happy to get "yes [more specific references are available]; they're linked
from the draft".

I'll reiterate that trying to convince me that these techniques are
"obviously safe" is not a fruitful approach, as I have already disclaimed
the competence to make such an assessment.  It's possible the extra
exposition you included here will be helpful if I need to forward the
inquiry to a different forum.

Thanks,

Ben