The paper present a protocol for establishing secure communications over an insecure communications channel in the absence of trusted third parties or authenticated keys.
Key authentication is the process of assuring that the key of person A held by person B does in fact belong to"person A and vice versa.
Eavesdropper: someone who wants to monitor the communication between two parties without tampering with the data and without exposing his existence.
The protocol forces a potential eavesdropper — if they want to understand the communication — to reveal their existence by modifying the communication.
An eavesdropper has to be as transparent as possible to minimize detection: They can tamper with the the ciphertext stream (by deleting, delaying, substituting, or inserting ciphertexts), but they can’t tamper with the cleartext received by the communicating parties.
In the context of a public-key crypto-system, a successful eavesdropper must actively participate in the key exchange protocol.
A well-known and serious problem with unauthenticated public-key exchange protocols is that the communication between two parties, A and B, can be transparently monitored by an eavesdropper, C, who inserts into the communication line an encryption/decryption device as follows:
When A wants to communicate with B, C replaces both the public key, KA, that A sends to B and the public key, KB, that B sends to A by his own public key, KC (or by a pair of keys, KC' and KC'', if the keys contain an identifying prefix).
Whenever A sends an encrypted message EKC(MA) to B, C intercepts it, decrypts it in order to read MA, and then reencrypts it as EKB(MA) before sending it to B.
Messages, MB, sent by B to A are handled in a similar way.
The protocol proposed in this paper forces the eavesdropper C to act in a non-transparent way — i.e: modifying the cleartext. Thus, it only works (i.e: capable of exposing an eavesdropper) if A and B share knowledge of each other that C is not able to emulate. E.g. Tone of voice in a video call app, patterns in text in a text app, etc.
The "Interlock" protocol: After A and B have exchanged their public keys, they exchange a pair of data blocks, MA and MB, as follows:
A encrypts MA under KB but sends B only the first half of the bits of the resulting ciphertext EKB(MA).
B encrypts MB under KA and sends A the first half of EKA(MB).
A sends B the second half EKB(MA).
B sends A the second half of EKA(MB).
A and B concatenate the two halves of EKA(MB) and EKB(MA), respectively, and use their secret decryption keys to read the messages.
Each side performs a step in this protocol only after they receives the information sent by the other side in the previous step.
Any attempt by C to read MA and MB will either garble or completely change the communication between A and B:
If C tries to use the relay attack described in (7), they can’t decrypt half of MA. They have to wait until the end to get the full MA to decrypt. But
Because the protocol wouldn’t proceed without each previous step (11), C is forced to commit to the first half of the ciphertexts before they know the full message. They have two options:
Send the message MA as-is to B and MB as-is to A: However, since the eavesdropper has intercepted and changed the public keys on both sides as described in (7), neither side will be able to decrypt the message using their private keys.
Invent a new MA' and MB': By the time he discovers the true values of MA and MB in Steps 3 and 4, it is too late to change MA' and MB', since they are already committed to the first halves of their ciphertexts.
The key is that the transmission of the first part effectively commits the sender to the final cleartext although the cleartext cannot be computed without the use of the second half as well.
Hence, other two-part methods can be used instead of transmitting the two halves of the cipher-text separately as proposed above. E.g: the first part could be a "cryptographic checksum" or "one-way function" of the ciphertext, and the second part could be the ciphertext itself.
If A and B want to exchange n blocks of information, they can repeat the interlock protocol for each pair of blocks. While a delayed relay attack can be successful in this scenario, C will be forced to deliver messages out of phase, and hence, wouldn’t be transparent to A and B.
One mode of operation in which the existence of an eavesdropper cannot be exposed is a one-way communication between A and B.