Score:5

Crypto

Is it insecure to sign the value 0 with ElGamal?

PCFX

3/12/24, 8:44 PM

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?

944

1 + 0

elgamal-signature

attack

Score:11

Crypto

poncho

3/12/24, 9:53 PM

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.

+ 8

swineone

3/12/24, 10:29 PM

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.

PCFX

3/15/24, 11:15 AM

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

poncho

3/15/24, 1:01 PM

@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^*$

PCFX

3/15/24, 1:13 PM

@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: https://swarm.cs.pub.ro/~mbarbulescu/cripto/Understanding%20Cryptography%20by%20Christof%20Paar%20.pdf 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.

PCFX

3/15/24, 8:05 PM

@poncho: Is it a requirement that x or H(m) must be a group member of Zp*?

poncho

3/15/24, 8:10 PM

@PCFX: no; El Gamal signature performs operations on it as a member of $\mathbb{Z}_{p-1}$ (addition, using it as an exponent); 0 is a member of that ring...

PCFX

3/15/24, 8:20 PM

@poncho: Can you explain why ElGamal signature uses an additive group in that case? I always thought ElGamal only operates on a multiplicative prime group?

poncho

3/15/24, 8:27 PM

@PCFX: as part of the process, the signer computes $(H(m) - priv \cdot r) \cdot k^{-1}$. Those operations are done in $\mathbb{Z}_{p-1}$

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is it insecure to sign the value 0 with ElGamal?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.