Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The professor left us a question on ElGamal signatures:

Given the hash function $H$ and message $M$, choose a random $r$ and compute $h=g^r$ and $H(M||h)$. Show that, if $H(M)$ is used instead of $H(M||h)$, the signature can be existentially forged.

I am struggling with the problem, and I think that maybe we can get one known message signed twice with different $(M, c_1, h_1)$ and $(M, c_2, h_2)$, and then use that to sign some other messages $M'$, but I have no idea how to proceed. Can anyone give me some hints?

share|improve this question
3  
I tried to clean up your question a bit, but there were some places where I wasn't really sure what you meant. Could you please check that I didn't introduce any mistakes, and maybe try to clarify your question further. –  Ilmari Karonen Feb 27 '13 at 12:22
2  
It would useful to clarify how the question relates to the ElGamal signature scheme –  fgrieu Feb 27 '13 at 12:40

2 Answers 2

It's not a complete answer because an adversary needs control on the random choice of a signing algorithm.

  1. First let me define ElGamal signature to not get lost in notation. $x \in N$ is the secret key. $p$ is a prime, it defines $Z_p^*$. $g$ is a generator of $Z_p^*$. $y=g^x$ and the public key is $(p, g, g^x)$. Then $k$ is picked at random from $0<k<p-1$, $r = g^k \bmod p$, $s = (H(m) - xr)k^{-1} \bmod (p-1)$ and the signature is $(r,s)$.

  2. Suppose we know two signatures of the message $m$ for different $k$-s: $\sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1)$ and $\sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2)$.

Let $\sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1))$.

  1. Verification of $\sigma_3$ leads us to an equation $(k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1)$. If an attacker can choose $k_1, k_2$, then he can probably find proper $p$ and $k_1, k_2$. Otherwise - still a problem.
share|improve this answer
    
How is this an answer to the question? –  poncho Jun 14 at 1:15

Daniel Bleichenbacher has described such kind of attacks in his article Generating ElGamal signatures without knowing the secret key. (PDF)

He noticed that if verifier would accept signatures where $r$ is larger than $p$ then any signature $(r,s)$ on $H(M)$ could be used to generate a signature $(r2, s2)$ on arbitrary hash value $H(M2)$.

For that attacker should calculate $u=H(M2)H(M)^{-1} \bmod (p-1)$. This implies $g^{H(M2)}=g^{uH(M)}=y^{ru}r^{su}$. $s2$ could be setting as $s2=su\bmod (p-1)$ and $r2$ could be computing by using Chinese Remainder Theorem for two equations $r2=ru\bmod (p-1)$ and $r2=r\bmod p$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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