Digital signature forgery

More general than the following attacks, there is also a total break: when adversary can recover the private information and keys used by the signer, they can create any possible signature on any message.[2]

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 they chose themselves (as in selective forgery), messages chosen at random, or even specific messages provided by an opponent.[1]

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

Existential forgery (existential unforgeability, EUF) 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.

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 \left(m'\right)=\sigma (m_{1}\cdot m_{2})=\sigma (m_{1})\cdot \sigma (m_{2})}$.[5]

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

This notion is a stronger (more secure) variant of the existential forgery detailed above. Weak existential forgery is the creation (by an adversary) of at least one message/signature pair, ${\displaystyle \left(m',\sigma '\right)}$, given a number of different message-signature pairs ${\displaystyle (m,\sigma )}$ produced by the legitimate signer. In contrast to existential forgeries, an adversary is also considered successful if they manage to create a new signature for an already signed message ${\displaystyle m'}$.

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