The interlock protocol, as described by Ron Rivest

Ron Rivest

Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...

 and Adi Shamir

Adi Shamir

Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...

, 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

Diffie-Hellman key exchange

Diffie–Hellman key exchange Synonyms of Diffie–Hellman key exchange include:*Diffie–Hellman key agreement*Diffie–Hellman key establishment*Diffie–Hellman key negotiation...

 protocol introduced the concept of two parties establishing a secure channel (that is, with at least some desirable security properties) 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: Alice encrypts her message with Bob's key, then sends half her encrypted message to Bob. Bob encrypts his message with Alice's key and sends half of his encrypted message to Alice. 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 (encrypted using her key) 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

Steven M. Bellovin

Steven M. Bellovin is a researcher on computer networking and security. He is currently a Professor in the Computer Science department at Columbia University, having previously been a Fellow at AT&T Labs Research in Florham Park, New Jersey.- Career :...

 & 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(Pa)<1>------->

<-------Ea,b(Pb)<1>

Ea,b(Pa)<2>------->

<-------Ea,b(Pb)<2>

where Ea,b(M) 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(Pa)<1>------>

<------Ea,z(P?)<1>

Ea,z(Pa)<2>------>

                 Ez,b(Pa)<1>------>

                 <------Ez,b(Pb)<1>

                 Ez,b(Pa)<2>------>

                 <------Ez,b(Pb)<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(P?)<1> is sent, it is known to be invalid and Ea,z(Pa)<2> is never sent (suggested by Davies). 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 (the server) to delay all responses for a known duration:

A              B

Ka------------->

<-------------Kb

Ea,b(Ma)<1>---->

<----Ea,b(Mb)<1> (B delays response a fixed time, T)

Ea,b(Ma)<2>---->

<----Ea,b(Mb)<2> (delay again)

<----------data)

Where "data" is the encrypted data that immediately follows the Interlock Protocol exchange (it could be anything), encoded using an all-or-nothing transform

All-or-nothing transform

In cryptography, an all-or-nothing transform , also known as an all-or-nothing protocol, is an encryption mode which allows the data to be understood only if all of it is known. AONTs are not encryption, but frequently make use of symmetric ciphers and may be applied before encryption...

 to prevent in-transit modification of the message.

MITM can be attempted using the attack described in the Bellovin paper (Z being the man-in-the-middle):

A              Z              B

Ka------------->Kz------------->

<--------------
Ea,z(Ma)<1>---->

<--------------Ea,z(Mz)<1>       (delayed response)

Ea,z(Ma)<2>---->

<--------------Ea,z(Mz)<2>       (delayed response)

              Ez',b(Ma)<1>---->

              <----Ez',b(Mb)<2> (delayed response)

              Ez',b(Ma)<2>---->

              <----Ez',b(Mb)<2> (delayed response)

              <-------------data

<---------data

In this case, A receives the data approximately after 2*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 (opting to instead send his own Mb) 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

Authentication

Authentication is the act of confirming the truth of an attribute of a datum or entity...

, although it can ensure that no third party can modify the messages in transit without detection.

See also

• Computer security
  Computer security
  Computer security is a branch of computer technology known as information security as applied to computers and networks. The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to...
  
  
• Cryptanalysis
  Cryptanalysis
  Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
  
  
• Secure channel
  Secure channel
  In cryptography, a secure channel is a way of transferring data that is resistant to interception and tampering.A confidential channel is a way of transferring data that is resistant to interception, but not necessarily resistant to tampering....
  
  
• Key management
  Key management
  Key management is the provisions made in a cryptography system design that are related to generation, exchange, storage, safeguarding, use, vetting, and replacement of keys. It includes cryptographic protocol design, key servers, user procedures, and other relevant protocols.Key management concerns...
  
  
• Cryptographic protocol
  Cryptographic protocol
  A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
  
  

External links

• Interlock protocol for authentication
• Full-Duplex-Chess Grandmaster (was: anonymous DH & MITM)
• Defense Against Middleperson Attacks (Zooko's Forced-Latency Protocol)