Digital Signature Attack

Question

In a typical digital signature scheme in which in order to sign we compute:

1. hash of the message: $h(m)$
2. resulting hash signed with the private key $[h(m)](private key)$

If there were a collision on the hash, what an adversary could do?

Solution (?)

An adversary can find a different message $m_2$ with the same hash of $m_1$. The user (good guy) signs $m_1$. The adversary can claim that $m_2$ has been signed by the user because $m_1$ and $m_2$ have the same signature.

Is this the correct answer? How can the adversary claim that? I mean… the hash of the message is signed with the user's private key. The adversay does not know that key.

Answer 1

If the adversary gets a signature on $m_1$, then it's true that the adversary could claim the signature is a signature on both $m_1$ and $m_2$, if $h(m_1) = h(m_2)$ (i.e., there is a collision). The adversary does not need the private key to make this claim, anyone holding the public key should be able to verify the signature.

The reason the adversary can successfully make this claim is that the signature does not actually sign the message, it signs the hash. So since $h(m_1) = h(m_2)$ the resulting signature is in fact both a signature of $m_1$ and $m_2$.

The reason why this is not usually a problem is that the hash function $h$ will be chosen as a cryptographic secure hash function meaning that it should be (practically) impossible for the adversary to find such a collision.

Answer 2

A collision in a hash function $h()$ means that there are two different messages $m_1$ and $m_2$ such that $h(m_1) = d = h(m_2)$. A digital signature of $m_1$ will involve the value $d$, which can be generated by computing $h(m_1)$. But the same value $d$ can also be generated by computing $h(m_2)$.

If you are presented with the digital signature value $s = Gen_{PK}(d)$ and someone tells you that $s$ is a digital signature of message $m$, you will verify this by firstly calculating $d = h(m)$ and then checking $Ver_{PK}(s,d)$.

Hence, if you are presented with the digital signature value $s$ which was originally generated as $Gen_{PK}(h(m_1))$ and someone tells you that $s$ is a digital signature of message $m_2$, you will verify this by firstly calculating $d = h(m_2)$ and then checking $Ver_{PK}(s,d)$. This isn't supposed to check out unless $m_1 = m_2$, but if $h(m_1) = d = h(m_2)$ it will check out even if $m_1 \ne m_2$.