Interlock protocol


The interlock protocol, as described by Ron Rivest and Adi Shamir, was designed to frustrate eavesdropper attack against two parties that use an anonymous key exchange protocol to secure their conversation. A further paper proposed using it as an authentication protocol, which was subsequently broken.

Brief history

Most cryptographic protocols rely on the prior establishment of secret or public keys or passwords. However, the Diffie–Hellman key exchange protocol introduced the concept of two parties establishing a secure channel without any such prior agreement. Unauthenticated Diffie–Hellman, as an anonymous key agreement protocol, has long been known to be subject to man in the middle attack. However, the dream of a "zipless" mutually authenticated secure channel remained.
The Interlock Protocol was described as a method to expose a middle-man who might try to compromise two parties that use anonymous key agreement to secure their conversation.

How it works

The Interlock protocol works roughly as follows:
  1. Alice encrypts her message with Bob's key, then sends half her encrypted message to Bob.
  2. Bob encrypts his message with Alice's key and sends half of his encrypted message to Alice.
  3. Alice then sends the other half of her message to Bob, who sends the other half of his.
The strength of the protocol lies in the fact that half of an encrypted message cannot be decrypted. Thus, if Mallory begins her attack and intercepts Bob and Alice's keys, Mallory will be unable to decrypt Alice's half-message and re-encrypt it using Bob's key. She must wait until both halves of the message have been received to read it, and can only succeed in duping one of the parties if she composes a completely new message.

The Bellovin/Merritt Attack

Davies and Price proposed the use of the Interlock Protocol for authentication in a book titled Security for Computer Networks. But an attack on this was described by Steven M. Bellovin & Michael Merritt. A subsequent refinement was proposed by Ellison.
The Bellovin/Merritt attack entails composing a fake message to send to the first party. Passwords may be sent using the Interlock Protocol between A and B as follows:

 A B
Ea,b<1>------->
<-------Ea,b<1>
Ea,b<2>------->
<-------Ea,b<2>

where Ea,b is message M encrypted with the key derived from the Diffie–Hellman exchange between A and B, <1>/<2> denote first and second halves, and Pa/Pb are the passwords of A and B.
An attacker, Z, could send half of a bogus message—P?--to elicit Pa from A:

A Z B
Ea,z<1>------>
<------Ea,z<1>
Ea,z<2>------>
 Ez,b<1>------>
 <------Ez,b<1>
 Ez,b<2>------>
 <------Ez,b<2>

At this point, Z has compromised both Pa and Pb. The attack can be defeated by verifying the passwords in parts, so that when Ea,z<1> is sent, it is known to be invalid and Ea,z<2> is never sent. However, this does not work when the passwords are hashed, since half of a hash is useless, according to Bellovin. There are also several other methods proposed in, including using a shared secret in addition to the password. The forced-latency enhancement can also prevent certain attacks.

Forced-Latency Interlock Protocol

A modified Interlock Protocol can require B to delay all responses for a known duration:

A B
Ka------------->
<-------------Kb
Ea,b<1>---->
<----Ea,b<1> 
Ea,b<2>---->
<----Ea,b<2> 
<----------data

Where "data" is the encrypted data that immediately follows the Interlock Protocol exchange, encoded using an all-or-nothing transform to prevent in-transit modification of the message. Ma<1> could contain an encrypted request and a copy of Ka. Ma<2> could contain the decryption key for Ma<1>. Mb<1> could contain an encrypted copy of Kb, and Mb<2> could contain the decryption key for Mb<1> and the response, such as OK, or NOT FOUND, and the hash digest of the data.
MITM can be attempted using the attack described in the Bellovin paper :

A Z B
Ka------------->Kz------------->
<---------------Kz<-----------Kb
Ea,z<1>---->
<----Ea,z<1> 
Ea,z<2>---->
 Ez,b<1>----->
 <-----Ez,b<1> 
<----Ea,z<2>
 Ez,b<2>----->
 <-----Ez,b<2> 
 <------------data
<----------data

In this case, A receives the data approximately after 3*T, since Z has to perform the interlocking exchange with B. Hence, the attempted MITM attack can be detected and the session aborted.
Of course, Z could choose to not perform the Interlock Protocol with B but then the session would be between A and Z, not A, Z, and B: Z wouldn't be in the middle. For this reason, the interlock protocol cannot be effectively used to provide authentication, although it can ensure that no third party can modify the messages in transit without detection.