Types of attacks on signature schemes
The goal of an adversary is to forge signatures; that is, produce signatures which will be accepted as those of some other entity. The following provides a set of criteria for what it means to break a signature scheme.
- 1. total break. An adversary is either able to compute the private key information of the signer, or finds an efficient signing algorithm functionally equivalent to the valid signing algorithm. (For example, see §11.3.2(i).)
- 2. selective forgery’. An adversary' is able to create a valid signature for a particular message or class of messages chosen a priori. Creating the signature does not directly involve the legitimate signer. (See Example 11.21.)
- 3. existential forgery. An adversary is able to forge a signature for at least one message. The adversary has little or no control over the message whose signature is obtained, and the legitimate signer may be involved in the deception (for example, see Note 11.66(iii)).
There are two basic attacks against public-key digital signature schemes.
- 1. key-only attacks. In these attacks, an adversary knows only the signer’s public key.
- 2. message attacks. Here an adversary' is able to examine signatures corresponding either to known or chosen messages. Message attacks can be further subdivided into three classes:
- (a) known-message attack. An adversary has signatures for a set of messages which are known to the adversary but not chosen by him.
- (b) chosen-message attack. An adversary obtains valid signatures from a chosen list of messages before attempting to break the signature scheme. This attack is поп-adaptive in the sense that messages are chosen before any signatures are seen. Chosen-message attacks against signature schemes are analogous to chosen-ciphertext attacks against public-key encryption schemes (see §1.13.1).
- (c) adaptive chosen-message attack. An adversary is allowed to use the signer as an oracle; the adversary may request signatures of messages which depend on the signer’s public key and he may request signatures of messages which depend on previously obtained signatures or messages.
- 11.15 Note (adaptive chosen-message attack) In principle, an adaptive chosen-message attack is the most difficult type of attack to prevent. It is conceivable that given enough messages and corresponding signatures, an adversary could deduce a pattern and then forge a signature of its choice. While an adaptive chosen-message attack may be infeasible to mount in practice, a well-designed signature scheme should nonetheless be designed to protect against the possibility.
- 11.16 Note (security considerations) The level of security required in a digital signature scheme may vary according to the application. For example, in situations where an adversary is only capable of mounting a key-only attack, it may suffice to design the scheme to prevent the adversary from being successful at selective forgery'. In situations where the adversary is capable of a message attack, it is likely necessary to guard against the possibility of existential forgery.
- 11.17 Note (hash functions and digital signature processes) When a hash function h is used in a digital signature scheme (as is often the case), h should be a fixed part of the signature process so that an adversary is unable to take a valid signature, replace h with a weak hash function, and then mount a selective forgery attack.