Digital signature forgery

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 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 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 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 (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]

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.