# Digital signature forgery

(Redirected from Existential 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}$, but has not been created in the past by the legitimate signer. There are different types of forgery.[1]

To each of these types, security definitions can be associated. A signature scheme is secure by a specific definition if no forgery of the associated type is possible.

## Types

The following definitions are ordered from lowest to highest achieved security, in other words, from most powerful to the weakest attack. The definitions form a hierarchy, meaning that an attacker able to do mount a specific attack can execute all the attacks further down the list. Likewise, a scheme that reaches a certain security goal also reaches all prior ones.

### Total break

More general than the following attacks, there is also a total break: when adversary can compute the signer's private key, they can forge any possible signature on any message.[2]

### Universal forgery (universal unforgeability, UUF)

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.

### Selective forgery (selective unforgeability, SUF)

Selective forgery is the creation of a message/signature pair ${\displaystyle (m,\sigma )}$ by an adversary, where ${\displaystyle m}$ has been chosen by the challenger prior to the attack.[3] ${\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.

### Existential forgery (existential unforgeability, EUF)

Existential forgery is the creation (by an adversary) of at least one message/signature pair, ${\displaystyle (m,\sigma )}$, where ${\displaystyle m}$ has never been signed by the legitimate signer. The adversary can choose ${\displaystyle m}$ freely; ${\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. Thus, creating an existential forgery is easier than a selective forgery, because the attacker may select a message ${\displaystyle m}$ for which a forgery can easily be created, whereas in the case of a selective forgery, the challenger can ask for the signature of a “difficult” message.

#### Example of an existential forgery

The RSA cryptosystem has the following multiplicative property: ${\displaystyle \sigma (m_{1})\cdot \sigma (m_{2})=\sigma (m_{1}\cdot m_{2})}$.

This property can be exploited by creating a message ${\displaystyle m'=m_{1}\cdot m_{2}}$ with a signature ${\displaystyle \sigma (m')=\sigma (m_{1}\cdot m_{2})=\sigma (m_{1})\cdot \sigma (m_{2})}$.[4]

A common defense to this attack is to hash the messages before signing them.[4]

### Strong existential forgery (strong (existential) unforgeability, sEUF or SUF)

This notion is a stronger (more secure) variant of the existential forgery detailed above. Existential forgery is the creation (by an adversary) of at least one message/signature pair, ${\displaystyle (m,\sigma )}$, where ${\displaystyle (m,\sigma )}$ was not produced by the legitimate signer. The difference to existential forgery is that an attacker wins if, after asking for a signature of some message, they can create a different signature ${\displaystyle \sigma '}$ for the same message.

Strong existential forgery is essentially the weakest adversarial goal, therefore the strongest schemes are those that are strongly existentially unforgeable.

## 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. ^ Smart, Nigel P. Cryptography Made Simple. Springer. p. 217. ISBN 978-3-319-21935-6.
4. ^ a b Fabrizio d'Amore (April 2012). "Digital signatures - DSA" (PDF). La Sapienza University of Rome. pp. 8–9. Retrieved July 27, 2018.