7
$\begingroup$

FIPS 186-4, sections B.2.1 and B.2.2, discuss two different methods for generating k for DSA / ECDSA. Unless I'm mistaken RFC 6979 discusses another method utilizing HMAC_DRBG.

So what method is the preferred method?

FIPS 186-4 was published July 2013. RFC 6979 was published August 2013. So the RFC is newer but not much newer.

$\endgroup$
  • 1
    $\begingroup$ To be exact B.2 is DSA and B.5 is ECDSA, but they are functionally the same. They are also not significantly changed from 186-3 in June 2009, and random choice (but with different RNGs) goes back to App3 of 186-2 in Jan 2000 (improved Oct 2001) and 186-1 in Dec 1998 and 186 original in May 1994. $\endgroup$ – dave_thompson_085 Dec 26 '16 at 7:34
  • 1
    $\begingroup$ Note: Lily Chen (of NIST) has recently announced that the next revision of FIPS 186 will officially bless the RFC 6979 method $\endgroup$ – poncho Dec 26 '16 at 21:59
7
$\begingroup$

The "normal" way of generating the k value is by doing it randomly, which is what FIPS 186 describes. FIPS 186-4 does not conceptually deviate from previous incarnations of FIPS 186 in that respect.

It so happens that having a good random generator is a tough requirement; some systems (especially embedded) do not have such a generator; it can also be quite inconvenient to make an external PRNG available to the signing engine (it's an extra parameter to pass through several API layers).

One particularly vexing characteristic of random number generation is that it cannot be tested. If you implement ECDSA with a poor generator, then signing will still happen, verifiers will verify, and all unit tests will report that everything is fine. This is the perfect setup for wide-scale blunders, and, indeed, it happened.

Derandomization is a generic methodology for fixing such issues in signature algorithms: it removes the need for a source of randomness, and since it makes the signature deterministic, it can be tested: unit test will not only check that the generated signature is a valid one, but also that it is the valid signature that should be produced. RFC 6979 is an incarnation of derandomization for DSA and ECDSA: generated signatures are fully compatible with standard DSA/ECDSA verifiers, but they are also deterministic and thus can be tested against the test vectors provided in the RFC.

I wrote that RFC all by myself, and pushed it as "informational"; it was not a mandate by NIST or ANSI or whatever, and it did not receive any such "official" blessing. It still went through some reviewing: the draft has been around since March 2011, the test vectors have been independently verified, the internal construction uses HMAC_DRBG (which has itself been thoroughly reviewed), and nobody found anything wrong with it (from a cryptographic point of view)*. RFC 6979 has found its way into some well-known cryptographic libraries, such as Crypto++ of Libgcrypt; it has also been deployed in implementations of Bitcoin "wallets", following a number of incidents where bitcoins were siphoned out because of poor PRNG.


One may note that the mechanism described in RFC 6979 more or less follows the generation method described in section B.2.2 of FIPS 186-4: it really is works by "testing candidates", and the candidates are produced by an "approved RBG" (HMAC_DRBG is one of the NIST-approved PRNG construction). The real deviation is that in RFC 6979, the PRNG is not seeded by gathered entropy, but by the concatenation of the private key and the hash of the signed message. Thus, it may be argued that you can implement RFC 6979 and still comply to the letter of FIPS 186-4.

It is possible to use RFC 6979 with the internal HMAC_DRBG seeded with not only the private key and hashed message, but also some gathered entropy, at which point the signatures are no longer deterministic, and you lost the ability to test the implementation against test vectors, but you then are fully back into the NIST fold, which might be convenient if you aim for full formal compliance to some set of regulations.


(*) It has been remarked that HMAC_DRBG is relatively heavy-handed with regards to the number of invocations of the underlying hash function. In practice, the elliptic-curve computations will dominate the overall cost, the hashing cost being typically less than 10% of the total cost.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Regarding the PS3 incident... that makes me wonder what they were using for their generator. en.wikipedia.org/wiki/PlayStation_3_system_software makes it sound as if the OS is basically FreeBSD. FreeBSD implements /dev/random, doesn't it? So why not just read qlen bytes from /dev/random and (if those bytes are less than q) use that as k? $\endgroup$ – neubert Dec 27 '16 at 23:23
  • 1
    $\begingroup$ Since they always used the same value for k, chances are that either they used a hardcoded value (something which might have been made life easier during development, but the developer forgot to remove afterwards), or they did use a PRNG, but the code that should have done the seeding was dropped by mistake and nobody noticed it. After all, the signatures were generated, and the verification code was happy with them. $\endgroup$ – Thomas Pornin Dec 28 '16 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.