Exactly what RNG weaknesses endanger (EC)DSA?

Question

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?

Answer 1

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.