IT Certifications and Attacks on Cryptography

19.5.4 Interleaving attacks

An interleaving attack is a special type of replay attack where Mallory executes multiple protocol sessions in parallel to compromise the protocol’s security. Interleaving attacks are hard to spot even for seasoned cryptographers, so we’ll use a concrete example to show how such attacks work.

Figure 19.12 shows a cryptographic protocol for establishing a shared secret key. First, Alice sends Bob her name A and a nonce NA so Bob knows who is trying to communicate with him.

Upon receiving Alice’s message, Bob sends a message to the server containing his name B, his nonce NB, and the pair (A,NA) encrypted under the secret key kBS shared by Bob and the server. The server, in turn, sends Alice a message containing the following data:

• Bob’s nonce NB
• The triple (B,kAB,NA) encrypted under secret key kAS, shared by Alice and the server
• The triple (A,kAB,NB) encrypted under secret key kBS, shared by Bob and the server

where kAB is a shared session key that the server generated for Alice and Bob. The first triple (B,kAB,NA) does the following:

• Tells Alice that the server has indeed been talking to Bob
• Demonstrates that the server’s message is fresh (since it contains Alice’s nonce NA)
• Gives Alice the session key kAB

The second triple (A,kAB,NB) is to be passed to Bob. So, in the final message of the protocol, Alice sends (A,kAB,NB), encrypted under kBS, and NB encrypted under kAB to Bob. This message tells Bob that the server has indeed recently talked to Alice (via NB) and gives him the session key kAB. Moreover, because Alice used the session key kAB to encrypt Bob’s nonce NB, Bob is assured that Alice obtained the session key recently – that is, it guarantees the freshness of this message and that of the session key.

At first glance, the protocol in Figure 19.12 appears to be secure. It allows Alice and Bob to verify the freshness of the messages they receive and since the session key kAB is generated by the trusted server, there is seemingly no way to compromise security. In reality, however, that protocol is vulnerable to an interleaving attack [170].

Figure 19.12: Example of a key establishment protocol vulnerable to an interleaving attack

Figure 19.13 illustrates an interleaving attack on the key establishment protocol we just introduced. The attack starts with Mallory either eavesdropping on the initial message from Alice to Bob (alternatively, Mallory could send that message herself). Upon receiving Alice’s message, Bob sends a message to the server containing his name B, his nonce NB, and the pair (A,NA) encrypted under the secret key kBS shared by Bob and the server. So far, the protocol execution is the same as in the benign case shown in Figure 19.12.

Figure 19.13: Interleaving attack on a key establishment protocol

However, after Bob’s message to Alice, Mallory initiates a second protocol run pretending to be Alice. She concatenates the nonces from the first protocol run and uses the result (NA,NB) as the nonce in the first message of the second protocol run. In Figure 19.13, messages from the first run are denoted by (1) and those from the second protocol by (2).

Upon receiving the message A,(NA,NB)∗ – which Bob believes to come from Alice – Bob responds with a message to the server. In the benign case, this message would be B, NB, ekBS(A,NA). However, because Alice manipulated this message by replacing NA with (NA,NB), Bob responds with B, NB′, ekBS(A,NA,NB). Here, NB′ denotes a nonce Bob chose in the second protocol run that is different from NB used in the first protocol run.

Mallory intercepts Bob’s response B, NB′, ekBS(A,NA,NB)(2) and ends the second protocol run. She then uses the encrypted chunk ekBS(A,NA,NB) to construct the last message for the first protocol run:

Because Bob’s nonce NB was previously transmitted in plaintext, the session key kAB is actually NA and was also transmitted in plaintext, Mallory can compute ekAB(NB).

As a result, Mallory has successfully impersonated Alice while communicating with Bob and obtained the session key. The attack is an interleaving attack because Mallory uses multiple protocol runs to construct the elements of the last message ekBS(A,NA(= kAB),NB), ekAB(NB). Without the parallel second protocol run, Mallory would not be able to perform the attack.