Why go through the trouble of using the HMAC_DRBG process, instead of simply hashing [message | private key] to calculate $k$ for deterministic ECDSA?

If the resulting $k$ or the signature is invalid, then a known byte value can be appended to the input, and re-hashed, until an acceptable result is achieved: k=h([message|privateKey|0x00 … 0x00])

As many 0x00 bytes as the number of iterations it takes.

Am I missing an inherent weakness here?

Edit: If the hash function output length is smaller than the curve order, multiple hash outputs (produced by appending a known byte, similar to what was described above) can be concatenated as necessary: k=[ h([message|privateKey]) | h([message|privateKey|0x00]) ... ] Once you have enough output, you can then truncate it to match the curve order bit length.

And if the resulting $k$ or the signature is no good, then restart with the known byte appended: k=[ h([message|privateKey|0x00]) | h([message|privateKey|0x00 0x00]) ... ]

And so on, until an acceptable $k$ is produced.

  • $\begingroup$ It decouples the output length of the hash function from the required length of k. I would have said it was to provide security even in the presence of a collision in the hash function, but I don't think it does. $\endgroup$ – Michael Nov 30 '14 at 9:54
  • $\begingroup$ Thanks Michael. I added the necessary info to the question. As for the collisions, I don't see them being an issue. $\endgroup$ – thera Nov 30 '14 at 12:30
  • $\begingroup$ How would you handle the case when the order of generator is of larger bit size than your hash function digest (e.g. SHA-256 and P-521) ? $\endgroup$ – Ruggero Nov 30 '14 at 19:23
  • $\begingroup$ That was Michael's point as well I believe. I initially had thought you would just restrict the usage to curves smaller than the hash size, but it would also be feasible to just do the iteration I described and keep appending until enough output is available to match the curve order bit length. $\endgroup$ – thera Nov 30 '14 at 21:06
  • $\begingroup$ Or you could use a sponge based hash like SHA3 that can have an arbitrary output length. $\endgroup$ – John Meacham Nov 30 '14 at 22:02

Deterministic signatures are safe in the random oracle model. Using HMAC_DRBG allowed me to rely on existing research on the safety of that construction and how close it comes to a "true" random oracle. If I had used any other "handmade" construction, then I would have had to provide extensive analysis on why it is secure. Being naturally lazy, I chose HMAC_DRBG.

Moreover, this use of HMAC_DRBG makes the end result more "convincing" -- and a large part of specifying a cryptographic algorithm as a RFC is to get other people to use it.

(If I had been aware of its existence at that time, I might have considered HKDF instead of HMAC_DRBG, but that does not matter much in practice.)

  • 1
    $\begingroup$ Is prof Bernstein providing any "extensive analysis" on why it is secure his deterministic nonce derivation in EdDSA ? $\endgroup$ – Ruggero Mar 11 '15 at 13:50
  • 1
    $\begingroup$ In their article, the EdDSA authors mostly say that: "Standard PRF hypotheses imply that this pseudorandom session key r is indistinguishable from a truly random string generated independently for each M, so there is no loss of security". This is a bit too terse to be called "extensive analysis" but it makes sense. For more analysis, you may read the Leurent & Nguyen article cited from RFC 6979 (under the reference "LN2009"); that article includes some analysis and pointers. $\endgroup$ – Thomas Pornin Mar 11 '15 at 14:34

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.