The three-pass protocol

The three-pass protocol lets two people who've never met and share no secret send each other a message an eavesdropper can't read, without ever exchanging a key. It's the mathematical form of an old riddle. Alice wants to send Bob a treasure through a postman who opens anything unlocked, and neither she nor Bob can send a key. Below: the protocol, why XOR can't be used for it but exponentiation can, where its security comes from, why almost nobody uses it today, and what replaced it.

The riddle, and its answer

Alice puts the treasure in a chest and locks it with a padlock only she can open, then sends it. Bob can't open it, but he adds his own padlock and sends it back. Alice removes her padlock and sends the chest again, now locked only with Bob's. Bob opens it. That's three trips. The chest was never unlocked on the road, and no key ever traveled. (You can play it in the treasure-chest puzzle.)

In a computer, a lock is an encryption function. Alice's lock is EA with its undoing DA, Bob's is EB and DB, and the three messages are:

1. Alice → Bob: EA(m)
2. Bob → Alice: EB(EA(m))
3. Alice → Bob: DA(EB(EA(m))), which must equal EB(m). Bob applies DB and reads m.

Step 3 only works if Alice can take her lock off from underneath Bob's. That requires the two encryptions to be commutative: EB(EA(m)) = EA(EB(m)) for all keys. Most ciphers aren't. Encrypt with AES under one key and again under another, and you can't remove the inner layer without removing the outer one first. The protocol needs a cipher with this unusual property.

Commutative ciphers, and why XOR fails

The simplest commutative operation is XOR, the "add without carrying" of the binary world. If a lock is "XOR with a secret key", then (m ⊕ a) ⊕ b = (m ⊕ b) ⊕ a, and the protocol runs: Alice sends m ⊕ a, Bob sends m ⊕ a ⊕ b, Alice sends m ⊕ b. With random keys as long as the message, each transmission looks like noise. But an eavesdropper who records all three gets a gift:

Each key appears twice and cancels, and the message appears three times, which XOR reduces to once. XOR is linear, and the same property that makes the locks commute makes them transparent to anyone who combines the transmissions. A useful lock has to commute and resist being peeled off. (The XOR tool lets you try it on real data.)

Exponentiation: the lock that works

Raising a number to a power modulo a prime p commutes, and combining transmissions doesn't undo it. Let p be a large prime both parties know. Alice picks a secret exponent a with gcd(a, p − 1) = 1 and computes its inverse a′, where a·a′ ≡ 1 (mod p − 1). Bob does the same with b and b′. The message is a number m below p.

1. Alice → Bob: ma mod p
2. Bob → Alice: (ma)b mod p
3. Alice → Bob: ((ma)b)a′ mod p = mb mod p
4. Bob computes (mb)b′ mod p = m.

Why does raising to a′ remove the lock a? Fermat's little theorem says mp−1 ≡ 1 (mod p) for any m not divisible by p. Since a·a′ = 1 + k(p − 1) for some integer k, ma·a′ = m · (mp−1)k ≡ m. And (ma)b = mab = (mb)a, which is the commutativity. You can follow the numbers by hand with p = 23, m = 7, a = 3, b = 5 (their inverses modulo 22 are 15 and 9). scripts/examples/three-pass-small.mjs computes them:

Bob ends with 7. People often credit the exponent-modulo-a-prime version to Adi Shamir (around 1980), whose "no-key protocol" is the three-pass idea. James Massey and Jim Omura proposed a variant over finite fields of characteristic two in 1982, covered by US patent 4,567,600, and it's often called Massey–Omura. Commutative ciphers also turn up in "mental poker" (Shamir, Rivest and Adleman, 1981), where players shuffle and lock a deck in turn, and you'll meet the idea again in some secure-computation schemes.

Where the security comes from

What does the eavesdropper Eve see? ma, mab and mb, and she knows p. To find m she has to undo one of the powers, recovering an exponent from the result of raising to it. That's a discrete logarithm, and nobody knows a fast method for it when p is large. It's the same hard problem that protects Diffie–Hellman. Given x₁ = ma and x₂ = x₁b, Eve solves for b and then m = (mb)b⁻¹. The puzzle's level 4 does exactly this, and it's quick when p is small: the baby-step giant-step method needs about √p steps, a thousand for a six-digit prime. Making it hopeless takes a big prime. NIST's key-management guidance rates a 2,048-bit prime at about 112 bits of security and a 3,072-bit one at 128 (the calculator prints how the generic attack scales: 2¹⁰²⁴ steps for 2,048 bits, far beyond any hardware). Real deployments therefore use primes of at least 2,048 bits, or switch to elliptic curves.

Why it's rarely used

• Three messages, in both directions. A whole conversation has to happen before the first byte is delivered. Public-key encryption needs one message once you know the recipient's public key, and Diffie–Hellman needs two.
• No authentication. The protocol hides the message from someone who listens, but not from someone who also changes what's sent. Suppose the postman adds his own padlock to Alice's chest and sends it back. Alice can't tell whose lock it is, takes off her own, and returns the chest for the postman to open. That's a man-in-the-middle attack. The fix is some way for Alice to know whose lock she's looking at, which is the problem of authentication (safety numbers, certificates, signatures). The puzzle's level 5 plays it out.
• It needs a commutative cipher. The standard modern ciphers, AES among them, aren't commutative, so the protocol can't simply reuse them, and the commutative ones (modular exponentiation, and some stream ciphers) have their own limits. A stream cipher or plain XOR commutes and fails as shown above.
• Public-key cryptography won. From 1976 (Diffie and Hellman) and 1977 (RSA) onward, one-message systems with independent authentication, built from signatures and certificates, are what the internet runs on. GCHQ had also found the idea earlier, in secret (public-key cryptography was invented twice).

How cipher.ink relates to it

cipher.ink doesn't solve Alice's problem, and we say so. A passphrase, or the key in a secret link, is a secret that has to reach the reader somehow, which is exactly where the postman riddle starts. What cipher.ink does is shrink the problem. Passphrase mode asks you to send the passphrase by a second channel, so someone who sees the link never sees the key. A secret link puts the key in the part of the address after the #, which the server never receives (why the fragment never reaches the server). Neither one is the three-pass protocol, and neither provides authentication, because nobody has an account to prove who they are (client-side encryption, honestly). If you need to be sure who you're talking to, use end-to-end encrypted messaging with verified keys.