# How is the Schnorr Signature insecure in the following 2 scenarios:

1. When there is no hash function used, $s = k-x \cdot m \mod {q}$ instead of $s = k-x \cdot H(m||r) \mod{q}$?
2. When a hash function is defined as $H(m)$ instead of $H(m||r)$?
-
If you're going to post homework, it's polite to show that you have made some effort. So how far have you got, and what specific problems do you have? – Peter Taylor Feb 25 '11 at 9:46
My understanding is as follows: When m is used as a plain text, Then it can be divided across the equation: s.m^-1 = k.m^-1 - x mod q. Two signatures to the same msg then can solve x from this equation which is total break. I am not able think differently for the second case because attacker can get the hash from the plain text. Apology, its my first time here and I am a beginner in this field. – bala maverick Feb 25 '11 at 10:07
In case 1, is $e$ still the same $H(m || r)$? – Henno Brandsma Feb 25 '11 at 21:46
In case 2, what is the full signature? How do you verify it? – Henno Brandsma Feb 25 '11 at 21:52

As to 2: if $e= H(m)$ and $s = k - x \cdot H(m)$, the $k$ serves no purpose any more. Anyone can create $H(m)$ and there is no way to verify that $s$ has been created by the one possessing the private key $x$. In the original scheme, $g^s \cdot y^e$ yields $g^k = r$, so that we can verify that $e = H(m \| r)$ is correct. In variation 2, the $r$ has been eliminated, and cannot be computed by a verifier. This is not even a signature scheme, really, as there is no verifying beyond checking $e = H(m)$.

To address variation 1, as in the comment: if we use $(r,s)$ where $s = k - x \cdot m$, then the verifying equation becomes $g^s \cdot y^m = r$, given $(r,s)$ and the message $m$ and public key $y$; if it holds it's a valid signature (no need for hashing). But then from a valid signature $(r,s)$ for message $m$ we generate one for $m+1$ by multiplying $r$ by $y$, and keeping $s$. The check then becomes $$g^s \cdot y^{m+1} = g^s \cdot y^m \cdot y = r \cdot y$$ which is valid too. So then also the hashing stays necessary.

And if we use $e = H(m)$ and so $(r,s) = (g^k, k - x \cdot H(m))$ as the signature, we can do a similar thing: the verifying equation becomes $g^s \cdot y^{H(m)} = r$ (valid iff true) and then $(g \cdot r, s+1)$ is also a valid signature for $m$: verifying gives $$g^{s+1} \cdot y^{H(m)} = g \cdot (g^s \cdot y^{H(m)}) = g \cdot r$$ as $(r,s)$ was valid, and so the new one is valid too.

Note also that if we re-use the same $k$ (and thus $r = g^k$) for 2 signatures for different messages (in the secure, normal scheme), and the opponent knows or guesses this, then we can compute $x$, the secret key: we then have $(e_1, s_1)$ and $(e_2, s_2)$ where $e_1 = H(m_1 \| r)$, $e_2 = H(m_2 \| r)$, $s_1 = k - x \cdot e_1$, $s_2 = k - x \cdot e_2$; the opponent computes $$s_1 - s_2 = x \cdot (e_2 - e_1)$$ and $s_1, s_2, e_1, e_2$ are known, allowing us to solve for $x$, in most cases. Of course, for a large enough group, and good random choices, this is very unlikely to happen.

As you see, it's quite intricate to see why we need certain stuff.

-
Thanks! I am almost getting it.. It is that there is no binding between the randomness and the signature components. Am i right? – bala maverick Feb 26 '11 at 11:05
++ in this case 2: when we have e=H(m) then why cant we pass the signature as (r,s). Will it be of any use? – bala maverick Feb 26 '11 at 11:11
Thanks for the effort. A brilliant explanation, I am getting a clearer picture now of why we use certain primitives. !! #clear – bala maverick Feb 28 '11 at 3:24