{"history":[],"article":{"id":"a30609a2-51c2-4917-9dfe-849a3fb4cd40","title":"Interlock protocol","slug":"interlock-protocol","content":":::summary\n:::\n\n# \nIn [cryptography](https://bliptext.com/articles/cryptography), the **interlock [protocol](https://bliptext.com/articles/cryptographic-protocol)**, as described by [Ron Rivest](https://bliptext.com/articles/ron-rivest) and [Adi Shamir](https://bliptext.com/articles/adi-shamir), is a [protocol](https://bliptext.com/articles/cryptographic-protocol) designed to frustrate eavesdropper attack against two parties that use an anonymous [key exchange](https://bliptext.com/articles/key-exchange) [protocol](https://bliptext.com/articles/cryptographic-protocol) to secure their conversation.\nA further paper proposed using it as an authentication protocol, which was subsequently broken.\n\n# Brief history\nMost cryptographic protocols rely on the prior establishment of secret or public keys or passwords.\nHowever, the [Diffie–Hellman key exchange](https://bliptext.com/articles/diffie-hellman-key-exchange) 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.\nUnauthenticated Diffie–Hellman, as an anonymous key agreement protocol, has long been known to be subject to [man in the middle attack](https://bliptext.com/articles/man-in-the-middle-attack).\nHowever, the dream of a \"zipless\" mutually authenticated secure channel remained.\nThe 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.\n\n# How it works\nThe Interlock protocol works roughly as follows:\nThe strength of the protocol lies in the fact that half of an encrypted message cannot be decrypted.\nThus, 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.\nShe 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.\n\n# The Bellovin/Merritt Attack\nDavies and Price proposed the use of the Interlock Protocol for authentication in a book titled Security for Computer Networks.\nBut an attack on this was described by [Steven M. Bellovin](https://bliptext.com/articles/steven-m-bellovin) & Michael Merritt.\nA subsequent refinement was proposed by Ellison.\nThe Bellovin/Merritt attack entails composing a fake message to send to the first party.\nPasswords may be sent using the Interlock Protocol between A and B as follows:\nA B Ea,b(Pa)<1>--->\n<---Ea,b(Pb)<1>\nEa,b(Pa)<2>--->\n<---Ea,b(Pb)<2>\nwhere 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.\nAn attacker, Z, could send half of a bogus message—P?--to elicit Pa from A:\nA Z B Ea,z(Pa)<1>-->\n<--Ea,z(P?)<1>\nEa,z(Pa)<2>-->\nEz,b(Pa)<1>-->\n<--Ez,b(Pb)<1>\nEz,b(Pa)<2>-->\n<--Ez,b(Pb)<2>\nAt this point, Z has compromised both Pa and Pb.\nThe 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).\nHowever, this does not work when the passwords are hashed, since half of a hash is useless, according to Bellovin.\nThere are also several other methods proposed in, including using a shared secret in addition to the password.\nThe forced-latency enhancement can also prevent certain attacks.\n\n# Forced-Latency Interlock Protocol\nA modified Interlock Protocol can require B (the server) to delay all responses for a known duration:\nA B Ka->\n<-Kb\nEa,b(Ma)<1>>\n (B delays response a fixed time, T) Ea,b(Ma)<2>>\n (delay again)\n<--data\nWhere \"data\" is the encrypted data that immediately follows the Interlock Protocol exchange (it could be anything), encoded using an [all-or-nothing transform](https://bliptext.com/articles/all-or-nothing-transform) to prevent in-transit modification of the message.\nMa<1> could contain an encrypted request and a copy of Ka.\nMa<2> could contain the decryption key for Ma<1>.\nMb<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.\nMITM can be attempted using the attack described in the Bellovin paper (Z being the man-in-the-middle):\nA Z B Ka->Kz->\n<---Kz<---Kb\nEa,z(Ma)<1>>\n (delayed response)\nEa,z(Ma)<2>>\nEz,b(Ma)<1>->\n<-Ez,b(Mb)<1> (delayed response)\n\nEz,b(Ma)<2>->\n<-Ez,b(Mb)<2> (delayed response)\n\n \nEa,b(Pa) --->\n \nwhere Ea,b(M) is message M encrypted with the key derived from the Diffie–Hellman exchange between A and B, / denote first and second halves, and Pa/Pb are the passwords of A and B.\nAn attacker, Z, could send half of a bogus message—P?--to elicit Pa from A:\nA Z B Ea,z(Pa) -->\n \nEa,z(Pa) -->\nEz,b(Pa) -->\n \nEz,b(Pa) -->\n \nAt this point, Z has compromised both Pa and Pb.\nThe attack can be defeated by verifying the passwords in parts, so that when Ea,z(P?) is sent, it is known to be invalid and Ea,z(Pa) is never sent (suggested by Davies).\nHowever, this does not work when the passwords are hashed, since half of a hash is useless, according to Bellovin.\nThere are also several other methods proposed in, including using a shared secret in addition to the password.\nThe forced-latency enhancement can also prevent certain attacks.\n\n# Forced-Latency Interlock Protocol\nA modified Interlock Protocol can require B (the server) to delay all responses for a known duration:\nA B Ka->\n >\n (B delays response a fixed time, T) Ea,b(Ma) >\n (delay again)\n could contain an encrypted request and a copy of Ka.\nMa could contain the decryption key for Ma .\nMb could contain an encrypted copy of Kb, and Mb could contain the decryption key for Mb and the response, such as OK, or NOT FOUND, and the hash digest of the data.\nMITM can be attempted using the attack described in the Bellovin paper (Z being the man-in-the-middle):\nA Z B Ka->Kz->\n >\n (delayed response)\nEa,z(Ma) >\nEz,b(Ma) ->\n (delayed response)\n \nEz,b(Ma) ->\n (delayed response)\n

History