Subject: [lamps] Feedback on draft-struik-lamps-verification-friendly-ecdsa-01

From: Mike Ounsworth <[email-masked]>
Date: Fri, 12 Mar 2021 18:08:45 +0000

Hi,

I am understanding this draft to be a performance improvement on ECDSA signatures that has backwards compatibility issues; and therefore requires a whole standardization - implementation - adoption - migration cycle which would take years. Aren't we, during the same time period, trying to get rid of Elliptic Curve entirely in favour of post quantum crypto?

---
Mike Ounsworth
Software Security Architect, Entrust

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 14:05:28 -0500

Hi Mike:

I think this understanding is incorrect. The main idea is as follows:
(a) any device can put an existing ECDSA signature in a form (ECDSA*) 
that allows speed-ups at the verifying side to be taken advantage of, if 
they wish to do so;
(b) a verifying device sees a signature that is a valid ECDSA signature, 
so if it does not want to use faster techniques for ECDSA signature 
verification (for whatever reason), it can do so. {My presentation gave 
three options for doing so, so as to solicit feedback [it was to 
socialize the main message in this first presentation].}
The entire point is to give verifiers choice to use batch verification 
and single verification speed-ups, a choice they currently do not have 
(even though techniques have been known for over 16 years by now).

As to crystal ball gazing: in the long run, we may all be dead. This 
should not prevent us from trying to live interesting lives and do 
useful things, in a timely fashion.

Best regards, Rene

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

---

From: Russ Housley <[email-masked]>
Date: Fri, 12 Mar 2021 14:42:06 -0500

Rene:

If I understood your presentation properly, what you say above is correct if you do OPTION 2.  However, OPTION 3 would introduce a new algorithm identifier, so no existing implementation would try to verify the signature.  The new algorithm identifier would be treated an an unknown algorithm.

Russ

> On Mar 12, 2021, at 2:05 PM, Rene Struik <[email-masked]> wrote:
> 
> Hi Mike:
> 
> (a) any device can put an existing ECDSA signature in a form (ECDSA*) that allows speed-ups at the verifying side to be taken advantage of, if they wish to do so;
> (b) a verifying device sees a signature that is a valid ECDSA signature, so if it does not want to use faster techniques for ECDSA signature verification (for whatever reason), it can do so. {My presentation gave three options for doing so, so as to solicit feedback [it was to socialize the main message in this first presentation].}
> The entire point is to give verifiers choice to use batch verification and single verification speed-ups, a choice they currently do not have (even though techniques have been known for over 16 years by now).
> 
> As to crystal ball gazing: in the long run, we may all be dead. This should not prevent us from trying to live interesting lives and do useful things, in a timely fashion.
> 
> Best regards, Rene
> 
> 
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 15:06:01 -0500

Hi Russ:

Option #3 on my slides discusses encoding options for the on/off 
"button" for "was modified ECDSA signing procedure applied (yes/no)", 
where this is aimed at addressing the question "how does a receiving 
device know that the modified signing procedure was indeed used?"

In my slides, encoding this on/off button is further subdivided into two 
potential approaches, viz. (1) pick new OID; (2) define new non-critical 
extension. Here, in case (2), old devices who do not recognize this new 
extension, will simply skip that and process the remainder of the cert 
as usual, whereas new devices would recognize this indicator and take 
advantage of this if they wish. So, old devices would use traditional 
ECDSA verification, whereas new devices can choose to use accelerated 
ECDSA verification. With Option #3 - (1), old devices will not process 
the new oid, hence needing the flimsy parser mentioned in the draft to 
overwrite the new oid by the old one.

Right now, it seems option #3 - (2) is easiest from a transition 
perspective (also to accommodate speed-ups for SM2, ECGDSA, etc.). 
However, there are many-many options of doing things: if one wishes to 
explicitly encode the on/off button, one needs a single bit and can 
encode this into serial #s, the lowest-order bit in time validity 
windows, etc., etc. Hence, trying to tap your good ideas in my final 
question to the group re what works best.

Rene

---

From: Dmitry Belyavsky <[email-masked]>
Date: Fri, 12 Mar 2021 21:38:01 +0100

Dear Rene,

I have some doubts that the extensions (X509-level?) can be passed down to
the lower level (signature itself) without significant application redesign.
The protocol-level change has the same problems.

The OID change is a significantly clearer way from the implementation point
of view.

On Fri, Mar 12, 2021 at 9:06 PM Rene Struik <[email-masked]> wrote:

> > If I understood your presentation properly, what you say above is
> correct if you do OPTION 2.  However, OPTION 3 would introduce a new
> algorithm identifier, so no existing implementation would try to verify the
> signature.  The new algorithm identifier would be treated an an unknown
> algorithm.
> >
> > Russ
> >
> >> (b) a verifying device sees a signature that is a valid ECDSA
> signature, so if it does not want to use faster techniques for ECDSA
> signature verification (for whatever reason), it can do so. {My
> presentation gave three options for doing so, so as to solicit feedback [it
> was to socialize the main message in this first presentation].}
> should not prevent us from trying to live interesting lives and do useful
> things, in a timely fashion.
> >>
> >> Best regards, Rene
> >>
> >>
> >>> I am understanding this draft to be a performance improvement on ECDSA
> signatures that has backwards compatibility issues; and therefore requires
> a whole standardization - implementation - adoption - migration cycle which
> would take years. Aren't we, during the same time period, trying to get rid
> of Elliptic Curve entirely in favour of post quantum crypto?
> >>>
> >>> ---
> >>> Mike Ounsworth

-- 
SY, Dmitry Belyavsky

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 15:53:37 -0500

On 2021-03-12 3:51 p.m., Rene Struik wrote:
> Hi Dimitry:
>
> I do not know how to "parse" your email, since it suggests to me that (e.g.,  if one were to define a non-critical extension, as in Option #3 (2) on my slides),
> accommodating any new extension seems impossible. {I focus on extension, since that facilitates the GOST signature scheme "R compression bit".}
>
> What do you mean? Do you mean that the notion of "extension" in PKIX is a dead letter?
>
>  From page 18 of RFC 5280 (seehttps://datatracker.ietf.org/doc/html/rfc5280#page-18):
>
> Extension  ::=  SEQUENCE  {
>          extnID      OBJECT IDENTIFIER,
>          critical    BOOLEAN DEFAULT FALSE,
>          extnValue   OCTET STRING
>                      -- contains the DER encoding of an ASN.1 value
>                      -- corresponding to the extension type identified
>                      -- by extnID
>          }
>
> If one defines exnId="modified ECDSA signing has been applied", 
> critical=FALSE, and extnValue=[] (empty string), wouldn't a new device 
> be able to recognize this as a "fast verification" flag and act 
> accordingly, while allowing an old device to skip over this 
> nonrecognized alien species?
>
> Best regards, Rene
>
>
> On 2021-03-12 3:38 p.m., Dmitry Belyavsky wrote:
>> Dear Rene,
>>
>> I have some doubts that the extensions (X509-level?) can be passed 
>> down to the lower level (signature itself) without significant 
>> application redesign.
>> The OID change is a significantly clearer way from the implementation 
>> point of view.
>>
>> On Fri, Mar 12, 2021 at 9:06 PM Rene Struik <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>>     Hi Russ:
>>
>>     > If I understood your presentation properly, what you say above
>>     is correct if you do OPTION 2.  However, OPTION 3 would introduce
>>     a new algorithm identifier, so no existing implementation would
>>     try to verify the signature.  The new algorithm identifier would
>>     be treated an an unknown algorithm.
>>     >
>>     > Russ
>>     >
>>     >> On Mar 12, 2021, at 2:05 PM, Rene Struik
>>     <[email-masked] <mailto:[email-masked]>> wrote:
>>     >>
>>     >> Hi Mike:
>>     >>
>>     >> (a) any device can put an existing ECDSA signature in a form
>>     (ECDSA*) that allows speed-ups at the verifying side to be taken
>>     advantage of, if they wish to do so;
>>     signature, so if it does not want to use faster techniques for
>>     ECDSA signature verification (for whatever reason), it can do so.
>>     {My presentation gave three options for doing so, so as to
>>     solicit feedback [it was to socialize the main message in this
>>     first presentation].}
>>     >> The entire point is to give verifiers choice to use batch
>>     verification and single verification speed-ups, a choice they
>>     currently do not have (even though techniques have been known for
>>     over 16 years by now).
>>     >>
>>     >> As to crystal ball gazing: in the long run, we may all be
>>     dead. This should not prevent us from trying to live interesting
>>     lives and do useful things, in a timely fashion.
>>     >>
>>     >> Best regards, Rene
>>     >>
>>     >>
>>     >>> I am understanding this draft to be a performance improvement
>>     on ECDSA signatures that has backwards compatibility issues; and
>>     therefore requires a whole standardization - implementation -
>>     adoption - migration cycle which would take years. Aren't we,
>>     during the same time period, trying to get rid of Elliptic Curve
>>     entirely in favour of post quantum crypto?
>>     >>>
>>     >>> ---
>>     >>> Mike Ounsworth
>>     >> email: [email-masked] <mailto:[email-masked]> |
>>     Skype: rstruik
>>     >> [email-masked] <mailto:[email-masked]>
>>     <https://www.ietf.org/mailman/listinfo/spasm>
>>
>>
>>     -- 
>>     email: [email-masked] <mailto:[email-masked]> |
>>     Skype: rstruik
>>     [email-masked] <mailto:[email-masked]>
>>     <https://www.ietf.org/mailman/listinfo/spasm>
>>
>>
>>
>> -- 
>> SY, Dmitry Belyavsky
>
>
> -- 
> email:[email-masked]  | Skype: rstruik

---

From: Dmitry Belyavsky <[email-masked]>
Date: Fri, 12 Mar 2021 21:59:47 +0100

Dear Rene,

Let's temporarily leave GOST aside :)

Do I correctly understand that the extension you speak about is a possible
new X.509 extension?

On Fri, Mar 12, 2021 at 9:53 PM Rene Struik <[email-masked]> wrote:

> >From page 18 of RFC 5280 (see https://datatracker.ietf.org/doc/html/rfc5280#page-18):
>
> Extension  ::=  SEQUENCE  {
> critical=FALSE, and extnValue=[] (empty string), wouldn't a new device be
> able to recognize this as a "fast verification" flag and act accordingly,
> while allowing an old device to skip over this nonrecognized alien species?
>
> Best regards, Rene
>
>
>> >>> I am understanding this draft to be a performance improvement on
>> ECDSA signatures that has backwards compatibility issues; and therefore
>> requires a whole standardization - implementation - adoption - migration
>> cycle which would take years. Aren't we, during the same time period,
>> trying to get rid of Elliptic Curve entirely in favour of post quantum
>> crypto?
>> >>>
>> >>> ---
>> >>> Mike Ounsworth

-- 
SY, Dmitry Belyavsky

---

From: Russ Housley <[email-masked]>
Date: Fri, 12 Mar 2021 16:01:49 -0500

Rene:

I read Dmitry's not to be saying that pulling information out of the extension and passing it to the crypto library will not necessarily be easy in many implementations.  The application may need to be restructured to pass something that is learned in the extension processing to the part that handles signature processing.

In addition to this point, I can imagine an implementation that checks the certificate signature before looking at the extensions to ensure that the certificate has not been altered before acting on any of the extensions.

Russ

> On Mar 12, 2021, at 3:53 PM, Rene Struik <[email-masked]> wrote:
> 
>> From page 18 of RFC 5280 (see https://datatracker.ietf.org/doc/html/rfc5280#page-18 <https://datatracker.ietf.org/doc/html/rfc5280#page-18>):
>> 
>> Extension  ::=  SEQUENCE  {
>> If one defines exnId="modified ECDSA signing has been applied", critical=FALSE, and extnValue=[] (empty string), wouldn't a new device be able to recognize this as a "fast verification" flag and act accordingly, while allowing an old device to skip over this nonrecognized alien species?
>> 
>> Best regards, Rene
>> 
>> 
>>> I have some doubts that the extensions (X509-level?) can be passed down to the lower level (signature itself) without significant application redesign.
>>> The OID change is a significantly clearer way from the implementation point of view.
>>> 
>>> On Fri, Mar 12, 2021 at 9:06 PM Rene Struik <[email-masked] <mailto:[email-masked]>> wrote:
>>> Hi Russ:
>>> 
>>> >> On Mar 12, 2021, at 2:05 PM, Rene Struik <[email-masked] <mailto:[email-masked]>> wrote:
>>> >>
>>> >> Hi Mike:
>>> >>
>>> >> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik
>>> >> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>
>>> 
>>> 
>>> -- 
>>> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik
>>> https://www.ietf.org/mailman/listinfo/spasm <https://www.ietf.org/mailman/listinfo/spasm>
>>> 
>>> 
>>> -- 
>>> SY, Dmitry Belyavsky
>> 
>> -- 
>> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik
> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 16:06:51 -0500

Yes, if one wishes to explicitly codify "modified ECDSA signing used" as 
a non-critical extension field (hence, my reference to that syntax, 
based on my understanding of RFC 5280 extensions).

On 2021-03-12 3:59 p.m., Dmitry Belyavsky wrote:
> Do I correctly understand that the extension you speak about is a 
> possible new X.509 extension?
>
>
> On Fri, Mar 12, 2021 at 9:53 PM Rene Struik <[email-masked] 
>>     critical=FALSE, and extnValue=[] (empty string), wouldn't a new
>>     device be able to recognize this as a "fast verification" flag
>>     and act accordingly, while allowing an old device to skip over
>>     this nonrecognized alien species?
>>
>>     Best regards, Rene
>>
>>
>>>     I have some doubts that the extensions (X509-level?) can be
>>>     passed down to the lower level (signature itself) without
>>>     significant application redesign.
>>>     On Fri, Mar 12, 2021 at 9:06 PM Rene Struik
>>>         > If I understood your presentation properly, what you say
>>>         above is correct if you do OPTION 2. However, OPTION 3 would
>>>         introduce a new algorithm identifier, so no existing
>>>         implementation would try to verify the signature.  The new
>>>         algorithm identifier would be treated an an unknown algorithm.
>>>         >
>>>         > Russ
>>>         >
>>>         >> (a) any device can put an existing ECDSA signature in a
>>>         form (ECDSA*) that allows speed-ups at the verifying side to
>>>         be taken advantage of, if they wish to do so;
>>>         >> (b) a verifying device sees a signature that is a valid
>>>         ECDSA signature, so if it does not want to use faster
>>>         techniques for ECDSA signature verification (for whatever
>>>         reason), it can do so. {My presentation gave three options
>>>         for doing so, so as to solicit feedback [it was to socialize
>>>         the main message in this first presentation].}
>>>         verification and single verification speed-ups, a choice
>>>         they currently do not have (even though techniques have been
>>>         known for over 16 years by now).
>>>         >>
>>>         dead. This should not prevent us from trying to live
>>>         interesting lives and do useful things, in a timely fashion.
>>>         >>
>>>         >> Best regards, Rene
>>>         >>
>>>         >>
>>>         >>> I am understanding this draft to be a performance
>>>         improvement on ECDSA signatures that has backwards
>>>         compatibility issues; and therefore requires a whole
>>>         standardization - implementation - adoption - migration
>>>         cycle which would take years. Aren't we, during the same
>>>         time period, trying to get rid of Elliptic Curve entirely in
>>>         favour of post quantum crypto?
>>>         >>>
>>>         >>> ---
>>>         >>> Mike Ounsworth
>>>         >> email: [email-masked]
>>>         <mailto:[email-masked]> | Skype: rstruik
>>     email:[email-masked]  <mailto:[email-masked]>  | Skype: rstruik
>     email:[email-masked]  <mailto:[email-masked]>  | Skype: rstruik

---

From: Dmitry Belyavsky <[email-masked]>
Date: Fri, 12 Mar 2021 22:07:38 +0100

Dear Russ,

Many thanks for your rewording! Yes, it's what I meant.

On Fri, Mar 12, 2021 at 10:01 PM Russ Housley <[email-masked]> wrote:

> Rene:
>
> I read Dmitry's not to be saying that pulling information out of the
> extension and passing it to the crypto library will not necessarily be easy
> in many implementations.  The application may need to be restructured to
> pass something that is learned in the extension processing to the part that
> handles signature processing.
>
> In addition to this point, I can imagine an implementation that checks the
> certificate signature before looking at the extensions to ensure that the
> certificate has not been altered before acting on any of the extensions.
>
> Russ
>
>

-- 
SY, Dmitry Belyavsky

---

From: Mike Ounsworth <[email-masked]>
Date: Fri, 12 Mar 2021 21:30:25 +0000

If this is data that’s useful to the crypto library in validating the signature, wouldn’t it be a better fit in the signatureAlgorithm’s parameters? That structure is intended to be passed down into the crypto layer along with the signature bytes, right?

   AlgorithmIdentifier  ::=  SEQUENCE  {
        algorithm               OBJECT IDENTIFIER,
        parameters              ANY DEFINED BY algorithm OPTIONAL  }

---
Mike Ounsworth

From: Spasm <[email-masked]> On Behalf Of Dmitry Belyavsky
Sent: March 12, 2021 3:08 PM
To: Russ Housley <[email-masked]>
Cc: LAMPS <[email-masked]>; Rene Struik <[email-masked]>
Subject: [EXTERNAL] Re: [lamps] (+ Russ Housley, lamps mailing list) Re: Feedback on draft-struik-lamps-verification-friendly-ecdsa-01

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.
________________________________________
Dear Russ,

On Fri, Mar 12, 2021 at 10:01 PM Russ Housley <mailto:[email-masked]> wrote:
Rene:

Russ

On Mar 12, 2021, at 3:53 PM, Rene Struik <mailto:[email-masked]> wrote:

>From page 18 of RFC 5280 (see https://urldefense.com/v3/__https://datatracker.ietf.org/doc/html/rfc5280*page-18__;Iw!!FJ-Y8qCqXTj2!OQ4cRMf10ZefpzHaEPZdFEDrpxYQWXf5qXluqmehvl8LAL7BTwq7Kce_zi6L_1EsN3fK4leI_Q$):

Extension  ::=  SEQUENCE  {

Best regards, Rene

On Fri, Mar 12, 2021 at 9:06 PM Rene Struik <mailto:[email-masked]> wrote:
Hi Russ:

Rene

On 2021-03-12 2:42 p.m., Russ Housley wrote:
>> On Mar 12, 2021, at 2:05 PM, Rene Struik <mailto:[email-masked]> wrote:
>>
>> Hi Mike:
>>
>> email: mailto:[email-masked] | Skype: rstruik
>> mailto:[email-masked]
>> https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/spasm__;!!FJ-Y8qCqXTj2!OQ4cRMf10ZefpzHaEPZdFEDrpxYQWXf5qXluqmehvl8LAL7BTwq7Kce_zi6L_1EsN3d3_3kCfQ$

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

_______________________________________________
Spasm mailing list
mailto:[email-masked]
https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/spasm__;!!FJ-Y8qCqXTj2!OQ4cRMf10ZefpzHaEPZdFEDrpxYQWXf5qXluqmehvl8LAL7BTwq7Kce_zi6L_1EsN3d3_3kCfQ$

-- 
SY, Dmitry Belyavsky

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

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

-- 
SY, Dmitry Belyavsky

---

From: Rene Struik <[email-masked]>
Date: Fri, 12 Mar 2021 16:35:03 -0500

Hi Dmitry:

I understand that you were talking about parsing order and process flow, 
where the on/off "button" may be parsed later than processing the inputs 
required for verification. Note, though, that the extension field is 
part of the to-be-signed data (as is the public key Q of the signer), so 
has to be processed (i.e., hashed) before one can compute 
R':=(1/s)(eG+rQ). A fast-verify routine could therefore have access to 
this "flag" before the crypto processor is ready to do perform the 
computation of R'. Note that one has to invert the s value mod n before 
ECC computations can start, so one has time to look up the "flag" value 
and include this in an interface, it seems.

If an implementation does not have info allowing for accelerated 
speed-up (due to process flow decisions of its own making), it can still 
perform ordinary ECDSA signature verification (till it has fed the 
on/off "buttion" into the interface design of the fast-verification 
processor). This does not break things, though.

For batch verification, there is a strong incentive to look for these 
"flags", since the speed-ups that could be had are so large.

Best regards, Rene

On 2021-03-12 4:07 p.m., Dmitry Belyavsky wrote:
> On Fri, Mar 12, 2021 at 10:01 PM Russ Housley <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Rene:
>
>     I read Dmitry's not to be saying that pulling information out of
>     the extension and passing it to the crypto library will not
>     necessarily be easy in many implementations.  The application may
>     need to be restructured to pass something that is learned in the
>     extension processing to the part that handles signature processing.
>
>     In addition to this point, I can imagine an implementation that
>     checks the certificate signature before looking at the extensions
>     to ensure that the certificate has not been altered before acting
>     on any of the extensions.
>     tbs
>     Russ
>
>
>>     On Mar 12, 2021, at 3:53 PM, Rene Struik <[email-masked]
>>>>         above is correct if you do OPTION 2.  However, OPTION 3
>>>>         would introduce a new algorithm identifier, so no existing
>>>>         form (ECDSA*) that allows speed-ups at the verifying side
>>>>         to be taken advantage of, if they wish to do so;
>>>>         for doing so, so as to solicit feedback [it was to
>>>>         >> The entire point is to give verifiers choice to use
>>>>         batch verification and single verification speed-ups, a
>>>>         choice they currently do not have (even though techniques
>>>>         have been known for over 16 years by now).
>>>>         >>
>>>>         >> As to crystal ball gazing: in the long run, we may all
>>>>         be dead. This should not prevent us from trying to live
>>>>         time period, trying to get rid of Elliptic Curve entirely
>>>>         in favour of post quantum crypto?
>>>>         >>>
>>>>         >>> ---
>>>>         >>> Mike Ounsworth

---

From: Dmitry Belyavsky <[email-masked]>
Date: Fri, 12 Mar 2021 22:35:28 +0100

Dear Mike,

If we have to change the representation of parameters, it should be clearer
to specify a new OID.

On Fri, Mar 12, 2021 at 10:30 PM Mike Ounsworth <[email-masked]>
wrote:

> If this is data that’s useful to the crypto library in validating the
> signature, wouldn’t it be a better fit in the signatureAlgorithm’s
> parameters? That structure is intended to be passed down into the crypto
> layer along with the signature bytes, right?
>
> Subject: [EXTERNAL] Re: [lamps] (+ Russ Housley, lamps mailing list) Re:
> Feedback on draft-struik-lamps-verification-friendly-ecdsa-01
>
> I do not know how to "parse" your email, since it suggests to me that
> (e.g.,  if one were to define a non-critical extension, as in Option #3 (2)
> on my slides),
> accommodating any new extension seems impossible. {I focus on extension,
> since that facilitates the GOST signature scheme "R compression bit".}
>
> >From page 18 of RFC 5280 (see
> https://urldefense.com/v3/__https://datatracker.ietf.org/doc/html/rfc5280*page-18__;Iw!!FJ-Y8qCqXTj2!OQ4cRMf10ZefpzHaEPZdFEDrpxYQWXf5qXluqmehvl8LAL7BTwq7Kce_zi6L_1EsN3fK4leI_Q$
> ):
>
> Extension  ::=  SEQUENCE  {

-- 
SY, Dmitry Belyavsky

---

From: Mike Ounsworth <[email-masked]>
Date: Fri, 12 Mar 2021 22:39:50 +0000

Right, that's kinda where I'm going here...

In the slides, the question was "with PKIX, is new OID best, or non-critical extension?" I see where Rene is coming from that if the signatureValue bits are truly backwards-compatible, then you would want the flag to be as well, but an X.509v3 extension is a weird place to put instructions to the crypto layer on how to parse the signatureValue bits. 

I'm a little unclear what the semantics would be of putting this in a non-critical extension; would that affect the parsing of the signature on this certificate? Or the parsing of signatures verified with the public key in this certificate? If the former then you have Russ' issue of cert parsing order (usually sig before extensions). If the latter, then it's a bit weird to put ECDSA alg params on a public key which is presumably of type id-ecPublicKey which could be used for things other than ECDSA? Do you end up with weird interactions between this extension and keyUsage? So I understand the backwards compatibility desire to put this in a non-critical extension, but I don't understand the semantics of  doing so. This is an ECDSA signature parameter, so it feels like it belongs in signatureAlgorithm.parameters, which probably then needs a new OID.... at which point you might as well define `id-ecdsa-star-with-sha256` as Rene has already done in his draft.

---
Mike Ounsworth

From: Spasm <[email-masked]> On Behalf Of Dmitry Belyavsky
Sent: March 12, 2021 3:35 PM
To: LAMPS <[email-masked]>
Subject: Re: [lamps] [EXTERNAL] Re: (+ Russ Housley, lamps mailing list) Re: Feedback on draft-struik-lamps-verification-friendly-ecdsa-01

Dear Mike,

If we have to change the representation of parameters, it should be clearer to specify a new OID.

On Fri, Mar 12, 2021 at 10:30 PM Mike Ounsworth <mailto:[email-masked]> wrote:
If this is data that’s useful to the crypto library in validating the signature, wouldn’t it be a better fit in the signatureAlgorithm’s parameters? That structure is intended to be passed down into the crypto layer along with the signature bytes, right?

---
Mike Ounsworth

From: Spasm <mailto:[email-masked]> On Behalf Of Dmitry Belyavsky
Sent: March 12, 2021 3:08 PM
To: Russ Housley <mailto:[email-masked]>
Cc: LAMPS <mailto:[email-masked]>; Rene Struik <mailto:[email-masked]>
Subject: [EXTERNAL] Re: [lamps] (+ Russ Housley, lamps mailing list) Re: Feedback on draft-struik-lamps-verification-friendly-ecdsa-01

On Fri, Mar 12, 2021 at 10:01 PM Russ Housley <mailto:mailto:[email-masked]> wrote:
Rene:

Russ

On Mar 12, 2021, at 3:53 PM, Rene Struik <mailto:mailto:[email-masked]> wrote:

Extension  ::=  SEQUENCE  {

Best regards, Rene

On Fri, Mar 12, 2021 at 9:06 PM Rene Struik <mailto:mailto:[email-masked]> wrote:
Hi Russ:

Rene

On 2021-03-12 2:42 p.m., Russ Housley wrote:
>> On Mar 12, 2021, at 2:05 PM, Rene Struik <mailto:mailto:[email-masked]> wrote:
>>
>> Hi Mike:
>>
>> email: mailto:mailto:[email-masked] | Skype: rstruik
>> mailto:mailto:[email-masked]

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

_______________________________________________
Spasm mailing list
mailto:mailto:[email-masked]
https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/spasm__;!!FJ-Y8qCqXTj2!OQ4cRMf10ZefpzHaEPZdFEDrpxYQWXf5qXluqmehvl8LAL7BTwq7Kce_zi6L_1EsN3d3_3kCfQ$

-- 
SY, Dmitry Belyavsky

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

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

-- 
SY, Dmitry Belyavsky

-- 
SY, Dmitry Belyavsky

---

From: Rene Struik <[email-masked]>
Date: Thu, 18 Mar 2021 12:21:56 -0400

Dear colleagues:

I did a quick calculation of approximate speed-ups with batch 
verification of ECDSA signatures with NIST prime-order curves:
a) batch verification of multiple signatures with same signer:
roughly 5.0x per signature incremental verification cost compared to 
performing each verification independently;
b) batch verification of multiple signatures with all signers different:
roughly 2.2x per signature incremental verification cost compared to 
performing each verification independently;
Note 1: This obviously assumes one facilitates the techniques in my 
draft; otherwise, *none* of these speed-ups are possible
Note 2: under some mild conditions, one can get a roughly 9.3x speed-up 
with batch verification with single signer and 3.1x speed-up with all 
signers different.

As already mentioned during my presentation, for single ECDSA verifies, 
enabling the technique in my draft facilitates a roughly 1.3x speed-up 
compared to performing verifies the old-fashioned way.

I hope this helps.

Rene

[excerpt of email RS of Fri arch 12, 2021, 4.35pm EDT]
For batch verification, there is a strong incentive to look for these 
"flags", since the speed-ups that could be had are so large

On 2021-03-12 4:35 p.m., Rene Struik wrote:
> Hi Dmitry:
>
> I understand that you were talking about parsing order and process 
> flow, where the on/off "button" may be parsed later than processing 
> the inputs required for verification. Note, though, that the extension 
> field is part of the to-be-signed data (as is the public key Q of the 
> signer), so has to be processed (i.e., hashed) before one can compute 
> computation of R'. Note that one has to invert the s value mod n 
> before ECC computations can start, so one has time to look up the 
> "flag" value and include this in an interface, it seems.
>
> speed-up (due to process flow decisions of its own making), it can 
> still perform ordinary ECDSA signature verification (till it has fed 
> the on/off "buttion" into the interface design of the 
> fast-verification processor). This does not break things, though.
>

---

From: Rene Struik <[email-masked]>
Date: Thu, 18 Mar 2021 12:45:22 -0400

Hmm... obviously "per signature incremental verification cost" should 
have read "per signature incremental speed-up of verification cost". 
Corrected below [ ... ]

On 2021-03-18 12:21 p.m., Rene Struik wrote:
> roughly 5.0x per signature incremental [speed-up of] verification cost 
> compared to performing each verification independently;
> roughly 2.2x per signature incremental [speed-up of] verification cost 
> compared to performing each verification independently;
> Note 2: under some mild conditions, one can get a roughly 9.3x 
> speed-up with batch verification with single signer and 3.1x speed-up 
> with all signers different.
>
> As already mentioned during my presentation, for single ECDSA 
> verifies, enabling the technique in my draft facilitates a roughly 
> 1.3x speed-up compared to performing verifies the old-fashioned way.
>
> I hope this helps.
>
> Rene
>
>> the inputs required for verification. Note, though, that the 
>> extension field is part of the to-be-signed data (as is the public 
>> key Q of the signer), so has to be processed (i.e., hashed) before 
>> one can compute R':=(1/s)(eG+rQ). A fast-verify routine could 
>> therefore have access to this "flag" before the crypto processor is 
>> ready to do perform the computation of R'. Note that one has to 
>> invert the s value mod n before ECC computations can start, so one 
>> has time to look up the "flag" value and include this in an 
>> interface, it seems.
>>
>>>     necessarily be easy in many implementations.  The application
>>>     may need to be restructured to pass something that is learned in
>>>     the extension processing to the part that handles signature
>>>     processing.
>>>
>>>     checks the certificate signature before looking at the
>>>     extensions to ensure that the certificate has not been altered
>>>     before acting on any of the extensions.
>>>     tbs
>>>     Russ
>>>
>>>
>>>>>     If one defines exnId="modified ECDSA signing has been
>>>>>     applied", critical=FALSE, and extnValue=[] (empty string),
>>>>>     wouldn't a new device be able to recognize this as a "fast
>>>>>     verification" flag and act accordingly, while allowing an old
>>>>>     device to skip over this nonrecognized alien species?
>>>>>
>>>>>     Best regards, Rene
>>>>>
>>>>>
>>>>>>         > If I understood your presentation properly, what you
>>>>>>         say above is correct if you do OPTION 2.  However, OPTION
>>>>>>         3 would introduce a new algorithm identifier, so no
>>>>>>         existing implementation would try to verify the
>>>>>>         signature.  The new algorithm identifier would be treated
>>>>>>         an an unknown algorithm.
>>>>>>         >
>>>>>>         > Russ
>>>>>>         >
>>>>>>         >> (a) any device can put an existing ECDSA signature in
>>>>>>         a form (ECDSA*) that allows speed-ups at the verifying
>>>>>>         side to be taken advantage of, if they wish to do so;
>>>>>>         >> (b) a verifying device sees a signature that is a
>>>>>>         valid ECDSA signature, so if it does not want to use
>>>>>>         faster techniques for ECDSA signature verification (for
>>>>>>         whatever reason), it can do so. {My presentation gave
>>>>>>         three options for doing so, so as to solicit feedback [it