# Exactly what RNG weaknesses endanger (EC)DSA?

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?

• 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)?
– SEJPM
Dec 14 '18 at 14:02
• @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.
– 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.
• 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...