6
$\begingroup$

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$)

$\endgroup$
0
7
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ One of you and Galvatron must be wrong. Who has made the mistake? and where? $\endgroup$ – Martin Bonner supports Monica Jun 13 '17 at 17:53
  • 1
    $\begingroup$ @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). $\endgroup$ – Thomas Pornin Jun 13 '17 at 18:48
  • $\begingroup$ 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. $\endgroup$ – user47922 Jun 13 '17 at 19:40
1
$\begingroup$

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?

$\endgroup$

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.