Subject: Re: [COSE] (please - can we approach this systematically) Re: (on ecdsa codepoints cose iana) Re: next steps for draft-ietf-lwig-curve-representations

From: Rene Struik <[email-masked]>
Date: Wed, 1 Dec 2021 10:01:34 -0500

Hi Ilari:

Can we please get closure on the a) and b) points *today*? This does not 
require programming, experiments, etc., since simply a less than 
1-minute exercise.

There is no need to drag this on forever and I would like to move on.

Rene

On 2021-11-27 12:59 p.m., Rene Struik wrote:
> 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
>
> On 2021-11-27 6:15 a.m., Ilari Liusvaara wrote:
>> 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.
>>>
>>> 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.
>> 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
>
>

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 1 Dec 2021 20:50:32 +0200

On Wed, Dec 01, 2021 at 10:01:34AM -0500, Rene Struik wrote:
> require programming, experiments, etc., since simply a less than 1-minute
> exercise.

a)  ECDSA with hash H is well-defined iff H has well-defined bit string
output.

SHA-2 and SHAKE have well-defined bit string outputs, so all uses of
ECDSA in draft-ietf-lwig-curve-representations are well-defined.

b) The hash function output ECDSA uses is bit string.

With a) and b) closed... to c):

c) SHA-2 and SHAKE have different bitendianess. And this absolutely
has to be taken into account in software ECDSA implmentations that
implement both hashes.

The easiest way to take this difference in account is performing octet-
wise bitreverse on the hash value if hash function used is SHA-3 or
SHAKE. Then the rest can be the same as it is for SHA-2.

And unfortunately the part of FIPS 202 that warns about this difference
is written in really unclear way:

"The convention for interpreting hexadecimal strings as bit strings for
the inputs and outputs of the SHA-3 examples is different from the
convention for other functions on the examples page." 

- FIPS 202, section B, page 25 (page 33 in the PDF).

This is closely related to why I disagree with the test vectors in
sections Q.3.2. and Q.3.3: Those test vectors seem to incorrectly
assume that SHAKE and SHA-2 have the same bitendian.

> > 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
> > 
> > > > I have trouble trying to understand your reasoning, since it
> > > > seems to drift
> > > > Here, I refuted this with reference to FIPS 186-4, FIPS 180-4,
> > > > and FIPS 202,

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Wed, 1 Dec 2021 14:16:10 -0500

Hi Ilari:

Thanks for your note.

To summarize:
a) You agree that ECDSA, in all its incarnations, is well-defined (where 
H is clearly stipulated to be a hash function with bit-string outputs).
b) You believe that the example of Appendix Q.3.2 (w/ SHAKE128 w/ 
output-size d0=256) and that of Appendix Q.3.3 (w/SHAKE256 w/ 
output-size d0=512 bits) use a numerical value E that has been 
incorrectly computed, where your belief is based on a particular 
interpretation of FIPS 202. I think you will agree with me that the 
remainder of the computation is consistent with its stated inputs.

All right, conclusion on my part:
i) [CLOSED] ECDSA w/ SHA256, ECDSA w/ SHAKE128 and ECDSA w/ SHAKE256 
have been correctly specified.
ii) [TO BE CHECKED] Verify output E of the two examples in Q3.2 and Q3.3.

The only action item would be to verify i) above, which (if your claim 
is correct) would result in replacing the single-line E strings in both 
examples by another string and recomputing values that depend on E in 
either case.

I will look into this and let you know my findings.

Please note, however, have no impact on the specification of ECDSA and 
the iana cose codepoints for the invocations with SHAKE* functionality.

To be frank: your comment is just about an (in your mind) one-line 
glitch in two informational examples I included as courtesy to readers 
to illustrate a specification.

Rene

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 1 Dec 2021 11:26:34 -0800

> the iana cose codepoints for the invocations with SHAKE* functionality.

I think there is a question about whether all of NISTs publications
(including examples) are internally consistent.  It is perhaps conceivable
that NIST would choose to make the published examples (and implementations
that used them as test vectors) the "correct" version and change the ECDSA
(or SHA-3/SHAKE) specification to resolve such an inconsistency, so I am
relucant to agree to a "no impact" determination.  (Note that due to
illness and a busy schedule I am not caught up on all the relevant mail, so
maybe I missed some important previous traffic on this topic.)

> to illustrate a specification.

I do not think that the scope of Ilari's concerns is limited to just this
"one-line glitch".  I am hearing the sentiment that NIST has set things up
with a significant risk of a harmful "gotcha" for implementations, and that
by specifying codepoints for ECDSA with SHAKE* we are enabling that
"gotcha" and thereby incurring an ethical responsibility to include a
prominent disclaimer about the "gotcha" and how to avoid it.  This is not
limited to the examples and we incur the responsibility just by specifying
the combination of ECDSA and SHAKE*, independently of whether we provide
examples of such functionality.

-Ben

---

From: Rene Struik <[email-masked]>
Date: Wed, 1 Dec 2021 14:47:30 -0500

Well, this is quite a blanket statement, without any substantiation of 
claims.

If there would have been an issue, I would have expected you to 
immediately call for withdrawing RFC 8692 [1], where - according to the 
IESG ballot evaluation record [2] - you did not bring any conversion 
issues up yourself. Instead, I have been waiting for over half a year 
for a follow-up email on suggested resolution of a few small comments 
you had on the draft (and still have not heard back to this date on the 
June 9, 2021 email).

If you believe nothing of NIST can be trusted, I would have expected an 
email marked "extremely urgent - all ietf" with any substantiation of 
claims so that one can roll up one's sleeves and verify this and define 
follow-up actions accordingly. Instead, I have not seen anything of this 
type.

Given this, I have to say I am struggling with the ethical remarks.

Ref: [1] RFC 8692 - Internet X.509 Public Key Infrastructure, Additional 
Algorithm Identifiers for RSASSA-PSS and ECDSA Using SHAKEs (December 2019)
[2] https://datatracker.ietf.org/doc/rfc8692/ballot/

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 1 Dec 2021 12:22:10 -0800

Hi Rene,

There is no substantiation of claims from me because only conditional or
hypothetical claims are made -- "there is a question of whether NISTS's
publications are internally consistent", "it is perhaps conceivable", "I am
hearing the sentiment [from Ilari]", etc.  My remarks are an attempt to
mediate in the discussion and help you understand the points that I think
Ilari is trying to make, so that the conversation can actually reach a
resolution instead of lingering on and on.  The "ethical" point is (to me)
a natural corollary of the position I see Ilari taking, and so I hope you
will see that topic as part of the conversation that needs to be had.

As I have already said in earlier messages on this topic, I do not consider
myself competent to make a decisive assessment of the question of
SHA3/SHAKE bit order for ECDSA, and must defer to others to figure out the
actual answer.  I believe that at least three people have independently
tried to reach out to NIST to get an answer, but I haven't heard any
updates on those processes recently.

As far as RFC 8692, I reviewed that document in June 2019, well before I
was aware of the potential issue of bit vs byte order in SHA-3/SHAKE
output (as a non-expert, I don't think one could reasonably expect me to
independently discover it).  If, per the previous paragraph, we do reach a
conclusion that there is an issue, then yes, of course I would call for
changing RFC 8692.  But I do not *know* there is a problem, and so find it
hard to advocate for changing RFC 8692 based on the information available
to date.  

I am sorry that you have been waiting for months to hear back from me in
those other threads.  There are others that are in that position as well,
and it is not something I am proud of.  I expect to increase the priority
of this LWIG document once the CFRG crypto-panel review is addressed and it
can come back in front of the IESG for evaluation.

-Ben

---

From: Rene Struik <[email-masked]>
Date: Wed, 1 Dec 2021 15:32:24 -0500

Hi Ben:

With all due respect, one would expect an Area Director to stay away 
from hypothetical and conditional claims (which in this case seem to be 
single-source base, based on Ilari Liusvaara's assessments {where, in 
the past, these were consistently inaccurate, but nevertheless quoted}). 
Moreover, one would expect a Security Area Director to be able to look 
up some specs and read this, if this helps, and not simply declare 
oneself incompetent in the matter.

I do think staying mum for over half a year and throwing other 
gratuitous spokes in the wheel is an AD-role unworthy behavior (but 
perhaps my standards are higher).

Rene

---

From: Rene Struik <[email-masked]>
Date: Wed, 1 Dec 2021 17:16:33 -0500

Hi Ben:

If one had wanted to be consistent in reasoning, one should also have 
pulled draft-ietf-hash-algs out of the AUTH48 queue (since July 14, 2021 
[1]) and should not have assigned a iana cose code point for shake128 
(now, -18, see [2]). None of that happened either, despite these numbers 
to be jealously treated as valuable assets.

Ref: [1] https://datatracker.ietf.org/doc/draft-ietf-cose-hash-algs/history/
[2] https://www.iana.org/assignments/cose/cose.xhtml#algorithms

This being said, as already indicated I will do my own technical due 
diligence (on the example E value computation), since do not base my own 
findings on hearsay or unverified claims.

Rene

---

From: Rene Struik <[email-masked]>
Date: Fri, 3 Dec 2021 11:55:18 -0500

Hi Ilari:

As follow-up of your SHAKE remarks,
a) I reran calculations. These all correspond to the NIST hash function 
validation numbers for posted test vectors. (This suggests that my 
calculations on E in Q3.2 and Q.3.3 were also correct.)
b) I reread FIPS 202. I do believe the specifications of SHA3-256, 
SHA3-384, SHA3-512, SHAKE128, and SHAKE256 are unambiguous and clearly 
have bit-string inputs and outputs. As to Appendix B, this is not part 
of the specification (and not cross-referenced in Section 1-7 of FIPS 
Pub 202). So, Appendix B is irrelevant from a specification perspective 
and should perhaps be ignored.
c) I do believe that you misread Appendix B (see the quote in your email 
below [2]) as to apply to the specification. Instead, Appendix B refers 
to how certain examples of NIST's own website have been codified, 
witness "Examples of the five step mappings and of the six SHA-3 
functions are available at the examples page at NIST’s Computer Security 
Resource Center web site: http://csrc.nist.gov/groups/ST 
/toolkit/examples.html." This has nothing to do with the specification 
of SHA3x itself, just with how data in a particular file on NIST's own 
website is represented.
To illustrate this, simply have a look at the computation of 
SHAKE128(M,d), where M is the empty message (zero-length bit string) 
(see [1]). According to the specification, one has

SHAKE128(M,d)=Keccak[256](M || 1111, d), i.e., in this particular case 
one has b=1600, c=256, r=1344, and M||1111 is the four-bit all-one 
string. After padding, this yields the initial state
S=1111,10.........01 || 0....0 = P0 || 0^c and where P0 has bit-length 
r. One can represent the initial state S in hexadecimal notation as f8, 
00, 00, 00, ...., 01 || 00, ..., 00. In [1], each of these octets is 
represented in bit-reversed order (i.e., what I call in the lwig curve 
draft MSB/lsb), where (see XOR'ed state, end of page 1 of [1]), this 
yields 1f, 00, 00, 00, ..., 80 || 00, ..., 00. To add insult to injury, 
page 2 of [1] writes the so-called lanes of integers as [0,0] = 00, 00, 
00, 00, 00, 00, 00, 1f, whereas the specification (Section 3.1.3) 
stipulates that this should be the bit-string 1111,1000, 0...0 (i.e., 
also here in each lane, the integer representation has been taken with 
lowest-bit on the right (b0....b63 --> b63*2^{63} + b62*2^{62} + ... 
b1*2^1 + b0*2^0). In reality, all steps in the hash computations are bit 
operations, so the "integer representation" displayed in the NIST 
website [1] is somewhat a misnomer.

I think this explains your confusion. In my mind, Appendix B is an 
artifact of the SHA3 competition, where NIST already had some files and, 
for whatever reason, felt it necessary to put language in Appendix B of 
the spec on how to read those files, instead of updating those files 
without any need for representation lingo.

In short: don't read Appendix B.1: (i) it has nothing to do with the 
specification (no cross-referencing); (ii) it seems to be an artifact of 
someone at NIST not wanting to do the work of updating example 
representations that had already been lying around since during the NIST 
SHA3 competition. Admittedly, point (ii) is just speculation on my side.

I hope this settles this issue. If not, please send me the material that 
produced your inputs/outputs and I may have another look. (If I have 
time, I will also recodify the entire Keccak spec in Sage and run all 
experiments that way. If you send code, this is only useful if easy to 
read, and clearly shows bit/byte conversion steps, etc. (without this, 
it is useless). I want to be able to review this by reading only, not by 
running scrypts, etc. Once again, though, I do hope my interpretation 
above settles this.

Best regards, Rene

Ref: [1] 
https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/examples/SHAKE128_Msg0.pdf

[2] Excerpt of your email of Wed Dec 1, 2021:
The convention for interpreting hexadecimal strings as bit strings for 
the inputs and outputs of the SHA-3 examples is different from the 
convention for other functions on the examples page." - FIPS 202, 
section B, page 25 (page 33 in the PDF).

On 2021-12-01 2:16 p.m., Rene Struik wrote:
> Hi Ilari:
>
> Thanks for your note.
>
> To summarize:
> a) You agree that ECDSA, in all its incarnations, is well-defined 
> (where H is clearly stipulated to be a hash function with bit-string 
> outputs).
> is correct) would result in replacing the single-line E strings in 
> both examples by another string and recomputing values that depend on 
> E in either case.
>
>>> 1-minute
>>>> which
>>>>> vectors in section Q.3.2. of 
>>>>> draft-ietf-lwig-curve-representations-22,

---

From: Rene Struik <[email-masked]>
Date: Fri, 3 Dec 2021 17:13:28 -0500

Hi Ilari, all:

I will implement all Keccak functions of FIPS202 from scratch in Sage 
(operating all on bits only) and compare with all intermediate values 
and posted test vectors, just to be sure.

If you have any code or other stuff you wish to share, please send me 
offline.

Thanks, Rene

On 2021-12-03 11:55 a.m., Rene Struik wrote:
> a) I reran calculations. These all correspond to the NIST hash 
> function validation numbers for posted test vectors. (This suggests 
> that my calculations on E in Q3.2 and Q.3.3 were also correct.)
> Pub 202). So, Appendix B is irrelevant from a specification 
> perspective and should perhaps be ignored.
> c) I do believe that you misread Appendix B (see the quote in your 
> email below [2]) as to apply to the specification. Instead, Appendix B 
> refers to how certain examples of NIST's own website have been 
> codified, witness "Examples of the five step mappings and of the six 
> SHA-3 functions are available at the examples page at NIST’s Computer 
> Security Resource Center web site: http://csrc.nist.gov/groups/ST 
> r. One can represent the initial state S in hexadecimal notation as 
> f8, 00, 00, 00, ...., 01 || 00, ..., 00. In [1], each of these octets 
> is represented in bit-reversed order (i.e., what I call in the lwig 
> curve draft MSB/lsb), where (see XOR'ed state, end of page 1 of [1]), 
> this yields 1f, 00, 00, 00, ..., 80 || 00, ..., 00. To add insult to 
> injury, page 2 of [1] writes the so-called lanes of integers as [0,0] 
> = 00, 00, 00, 00, 00, 00, 00, 1f, whereas the specification (Section 
> 3.1.3) stipulates that this should be the bit-string 1111,1000, 0...0 
> (i.e., also here in each lane, the integer representation has been 
> taken with lowest-bit on the right (b0....b63 --> b63*2^{63} + 
> b62*2^{62} + ... b1*2^1 + b0*2^0). In reality, all steps in the hash 
> computations are bit operations, so the "integer representation" 
> displayed in the NIST website [1] is somewhat a misnomer.
>
> artifact of the SHA3 competition, where NIST already had some files 
> and, for whatever reason, felt it necessary to put language in 
> Appendix B of the spec on how to read those files, instead of updating 
> those files without any need for representation lingo.
>
> specification (no cross-referencing); (ii) it seems to be an artifact 
> of someone at NIST not wanting to do the work of updating example 
> representations that had already been lying around since during the 
> NIST SHA3 competition. Admittedly, point (ii) is just speculation on 
> my side.
>
> I hope this settles this issue. If not, please send me the material 
> that produced your inputs/outputs and I may have another look. (If I 
> have time, I will also recodify the entire Keccak spec in Sage and run 
> all experiments that way. If you send code, this is only useful if 
> easy to read, and clearly shows bit/byte conversion steps, etc. 
> (without this, it is useless). I want to be able to review this by 
> reading only, not by running scrypts, etc. Once again, though, I do 
> hope my interpretation above settles this.
>
> Best regards, Rene
>
> Ref: [1] 
>> The only action item would be to verify i) above, which (if your 
>> claim is correct) would result in replacing the single-line E strings 
>> in both examples by another string and recomputing values that depend 
>> on E in either case.
>>
>> Please note, however, have no impact on the specification of ECDSA 
>> and the iana cose codepoints for the invocations with SHAKE* 
>> functionality.
>>
>> glitch in two informational examples I included as courtesy to 
>> readers to illustrate a specification.
>>
>> Rene
>>
>>

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 8 Dec 2021 15:01:18 -0800

Hi Rene,

> single-source base, based on Ilari Liusvaara's assessments {where, in 

To reiterate: my comments here were intended to mediate in the discussion
between you and Ilari.  That is, if you want Ilari to stop raising this
topic, you should (in my opinion) address the questions and concerns as I
phrased them, since I believe that my restatement matches Ilari's intent.
Your answers thus far have addressed only some parts of what I have
understood Ilari to be saying, and thus I expect Ilari to consider his
concerns unaddressed.

> oneself incompetent in the matter.

To be clear, I did spend quite some time with the relevant standards, even
going so far as to spend my employer's money to purchase the relevant ANSI
standard.  I concluded (as you do downthread) that the standards are clear
and consistent and treat inputs/outputs as bit strings.  However, when I
went to go compare what common implementations (openssl, in particular) do
against what the standard says, I ran into some behaviors that I could not
fully explain.  NIST provides some examples that include both bitwise and
hex representations of SHA-3 inputs, that helped me understand that part of
implementation behavior, but I don't remember seeing anything that really
provided clarity on the bitstring interpretation of the outputs.  I believe
that I wrote this all up back in August and included you on the email, so I
thought you had the benefit of this background on what investigation I have
done myself.

> perhaps my standards are higher).

I am surprised to see an attempt to mediate an ongoing discussion between
WG participants be characterized as "throwing other gratuitous spokes in
the wheel".

-Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 8 Dec 2021 15:09:39 -0800

Hi Rene,

> pulled draft-ietf-hash-algs out of the AUTH48 queue (since July 14, 2021 

It's not necessary to specifically pull the document out of the AUTH48
queue in order to place a hold on its publication while a (potential)
technical matter is resolved.  I noted this topic as a github issue on that
draft (https://github.com/cose-wg/X509/issues/42) and we will be making
sure that the github issue list is empty before approving publication of
that document.

> to be jealously treated as valuable assets.

Perhaps it should not have gotten a codepoint, but un-issuing a codepoint
is a very fraught operation.  Almost universally we add additional
references or notes rather than silently remove a registration.  For
example, the Russian GOST signature schemes should not have been assigned
values in the TLS SignatureAlgorithm registry
(https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-16),
as the values were previously in state "reserved" (not "unassigned"), but
since they had been assigned well before the error was discovered, it was
not reasonable to retroactively "un-assign" them and so we have left them
in place with a note about how they came to be (mis-)allocated.

In other words, I have to deal with the facts on the ground, not what I
would like them to be.

> findings on hearsay or unverified claims.

Thank you!

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 9 Dec 2021 15:50:19 +0200

> understood Ilari to be saying, and thus I expect Ilari to consider his

I think this is one the thorniest standards interpretation issues I
have ever came across.

Basically, if one takes the definitions of ECDSA and SHA-3/SHAKE and
cooks an bug-free implementation based on those definitions:

- It will not interoperate with multiple existing implementations.
- It will not agree with ECDSA with SHA-3 examples from NIST.
- Two such implementations would interoperate.

This also impacts RFC 8692. I wonder how many implementations there are
for ECDSA with SHAKE, and how many get the bit order right.

> fully explain. 

The way software implmentations of SHA-3/SHAKE work is that lanes
(64 bits) are mapped into 64-bit words using the bijection:

A'[x,y] = sum(A[x,y,z]*2^z,z,0,63)

Then every operation Keccak permutation does to the state can be
expressed as combination of four simple operations:

- Permuting the word order.
- Rotating the words.
- Performing bitwise AND on words.
- Performing bitwise XOR on words.

Translating words to octets can be described as storing words using
little-endian. Translating octets to strings can be described as
loading words using litle-endian. There are no explicit bitreversals
or other annoying operations.

This comes from Keccak, which was designd for 64-bit little-endian
CPUs. And then the bit order was chosen to be something convinent for
that.

>From that description, one can already tell there is trouble: The
first bit, A[0,0,0], ends up as LSB of A'[0,0]. Little-endian store is
going to place it as LSB of the first octet. Which the generic ECDSA
signhash is going to incorrectly interpret as 8th bit.

> NIST provides some examples that include both bitwise and hex
> representations of SHA-3 inputs, that helped me understand that part
> of implementation behavior, but I don't remember seeing anything that
> really provided clarity on the bitstring interpretation of the
> outputs.  

If one takes the definition of SHA-3/SHAKE from FIPS202, that
definition already gives a bit string. The bad thing about the SHA-3
examples is that they proceed to interpret that bit string as an
octet string, without giving the original bit string output.

If I take the 30-bit example file for SHA3-256 which is hash for:

1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0

And compute what is the hash for that using my translation of FIPS202
into Rust, I get:

0001001100100100111101001111011100000010011110010101101010010111
1000101110001111000100111110101001110101101100100110001100100100
1001110111010100100110000000000111111001010001100101010100110001
1110000010000010001110000010101000000101000111101000110100001011

The example file itself says:

C8 24 2F EF 40 9E 5A E9 D1 F1 C8 57 AE 4D C6 24
B9 2B 19 80 9F 62 AA 8C 07 41 1C 54 A0 78 B1 D0

Turns out these two outputs are related by the b2h/h2b algorithms from
the infamous Appendix B of FIPS 202.

And if one wants to go through NIST SHAKE examples looking for trouble,
there are the SHAKE128 truncation examples. Those show pretty clearly
that the order of bits in octet is LSB to MSB, not the usual MSB to
LSB.

Oh, and in investigating this, I found out that sha3sum (version 1.04)
bitreverses the input (octetwise) if reading in bits mode:

$ echo "1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0" | sha3sum --01 -a 256
04a488169a7fe0f21bfe38ecf30098198bbdb87ba39394b949f5c1c4e691a375 ^-
$ echo "01010011  01011000  01111011  011001 " | sha3sum --01 -a 256
c8242fef409e5ae9d1f1c857ae4dc624b92b19809f62aa8c07411c54a078b1d0 ^-

-Ilari