RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction

One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process. Even slight biases in that process may be turned into attacks on the signature schemes.

How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?

  • 1
    $\begingroup$ Does this Q&A answer your question? Also would you prefer the questions to be merged (ie comments and answers would all live under a single question)? $\endgroup$ – SEJPM Dec 14 '18 at 14:02
  • $\begingroup$ @SEJPM: I had missed this Q&A, and it is definitely very relevant to my question. However the question there is restricted to a particular attack, I'm asking for a characterization of what misguided choices of $k$ allow attack. Yehuda Lindell's answer gives two examples, this Q&A another. $\endgroup$ – fgrieu Dec 14 '18 at 17:49

It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}\cdot(H(m_1)+x\cdot r) \bmod q$ and $s_2=k^{-1}\cdot(H(m_2)+x\cdot r) \bmod q$. Computing $d = \frac{s_1}{s_2} \bmod q$ one obtains $d = \frac{H(m_1) + r\cdot x}{H(m_2) + r\cdot x} \bmod q$, and so $(d-1)\cdot r \cdot x = H(m_1) - d \cdot H(m_2)$ yielding $x = \frac{H(m_1)-d\cdot H(m_2)}{(d-1)\cdot r} \bmod q$.

One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.

The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.

| improve this answer | |
  • $\begingroup$ Generating the random $k$ using a LCG (as the linked paper considers) is well beyond "slight biases". That's giving up on all true entropy beyond that in the initial state of the LCG, and linking successive values with a simple public transformation, rather than a strong secret one in de-randomized (EC)DSA. I do agree that only good randomness (true or pseudo) should be used, but I find it interesting to investigate "what if" scenarios where it does not. Not all people are as careful as I am with their source of entropy, its monitoring, and post-conditioning... $\endgroup$ – fgrieu Dec 14 '18 at 8:06
  • 1
    $\begingroup$ @fgrieu I have updated the answer to relate to small local biases as well. $\endgroup$ – Yehuda Lindell Dec 14 '18 at 9:02

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.