# 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, ${\displaystyle m}$, and a signature (or MAC), ${\displaystyle \sigma }$, that is valid for ${\displaystyle m}$, where ${\displaystyle 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 (EUF, Existential Unforgeability)

Existential forgery is the creation (by an adversary) of at least one message/signature pair, ${\displaystyle (m,\sigma )}$, where ${\displaystyle \sigma }$ was not produced by the legitimate signer. The adversary need not have any control over ${\displaystyle m}$; ${\displaystyle m}$ need not have any particular meaning; the message content is irrelevant — as long as the pair, ${\displaystyle (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 ${\displaystyle e}$ be the RSA public key.
2. Choose a random signature, ${\displaystyle \sigma }$.
3. Send the message as: ${\displaystyle \sigma ^{e}(\operatorname {mod} n)\parallel \sigma (\operatorname {mod} n)}$.
4. The recipient checks the signature: ${\displaystyle \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 ${\displaystyle \sigma _{1}=S_{k}(m_{1})}$ be the RSA signature on the message, ${\displaystyle m_{1}}$, under the key, ${\displaystyle k}$.
2. Analogously, ${\displaystyle \sigma _{2}=S_{k}(m_{2})}$.
3. In that case ${\displaystyle \sigma _{1}\cdot \sigma _{2}{\pmod {n}}}$ will be the valid RSA signature on the message, ${\displaystyle m_{1}\cdot m_{2}{\pmod {n}}}$, under the key, ${\displaystyle k}$.[3]

### Selective forgery (SUF, Selective Unforgeability)

Selective forgery is the creation (by an adversary) of a message/signature pair ${\displaystyle (m,\sigma )}$ where ${\displaystyle m}$ has been chosen by the challenger prior to the attack.[4] ${\displaystyle m}$ may be chosen to have interesting mathematical properties with respect to the signature algorithm; however, in selective forgery, ${\displaystyle 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 (UUF, Universal Unforgeability)

Universal forgery is the creation (by an adversary) of a valid signature, ${\displaystyle \sigma }$, for any given message, ${\displaystyle 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).
4. ^ Smart, Nigel P. Cryptography Made Simple. Springer. p. 217. ISBN 978-3-319-21935-6.