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, ReneRef: [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). 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 On 2021-12-01 1:50 p.m., Ilari Liusvaara wrote:On Wed, Dec 01, 2021 at 10:01:34AM -0500, Rene Struik wrote: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-minuteexercise.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.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 aredefined 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.1Thanks, 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:ECDSA is well-defined if instantiated with SHA-1, SHA-2, SHA-3 or SHAKE.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, FIPS186-4. b) Specification of hash functions.Here, you claimed that the output of hash functions (in the context ofECDSA) 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 stringconversion 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.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 testvectors in section Q.3.2. of draft-ietf-lwig-curve-representations-22, closely following definitions of ECDSA and SHAKE. The resulting e failsto 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:2612961505806908197104377195031002667796773794190844346899366204629451015832This 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 protected] | Skype: rstruik cell: +1 (647) 867-5658 | US: +1 (415) 287-3867 _______________________________________________ COSE mailing list [email protected] https://www.ietf.org/mailman/listinfo/cose
