FIPS 186 compliant mode where message-dependent pseudorandom values are used as ‘additional input’?

[emanjon]

People have suggested a FIPS 186 compliant mode where message-dependent pseudorandom values are used as ‘additional input’ in the random number generation for randomized ECDSA [FIPS 186]. Such a mode could compliment the current hedged construction based on Deterministic ECDSA [RFC 6979].
https://blogs.cisco.com/security/fips-and-deterministic-ecdsa-achieving-robust-security-and-conformance

[FiloSottile]

I believe Hedged ECDSA as described in draft-irtf-cfrg-det-sigs-with-noise-03 is already FIPS 186-5 compliant.

It's using HMAC_DRBG consistently with SP 800-90Ar1, with Z as entropy (which has length sufficient to provide the requested DRBG security strength for the ECDSA key size, double that in fact), no nonce (as allowed by SP 800-90Ar1, Sections 8.6.7 and 9.1), and a personalization_string of 000... || int2octets(x) || 000... || bits2octets(h1) (consistent with SP 800-90Ar1, Section 8.7.1, "The personalization string may contain secret information").

Alternatively, one could argue that int2octets(x) || 000... is the nonce, and Z || 000... is the entropy (which is allowed to be longer than the actual bits of entropy it contains). Yet another argument could be that the first half of Z is the entropy (since e.g. a 256 bit ECDSA key requires a DRGB with minimum security strength of 128 per SP 800-57 Part 1), and the second half is the nonce. We have options (and as I type this I think I like that last one the most).

It then uses this cryptographically strong DRBG to generate the nonce according to FIPS 186-5, Appendix A.3.2, "Per-Message Secret Number Generation of Private Keys by Rejection Sampling". RFC 6979 checks 0 < x < q, while Appendix A.4.2 checks 0 <= x < q-1 and then returns x + 1 (which is way more annoying to implement), but note that Appendix A.3.2 says "Convert returned_bits to the (non-negative) integer k using the procedure in Appendix A.4.2 or an equivalent process" (emphasis mine).

Are there concerns about the compliance of the current version? I actually landed here by first rederiving the exact same scheme (except for the 000... padding) as a FIPS-compliant hedged ECDSA I will need to implement, and then remembering about this draft, and I was happy to find it similarly compliant.

[FiloSottile]

Ah, actually, more evidence from SP 800-90Ar1, Section 8.6.7 in support of just calling Z entropy+nonce.

For case 1 above, the random value could be acquired from the same source and at the same time as the entropy input. In this case, the seed could be considered to be constructed from an “extra strong” entropy input and the optional personalization string, where the entropy for the entropy input is equal to or greater than (3/2 security_strength) bits.

This is very reasonable, especially for ECDSA nonce generation, because this use case is susceptible to birthday bounds. This is explicitly called out.

The nonce provides greater assurance that the DRBG provides security_strength bits of security to the consuming application. If a DRBG were instantiated many times without a nonce, a compromise could become more likely. In some consuming applications, a single DRBG compromise could reveal long-term secrets (e.g., a compromise of the DSA per-message secret could reveal the signing key).

Given P-256, P-384, and P-521 require a security strength of 128, 192, and 256 respectively per SP 800-57 Part 1 Rev. 5, Section 5.6.1.1, the Z length of 256, 384, and 528 respectively is always greater than 3/2 security_strength.

Also, SHA-256 or better is sufficient for all those security strengths per SP 800-57 Part 1 Rev. 5, Section 5.6.1.2. From SP 800-90Ar1, Section 10.1:

The maximum security strength that can be supported by each DRBG based on a hash function is the security strength of the hash function for pre-image resistance; these security strengths are provided in [SP 800-107]. [SP 800-57] identifies hash functions that can be used to support a required security strength.

[ethorm]

Thanks @FiloSottile,
I tried to look into this and to me it is not clear that the current Hedged ECDSA is compliant to FIPS 186-5. You wrote:

It then uses this cryptographically strong DRBG to generate the nonce according to FIPS 186-5, Appendix A.3.2, "Per-Message Secret Number Generation of Private Keys by Rejection Sampling". RFC 6979 checks 0 < x < q, while Appendix A.4.2 checks 0 <= x < q-1 and then returns x + 1 (which is way more annoying to implement), but note that Appendix A.3.2 says "Convert returned_bits to the (non-negative) integer k using the procedure in Appendix A.4.2 or an equivalent process" (emphasis mine).

FIPS 186-5 also says:

Two processes are equivalent if the same output is produced when the same values are input to each process (either as input parameters, as values made available during the process, or both).

But, compared to RFC 6979, FIPS 186-5 act slightly different on returned_bits by shifting with +1 as you note, and RFC 6979 also checks that k does not result in an r value that is 0. While these things are irrelevant to security and the latter will never happen in practice, the two processes seem to not be equivalent by the given definition.

Any thoughts on these things?

[FiloSottile]

Our argument was that bits from the DRBG are not an input parameter of Appendix A.3.2 (because they are not deterministic and the DRBG is not rigidly specified, and indeed they are not listed as inputs), so when Appendix A.3.2 says "The following procedure or its equivalent" we can apply the RFC 6979 process to produce an "Integer in the interval [1, n–1]" from an abstract DRBG.

Note that [0, n-2]+1 and [1, n-1] are strictly equivalent, we don't rely on the negligible chance of hitting 0.

Moreover, these are appendixes that use "may", not "shall".

We linked our lab to this issue, and they were satisfied.