5
$\begingroup$

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?

$\endgroup$

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
8
  • 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$
    – swineone
    Commented Mar 12, 2023 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$
    – PCFX
    Commented Mar 15, 2023 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$
    – poncho
    Commented Mar 15, 2023 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$
    – PCFX
    Commented Mar 15, 2023 at 13:13
  • $\begingroup$ @poncho: Is it a requirement that x or H(m) must be a group member of Zp*? $\endgroup$
    – PCFX
    Commented Mar 15, 2023 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.