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
