Is it insecure to sign the plaintext 0 with ElGamal signature algorithm? Can this leak the private key, give the possibility to forge other signatures or does provide any other attack vector?
1 Answer
$\begingroup$
$\endgroup$
8
Is it insecure to sign the plaintext 0 with ElGamal signature algorithm?
It is insecure to verify the plaintext that hashes to 0 with the ElGamal signature algorithm, because anyone can generate such a signature with only the public key.
The validation requirement is:
$$g^{H(m)} = pk^r r^s$$
(where $g$ is the curve generator, $H(m)$ is the hash of the message, $pk$ is the public key, and $r, s$ are values provided in the signature).
If $H(m) = 0$, then this reduces to $1 = pk^r r^s$. If we generate a signature with $r = pk$, and $s = (p-1)-pk$ (where $p$ is the prime modulus), then it is easy to see that the relation is satisfied, and that we have successfully generated a signature with only the public key.
-
4$\begingroup$ If I may add to the excellent answer, because of the expected preimage resistance of any decent hash function $H$, it's effectively impossible to find a message that hashes to 0. $\endgroup$– swineoneMar 12 at 22:29
-
$\begingroup$ This was a question from university. In the meantime we got the solution. The attack is not possible because x must be a group element of Zp*. 0 is never an element in Zp*. $\endgroup$– PCFXMar 15 at 11:15
-
$\begingroup$ @PCFX: if $x$ refers to what I call $H(m)$, that doesn't make sense - El Gamal doesn't use $x$ as a group element of $\mathbb{Z}_p^*$ $\endgroup$– ponchoMar 15 at 13:01
-
$\begingroup$ @poncho: Yes we use x instead of H(m) sorry. You are right, we use this book (p. 271) and I also don't see any restriction on x or H(m) there: swarm.cs.pub.ro/~mbarbulescu/cripto/… Well you could e.g. not calculate anything in the s equation where H(m)^-1 is needed if H(m) is not element of Zp*. But I guess this applies to multiple other H(m) as well that are not part of Zp*. I guess nobody can restrict me which messages or hashes I try to sign with ElGamal. $\endgroup$– PCFXMar 15 at 13:13
-
$\begingroup$ @poncho: Is it a requirement that x or H(m) must be a group member of Zp*? $\endgroup$– PCFXMar 15 at 20:05