Tag Info

The three-pass protocol uses commutative encryption to let two people communicate privately without having to exchange keys in advance.

The three-pass protocol is a cryptographic protocol that allows two people to communicate privately without having to exchange keys in advance. It is based on commutative encryption, i.e. an encryption method $E$, and its corresponding decryption method $D$, which allow a message encrypted with two different keys to be decrypted using those keys in either order.

The protocol gets its name from the fact that transmitting a secret message $M$ from Alice to Bob requires the exchange of three messages:

1. ${\rm Alice \to Bob}: \quad C_A = E(K_A, M)$
2. ${\rm Bob \to Alice}: \quad C_{AB} = E(K_B, C_A)$
3. ${\rm Alice \to Bob}: \quad C_B = D(K_A, C_{AB})$

Bob then calculates $M = D(K_B, C_B) = D(K_B, D(K_A, E(K_B, E(K_A, M))))$. Because $(E,D)$ is a commutative encryption method, the decryption succeeds even though it's done in the "wrong order".

For the three-pass protocol to be secure, an attacker observing the encrypted messages $C_A$, $C_{AB}$ and $C_B$ must not be able to determine the secret message $M$. A trivial implementation of the three-pass protocol using a synchronous stream cipher $E(K,M) = D(K,M) = S(K) \oplus M$ is not secure, since an attacker can calculate

$$C_A \oplus C_{AB} \oplus C_B = (S_A \oplus M) \oplus (S_B \oplus S_A \oplus M) \oplus (S_B \oplus M) = M,$$

where $S_A = S(K_A)$ and $S_B = S(K_B)$ are the keystreams used by Alice and Bob.

The first secure three-pass protocol was developed by Adi Shamir circa 1980, and is based on modular exponentiation, i.e. $E(K, M) = M^{e_K} \bmod p$, $D(K, C) = C^{d_K} \bmod p$, where $p$ is a large prime and $e_K d_K \equiv 1 \pmod{p-1}$. The Massey–Omura cryptosystem, a similar system developed in 1982 by James Massey and Jim K. Omura, uses exponentiation in the Galois field $GF(2^k)$ instead.

The three-pass protocol does not (and generally cannot) provide authentication. In particular, this means that, if Alice and Bob have no means of authenticating each other, an attacker controlling the communications channel between them can impersonate Bob to Alice and vice versa, and can thus decrypt and/or modify any messages, or even send completely bogus messages to either party.