Attacks on identification protocols

The methods an adversary may employ in an attempt to defeat identification protocols are a subset of those discussed in Chapter 12 for authenticated key establishment, and the types of adversaries may be similarly classified (e.g., passive vs. active, insider vs. outsider); for a discussion of attacks on simple password schemes, see §10.2.2. Identification is, however, less complex than authenticated key establishment, as there is no issue of an adversary learning a previous session key, or forcing an old key to be reused. For conciseness, the following definitions are made:

  • 1. impersonation: a deception whereby one entity purports to be another.
  • 2. replay attack: an impersonation or other deception involving use of information from a single previous protocol execution, on the same or a different verifier. For stored files, the analogue of a replay attack is a restore attack, whereby a file is replaced by an earlier version.
  • 3. interleaving attack: an impersonation or other deception involving selective combination of information from one or more previous or simultaneously ongoing protocol executions (parallel sessions), including possible origination of one or more protocol executions by an adversary itself.
  • 4. reflection attack: an interleaving attack involving sending information from an ongoing protocol execution back to the originator of such information.
  • 5. forced delay: a forced delay occurs when an adversary intercepts a message (typically containing a sequence number), and relays it at some later point in tune. Note the delayed message is not a replay.
  • 6. chosen-text attack: an attack on a challenge-response protocol wherein an adversary strategically chooses challenges in an attempt to extract information about the claimant’s long-term key.

Chosen-text attacks are sometimes referred to as using the claimant as an oracle, i.e., to obtain information not computable from knowledge of a claimant’s public key alone. The attack may involve chosen-plaintext if the claimant is required to sign, encrypt, or MAC the challenge, or chosen-ciphertext if the requirement is to decrypt a challenge.

Potential threats to identification protocols include impersonation by any of the following attacks: replay, interleaving, reflection, or forced delay. Impersonation is also trivial if an adversary is able to discover an entity’s long-term (secret or private) keying material, for example, using a chosen-text attack. This may be possible in protocols which are not zero- knowledge, because the claimant uses its private key to compute its response, and thus a response may reveal partial information. In the case of an active adversary, attacks may involve the adversary itself initiating one or more new protocol runs, and creating, injecting, or otherwise altering new or previous messages. Table 10.3 summarizes counter-measures for these attacks.

Type of attack

Principles to avoid attack


use of challenge-response techniques; use of nonces; embed target identity hr response


linking together all messages from a protocol run (e.g., using chained nonces)


embed identifier of target party in challenge responses; construct protocols with each message of different form (avoid message symmetries); use of uni-directional keys


use of zero-knowledge techniques; embed hr each challenge response a self-chosen random number (confounder)

forced delay

combined use of random numbers with short response time-outs; timestamps plus appropriate additional techniques

Table 10.3: Identification protocol attacks and counter-measures.

  • 10.40 Remark {use of keys for multiple purposes) Caution is advised if any cryptographic key is used for more than one purpose. For example, using an RSA key for both entity authentication and signatures may compromise security by allowing a chosen-text attack. Suppose authentication here consists of В challenging A with a random number rp RSA-encrypted under .Ts public key, and A is required to respond with the decrypted random number. If В challenges A with rp = h(x), A’s response to this authentication request may (unwittingly) provide to В its RSA signature on the hash value of the (unknown to A) message x. See also Example 9.88, where a DES key used for both CBC encryption and CBC-MAC leads to a security flaw; and Remark 13.32.
  • 10.41 Remark (adversary acting “as a wire”) In any identification protocol between A and B, an adversary C may step into the communications path and simply relay (without changing) the messages between legitimates parties A and B, itself acting as a part of the communications link. Typically in practice, this is not considered a true “attack”, in the sense that it does not alter the aliveness assurance delivered by the protocol; however, in some special applications, this may be a concern (see Remark 10.42).
  • 10.42 Remark (grandmaster postal-chess problem) Identification protocols do not provide assurances about the physical location of the authenticated party. Therefore, Remark 10.41 notwithstanding, a concern may arise in the special case that the following is possible: an adversary C attempts to impersonate B, is challenged (to prove it is B) by A, and is able to relay (in real time, without detection or noticeable delay, and pretending to be A) the challenge on to the real B, get a proper response from B, and pass this response along back to A. In this case, additional measures are necessary' to prevent a challenged entity from eliciting aid in computing responses. This is related to the so-called grandmaster postal-chess problem, whereby an amateur’s chess rating may unfairly be improved by engaging in two simultaneous chess games with distinct grandmasters, playing black in one game and white in the second, and using the grandmaster’s moves from each game in the other. Either two draws, or a win and a loss, are guaranteed, both of which will improve the amateur’s rating.

For further discussion of protocol attacks including specific examples of flawed entity authentication protocols, see §12.9.

(i) Maintaining authenticity

Identification protocols provide assurances corroborating the identity of an entity only at a given instant in time. If the continuity of such an assurance is required, additional techniques are necessary to counteract active adversaries. For example, if identification is carried out at the beginning of a communications session to grant communications permissions, a potential threat is an adversary who “cuts in” on the communications line immediately after the successful identification of the legitimate party'. Approaches to prevent this include:

  • 1. performing re-authentication periodically, or for each discrete resource requested (e.g., each file access). A remaining threat here is an adversary who “steps out” every time re-authentication is performed, allowing the legitimate party to perform this task, before re-entering.
  • 2. tying the identification process to an ongoing integrity service. In this case, the identification process should be integrated with a key establishment mechanism, such that a by-product of successful identification is a session key appropriate for use in a subsequent ongoing integrity mechanism.
  • (ii) Security level required for on-line vs. off-line attacks

The security level required for identification protocols depends on the environment and the specific application at hand. The probability of success of “guessing attacks” should be considered, and distinguished from the amount of computation required to mount on-line or off-line attacks (using the best techniques known). Some illustrative notes follow (see also Note 10.28).

  • 1. Local attacks. Selecting security' parameters which limit the probability of successful impersonation of a guessing attack (an adversary simply guesses a legitimate party’s secret) to a 1 in 220 chance (20 bits of security) may suffice if, for each attempted impersonation, a local appearance is required by the would-be impersonator and there is a penalty for failed attempts. Depending on the potential loss resulting relative to the penalty, 10 to 30 bits or more of security may be required.
  • 2. Remote attacks. A higher level of security is required in environments where unlimited identification attempts, each involving minimal computational effort, are possible by remote electronic communications, by an anonymous claimant interacting with an on-line system, with no penalties for failed attempts. 20 to 40 bits of security or more may be called for here, unless the number of interactions may be somehow limited.
  • 3. Off-line or non-interactive attacks. Selecting security parameters such that an attack requires 240 computations in real-time (during a protocol execution) may be acceptable, but a bound of 2C0 to 280 computations (the latter should be adequate in all cases) may be called for if the computations can be carried out off-line, and the attack is verifiable (i.e., the adversary can confirm, before interacting with the on-line system, that Iris probability of successful impersonation is near 1; or can recover a long-term secret by off-line computations subsequent to an interaction).
< Prev   CONTENTS   Source   Next >