# Is DSA vulnerable if verifier doesn't check r' > 0?

If a DSA implementation neglects to check $r' > 0$ when verifying signatures, what are the consequences? Creating a forged $s$ would seem to require solving for $k$

$g^k mod\ p = nq$

which is still a hard problem?

Assume that all other range checks for parameters are being carried out (particularly $r' < q$)

Let's write down naming conventions explicitly:

• We work modulo prime $p$. There is a smaller prime $q$ that divides $p-1$; we write $p = 1 + qn$ for some integer $n$. Traditionally, the sizes of $p$ and $q$ would have been 1024 and 160 bits, respectively; nowadays, we would rather use 2048 and 256 bits.

• $g$ is an integer modulo $p$ of order $q$; i.e. $1 < g < p$, and $g^q = 1 \pmod p$.

• Private key is some non-zero integer $x$ modulo $q$.

• Public key is: $y = g^x \pmod p$

• Normal signature generation is:

• Generate a random non-zero $k$ modulo $q$.

• Compute $r = g^k \pmod p \pmod q$ (we compute the exponentiation modulo $p$, and the result, which is in the $0$ to $p-1$ range, is further reduced modulo $q$). At that point the signer is supposed to check that $r \neq 0$; if that very improbable case shows up, then he should start again with a new random $k$.

• Compute $s = (h+xr)/k \pmod q$ where $h$ is the hash of the message, suitably truncated and reduced modulo $q$.

• Normal signature verification is:

• Verify that $r$ and $s$ are in the $0$ to $q-1$ range.

• Verify that $r \neq 0$.

• Compute: $w = 1/s \pmod q$

• Compute: $r' = g^{wh} y^{wr} \pmod p \pmod q$

• Signature is considered valid if and only if $r = r'$.

The question is then: what if the verifier does not check that $r\neq 0$ ? In other terms, if a signature such that $r = 0$ is deemed acceptable, then does this allow attackers to forge signatures?

The attacker succeeds if he can show values $(r, s)$ that fulfill the equation:

$$g^{wh} y^{wr} \pmod p \pmod q = r$$

where $h$ is a given (hash function output). If $r = 0$, then this simplifies to:

$$g^{wh} = 0 \pmod p \pmod q$$

If there is an integer $u$ modulo $q$ such that $g^u = 0 \pmod p \pmod q$, and the attacker can find it, then a forgery is easily computed by setting $s = u/h \pmod q$. This can allow forgery for any message, and, interestingly, for any public key $y$ that uses these DSA parameters, since $y$ does not appear at all in the equation.

Now the attacker's problem is finding that value $u$, if it exists. Now comes the hand-wavy part: this problems seems difficult, for the following reason: there are very few solutions.

Namely, $g$ generates a subgroup of size $q$, and there are about $p/q$ values modulo $p$ which are also a multiple of $q$. So the possible solutions $u$ are in the intersection of a set of size $q$ (the subgroup) and a set of size $p/q$ (the multiples of $q$), both sets being subsets of a set of size $p$ (the integers modulo $q$). If both subsets were generated randomly, then the probability of having no common element would be about $((q-1)/q)^q$, which converges to $e^{-1} \approx 0.3679$ when $q$ is large. In other words, in about 37% of the cases, there will be no solution at all, i.e. there would be no signature with $r = 0$ that the verifier would accept. And when there is a solution, there will usually be only one or two.

Thus, the attacker's job is about finding a discrete logarithm $u$, in base $g$, for a single target value. This is exactly the discrete logarithm problem and we assume it to be hard modulo $p$ (otherwise, why would you use DSA at all?). Note that this would hold even if the attacker knows exactly what multiple of $q$ he should target; not knowing that value makes the task only harder for him.

Now, of course, the two subsets are not generated randomly. I made some measures with small values. For instance, with $p = 1993$ and $q = 89$, then none of the elements of the subgroup of order $q$ is a multiple of $q$; however, with $p = 1553$ and $q = 97$, using $g = 310$, then $g^6 \pmod p = 776$, which is a multiple of $97$, and $g^{18} \pmod p = 194$, which is also a multiple of $97$.

Generating all possible DSA parameters such that $200 \leq q \leq 500$ and $100000 \leq p \leq 200000$, I find 1218 sets of DSA parameters; for 442 of them (36.3%), there is no solution; for 438 (36.0%), there is exactly one solution; for 231 (19.0%) there are exactly two solutions; and so on. This is compatible with the analysis above: solutions are rare, so finding a solution should be as hard as solving discrete logarithm generically.

(Unless there's some magical math that allows easily finding a solution in that specific case. Sometimes the World does that, just to spite me.)

• One of you and Galvatron must be wrong. Who has made the mistake? and where? – Martin Bonner supports Monica Jun 13 '17 at 17:53
• @MartinBonner: Galvatron answers a different question. What he says is that if there is a signature with r = 0, then it can be repurposed to match any message without knowledge of the private key. The question I try to tackle is whether producing such a signature is doable (with non-negligible probability of success). – Thomas Pornin Jun 13 '17 at 18:48
• I appreciate this answer. Usually the recommendations say "Check to make sure $r \neq 0, s \neq 0$, but really $r=0$ or $s=0$ is rare so it's not a problem" and I'd just take that on faith. – user47922 Jun 13 '17 at 19:40

If $r=0$, then $s \equiv k^{-1}(D + xr) \mod q \equiv k^{-1} D \mod q$. Here, $x$ is your private key, and $D$ is the (hashed) document that you want to sign. Since the attackers can see $s$ and $D$, all they have to do is solve

$$k \equiv s^{-1} D \mod q$$

And now they have your $k$ without having to solve the discrete log problem. $r=0$ effectively "wipes out" the dependence of the signature on your private key $x$. This is effectively the same danger of reusing $k$, except this is even easier for an attacker. $r=0$ does all the work for them!

Finally, the standard requires it (see Section 4.6). Maybe for this very reason?