Digital signature forgery

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message, , and a signature (or MAC), , that is valid for , where has not been signed in the past by the legitimate signer. There are three types of forgery: existential, selective, and universal.[1]

Types[edit]

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 (existential unforgeability, EUF)[edit]

Existential forgery is the creation (by an adversary) of at least one message/signature pair, , where was not produced by the legitimate signer. The adversary need not have any control over ; need not have any particular meaning; the message content is irrelevant — as long as the pair, , 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 be the RSA public key.
  2. The legitimate signer signs a message m. This means, he calculates the signature .
  3. The adversarial can create the message .
  4. The signature of , so the adversarial has found a valid pair .

Signature of a product of two messages[edit]

This forgery can be done with two messages and their signatures since

.

Selective forgery (selective unforgeability, SUF)[edit]

Selective forgery is the creation (by an adversary) of a message/signature pair where has been chosen by the challenger prior to the attack.[3] may be chosen to have interesting mathematical properties with respect to the signature algorithm; however, in selective forgery, 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 (universal unforgeability, UUF)[edit]

Universal forgery is the creation (by an adversary) of a valid signature, , for any given message, . 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[edit]

  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.