# DSA signatures with related k and unknown payloads

Suppose that we are given DSA parameters $p$, $q$, $g$, a public key $y = g^x$, and two signatures $(r_1,s_1)$ and $(r_2,s_2)$. We are told that $(r_1,s_1)$ and $(r_2,s_2)$ were produced by related nonces $k_1 = k$ and $k_2 = k+1$, but we do not know the value of $k$, and we do not know the messages.

(In practical terms: the PRNG is broken, but it's somehow well-seeded, and we can't submit any messages for signing. We cannot guess the contents of the messages, e.g. they're encrypted with a secret key.)

So we know $$\begin{array}{lll} r_1 = (g^k \bmod p) \hphantom{(g\cdot{})} \mod q && s_1 = k^{-1} (h_1 + x \, r_1) \hphantom{{}-s_2} \mod q \\ r_2 = ((g \cdot g^k) \bmod p) \mod q && s_2 = k^{-1} (h_2 + x \, r_2 - s_2) \mod q \\ \end{array}$$ but we don't know the $h_i$. Can we find the private key?

Does it help to have more (but $\ll q$) known signatures made with $k+2, k+3, \ldots$ (but with unknown messages)?

(Inspired by Attack on DSA with signatures made with k, k+1, k+2)

-
If we know the plain text messages $m_1$ and $m_2$, we know the hash values $h_1$ and $h_2$. Since the signed message is normally known, you might have to expand on exactly what kind of scenario you are considering. –  Henrick Hellström Apr 4 '13 at 20:46
@HenrickHellström This isn't a concrete scenario. I know that in practice, it's rare to have the signatures but not the messages or at least the hashes. That previous question made me wonder whether related $k$s were immediately damning even if the attacker only has the signatures and not the hashes they were made from. –  Gilles Apr 4 '13 at 20:51
The assumption that you don't know the messages is not very realistic. (And if you do know the messages, this is easy to break using Gaussian elimination, as described in the other question you linked to.) –  D.W. Apr 5 '13 at 1:46
@D.W.: I agree this is not a very realistic scenario if the signatures are used in a properly designed protocol, but then again, in a properly designed protocol the randomizers wouldn't be generated this way either. –  Henrick Hellström Apr 5 '13 at 7:32

If the messages are unknown, there are no two messages $m_i, m_j$ such that $m_i = m_j$ and the messages have sufficiently high entropy (which might be shared across several messages, if the hash function is a CSOWF and the messages e.g. have low entropy unique sub strings or are made unique in some other way), and the underlying hash function is secure in a random oracle model and has an output bit length equal to or greater than $2n$ such that $q \lt 2^n$ (see below), then this scheme is secure in this hypothetical scenario.

Firstly, note that

$s_i \equiv h(m_i)/(k+i) + xr_i/(k+i) \pmod q$

Case #1 - large untruncated hashes (non-DSA compliant)

$h^\prime_i = h(m_i)(k+i)^{-1} \mod q$

Define the adversary $A_h$ such that $i$ is fixed, and that $A_h$ might submit any $j \ne i$ to the oracle and get the corresponding $h^\prime_j$ value. Then $A_h$ submits $i$ and gets either $h^\prime_i$ or $z \leftarrow_{uniform} \mathbb Z_q$. $A_h$ might continue to submit any queries to the oracle subject to the first constraint that $j \ne i$. If the function $h(m)$ and the $m_i$ messages have the assumed properties, $A_h$ will have but negligible probability of succeeding.

As noted, the assumption about the uniformity of $h(m)$ is problematic if the underlying implementation conforms to FIPS 186-3 with the only exception of the way the randomizer values are generated. Since FIPS 186-3 prescribes that the left most $n = |q|$ bits of $h(m)$ are used, we will get a clear bias with $h(m) < 2^n-q$ being twice as probable than $2^n-q \le h(m) < q$. However, if the hash output is at least $cn$ and is not truncated before being reduced $\mod q$ this bias will be at most $2^{-n(c-1)}$

Secondly, note that we now have

$s_i = h^\prime_i + xr_i(k + i)^{-1} \mod q$

Define the adversary $A_s$ such that $A_s$ might adaptively submit any $j$ subject to the same conditions as above. When $A_s$ submits $j = i$, the oracle returns either $s_i$ or $w \leftarrow_{uniform} \mathbb Z_q$. $A_s$ might then continue to submit queries as above.

Now, note that for any $w$ and $i$ there exists a value $z_{w,i}$ such that

$w = z_{w,i} + xr_i(k + i)^{-1} \mod q$

Hence, if the adversary $A_s$ is able to tell if the $s$-oracle returned $w$ or $s_i$, we have a distinguisher for $A_h$ as well, by noting that $A_s$ is able to tell $z_{w,i}$ from $h^\prime_i$.

Case #2 - truncated or equisized hashes (DSA compliant)

If the hash output is exactly $n$ bits in length, there will be a significant bias in $h(m) \pmod q$ as noted above. Given the other assumptions regarding the messages and the hash function, we might assume this is the only bias we have to consider. However, presuming $q$ is a uniform prime in the range $2^{n-1} \lt q \lt 2^n$, multiplication by $(k+i)^{-1} \mod q$ will mask this bias to some extent. Given that both terms of the right hand expression share this factor, the above proof is not valid in this case. Intuitively, though, the combined (and theoretically detectable) bias of $h(m_i) + xr_i$ ought to be masked to some reasonable extent by the $(k+1)^{-1}$ factor sequence, as long as the total number of signatures is not large enough.

-
I can see that might require some additional explanation, yes. –  Henrick Hellström Apr 5 '13 at 8:07
But hash values are not uniform modulo q; there is a slight bias (in standard DSA, the hash value is first truncated to the bit length of q, then reduced modulo q). Bleichenbacher found an attack when k is chosen with such a bias (works with 2^63 known message/signature pairs for a 160-bit q, if I remember correctly). I would not be surprised if there was a similar attack in this case. –  Thomas Pornin Apr 5 '13 at 13:12

Even if the messages are not known, if the messages are low-entropy, then this can be broken.

In particular, given a guess at message $m_1$, you can use the DSA signature verification algorithm to test your guess. So keep guessing until you find $m_1$; if $m_1$ is low-entropy, this shouldn't take too long. Similarly, find $m_2$. Then, once you know $m_1,m_2$, you know $h_1,h_2$, and you can solve the system of equations using Gaussian elimination. This reveals the private key $x$. (The latter part is the attack procedure described in the answer to the other question you linked to.) Therefore, the effectiveness of this attack method is determined by how easy it is to guess the messages used.

For example, if each message is a 4-digit PIN, and we have the corresponding DSA signatures, this will be easy to break: after $2 \times 10^4$ guesses (and applications of the DSA signature verification algorithm), you will know both messages, and then the private key falls out immediately.

Thanks to @poncho for this improved attack.

-
Actually, it'd be more practical to check the guesses for the messages using the standard DSA signature algorithm; it takes longer than doing a Gaussian elimination; on the other hand, we don't have to check each potential pair of messages $(m_1, m_2)$, we can check each message individually. This reduces the number of tests from $10^8$ to $2 \cdot 10^4$ in your scenario, –  poncho Apr 5 '13 at 2:06
@poncho, I don't understand the attack you have in mind. Care to elaborate? Are you sure what you are talking about works? How is the attacker going to apply the standard DSA signature algorithm to the message without knowing $x$ or $k$? (Keep in mind, neither $k$ nor $x$ are known to the attacker a priori.) –  D.W. Apr 5 '13 at 4:30
My assumption here is that the messages are unknown. If they were successfully guessed, then the straightforward recovery of $k$ would work. –  Gilles Apr 5 '13 at 14:30
@D.W.: sorry about that; I meant the DSA signature verification algorithm. –  poncho Apr 5 '13 at 14:31
@poncho, ahh, thanks, that is much better. I've revised my answer accordingly. Thank you! –  D.W. Apr 5 '13 at 17:47