How Signal & WhatsApp Encryption Actually Works · 3

Prekeys vs. the Offline Problem

Bob is offline.

Alice starts anyway.

Next: the stolen phone.

How Signal & WhatsApp Encryption Actually Works

Bob is asleep, and his phone is off.

Alice wants to start an encrypted conversation with him.

Right now.

That shouldn't be possible.

And yet it works.

In episode one, Alice and Bob agreed on a secret by each sending a public key.

In episode two, Bob signed his key with his identity key,

so Mallory couldn't swap it.

But both tricks have the same catch: it's a back-and-forth.

Alice sends her key, Bob sends his.

If Bob's phone is off, Alice is stuck waiting.

And nobody wants to wait before they can send a message.

The solution: Bob leaves his keys behind,

in advance.

Every message passes through Signal's server.

So far, we treated the middle of the network as dangerous.

This time, the thing in the middle isn't an attacker.

Think of it as a post office: it holds things for you while you're away.

While his phone is still on, Bob drops off a package of public keys.

Three kinds.

His identity key, from episode two.

A signed pre-key: a public key, signed with his identity key,

so the post office can't swap it without Alice noticing.

And a stack of one-time pre-keys: public keys that will each be used exactly once.

The private halves of all these keys stay on Bob's phone.

Alice wants to talk to Bob.

She asks the post office for Bob's package,

and gets his identity key, his signed pre-key,

and one key off the stack.

First, she checks the signature with Bob's identity key.

It matches: this pre-key really comes from Bob.

Then she makes a fresh key pair of her own,

just for this conversation.

Now Alice does Diffie–Hellman.

Not once, but four times.

She has two keys: her identity key, and her fresh key.

Bob left three.

Alice combines them in four pairs, and each pair gives its own shared number,

just like in episode one.

Two of those lines involve an identity key.

Alice's identity key with Bob's signed pre-key,

and Alice's fresh key with Bob's identity key.

Apart from Bob, only the real Alice can calculate the first.

Apart from Alice, only the real Bob can calculate the second.

Together, they prove who's who.

The other two lines use Alice's fresh key with Bob's pre-keys.

Those make the secret brand new for every conversation.

And look at this one: Alice's fresh key with Bob's signed pre-key.

Six jumps, fifteen jumps, and it lands on two.

That's exactly the Diffie–Hellman from episode one.

Five, twelve, two and eighteen.

Alice puts all four into the blender from episode one,

the key derivation function, and gets one strong key.

She locks her first message with it: hi Bob.

Then she sends it to the post office, together with everything Bob needs to rebuild

the key: her identity key, her fresh public key,

and which of Bob's pre-keys she used.

And she goes on with her day.

The next morning, Bob's phone comes online and picks up the message.

He combines his own private keys with Alice's public keys:

the same four lines, from the other side.

Five, twelve, two, eighteen.

Same blender, same key.

And he reads: hi Bob.

Then Bob deletes the private half of that one-time pre-key.

For good.

Why one-time?

The post office gives each one-time pre-key to only one person,

and then throws it away.

And Bob deletes his half after using it.

So that exact key can never be used again.

If someone records Alice's first message and sends it to Bob a second time,

Bob doesn't have that key any more, and it doesn't work.

What if the stack runs out, because lots of people message Bob while he's offline?

Then Alice uses the other three lines.

It still works.

It's just a little weaker: without a one-time pre-key,

that first message could be sent to Bob again,

and he would accept it.

So Bob's phone tops up the stack whenever it can.

And the signed pre-key gets replaced every week or month.

So isn't the post office the weak spot now?

It sees every package come and go.

But it can't open them: it never gets a private key.

It can't swap Bob's keys without being caught:

the signature and the safety numbers from episode two see to that.

The worst it can do is refuse to deliver,

or stop handing out one-time pre-keys.

Annoying.

But it can't read a word.

This whole procedure is called X 3 D H: extended triple Diffie–Hellman.

WhatsApp describes exactly these four calculations in its security paper.

Signal has since added a fifth ingredient to the blend,

one designed to hold up even against quantum computers.

That gets its own episode.

So: Bob leaves keys at the post office, Alice combines four pairs into one secret,

and Bob can rebuild it whenever he wakes up.

Now they'll send thousands of messages with that secret.

But what if someone steals Bob's phone next year?

Could they unlock everything Alice and Bob said today?

That's the next episode.