The Three-Pass Protocol Magic

Or how Alice unlocks her box while it is inside Bob’s locked box.

During my recent research, I encountered a nice cryptographic protocol named: the “Three-pass protocol”, originally developed by Adi Shamir.

In this post, I will demonstrate its basic form (there are further developments and evolutions for this protocol, please check the Wikipedia link above).

For the algorithm implementation I use Python withing Google Colaboratory here.

Alice wishes to send a secret to Bob through a public communication channel without them exchanging cryptographic keys beforehand.
The shared secret may be the secret-message itself, or a shared secret key, or a password to be used in an encryption mechanism for encrypting data in a later communication session.
Here I use the shared secret as a shared password that is then used to encrypt and decrypt a secret message.

Imagine the following scenario:
Alice and Bob are students sitting in the same classroom. This is a classroom of students from different faculties (where many of them don’t know each other).
Alice wants to pass a secret message to Bob who sits on the other side of the class.
Alice writes her secret message on a note, puts the note in a small box, and locks the box with her padlock.
She writes “To Bob” on the box and asks the other students to pass the box to Bob.
When Bob receives the box, he adds his padlock to the box, writes “To Alice,” and asks the students to pass the box back to Alice.
Alice then receives the box, removes her padlock, writes on the box “To Bob” and asks the students to pass the box again.
At this point, when Bob receives the box, he removes his padlock, opens the box, and reads the secret message.

Note that this is a non-authenticated protocol. No sender nor responder trust the other side’s authenticity.
In our example, the box may reach Mallory who is also in the class.
Since people don’t know each other in this class, Mallory, who sits on the far side from Alice and has received the box, may put his padlock on the box and send it back to Alice.
Alice can’t see who received the box and she doesn’t really know who the owner of the other padlock on the box is. Alice believes that she is communicating with Bob, while she is actually communicating with Mallory.

In the classroom scenario, Bob puts his padlock on the box near Alice’s, and Alice can remove her padlock while Bob’s padlock is locked.
In the three-pass protocol we place a second encryption (encryption = locked padlock) on top of the first one.
It is as if Bob puts Alice’s locked box inside his box and locks his box using his padlock.
For this protocol to work, it must be possible to remove the first (Alice’s) encryption after a second (Bob’s) encryption has been performed, which means that Alice unlocks her box while it is inside Bob’s locked box.

Cool!

ka : Alice’s encryption key
dka : Alice’s decryption key
kb : Bob’s encryption key
m : Message
E : Encryption
D : Decryption

D(dka, E(kb, E(ka, m))) = E(kb, m)

This is possible with a commutative encryption, which is an encryption that is order-independent.

E(ka, E(kb, m)) = E(kb, E(ka, m))

And then:

D(dka, E(kb, E(ka, m))) = D(dka, E(ka, E(kb, m))) = E(kb, m)

The Three-Pass protocol uses modular multiplicative inverse to remove the keys.

Lets walk the algorithm’s steps:

Shared secret key: ks
Alice’s keys: ka, ka⁻¹
Bob’s keys: kb, kb⁻¹

1. Decide on the numbers’ bits length (e.g., 128 bits).
2. Everyone agree on a prime number p as a public key
3. Each user selects a random number k, that is a coprime to p-1

𝑔𝑐𝑑(𝑘, 𝑝−1)=1

4. Each user computes k⁻¹, the modular multiplicative inverse of their k

k⁻¹k ≅ 1(mod p-1)

Alice’s keys: ka, ka⁻¹
Bob’s keys: kb kb⁻¹

5. Alice chooses a shared-secret-key ks to be shared with Bob

6. Alice encrypts a message using the shared secret:

7. Alice sends the following to Bob:

8. Bob sends the following to Alice:

9. Alice sends the following to Bob:

10. Bob computes the following:

11. Verify that Bob’s and Alice’s shared-secret-keys are identical:

assert ks’ == ks

12. Bob decrypts Alice’s encrypted message using the shared secret key he computed:

m’= D(ks’, c)

13. Verify that the original and received messages are identical:

assert m’ == m

The execution of the algorithm’s code in the colab notebook produces the following output (you will get different generated numbers):