Subject: Re: [COSE] (on ecdsa codepoints cose iana) Re: next steps for draft-ietf-lwig-curve-representations

From: Rene Struik <[email-masked]>
Date: Sun, 7 Nov 2021 13:00:36 -0500

Hi Ben:

A friendly reminder of the reminder of the reminder. Is it really 
necessary (or fair, for that matter) that a simple technical disposition 
email exchange takes more than a half year, with me having to 
consistently pick up dropped balls?

Best regards, Rene

On 2021-08-06 12:21 p.m., Rene Struik wrote:
> Hi Ben:
>
> A friendly reminder: in your email of July 15th below you suggested 
> you still had to finalize the review of the OLD vs. NEW text for ECDSA 
> cose iana code points (that I suggested June 14, 2021). If you could 
> do so, that would be great, since it helps to get to badly needed 
> closure: this has been dangling for quite a while now.
>
> Best regards, Rene
>
> On 2021-07-15 12:25 a.m., Benjamin Kaduk wrote:
>> Hi Rene,
>>
>> Sorry to have dropped your earlier mail -- there's been enough going on
>> with family and time off that my inbox has been growing a bit faster 
>> than I
>> can process things, so I missed some things.
>>
>> The proposed NEW text regarding 'alg' generally looks good.  I would 
>> need
>> to check on the bit about setting the "crv" parameter as it appears 
>> in COSE
>> and JOSE, but the actual diff between OLD and NEW looks to be good 
>> changes.
>>
>> For the lack of precision in ES256 I don't have a clear answer just yet;
>> there seem to be a few options to consider, all of which have some 
>> reason
>> to be distasteful or procedurally challenging (e.g., pulling
>> rfc8152bis-algs out of the RFC Editor queue, doing a short document 
>> in COSE
>> to update the specification, having this document update the core COSE
>> specification, defining a new mostly-redundant codepoint).  It is very
>> useful to have the text in Appendix Q available as an example of what 
>> the
>> "more precise" definition would look like, even if it ends up 
>> appearing in
>> some other document rather than this one.
>>
>> You had also asked about ECDSA w/ SHAKE128.  I'm pretty ambivalent about
>> that -- while I can understand the desire to define both algorithms for
>> some kind of parity, it also seems quite defensible to wait to 
>> specify the
>> algorithm until there is an actual consumer ready.  It may be 
>> expedient to
>> keep things simple and not add unnecessary things at this stage.
>>
>> -Ben
>>
>> On Wed, Jul 14, 2021 at 02:04:26PM -0400, Rene Struik wrote:
>>> Hi Ben:
>>>
>>> Any feedback on my suggested disposition of your cose code point remark
>>> for ECDSA w/ SHAKE256? What about my note on lack of precision in ES256
>>> and suggested path to "fix" this? Please see my email of June 14th 
>>> below
>>> for details.
>>>
>>> Best regards, Rene
>>>
>>> On 2021-06-14 12:49 p.m., Rene Struik wrote:
>>>> Hi Ben:
>>>>
>>>> I do believe your suggestion to allocate a code point for ECDSA with
>>>> SHAKE256 (thereby, untie-ing this from the curve) is easy to
>>>> accommodate with the draft.
>>>>
>>>> This would come down to changing Section 12.3.2 as below (change of
>>>> Name and Description fields only, plus pointer to example):
>>>>
>>>> 12.3.2. COSE Algorithms Registration (1/2)
>>>> This section registers the following value in the IANA "COSE
>>>> Algorithms" registry [IANA.COSE.Algorithms].
>>>> Name: ECDSA with SHAKE256;
>>>> Value: TBD (Requested value: -48);
>>>> Description: ECDSA with SHAKE256;
>>>> Change Controller: IESG;
>>>> Reference: specified in Section 4.4 of this specification; for
>>>> encodings, see Section 10.2; for an example, see Appendix Q.3.3.
>>>>
>>>> and changing the last para of Section 10.2 as below (i.e., untieing
>>>> the curve from "alg" parameter [since "alg" now becomes ECDSA+SHAK256,
>>>> rather than ECDSA+SHAKE256+Wei448):
>>>>
>>>> OLD:
>>>> The encodings below specify the use of instantiations of ECDSA with
>>>> COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the
>>>> encoding for a specific ECDSA instantiation (i.e., with a specific
>>>> short-Weierstrass curve and specific hash function) results by setting
>>>> the "crv" parameter to the unique name of the underlying curve in
>>>> question and the "alg" parameter to the unique name of the specific
>>>> signature scheme instantiation (e.g., "ECDSA25519" for the ECDSA
>>>> scheme defined in Section 4.3 and "ECDSA448" for the scheme defined in
>>>> Section 4.4). Note that, in this case, the "alg" name uniquely defines
>>>> the curve (and, thereby, implicitly the underlying "crv" parameter)
>>>> and the underlying hash function.
>>>>
>>>> NEW:
>>>> The encodings below specify the use of instantiations of ECDSA with
>>>> COSE (see Section 10.2.1) and JOSE (see Section 10.2.2), where the
>>>> encoding for a specific ECDSA instantiation (i.e., with a specific
>>>> short-Weierstrass curve and specific hash function) results by setting
>>>> the "crv" parameter to the unique name of the underlying curve in
>>>> question and the "alg" parameter to the unique name of the specific
>>>> signature scheme instantiation. For JOSE, this is realized by setting
>>>> the "alg" parameter to "ECDSA25519" for the ECDSA scheme defined in
>>>> Section 4.3 and to "ECDSA448" for the scheme defined in Section 4.4).
>>>> For COSE, this is realized by setting the "alg" parameter to "ES256"
>>>> (short-hand for "ECDSA with SHA-256") for the ECDSA scheme defined in
>>>> Section 4.3 and to "ECDSA with SHAKE256" for the scheme defined in
>>>> Section 4.4). Note that, in the case of JOSE, the "alg" name uniquely
>>>> defines the curve (and, thereby, implicitly the underlying "crv"
>>>> parameter) and the underlying hash function, while in the case of
>>>> COSE, the "alg" name uniquely defines the underlying hash function,
>>>> but not the underlying curve.
>>>>
>>>> I do think this would highlight the (somewhat confusing [to me])
>>>> differences between COSE and JOSE treatment of ECDSA in a concise 
>>>> manner.
>>>>
>>>> I think this would settle the ECDSA/SHAKE256/Wei448 code point for
>>>> COSE. Could you confirm?
>>>>
>>>> As to using ES256, the main issue I see is that the definition of
>>>> ECDSA in RFC 8152 is not precise enough. For the exact definition, I
>>>> included Appendix Q (which is compatible with RFC8152's definition in
>>>> the deployed cases of ES256, ES384, and ES512, so using the exact
>>>> definition does not hurt current deployments and helps future ones).
>>>> Putting some verbiage to that effect into the draft should illuminate
>>>> this and settle this. Does this work? {If not, one still would need a
>>>> code point for "ECDSA with SHA-256 exact definition-style"; if so, one
>>>> would not need this (currently in Section 12.2.2).}
>>>>
>>>> Last note: RFC8692 defines ECDSA w/ SHAKEs (including both ECDSA w/
>>>> SHAKE128 and ECDSA w/ SHAKE256). It would be easy to align COSE to
>>>> this, simply by adding the ECDSA w/ SHAKE128 code point (to the
>>>> already requested code point for ECDSA w/ SHAKE256). There should be
>>>> sufficiently many "small-size" code points left to do so (one can use
>>>> "-9" if the verdict of the above para is okay).
>>>>
>>>> I hope this helps, Rene
>>>>
>>>> Ref: [1] Email Ben Kaduk of April 29, 2021, 6.29pm EDT, Subject: next
>>>> steps for draft-ietf-lwig-curve-representations
>>>>
>>>> [2]
>>>> https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-21 
>>>>
>>>>
>>>> [3] https://datatracker.ietf.org/doc/html/rfc8152
>>>>
>>>> [4] https://datatracker.ietf.org/doc/html/rfc8692
>>>>
>>>>
>>>> On 2021-04-29 6:53 p.m., Benjamin Kaduk wrote:
>>>>> Hi Rene,
>>>>>
>>>>> My apologies for the slow response -- Erik, Roman, and I were able 
>>>>> to get
>>>>> together to talk about this document last week but then I had to 
>>>>> take a
>>>>> couple days off, which interrupted my drafting of this note.
>>>>>
>>>>> It seems that there are a handful of mostly orthogonal axes along 
>>>>> which action
>>>>> is needed, so I will try to enumerate them separately.
>>>>>
>>>>> [1] Intended status of the document (Informational vs Proposed 
>>>>> Standard).
>>>>>
>>>>> Since, at its core, the point of this document is to provide 
>>>>> information about
>>>>> how you can use elliptic curve isogenies (and isomorphisms) to use 
>>>>> an ECC
>>>>> implementation that is generic within one family of curves to perform
>>>>> operations defined on a different family of curves, the 
>>>>> Informational status
>>>>> seems most appropriate.  My undersatnding is that the intended 
>>>>> status was
>>>>> changed to Proposed Standard in order to qualify for allocations 
>>>>> from a
>>>>> codepoint range in the IANA COSE registries that has a shorter 
>>>>> encoding.  At
>>>>> present, those IANA Considerations are not even in the document, 
>>>>> but even if
>>>>> we do want to have IANA registrations for those COSE codepoints 
>>>>> eventually, it
>>>>> is fairly straightforward to do to in a separate document as needed.
>>>>>
>>>>> Accordingly, assuming the WG chairs (on behalf of the WG) do not 
>>>>> object,
>>>>> please go back to the Informational status in the next version.
>>>>>
>>>>> [2] Describing the motivation for the document
>>>>>
>>>>> My understanding of the core purpose of this document is 
>>>>> summarized in the
>>>>> previous point -- to allow reuse of code that is "generic" (but 
>>>>> not fully
>>>>> generic ECC code) to make more algorithms accessible to that 
>>>>> implementation.
>>>>> In our discussions, it seemed that Sections 1 and 2 could be seen as
>>>>> subsections of a single "motivation" section, and that the document's
>>>>> accessibility would be improved by adding a few clarifying 
>>>>> sentences covering
>>>>> the importance/relevance of this type of strategy for lightweight
>>>>> implementation.  Please consider performing this type of 
>>>>> restructuring to
>>>>> improve the document.  I am willing to suggest specific edits if 
>>>>> desired
>>>>> (though probably not with a particularly fast turnaround time).
>>>>>
>>>>> [3] Key types
>>>>>
>>>>> The JOSE registration requests currently in the document (and the 
>>>>> COSE ones,
>>>>> when they were there) are doing something that is without 
>>>>> precedent, namely
>>>>> allowing the use of both "OKP" and "EC" ("EC2" in COSE) key types 
>>>>> (i.e.,
>>>>> representations) for a single curve.  All the curves defined in 
>>>>> RFC 7518 use
>>>>> "EC" and only "EC; likewise, all the curves defined in RFC 8037 
>>>>> use "OKP" and
>>>>> only "OKP".  RFC 8812 is the only other JOSE curve registration, 
>>>>> which uses
>>>>> kty "EC".  I think this deviation from precedent is something that 
>>>>> does not
>>>>> have a presumption of IETF consensus, and that the JOSE and COSE 
>>>>> communities
>>>>> should be consulted on whether diverging from precedent in this 
>>>>> way is the
>>>>> correct course of action.  I will initiate an email thread with 
>>>>> the COSE and
>>>>> JOSE WG lists (and am happy to put you on the CC list if desired) 
>>>>> to consider
>>>>> this question.  If you do believe that it is important to be able 
>>>>> to use both
>>>>> key types with these new curves, I implore you to specifically 
>>>>> discuss the
>>>>> topic in the IANA considerations and provide some explanation or 
>>>>> justification
>>>>> for why it is the right thing to do.  Such text would be a useful 
>>>>> input to the
>>>>> discussion I will initiate with the COSE/JOSE WG lists.
>>>>>
>>>>> [4] COSE Algorithm semantics
>>>>>
>>>>> I include this text only for completeness, even though it is 
>>>>> perhaps only a
>>>>> matter for the IANA Considerations that requested allocation from 
>>>>> COSE
>>>>> registries.  (On the other hand, the main body text still includes 
>>>>> treatment
>>>>> on the use of the new algorithms with COSE as well as JOSE, which 
>>>>> might
>>>>> suggest that COSE-related topics remain in scope.)
>>>>>
>>>>> One of the goals of the COSE work was to (in some sense) "avoid 
>>>>> repeating the
>>>>> mistakes of JOSE".  This led to, among other things, changing the 
>>>>> key type
>>>>> value for two-coordinate ECC points from "EC" to "EC2" (as 
>>>>> mentioned above),
>>>>> but it also led to a fundamental change in what a COSE Algorithm 
>>>>> indicates.
>>>>> Whereas a JOSE algorithm for ECC signature indicates all three of 
>>>>> signing
>>>>> algorithm, hash algorithm (if applicable), and curve, in COSE the 
>>>>> algorithm
>>>>> indicates only two of those three: the signing algorithm and hash 
>>>>> algorithm
>>>>> (if applicable).  COSE indiates the curve separately. (JOSE also 
>>>>> has an
>>>>> explicit curve parameter, and avoiding this type of redundancy and 
>>>>> risk of
>>>>> inconsistency was the motivation for making the change in COSE.)  
>>>>> There is one
>>>>> exception to this classification, as you know: the ES256K 
>>>>> algorithm.  That was
>>>>> a deliberate exception to the rule, made not for purposes of 
>>>>> restricting the
>>>>> signature algorithm but rather to restrict what the *curve* can be 
>>>>> used for.
>>>>>
>>>>> Because there is already a COSE codepoint for ECDSA using SHA256, 
>>>>> there is no
>>>>> need for a new "ECDSA25519" codepoint -- the existing ES256 
>>>>> codepoint with
>>>>> curve Wei25519 would be the appropriate combination. (There is not 
>>>>> a COSE
>>>>> codepoint for ECDSA using SHAKE256, so some new codepoint would be 
>>>>> needed for
>>>>> the intended Wei448 construction.)
>>>>>
>>>>> The situation for ECDH25519 and ECDH448 is somewhat, but not 
>>>>> entirely,
>>>>> analogous, due to the complications of requiring cofactor ECDH -- 
>>>>> RFC 8152,
>>>>> its "bis" version, and RFC 6090 as referenced therefrom do not 
>>>>> cover cofactor
>>>>> ECDH.  In my opinion the topic of how COSE should handle cofactor 
>>>>> ECDH is
>>>>> something that should be discussed in the COSE WG and a consensus 
>>>>> decision
>>>>> reached.  It may or may not be decided to use a new codepoint for 
>>>>> cofactor
>>>>> ECDH, and so I feel strongly that this document should not 
>>>>> allocate a new
>>>>> codepoint for cofactor ECDH.
>>>>>
>>>>> (Also, COSE ECDH algorithms using KDF specify whether they are for
>>>>> ephemeral-static or static-static, so potentially two new 
>>>>> codepoints would be
>>>>> needed for both variants.)
>>>>>
>>>>> [5] Crypto review
>>>>>
>>>>> I know that the -00 did receive positive review from the CFRG 
>>>>> crypto panel,
>>>>> but there have been some changes to the relevant text in the 
>>>>> ensuing versions
>>>>> (as well as a great deal of things moving around in the 
>>>>> document).  The ADs
>>>>> are going to request a new crypto-panel review to confirm the 
>>>>> positive
>>>>> assessment, but since there is potential for further changes to 
>>>>> the document
>>>>> in light of the other points, we plan to wait to request such a 
>>>>> review until
>>>>> it is clear that the document has stabilized again. According to 
>>>>> my notes the
>>>>> most important sections are currently (-20) 4.1, 4.2, and 4.4, and 
>>>>> at least
>>>>> appendices F, G, and I.
>>>>>
>>>>>
>>>>> In the interest of full disclosure, I do have a few other topics 
>>>>> that I still
>>>>> need to do some more work/investigation on in order to tell if 
>>>>> they are
>>>>> serious issues or not.  These include (but are not limited to):
>>>>>
>>>>> - whether it is harmful to the Internet community to mention 
>>>>> "X25519+" and
>>>>>     "X448+" as new things distinct from X25519/X448 (and thus, maybe
>>>>>     better/preferred) without discussion of whether/why they are 
>>>>> better.  There is
>>>>>     harm to interoperability in specifying new algorithms just 
>>>>> because we can,
>>>>>     and I have seen indications (though perhaps not strong 
>>>>> evidence) that IETF
>>>>>     consensus is to only define new algorithms when there is a 
>>>>> clear need or
>>>>>     benefit from them.  My current inclination is to suggest to 
>>>>> remove
>>>>>     discussion of the "plus" variants since they currently seem 
>>>>> under-motivated,
>>>>>     though of course my opinion may change as I get more information.
>>>>>     (Similar considerations may apply to Wei25519.2 and 
>>>>> Wei25519.-3., etc.)
>>>>>
>>>>> - the specifics of ECDSA+SHA256 on Wei25519.  This is related to a 
>>>>> point made
>>>>>     by Ilari but I am not sure that we ever came to clear 
>>>>> agreement as to what
>>>>>     was in quesiton (let alone the answer).  The premise here is 
>>>>> that for the
>>>>>     existing ECDSA schemes/curves (P-256+SHA256, P-384+SHA384, 
>>>>> P-521+SHA512),
>>>>>     the range of the hash function is very close to the domain of 
>>>>> input for the
>>>>>     signing function (that is, the size of the prime underlying 
>>>>> the field over
>>>>>     which the curve is defined).  In particular, one of the ECDSA 
>>>>> references I
>>>>>     read by following reference chains from this document (sadly, 
>>>>> I did not note
>>>>>     which one) clearly states that the pretreatment of the hash 
>>>>> function output
>>>>>     prior to doing the curve arithmetic for signing involves 
>>>>> subtracting zero or
>>>>>     one multiple of the prime.  However, subtracting one copy of 
>>>>> 2^255-19 from
>>>>>     the "maximum output" of SHA-256 (i.e., 2^256-1) produces a 
>>>>> value that is
>>>>>     still outside of [0, 2^255-19), and so the referenced ECDSA 
>>>>> procedures are
>>>>>     not applicable for the combination of SHA-256 and Wei25519.  
>>>>> Given your
>>>>>     detailed treatment of byte- and bit-encoding, I expect that 
>>>>> you have given a
>>>>>     precise specification of what you expect to happen in this case.
>>>>>     Unfortunately, I think it is clearly out of charter for LWIG 
>>>>> (and arguably a
>>>>>     bad idea for the IETF itself, vs CFRG or NIST) to define new 
>>>>> ECDSA procedures
>>>>>     outside of what NIST has already specified.  Ideally there 
>>>>> would be a NIST
>>>>>     reference we could point to for this class of scenario; if 
>>>>> there is not one
>>>>>     already then my preference would be to ask NIST to produce some
>>>>>     clarification (there are a few NIST staff who participate in 
>>>>> the IETF).
>>>>>
>>>>> - the extent to which normative requirements from other documents are
>>>>>     duplicated in normative language in this document. Generally, 
>>>>> we try to
>>>>>     only have one authoritative source of any given normative 
>>>>> requirement, so
>>>>>     that it's clear what to do if there is any inadvertent 
>>>>> conflict between the
>>>>>     specifications.
>>>>>
>>>>> Thank you again for your efforts so far on this document, and my 
>>>>> apologies
>>>>> that we have not been very effective at helping you to understand 
>>>>> the expected
>>>>> procedures for a successful IETF-consensus RFC.
>>>>>
>>>>> -Ben
>>>>
>>>> -- 
>>>> 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
>>>
>

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 19 Nov 2021 17:41:51 +0200

On Sun, Nov 07, 2021 at 01:00:36PM -0500, Rene Struik wrote:
> Hi Ben:
> 
> A friendly reminder of the reminder of the reminder. Is it really necessary
> (or fair, for that matter) that a simple technical disposition email
> exchange takes more than a half year, with me having to consistently pick up
> dropped balls?

I was trying (months ago) to figure out how exactly the hash-as-integer
in ECDSA signatures is computed when using SHA-3/SHAKE* as hash
function. Summarizing how far I got:

If using FIPS 186-5 draft rules (it is just ordinary binary number
representation already truncated to correct length), one can use the
following algorithm:

* Bitreverse all octets.
* Read octets as big-endian integer.
* Shift integer right to remove excess bits, if any.

If using signhash-style ECDSA API, it probably internally does the last
two steps, leaving just the first one to caller.

However, the problem is that FIPS 186-5 draft is draft, and the current
definitive spec is FIPS 186-4. What happens if one uses FIPS 186-4
(AFAIK, it has been amended to allow SHA-3/SHAKE) rules. FIPS 186-4
itself specifies that:

* The hash as bit string is truncated if it is too long.
* The remainder is specified in X9.62.

The issue here is that what happens here depends on exact specifics of
X9.62 rules, and X9.62 is paywalled. There are some open documents that
have description of ECDSA, but that description might have been
"simplified" using invalid assumptions. So these descriptions are
suspect at best.

For example, SEC1 version 2.0 has an self-contained description that
does not agree with FIPS 186-5 draft. Where things diverge is FIPS 186-5
draft directly taking hash as bit string, whereas SEC1 takes it as octet
string and then converts to bit string. That would be fine for SHA-2,
but it is very much not fine for SHA-3 or SHAKE*.

I would presume that ECDSA in FIPS 186-5 draft and amended FIPS 186-4
are exactly equivalent. If not, that would be a fine footgun...

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Fri, 19 Nov 2021 11:25:49 -0500

Hi Ilari:

Could you elaborate on "There are some open documents that have 
description of ECDSA, but that description might have been "simplified" 
using invalid assumptions. So these descriptions are suspect at best."?

I don't understand why one would read "some open documents" and 
speculate on its accuracy, rather than read the specification of ECDSA 
(which has been out for over 20 (!) years). The actual specification in 
SEC1, BSI, ANSI X9.62-2005, FIPS Pub 186-4 is only two pages, so it 
should be a two-minute read to remind oneself about the correct 
specifications. No need to look up blog posts by bitcoin developers, 
YouTube videos, etc.

The data conversion rules in SEC1 are described in Section 2.3 of SEC 1 
(see [1]), which treats data conversions between octet strings, bit 
strings, finite field elements, and integers, where the output of a hash 
function is a bit-string of fixed length. {SEC1 incorrectly suggests 
that the output of a hash function is an octet string, but due to the 
careful conversion rules in that document the description is still 
correct in any specification (see [1], Section 4.1.3, Step 5.1 - which 
describes conversion of hash function output to bit string in ECDSA and 
the subsequent conversion to integer in Steps 5.3, 5.4, after potential 
truncation in Step 5.2.}

I updated the lwig curve document in June 9, 2021 (nearly half a year 
ago), where I included an example of how ECDSA truncation and conversion 
works (see [2]).

Best regards, Rene

Ref: [1] https://www.secg.org/sec1-v2.pdf

[2] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.3.1

On 2021-11-19 10:41 a.m., Ilari Liusvaara wrote:
> _______________________________________________
> COSE mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cose

---

From: Rene Struik <[email-masked]>
Date: Fri, 19 Nov 2021 11:43:27 -0500

One more note (well, two):

i) What is "amended" FIPS 186-4? I do not know of such a thing (I only 
know of [1] and [2], where only [1] has official status).

You wrote: I would presume that ECDSA in FIPS 186-5 draft and amended FIPS 186-4 are exactly equivalent. If not, that would be a fine footgun...

ii) the output of SHA-hash function family in FIPS 180-4 [3] is a bit string, as are outputs of the SHA3-related functions in FIPS 202 (see Alg. 8 hereof for the output of the sponge function and Section 2.3 for definition of trunc_s() function, which operates on bit strings).

Ref: [1] FIPS Pub 186-4 Digital Signature Standard (July 2013)
[2] FIPS 186-5 - Digital Signature Standard (DSS) (draft, October 31, 2019)comments till January 29, 2020
[3] FIPS PUB 180-4 - Secure Hash Standard (Revision, August 6, 2015)
[4] FIPS Pub 202 - SHA-3 Standard - Permutation-Based Hash and Extendable Output Functions (August 6, 2015)

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 25 Nov 2021 16:55:24 +0200

On Fri, Nov 19, 2021 at 11:25:49AM -0500, Rene Struik wrote:
> Hi Ilari:
> 
> Could you elaborate on "There are some open documents that have description
> of ECDSA, but that description might have been "simplified" using invalid
> assumptions. So these descriptions are suspect at best."?
> 
> I don't understand why one would read "some open documents" and speculate on
> its accuracy, rather than read the specification of ECDSA (which has been
> out for over 20 (!) years). The actual specification in SEC1, BSI, ANSI
> X9.62-2005, FIPS Pub 186-4 is only two pages, so it should be a two-minute
> read to remind oneself about the correct specifications. No need to look up
> blog posts by bitcoin developers, YouTube videos, etc.
> 
> The data conversion rules in SEC1 are described in Section 2.3 of SEC 1 (see
> [1]), which treats data conversions between octet strings, bit strings,
> finite field elements, and integers, where the output of a hash function is
> a bit-string of fixed length. {SEC1 incorrectly suggests that the output of
> a hash function is an octet string, but due to the careful conversion rules
> in that document the description is still correct in any specification (see
> [1], Section 4.1.3, Step 5.1 - which describes conversion of hash function
> output to bit string in ECDSA and the subsequent conversion to integer in
> Steps 5.3, 5.4, after potential truncation in Step 5.2.}
> 
> I updated the lwig curve document in June 9, 2021 (nearly half a year ago),
> where I included an example of how ECDSA truncation and conversion works
> (see [2]).

The problem is that the descriptions of ECDSA based on bit strings and
octet strings are not equivalent when the hash function defines an un-
usual mapping between bit strings and octet strings. Unfortunately,
SHA-3/SHAKE does exactly this (Section B of FIPS pub 202).

In situation like this, one must resolve what happens based on the
definitive specification, which in case of ECDSA is ANSI X9.62-2005.
The above text confirms that it defines ECDSA in terms of bit strings.

If one has ECDSA library that has signhash-style interface written to
SEC1 or BSI specifications (e.g. libnettle), there is a trick to
make things work correctly with SHA-3/SHAKE: bitreverse all the octets
of the hash before signing. This works regardless of truncation.

And looking at LWIG curves draft, I see that sections Q.3.2 and Q.3.3.
have test vectors. I can't get those to match up, specifically things
go off-rails in conversion from E to e.

In section Q.3.2., the first octet of E is 0x74, which impiles that
the first octet of e should be 0x05. Instead, the section gives 0x0E
as the first octet of e.

0x74 -> 0010 1110 -> 000 0010 1110 -> 0000 0101 -> 0x05.

And computing e from E explictly using two different methods (one
directly picks the bits from hash and assembles the bits as e, and
the other is bitreverse followed by reading the number and dividing
the excess bits away) gives:

e=0x05c6e240e373b867cbc37895b0f362fd9445bc74617e92839f13331ec9f40698.

(Which also agrees with above on the first octet.)

In section Q.3.3., the first octet of E is 0xE6, which impiles that
the first octet of e should be 0x19. Instead, the section gives 0x39
as the first octet of e.

0xE6 -> 0110 0111 -> 00 0110 0111 -> 00011001 -> 0x19.

And direct computation of e from E using the same methods yields:

e=0x19d6f88f024cf0ef2b1b4bc6aef97946119a62cfdbede2a724ba64700230f5f408b85930f88022a5e891b0e638201aa0db1b607475f64c86.

(Which also agrees with above on the first octet.)

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Thu, 25 Nov 2021 10:32:29 -0500

Hi Ilari:

I have trouble trying to understand your reasoning, since it seems to 
drift from one email to the next.

I suggest we tackle this topic systematically, so as to get clarity:
a) Specification of ECDSA itself.
Here, you claimed that ECDSA is not well-defined.
Here, I refuted this with reference to SEC1, BSI, ANSI X9.62-2005, FIPS 
186-4.
b) Specification of hash functions.
Here, you claimed that the output of hash functions (in the context of 
ECDSA) is an octet string.
Here, I refuted this with reference to FIPS 186-4, FIPS 180-4, and FIPS 
202, which all specify the output as a bit string.
c) Specification of a specific hash function, viz. SHAKE-128 or SHAKE-256.
Here, you claimed that confusion regarding octet string vs. bit string 
conversion rules is unclear.
To me, if true, this is a problem with FIPS 202 and not with the 
specification of ECDSA. We can go over this, pending request below.

Could you please confirm that you agree with a) and b) above, so that we 
can then restrict discussion to c) only?

Once we have agreed-upon closure on a) and b), we can discuss c) itself.

Rene

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 27 Nov 2021 13:15:17 +0200

On Thu, Nov 25, 2021 at 10:32:29AM -0500, Rene Struik wrote:
> Hi Ilari:
> 
> I have trouble trying to understand your reasoning, since it seems to drift
> from one email to the next.
> 
> Here, I refuted this with reference to FIPS 186-4, FIPS 180-4, and FIPS 202,
> which all specify the output as a bit string.
>
> Could you please confirm that you agree with a) and b) above, so that we can
> then restrict discussion to c) only?
> 

ECDSA is well-defined if instantiated with SHA-1, SHA-2, SHA-3 or SHAKE.
The conversion rules for SHAKE are not unclear, they are defined in
section B of FIPS 202.

To give an example, let's go through converting m to e in for test
vectors in section Q.3.2. of draft-ietf-lwig-curve-representations-22,
closely following definitions of ECDSA and SHAKE. The resulting e fails
to agree:

1) The message to sign is:

"example ECDSA w/ Wei25519 and SHAKE128"

This is taken as correct by definition.

2) Computing 32 octets of SHAKE-128 of the mesage gives (in hex):

74ec48e0d8b9c37c7ad823b5e1d9e83745b4c7c5d02f29381f99196ff2052ce3

Which agrees with what test vectors claim.

3) However, in order to give octet string output, SHAKE internally
appiles b2h algorithm (FIPS 202 s. B.1). Doing h2b (FIPS 202 s. B.1)
in order to undo it and recover the bit string output gives:

0010111000110111000100100000011100011011100111011100001100111110
0101111000011011110001001010110110000111100110110001011111101100
1010001000101101111000111010001100001011111101001001010000011100
1111100010011001100110001111011001001111101000000011010011000111

This is the SHAKE output as bit string.

4) By definition of ECDSA for the instantiating curve, that hash
output as bits is truncated to 253 leftmost bits, giving:

0010111000110111000100100000011100011011100111011100001100111110
0101111000011011110001001010110110000111100110110001011111101100
1010001000101101111000111010001100001011111101001001010000011100
1111100010011001100110001111011001001111101000000011010011000

5) By definition of ECDSA, that bit string is the value of e.
Converting it to base 10 gives:

2612961505806908197104377195031002667796773794190844346899366204629451015832

This disagrees with the test vectors, which claim:
6610721166316936979487388405471295120434869298500984291368316241434902570396.

6) Converting that into hexadecimal gives:

05C6E240E373B867CBC37895B0F362FD9445BC74617E92839F13331EC9F40698

And this also disagrees with the test vectors, which claim:
0e9d891c1b17386f8f5b0476bc3b3d06e8b698f8ba05e52703f3232dfe40a59c.

There is a trick to calculate this: Taking the octet string output,
bitreversing each octet, interpretting result as big-endian integer,
and doing right shift by 3 bits gives the same 5C6...698 result.
This especially handy as it does not require any modifications to
hash or signhash steps.

The e I compute for section Q.3.3. test vectors also disagrees for
similar reasons.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Sat, 27 Nov 2021 12:59:27 -0500

Hi Ilari:

Could you please explicitly confirm closure on a) and b), as I 
requested, so that we can restrict attention to c) below?

Your present "ECDSA is well-defined if instantiated with SHA-1, SHA-2, 
SHA-3 or SHAKE. The conversion rules for SHAKE are not unclear, they are 
defined in section B of FIPS 202" still leaves this nebulous.

If you believe something of ECDSA is ill-defined, please indicate which 
substep of the signing operation in Appendix Q.1 of the lwig curve draft 
[1] is unclear and suggest edits:

Ref: [1] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-22#appendix-Q.1

Thanks, Rene