In cryptography, the interlock protocol, as described by Ron Rivest and Adi Shamir, is a protocol 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.
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 (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[1] 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.[2] But an attack on this was described by Steven M. Bellovin & Michael Merritt.[3] A subsequent refinement was proposed by Ellison.[4]
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.[3] There are also several other methods proposed in,[5][6][7][8] including using a shared secret in addition to the password. The forced-latency enhancement can also prevent certain attacks.
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 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 (Z being the man-in-the-middle):
A Z B Ka------------->Kz-------------> <---------------Kz<-----------Kb Ea,z(Ma)<1>----> <----Ea,z(Mz)<1> (delayed response) Ea,z(Ma)<2>----> Ez,b(Ma)<1>-----> <-----Ez,b(Mb)<1> (delayed response) <----Ea,z(Mz)<2> Ez,b(Ma)<2>-----> <-----Ez,b(Mb)<2> (delayed response) <------------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 (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, although it can ensure that no third party can modify the messages in transit without detection.
Diffie–Hellman (DH) key exchange is a mathematical method of securely generating a symmetric cryptographic key over a public channel and was one of the first public-key protocols as conceived by Ralph Merkle and named after Whitfield Diffie and Martin Hellman. DH is one of the earliest practical examples of public key exchange implemented within the field of cryptography. Published in 1976 by Diffie and Hellman, this is the earliest publicly known work that proposed the idea of a private key and a corresponding public key.
Kerberos is a computer-network authentication protocol that works on the basis of tickets to allow nodes communicating over a non-secure network to prove their identity to one another in a secure manner. Its designers aimed it primarily at a client–server model, and it provides mutual authentication—both the user and the server verify each other's identity. Kerberos protocol messages are protected against eavesdropping and replay attacks.
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security. There are many kinds of public-key cryptosystems, with different security goals, including digital signature, Diffie-Hellman key exchange, public-key key encapsulation, and public-key encryption.
The Secure Shell (SSH) Protocol is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution.
In computing, Internet Protocol Security (IPsec) is a secure network protocol suite that authenticates and encrypts packets of data to provide secure encrypted communication between two computers over an Internet Protocol network. It is used in virtual private networks (VPNs).
In cryptography, a key-agreement protocol is a protocol whereby two parties generate a cryptographic key as a function of information provided by each honest party so that no party can predetermine the resulting value. In particular, all honest participants influence the outcome. A key-agreement protocol is a specialisation of a key-exchange protocol.
In cryptography and computer security, a man-in-the-middle (MITM) attack, or on-path attack, is a cyberattack where the attacker secretly relays and possibly alters the communications between two parties who believe that they are directly communicating with each other, where in actuality the attacker has inserted themselves between the two user parties.
In computer security, challenge-response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated.
The Needham–Schroeder protocol is one of the two key transport protocols intended for use over an insecure network, both proposed by Roger Needham and Michael Schroeder. These are:
Key exchange is a method in cryptography by which cryptographic keys are exchanged between two parties, allowing use of a cryptographic algorithm.
A replay attack is a form of network attack in which valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and re-transmits it, possibly as part of a spoofing attack by IP packet substitution. This is one of the lower-tier versions of a man-in-the-middle attack. Replay attacks are usually passive in nature.
The Secure Remote Password protocol (SRP) is an augmented password-authenticated key exchange (PAKE) protocol, specifically designed to work around existing patents.
Encrypted Key Exchange is a family of password-authenticated key agreement methods described by Steven M. Bellovin and Michael Merritt. Although several of the forms of EKE in this paper were later found to be flawed, the surviving, refined, and enhanced forms of EKE effectively make this the first method to amplify a shared password into a shared key, where the shared key may subsequently be used to provide a zero-knowledge password proof or other functions.
In cryptography, a zero-knowledge password proof (ZKPP) is a type of zero-knowledge proof that allows one party to prove to another party that it knows a value of a password, without revealing anything other than the fact that it knows the password to the verifier. The term is defined in IEEE P1363.2, in reference to one of the benefits of using a password-authenticated key exchange (PAKE) protocol that is secure against off-line dictionary attacks. A ZKPP prevents any party from verifying guesses for the password without interacting with a party that knows it and, in the optimal case, provides exactly one guess in each interaction.
In cryptography, a password-authenticated key agreement (PAK) method is an interactive method for two or more parties to establish cryptographic keys based on one or more party's knowledge of a password.
SPEKE is a cryptographic method for password-authenticated key agreement.
In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key-agreement protocols that gives assurances that session keys will not be compromised even if long-term secrets used in the session key exchange are compromised, limiting damage. For HTTPS, the long-term secret is typically the private key of the server. Forward secrecy protects past sessions against future compromises of keys or passwords. By generating a unique session key for every session a user initiates, the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key. This by itself is not sufficient for forward secrecy which additionally requires that a long-term secret compromise does not affect the security of past session keys.
Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.
Mutual authentication or two-way authentication refers to two parties authenticating each other at the same time in an authentication protocol. It is a default mode of authentication in some protocols and optional in others (TLS).
In cryptography, the Salted Challenge Response Authentication Mechanism (SCRAM) is a family of modern, password-based challenge–response authentication mechanisms providing authentication of a user to a server. As it is specified for Simple Authentication and Security Layer (SASL), it can be used for password-based logins to services like LDAP, HTTP, SMTP, POP3, IMAP and JMAP (e-mail), XMPP (chat), or MongoDB and PostgreSQL (databases). For XMPP, supporting it is mandatory.
References
↑ R. Rivest and A. Shamir. How to Expose an Eavesdropper. CACM, Vol. 27, April 1984, pp. 393-395.
↑ D. W. Davies and W. L. Price. Security for Computer Networks. John Wiley & Sons, second ed., 1989.
↑ C. Ellison. Establishing Identity Without Certification Authorities. Proceedings of the Sixth Annual USENIX Security Symposium, San Jose, July 1996, pp. 67-76.
↑ R. H. Morris and K. Thompson, "Unix password security," Communications of the ACM, vol. 22, p. 594, November 1979
↑ F. T. Grampp and R. H Morris, "Unix operating system security," AT&T Bell Laboratories Technical Journal, vol. 63 pp. 1649-1672, October 1984
↑ D. V. Klein, "Foiling the cracker": A survey of, and improvements to, password security," in Proceedings of the USENIX UNIX Security Workshop, (Portland), pp. 5-14, August 1990
↑ P. Leong and C. Tham, "Unix password encryption considered insecure" in Proc. Winter USENIX Conference, (Dallas), 1000
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
