Digital signature forgery

In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message, $m$, and a signature (or MAC), $\sigma$, that is valid for $m$, where $m$ has not been signed in the past by the legitimate signer. There are three types of forgery: existential, selective, and universal.^[1]

Types

Besides the following attacks, there is also a total break: when adversary can compute the signer's private key and therefore forge any possible signature on any message.^[2]

Existential forgery

Existential forgery is the creation (by an adversary) of at least one message/signature pair, $(m, \sigma)$, where $\sigma$ was not produced by the legitimate signer. The adversary need not have any control over $m$; $m$ need not have any particular meaning; the message content is irrelevant — as long as the pair, $(m, \sigma)$, is valid, the adversary has succeeded in constructing an existential forgery.

Existential forgery is essentially the weakest adversarial goal, therefore the strongest schemes are those that are existentially unforgeable. Nevertheless, many state-of-art signature algorithms allow existential forgery. For example, an RSA forgery can be done as follows:

1. Let $e$ be the RSA public key.
2. Choose a random signature, $\sigma$.
3. Send the message as: $\sigma^e (\operatorname{mod} n) \parallel \sigma (\operatorname{mod} n)$.
4. The recipient checks the signature: $\sigma^e = \sigma^e$ so the check will pass.

Note: The sender cannot control the message content so it will be a random message, that may help in some cases.

Multiplication forgery

This forgery can be used with two messages and their signatures as follows:

1. Let $\sigma_1 = S_k(m_1)$ be the RSA signature on the message, $m_1$, under the key, $k$.
2. Analogously, $\sigma_2 = S_k(m_2)$.
3. In that case $\sigma_1 \cdot \sigma_2 \pmod{n}$ will be the valid RSA signature on the message, $m_1 \cdot m_2 \pmod{n}$, under the key, $k$.^[3]

Selective forgery

Selective forgery is the creation (by an adversary) of a message/signature pair $(m, \sigma)$ where $m$ has been chosen by the adversary prior to the attack. $m$ may be chosen to have interesting mathematical properties with respect to the signature algorithm; however, in selective forgery, $m$ must be fixed before the start of the attack.

The ability to successfully conduct a selective forgery attack implies the ability to successfully conduct an existential forgery attack.

Universal forgery

Universal forgery is the creation (by an adversary) of a valid signature, $\sigma$, for any given message, $m$. An adversary capable of universal forgery is able to sign messages he chose himself (as in selective forgery), messages chosen at random, or even specific messages provided by an opponent.

References

1. Vaudenay, Serge (September 16, 2005). A Classical Introduction to Cryptography: Applications for Communications Security (1st ed.). Springer. p. 254. ISBN 978-0-387-25464-7.
2. Goldwasser, Shafi; Bellare, Mihir (2008). Lecture Notes on Cryptography. Summer course on cryptography. p. 170.
3. Kantarcioglu, Murat. "Digital Signatures" (PDF).