The Shared Secret Problem

The scrambling system protected messages between customers and GlagalCloud. But a new request pushed the system further. Bretchka and Hjelvran the trader wanted to exchange messages with each other, routed through GlagalCloud. Bretchka was selling cattle to Hjelvran and wanted the transaction details — quantities, prices, delivery dates — kept confidential from other customers and from any pterodactyl that carried the messages.

The problem: Bretchka and Hjelvran each had their own scrambling booklets with GlagalCloud, but they did not have a shared scramble between themselves. If Bretchka scrambled a message with her booklet and sent it to GlagalCloud, GlagalCloud could unscramble it (GlagalCloud had her booklet). But then GlagalCloud would see the contents in plain arrangement before re-scrambling with Hjelvran's booklet and forwarding it.

Bretchka: I do not want GlagalCloud reading my transaction details.

Glagalbagal: I run GlagalCloud.

Bretchka: Exactly.

She had a point. Even if Glagalbagal was trustworthy, the principle was clear: end-to-end privacy meant that only the sender and receiver should be able to read the message. The intermediary — GlagalCloud — should carry it without understanding it.

The Key Exchange Problem

For Bretchka and Hjelvran to communicate privately, they needed a shared scrambling table that only they knew. But they were in different towns, three days' travel apart. Any message they sent to agree on a table could be intercepted. They could not meet in person without significant expense. And asking GlagalCloud to generate and distribute the table defeated the purpose — GlagalCloud would know the table.

Blortz: You need to agree on a secret while communicating over a channel that is not secret. This seems impossible.

Glagalbagal: It does seem impossible.

Blortz: And yet I have been thinking about paint.

The Paint Analogy

Blortz had been watching the annual Hrijpa mural being painted on the cave wall. The painters mixed pigments to create colours. Mixing was easy — pour yellow into blue, get green. But un-mixing was hard. Given a pot of green paint, you could not extract the original yellow and blue. The mixing was, in Blortz's word, one-directional.

Blortz: Imagine Bretchka and Hjelvran each have a private colour of paint that they keep secret. They also agree on a common starting colour — say, yellow — which everyone can know. It is not a secret.

Glagalbagal: Go on.

Blortz: Bretchka mixes her private colour — say, red — into the yellow. She gets orange. She sends the orange to Hjelvran. Hjelvran mixes his private colour — say, blue — into the yellow. He gets green. He sends the green to Bretchka.

Glagalbagal: A spy sees orange and green. Both travelling openly.

Blortz: Now Bretchka takes the green she received from Hjelvran and mixes in her private red. She gets a brownish colour — a specific shade that depends on yellow plus blue plus red. Hjelvran takes the orange he received from Bretchka and mixes in his private blue. He also gets brownish — yellow plus red plus blue. The same shade, because mixing does not depend on the order.

Glagalbagal: They both arrive at the same colour.

Blortz: Without ever sending that colour over the channel. The spy saw yellow, orange, and green. To compute the brownish colour, the spy would need to un-mix the orange to extract Bretchka's red, or un-mix the green to extract Hjelvran's blue. And un-mixing paint is—

Glagalbagal: Hard.

Blortz: Very hard.

The Pebble Version

Paint was a metaphor. The actual implementation used pebble operations. Glagalbagal needed a mathematical operation that was easy to perform forward but hard to reverse — the pebble equivalent of mixing paint.

He used modular arithmetic, which the velociraptors already understood from the carrying system. The operation was: take a number, multiply it by itself a certain number of times, and keep only the remainder after dividing by a large agreed-upon number. Computing the result was straightforward — multiplication and remainder, both operations the velociraptors could perform. But reversing it — figuring out how many times the number was multiplied, given only the result and the divisor — was extraordinarily tedious, requiring an exhaustive search through all possibilities.

The protocol worked as follows:

Public values (known to everyone, including any spy): a base number and a large divisor. Bretchka's private key: a secret number known only to her. Hjelvran's private key: a secret number known only to him.

Step 1: Bretchka computes (base raised to her private key) remainder divisor. Sends the result to Hjelvran. Step 2: Hjelvran computes (base raised to his private key) remainder divisor. Sends the result to Bretchka. Step 3: Bretchka takes Hjelvran's result and raises it to her private key, remainder divisor. Step 4: Hjelvran takes Bretchka's result and raises it to his private key, remainder divisor.

Both arrive at the same final number — which becomes their shared scrambling key. The spy, who saw only the intermediate results from steps 1 and 2, cannot compute the final number without knowing one of the private keys. And computing a private key from the intermediate result requires reversing the operation — which, for large enough numbers, would take a velociraptor longer than the remaining lifespan of the sun.

The Implementation

Glagalbagal set up the key exchange as a GlagalCloud service. Two customers who wanted to communicate privately would each submit their intermediate value (steps 1 and 2) through the normal protocol. GlagalCloud would relay the values — unable to read the final shared key, since it did not know either private key.

The customers would then use their shared key to scramble messages to each other, sending the scrambled messages through GlagalCloud. GlagalCloud would carry the messages faithfully, unable to read them.

Glagalbagal: We are carrying messages we cannot understand.

Blortz: That is the point. You are a postal service. The postal service does not need to read the letters.

Bretchka: Good. Keep it that way.