Encryption, from the ground up · Puzzle 2 · 3 of 6

A secret agreed in public

In puzzle 1, AES needed the same key on both sides, and sending it would hand it to the listener. Here's how two sides agree on a secret while every word they say is overheard.

The problem

In puzzle 1, your app and your server needed the same AES key, and sending it would give it to the listener from puzzle 0. Everything they say crosses the café Wi-Fi in plain sight. Is it even possible to agree on a secret when someone hears every word?

See it

Each side keeps a private value and sends a public value; each combines its own private value with the other's public value; both get the same shared secret; the listener sees only public values your app your server listener privateprivate public A public B hears both secretsecret same secret, never sent
  1. Each side picks a random number and keeps it: its private value.

    Step 1 of 4
  2. From it, each makes a public value and sends it openly. The listener hears both.

    Step 2 of 4
  3. Each combines its own private value with the other's public value. Predict: do the two sides get the same number?

    Step 3 of 4
  4. Yes: the shared secret, never sent. The listener, with only public values, can't compute it. This is a key exchange.

    Step 4 of 4

The building block

It is, with a key exchange. The idea, in the form called Diffie–Hellman, which HTTPS uses:

  1. Each side picks a random number and keeps it to itself: its private value.
  2. From it, each computes a public value and sends it openly. Going from private to public is easy; going back, from the public value to the private one, is a problem nobody knows how to solve in any useful time.
  3. Each side combines its own private value with the other side's public value. The math works out so both get the same number: the shared secret.

The listener has both public values, but neither private one, and with only public values there's no known way to compute the shared secret. So both sides now share a secret nobody else has, and the keys for AES from puzzle 1 are derived from it: computed from it in a fixed way both sides follow (puzzle 5). Once the connection ends, both private values are thrown away, so every connection gets fresh ones.

Mixing paint gives the feel of it. Both start from the same yellow, agreed in public. Each mixes a secret color into it and sends the mix. Each then adds its own secret color to the other's mix. Both end with the same brown; the listener, holding only the two mixes, can't un-mix them.

One gap is left: the exchange tells you that you share a secret with whoever answered, not who that is. If the listener answers in your server's place, you've agreed a secret with the listener. Puzzle 4 closes that gap.

The analogy

The paint, above: two people end up with the same color, and someone watching every mix travel between them still can't make it.

Check yourself

The listener records both public values from a key exchange. What can it do with them?

Right. Public values alone don't give the secret.

Not quite. Going back is a problem nobody knows how to solve in any useful time.

Not quite. Getting the secret needs one private value; public values alone don't give it.

Why does each side keep its private value to itself?

Not quite. The AES key comes from the shared secret, which both sides compute; the private value never leaves.

Right. The private value is what makes the secret yours.

What's the difference between a public value and the shared secret?

Not quite. If it were, the listener would have it; it's computed with a private value.

Right. Sent openly vs never sent.

Not quite. The secret is computed after both public values arrive, and never travels.

Sources

What you now know

In a key exchange, each side keeps a private value and sends a public value made from it. Each combines its own private value with the other's public value, and both get the same shared secret. The listener sees only the public values and can't compute it. But it doesn't tell you who you agreed with.