The first three elements characterize passive attacks; the fourth element exemplifies an active attack.
When cryptography is first mentioned, most people think about implementing confidentiality. If A and B share a key k, then one can send a message to the other, keeping the contents of that message secret from the adversary.
A -> B: k
This basic approach also works for storing confidential information on a device, like a disk. Think of the device as B; only encrypted information is written to B. Note, the fact that information stored on B is encrypted might not suffice for keeping that information confidential. A text editor, for example, will typically work by copying any files it opens from long term storage (i.e., disk B) into CPU main memory; manipulation of file contents are then done in the CPU main memory. The file in CPU main memory is unencrypted (possibly providing an attacker with one access point). Moreover, to ensure that file updates are not lost, an editor is likely to store the current state of the object being edited in a temporary file (i.e., on disk B), and that means confidential information might temporarily reside unencrypted on the disk too, despite our best intentions. In fact, file deletion often leaves the file contents on a disk, so the confidential information might remain available in unencrypted form on the disk long after the editing session has ended.
An authentication protocol allows a principal receiving a message to determine which principal sent that message. Any afficionado of spy movies is doubtless familiar with one means by which principals might authenticate each other: The first principal asks an innocuous question --- called the challenge --- of the second ("Its a bright sunny day in Dover."). And if the first principal knows the secret response to that challenge ("But the queen prefers rain.") then the first concludes that the second is a compatriot.
This authentication protocol has a significant weakness. Anyone overhearing the exchange is thereafter able to impersonate either side. The basic idea---using knowledge of a secret---is sound. The problem is that a principal must reveal the secret in order to prove knowledge of that secret. This is known as weak authentication, and it is subject to replay attacks whereby an adversary repeats fragments of a past protocol run, appearing to have knowledge of the secret, and thus passes the authentication test.
In a strong authentication protocol, knowledge of the secret is demonstrated without revealing the secret itself. If, for example, the secret is used in determining the answer for the challenge, then an adversary overhearing the challenge and response is not going to be able to feign knowledge of the secret when confronted with other, different challenges.
One way to implement strong authentication in a network starts from the assumption that principals share a secret key. Knowledge of that key is demonstrated by using the key to encrypt and decrypt challenges, but the key itself is never revealed. Here is a protocol that allows B to authenticate A. Assume that A and B are the only two principals with knowledge of secret key k.
1. B: select and store a new random value r. 2. B --> A: B,r 3. A --> B: k 4. B: check whether D(k, k) equals the stored value r from step 1.
Random value r selected in step 1 is called a nonce. It is (by design) new, so an attacker who has recorded previous versions of message 3 is unable to replay one of those messages in order to satisfy this new challenge issued by B. Inclusion of "B" in step 2 allows receiver A to select the correct shared key (i.e., the one shared with B) for generating message 3. An attacker seeing message 2 bearing the challenge does not know secret key k and thus should not be able to generate a response that satisfies B (in step 4) for the challenge (issued in step 2).
Reflection Attacks. An attacker T (traditionally cryptographers use T, short for "Trudy" to denote an intruder) can compromise the previous protocol, because A and B are each unwittingly running an "encryption service". In particular, A assumes any challenge it receives (message 2) is from an honest principal, and A always encrypts such challenges to produce responses. With a reflection attack, an intruder sends information from an on-going protocol execution back to the originator of that information. For example, an intruder might exploit an "encryption service" being run by both A and B and fool one of the participants into generating responses for its own challenges. To fool a participant, the intruder runs one or more concurrent instances of the protocol and interleaves them with the original. Because participants in protocol instances execute each protocol instance independently (and therefore no protocol instance inspects the state of any other concurrent instances, since doing that correlation would be expensive), a participant won't realize that it is generating responses for its own challenges.
Here's an example of a reflection attack. Indentation (and roman-numeral steps) indicate the concurrent instance of the protocol that T is running.
1. B: select and store a new random value r. 2. B --> T: B,r i. T --> B: A,r ii. B --> T: k 3. T --> B: k 4. B: check whether D(k, k) equals the stored value r from step 1.
In step 2, T has intercepted the message to A and learned the challenge (r). Then, in step i. T starts a second, concurrent instance of the protocol, impersonating A trying to authenticate B. In this second instance of the protocol, B does what it always does upon receiving a challenge---it encrypts the challenge using the correct key and replies (in step ii). But that reply provides what T needs for responding to the challenge posed by B in message 2 in order to convince B that T knows the shared key k with A and thus to convince B that T is A.
1. B: select and store a new random value r. 2. B --> T: B,r i T --> B: A,r ii. B --> T: k_AB 3. T --> B: . T sending k_AB doesn't suffice, since k_BA is awaited by B .
1. B: select and store a new random value r. 2. B --> A: B,r 3. A --> B: k 4. B: check whether D(k, k) equals "A,v" where v is the stored value r from step 1.And the reflection attack is again foiled:
1. B: select and store a new random value r. 2. B --> T: B,r i T --> B: A,r ii. B --> T: k 3. T --> B: . Sending k doesn't suffice, since k is awaited by B. .
Man-in-the-Middle Attacks. Nothing restricts an attacker T to using the "encryption service" that is provided by only a single protocol participant. Indeed, even with the defenses just outlined, an attacker T could run two instances of the protocol: one with A and the other with B, engaging as needed whichever of these principals would produce the value being needed by T to perpetuate its deception.
The general form of this attack is simple to understand. Each protocol step i of the form
i. X --> Y: mis replaced by two steps
i. X --> T: m i' T --> Y: m
Perhaps, in retrospect, it is not surprising that such an attack is always possible. After all, T is indistinguishable from a wire or a network channel (which itself might involve multiple store-and-forward routers).
We cannot eliminate man-in-the middle attacks, but we can blunt their effectiveness. If all traffic is encrypted using a key shared only by the endpoints, then an intruder in the middle cannot read or alter messages. There is now little to be gained from the attack. We now have two compelling reasons for principals to share keys. First, shared keys can be used to implement string authentication. Second, shared keys help in defending against man-in-the-middle attacks. The obvious question, then, is how do hosts come to share those keys.
With N hosts, O(N**2) shared keys are needed for each pair of hosts to have a distinct shared key. This is a large number of keys if N is large. Moreover, relatively few of those shared keys would ever actually be used, since any given host is likely to communicate only with a small subset of the hosts. So, instead, a mediated key exchange protocol is often used. Each host shares a key with some trusted host KDC (for Key Distribution Center), and KDC generates keys, on demand, for pairs of hosts that must communicate. Thus, starting from a relatively small number of shared keys we generate all the rest.
Assume each principal P shares key K_P with KDC. An obvious protocol for principal A to obtain a fresh secret key K_AB for communication with a principal B is:
1. A --> KDC: A,B 2. KDC --> A: A,B, K_A 3. KDC --> B: A,B, K_B
However, this protocol is not without vulnerabilities. Also it has an engineering flaw: A does not know whether B has received the key, and it is possible that a K_AB-encrypted message from A would reach B before K_AB does. (Message 3 from KDC is likely to be traveling a different route than a K_AB-encrypted message from A would.)
The engineering flaw is addressed by having A be responsible for forwarding K_AB to B rather than having KDC do this.
1. A --> KDC: A,B 2. KDC --> A: A,B, K_A, K_B 3. A --> B: A,B, K_B
We now turn to vulnerabilities in the protocol. An intruder T that can impersonate B, could obtain a key and position itself to read all traffic between A and B. This key is obtained by T using a man-in-the-middle attack at step 1 and starting a second, independent instance of the authentication after step 2.
1. A --> T: A,B 1' T --> KDC: A,T 2. KDC --> T: A,T, K_A, K_T T --> KDC: T,B KDC --> T: T,B K_T, K_B 2' T --> A: A,B, K_A, K_B 3. A --> B: A,B, K_B
This man-in-the-middle attack is possible because message 2 contains fields, so according to Dolev-Yao T can extract then mix-and-match in order to construct bogus message 2' that T ultimately sends to A. We can rule out such a parsing by T of message 2 simply by encrypting the entire message 2. The message must be intelligible by A, so it suffices to encrypt using K_A. Here is the revised protocol:
1. A --> KDC: A,B 2. KDC --> A: K_B>K_A 3. A --> B: A,B, K_B
The same vulnerability exists with message 3. Here is the attack: T impersonates A in message 3, by first contacting KDC (as itself, T) in order to get a key K_TB that can be foisted upon B as if it were K_AB.
1. T --> KDC: T,B 2. KDC --> T: K_B>K_T 3. T --> B: A,B, K_B
The defense here is to include the names A and B in the final field encrypted under K_A of message 2. This prevents message 3 (which contains that final field as its final field) from being misinterpreted by B as having come from A.
1. A --> KDC: A,B 2. KDC --> A: K_B>K_A 3. A --> B: A,B,K_B
The next vulnerability to note is that message 2 can be replayed by an attacker having intercepted message 1, forcing A and B to use an old key K_AB. Any attacker that had learned an old value of K_AB has the incentive to make this happen. We defend against A being fooled into using an old message 2 by including a nonce in message 1, which must be returned in message 2.
1. A --> KDC: A,B,r where r is a new random value 2. KDC --> A: K_B>K_A 3. A --> B: A,B, K_B
We might defend against B being fooled into using an old value of K_AB (resulting, for example, from a replay of an old message 3) by adding a challenge-response round to the end of the protocol, obtaining a protocol originally proposed by Roger Needham and Mike Schroeder (see "Using encryption for authentication in large networks of computers" Communications of the ACM 21 (1978), 993-999). It is still used today, and is the basis, for example, of the popular Kerberos system:
Needham-Schroeder Protocol: 1. A --> KDC: A,B,r where r is a new random value 2. KDC --> A: K_B>K_A 3. A --> B: A,B, K_B 4. B --> A: K_AB where r' is a new random value 5. A --> B: K_AB
Keys are sometimes compromised. One would hope that once such a compromise is detected, new keys could be selected and subsequent mischief derailed. Unfortunately, it isn't that simple. To start, consider the case where K_AB becomes known to attacker T. Suppose further, that T had the forethought to have saved message 3
3. A --> B: A,B, K_Bfrom the Needham-Schroeder run in which B was informed of this K_AB value.
T can now force B to use K_AB again, as follows: At the next execution of Needham-Schroeder, T blocks transmission of message 3 to B and instead forwards the saved version of that message (i.e., the message containing the old K_AB). T then intercepts message 4 and impersonates A in step 5 (using this old, compromised K_AB to generate K_AB). So, the result is that B will share an old K_AB with a process (T) that it believes is A.
1. A --> B: n,A,B, K_A 2. B --> KDC: n,A,B, K_A, K_B 3. KDC --> B: n,K_A, K_B, 4. B --> A: n,K_A
Both A and B can be certain that shared key K_AB is new, because the response each receives contains a nonce that was included in that principal's most recent request. This works since KDC checks that the request from A (K_A) and the request from B (K_B) are for the same protocol run by checking that the same value for n appears in the two requests.
A somewhat disturbing attack is possible against a protocol implementation unless care is taken with exactly how values are sent. Messages are just strings of bits, with each field in a message some substring of the whole. Moreover, Dolev-Yao allows an attacker to replace one field by the value found in another. So consider the following attack against an Otway-Rees protocol implementation. It assumes decryption just happens to produce outputs with the following lengths and correspondences:
| D(K_A) = | r1 | n | A | B |
| D(K_A) = | r1 | K_AB | ||
4. T --> A: n,K_A
3. T --> B: n,K_A, K_B
Because of the correspondences we assume, B will decrypt final field "K_B" assuming it was "K_B" and get as new key K_AB the bit string "n,A,B" which is known to T.
4. B --> A: n,K_A
Obviously, type attacks become impossible when this sort of mix-and-match substitution of different kinds of values is impossible. Use of a programming notation in which messages contain typing information is one way to avoid the problem.
We explored above the consequences that a key K_AB might be compromised. This led from Needham-Schroeder to Otway-Rees, and with Otway-Rees we took a short detour to understand type attacks. Let us now return to Needham-Schroeder---this time to investigate the consequences of having the key K_A that a principal A shares with KDC compromised.
The vulnerability actually permits a less passive attack: T need not have intercepted a previous message 2, instead forging a message 1 to receive a message 2 for every principal P). This leaves T free to then initiate a connection to any principal P, impersonating A, until such time that every other principal's key has been changed. So a single compromised key ultimately would require changing all KDC keys!
The defense against this attack is to have B create a nonce r" so that the step ii replay of the old Needham-Schroeder message 3 can be detected by B. This is achieved by prepending to Needham-Schroeder step 1 a protocol (labeled steps a and b) whereby B selects r" and sends it to A for forwarding to KDC, where it is used in forming message 2 (the contents of which are later used in building message 3).
a. A --> B: A,B b. B --> A: A,B,r" 1. A --> KDC: A,B,r,r" 2. KDC --> A: K_B>K_A 3. A --> B: A,B, K_B 4. B --> A: K_AB where r' is a new random value 5. A --> B: K_AB
B can now reject an old message 3, because the nonce r" contained in an old message 3 will not be the same as the nonce it generated in step b of this protocol run.