Bug in deterministic nonce generation for ECDSA using P-521 with SHA512

[mcarrickscott]

There seems to be an error in line 23 of

https://github.com/usnistgov/ACVP-Server/blob/master/gen-val/src/crypto/src/NIST.CVP.ACVTS.Libraries.Crypto/DSA.ECC/DeterministicNonceProvider.cs

The code does not appear to follow step 1.2 of the nonce generation process described in A3.3 of fips186-5

The conversion (padding) of the Hash to an octet string should follow the process described in B2.4, which takes the modulus n as an input. However the padding applied in line 23 does not consider n (orderN). Indeed the length of n, required for correct padding, is not considered until line 44.

Note this is only an issue when the length of n does not match the the output length of the hash. However it does affect the case for P-521 using SHA512 (for example).

[livebe01]

Thanks for sharing this. We'll take a look.

By the way, I'm curious how you discovered this. Were you testing an ECDSA implementation and found that some test cases were failing when you expected them to pass?

[mcarrickscott]

That is basically it. Tried 3 independent implementations, couldn't get a match with the test vectors. So finally went poking around your C# source code in a search for an answer.

…

On Fri, Jan 3, 2025 at 10:29 PM livebe01 ***@***.***> wrote: Thanks for sharing this. We'll take a look. By the way, I'm curious how you discovered this. Were you testing an ECDSA implementation and found that some test cases were failing when you expected them to pass? — Reply to this email directly, view it on GitHub <#377 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAU3ZDTON2KFJYNMCWIWJL32I3JKFAVCNFSM6AAAAABT4GUM5OVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKNRZGY2DSMJUHE> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[jbrock24]

Hi @mcarrickscott, I believe I've found the missing steps outside of the method. Within the EccDSA class the Sign method has that step on lines 132 & 136. Please let me know if there are any further questions or concerns.

[mcarrickscott]

Thanks for your response. Considering the 3 lines of code from the sign() function prior to calling Getnonce(), in the context of P-521, basically they result in e=SHA512(message)

Drilling down a bit deeper into Getnonce()... In the line

var seedMaterial = new BitString(privateD).PadToModulusMsb(32).ConcatenateBits(new BitString(hashedMessage).PadToModulusMsb(32));

There are two problems. The first PadToModulus() extends privateD unnecessarily from 528 bits to 544 bits (a 32-bit boundary). The second PadToModulus() is a no-op as the hashedMessage is already on such a boundary – its 512 bits. It actually should be extended to 528 bits by prepending two 0 bytes.

In short doing it the NIST way I get

0x00 0x00 privateD | hashedMessage

and using this I can reproduce the NIST test vectors

Whereas the RFC6979 way is

privateD | 0x00 0x00 hashedMessage

and doing it this way I can reproduce the RFC6979 test vectors.

They can’t both be right!