View source for Digital signature forgery

In a [[cryptography|cryptographic]] [[digital signature]] or [[Message authentication code|MAC]] system, '''digital signature forgery''' is the ability to create a pair consisting of a message, <math>m</math>, and a signature (or MAC), <math>\sigma</math>, that is valid for <math>m</math>, but has not been created in the past by the legitimate signer. There are different types of forgery.<ref name=":0">{{cite book
|last=Vaudenay 
|first=Serge
|authorlink=Serge Vaudenay
|title=A Classical Introduction to Cryptography: Applications for Communications Security
|edition=1st
|date=September 16, 2005
|publisher=Springer
|isbn=978-0-387-25464-7
|page=254
}}</ref>

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 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 an adversary can recover the private information and keys used by the signer, they can create any possible signature on any message.<ref name=GoldwasserBellare>{{cite book|last1=Goldwasser|first1=Shafi|last2=Bellare|first2=Mihir|title=Lecture Notes on Cryptography. Summer course on cryptography|date=2008|page=170|url=http://cseweb.ucsd.edu/~mihir/papers/gb.html|access-date=2011-01-30|archive-date=2012-04-21|archive-url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html|url-status=dead}}</ref>

==={{ANCHOR|UUF}} Universal forgery (universal unforgeability, UUF) ===
Universal forgery is the creation (by an adversary) of a valid signature, <math>\sigma</math>, for ''any'' given message, <math>m</math>.  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.<ref name=":0" />

=== Selective forgery (selective unforgeability, SUF) ===
Selective forgery is the creation of a message/signature pair <math>(m, \sigma)</math> by an adversary, where <math>m</math> has been ''chosen'' by the attacker prior to the attack.<ref>{{cite web|url=https://cseweb.ucsd.edu//~mihir/papers/gb.pdf|title=Lecture Notes on Cryptography|author=Shafi Goldwasser and Mihir Bellare}}</ref><ref>Bleumer G. (2011) Selective Forgery. In: van Tilborg H.C.A., Jajodia S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_225</ref> <math>m</math> may be chosen to have interesting mathematical properties with respect to the signature algorithm; however, in selective forgery, <math>m</math> 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 forgery (existential unforgeability, EUF) is the creation (by an adversary) of at least one message/signature pair, <math>(m, \sigma)</math>, where <math>m</math> has never been signed by the legitimate signer. The adversary can choose <math>m</math> freely; <math>m</math> need not have any particular meaning; the message content is irrelevant &mdash; as long as the pair, <math>(m, \sigma)</math>, 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 <math>m</math> for which a forgery can easily be created. In contrast, 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)|RSA cryptosystem]] has the following multiplicative property: <math>\sigma(m_1) \cdot \sigma(m_2) = \sigma (m_1 \cdot m_2)</math>.

This property can be exploited by creating a message <math>m' = m_1 \cdot m_2</math> with a signature <math>\sigma\left(m'\right) = \sigma (m_1 \cdot m_2)= \sigma(m_1) \cdot \sigma(m_2)</math>.<ref name="damore">{{cite web|url=http://www.dis.uniroma1.it/~damore/sicu/slide/slide2012/6.digital-signature.pdf|title=Digital signatures - DSA|date=April 2012|publisher=La Sapienza University of Rome|author=Fabrizio d'Amore|accessdate=July 27, 2018|pages=8–9}}</ref>

A common defense to this attack is to [[Hash function|hash]] the messages before signing them.<ref name="damore"/>

=== Weak existential forgery (strong existential unforgeability, strong unforgeability; sEUF, or SUF) ===
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, <math>\left(m', \sigma'\right)</math>, given a number of different message-signature pairs <math>(m, \sigma)</math> produced by the legitimate signer.
In contrast to existential forgeries, an adversary is also considered successful if they manages to create a new signature for an already signed message <math>m'</math>.

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

==References==
{{reflist}}

[[Category:Digital signature|Forgery]]


{{crypto-stub}}