Comments from Danny Niu - RNG use in ECDSA

[emanjon]

I'd like to let the interested parties know that, I've written a experimental C implementation of the draft. If anyone's interested in benchmarking or any kind of testing, I'd love to assist. I've also raised a few implementation-related issue at crypto.stackexchange.com/a/106599/36960 and I'll summarize here:

1. The draft treats ECDSA RNG as a white box and penetrates the PRNG boundary to seed it, which is something NIST specifies not to do. This isn't too big an issue, as there are ways to maintain functionality opacity.

2. The draft underspecifies how to use KMAC when the hash function is SHAKE. The way I prefer is to persuade NIST to specify and approve a permutation-based PRNG and use that instead. However in the interim time, we could add details on how KMAC should be used with HMAC-DRBG, but again, it'll penetrate the PRNG boundary. What's more, KMAC had not been approved for use with HMAC-DRBG yet.

[dannyniu]

Answering the email

1. I am correct in my understanding that this is concerning deterministic ECDSA (RFC 6979) and not just the hedged construction in draft-irtf-cfrg-det-sigs-with-noise?

Actually I directed my 1st comment directly at the new ECDSA hedged RNG construction.

I'll have to object to the construction in the new https://www.ietf.org/archive/id/draft-irtf-cfrg-det-sigs-with-noise-02.html - It uses 2 different Z (Zd and Zf) which completely breaks PRNG boundary. I'll assume with best of my faith that this is an oversight caused by not being able to realize the rationales that I'll provide below.

If you look at NIST.SP.800-90Ar1 Page 44 section 10.1.2.2, there's only 1 single provided_data in the HMAC_DRBG Update process, and RFC-6979 was drafted in such way that PRNG behavior can be preserved. See section 3.3 of RFC-6979. So by changing the value(s) of Z, you're really changing an established CSPRNG algorithm!

My interpretation on this is that the "deterministic" ECDSA should be implementable by combining an existing signing implementation with an existing HMAC-DRBG implementation. If the new hedged ECDSA use 2 different Zs, then it will be impossible to combine them in such way.

2. I don’t see excactly what is missing for KMAC. Maybe you can describe in more detail in the GitHub issue?

Actually, there isn't much missing for KMAC, except we need to specify whether to invoke KMAC as a XOF (with L=0) or a fixed-length PRF (with L being 32, 48, 64 66 (P-521)).

The other thing is just I hoped NIST can specify a DRBG based on Keccak-1600 so that something more efficient than KMAC can be adopted in the future.

More on PRNG boundary

I was recently amazed by this StackExchange post which talks about "tell, don't ask" paradigm, which I think is nice. I think it's best to:

• tell the PRNG we want to seed you with nonce, privkey, an H(msg),
• rather than asking "what's your block-length", than doing seed nonce, pad, seed privkey, pad, seed H(msg).

The HMAC calls in step d and f are part of PRNG operation, and they shouldn't be exposed, not to mention altered. Querying the block size of the hash function is the most I consider reasonable in this circumstance.

---

Existing experience

My parallel effort on ML-DSA and SLH-DSA also shows that it's easiest when hedged generation of nonce is part of algorithm, and especially easy when it can switch seemlessly between hedged and deterministic.

My EdDSA was able to be modified in-place. However, my existing implementation for ECDSA (as well as the similar SM2 DSS from China - my homeland):

1. didn't reserve a space for an instance of HMAC-DRBG
2. was intended to be combined with an external PRNG from day-one of its design

Therefore I implemented an external Signer.

[emanjon]

Hi Danny,

Yes, we missed that different random number is not compatible with HMAC_DRBG. The reason that we suggested different random numbers was that this improves security against second-order DPA attacks. We agree that compliance with HMAC_DRBG seems more important. I have made commits that change to a single random value Z and gives you acknowledgement.

https://author-tools.ietf.org/api/iddiff?doc_1=draft-irtf-cfrg-det-sigs-with-noise&url_2=https://cfrg.github.io/draft-irtf-cfrg-det-sigs-with-noise/draft-irtf-cfrg-det-sigs-with-noise.txt

Actually, there isn't much missing for KMAC, except we need to specify whether to invoke KMAC as a XOF (with L=0) or a fixed-length PRF (with L being 32, 48, 64 66 (P-521)).

Reading the current text is seems to be specified on a RECOMMENDED level to use the same value L as in the hashing of the message. I.e. when ECDSA is used with SHAKE128(M, 256) and SHAKE256(M, 512) as in RFC 8692 and FIPS-186-5, it is RECOMMENDED to use KMAC128(K, M, 256, "") and KMAC128(K, M, 512, ""). Note that L is specified in bits.

[dannyniu]

Thanks, appreciated.

Note that for the P-521 instance, 521 bits are needed, otherwise lattice attack will work.

to use KMAC128(K, M, 256, "") and KMAC128(K, M, 512, "").

You mean KMAC256(K, M, 512, "") with the 2nd instance?

[emanjon]

@dannyniu Do you by any way have test vectors? Taylor R Campbell are asking for test vectors in #4

[dannyniu]

@emanjon I can generate some, but some details are needed:

1. (for ECDSA & EdDSA) against which revision should I generate my test vectors,
2. (for ECDSA) which curves and hash lengths should I include? I'd go for P-256 and P-384 because that 2 are the ones I've implemented and also marked as recommended in one of the IANA registeries; whereas with P-521, we need to agree on whether to invoke KMAC with 521-bit output, or 2 successive 512-bit output with truncation.
3. (for ECDSA) we'd be needing SHA-2+HMAC test vectors I presume?
4. (for ECDSA) when instantiating with FIPS-202, do I use SHAKE+KMAC or the regular SHA-3 instances with HMAC (or some other combination)?
5. (misc) would anyone be interested in a set of BLAKE2 test vectors? BLAKE2 have both hashing and PRF modes.

[dannyniu]

@ethorm I checked out the new draft, and noticed a reference to "section 3.3 of RFC-8391". However, there's no section 3.3 in RFC-8391, there's only 1 2nd-level subsection in RFC-8391.

[ethorm]

Thank you @dannyniu, fixed it to reference RFC 6979.

[ethorm]

Thanks @dannyniu,

Note that for the P-521 instance, 521 bits are needed, otherwise lattice attack will work.

I assume that you mean that step h.2 of https://datatracker.ietf.org/doc/html/rfc6979#section-3.2 will be iterated twice. John just made a commit recommending that KMAC outputs at least qlen bits (more exactly max(d, qlen)), where qlen is from RFC 6979.

[dannyniu]

@ethorm It looks great.

I was going to say "exactly 521 bits may cause difficulty for octet-oriented HMAC-DRBG implementations instantiated with KMAC", because L=521 is baked into domain separation informations. So I prefer the wording change to "at least max(d, qlen) bits"; or allow L=0 to make the output idempotent (which I find more preferable) just like when instantiating with HMAC-SHA-512.

But I think I'll manage by breaking curve abstraction layer a bit. I'll let others raise their concern. At worst, I'll omit test vectors for P-521. When the next revision is posted on IETF data tracker, I'll try find time write up codes to generate test vectors.

[dannyniu]

I found some problem.

The current wording makes P-521+KMAC-256 unimplementable without making some breaking changes to existing codebase, both established ones such as LibreSSL, OpenSSL, NSS, etc. as well as my own MySuiteA. This is mostly with respect to octet-oriented assumptions in current implementations.

Vast majority of existing codes are octet-oriented, this means that requesting a fraction bytes' output is impossible since lengths are specified in units of bytes (and are integer types). Therefore when instantiating HMAC-DRBG with KMAC-256 to use with P-521, the biggest common denominator is not 521 bits, but rather 66 bytes.

One possible way to implement this in signing subroutine would be:

1. to request 66 bytes,
2. interpret the bytes and convert it to big-endian integer (using OS2IP).
3. right-shift 7 bits to get a 521-bit random number - this emulates what leftmost(bitstr) does.

On the same note, I recommend the following change to accomondate KMAC-instantiated HMAC-DRBG: change step h in generation of k to:

h. Apply the following algorithms until a proper value is found for k:

1. if KMAC is used:

   `T = KMAC-{128,256}(K, V, ceil(qlen/8)*8, "")

2. if HMAC is used, repeat the following steps until tlen >= qlen:

   2.1. V = HMAC_K(V)
   2.2. T = T || V

3. Compute k = bits2int(leftmost(T, qlen))

   If that value of k is within the [1,q-1], and is suitable for ...
   ... Otherwise compute:

   K = KMAC_K(V || 0)
   V = KMAC_K(V)

   and repeat this step h.

I said before not to break PRNG boundary, but since we're instantiating HMAC-DRBG with the unapproved combination of KMAC, the efficiency gain worth making the change. (although it's more preferable NIST specify a Keccak permutation-based PRNG.)

[emanjon]

Byte alignment seems like a good idea to align with libraries. Requesting 66 bytes seems like a good idea.

[FiloSottile]

bits2int is already defined to do a right shift in Section 2.3.2, there is no need for an explicit leftmost function.

(The right shift is actually much more annoying to implement than masking the 7 most significant bits, but we already need to implement it for ECDSA's hash2int, so might as well reuse it.)

[emanjon]

I made a PR that changes the recommended output lenght of KMAC to 8*ceil(qlen/8). As FiloScottile commented bit2ins is already doing a rightshift.