12
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 22:02

1 Answer 1

Reset to default
12
$\begingroup$

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.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Is prof Bernstein providing any "extensive analysis" on why it is secure his deterministic nonce derivation in EdDSA ? $\endgroup$
    – Ruggero
    Mar 11, 2015 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, 2015 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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