We've been talking about instant messaging in, you know, messaging apps
How can you start having the same conversations you might have over the Internet, but where maybe someone's got there phone off, or asynchronously?
You might have to wait six months before the next message comes.
These are things we have to think about.
That gives attackers a lot of time to break keys.
It gives you a lot of time, um,
to forget what the key was.
And then a message comes in and you can't read it.
We've only covered half the story.
We talked about this pre-key bundles, and this initial triple Diffie-Hellman key exchange
which is where we want to asynchonously
establish some keys.
Now, one option then would be to, just like on the Internet
when you're doing online shopping
is to use that key from now on
to secure every message.
This is not a good idea because imagine
you have a conversation for six months
and some nefarious party has recorded all of your messages.
Then what happens is you break one of them and you've got all of them
cause all the keys are always the same, right?
So we don't do that, we update the key.
I guess it's a question of how often do you update the key?
and Signal, and WhatsApp, and the Signal Protocol
are pretty, um, rigid about this.
They will update the key every single message, right?
Every single message, when you use an app like this, is a different key.
So basically making an app as absolutely difficult as possible as an attacker to get any message.
You break a message, maybe you read one message.
Maybe you'll get a couple, if you're lucky.
Cause you're sniffing everything.
But most of the time you'll get one and that's all.
And, of course, the keys are not exactly easy to break anyway.
So it makes it very, very difficult to break.
At the core of this is something called a ratchet function.
A ratchet function is a function that can sort of turn in one way, but not backwards.
So think of it like a hash function
you can take an input, go through a hash function
but you can't go backwards.
So that's kind of like a ratchet.
And the key derivation function that we use here, which is kind of like a hash
um, is used in this way. It's called a KDF ratchet or a key derivation function ratchet.
So let's imagine that we have our root key or our key.
So this is our current key
and we want to encrypt a message.
So what we do is we pass it through a key derivation function
which operates in a similar way, in this instance, to a hash
but they're a defined cryptographic primitive.
It has an input that comes in here.
This can be a constant, it could be relevant to whatever the application is.
And out comes a new key
and your current output key
or message key, or temporary key.
Whatever you want to call it.
So, this is a kind of chain.
So this is message #1 that we encrypt using this key.
Maybe we want to send another message.
So we put this through a KDF again
a KDF not KDE (fixes spelling)
Goes through here, this comes out with another key.
And another message #2 key.
And this goes on and on.
And this kind of function is absolutely at the core of things like Signal, Whatsapp.
The reason it's useful is because it doesn't let us turn backwards.
If I break this key, as an attacker
I can't reverse this one-way function to get to this key.
So I can't find out what this message key was, or this message key
or all of the ones back in time.
So, I can break a key somewhere in the conversation
and I can't read any of the messages you wrote previously.
That's a good thing.
What it doesn't do is provide us with, sort of, future secrecy.
So, if I break this key, I can use this KDF to produce this key and this key.
And so on and so forth.
That's a huge problem.
So how do we fix that? Well what we tend to do
is we bring in a Diffie-Hellman ratchet as well.
So sometimes what will happen is, when they're having these conversations
is that you will receive Diffie-Hellman parameters from the other party
and you'll use them to manipulate your key derivation function to change this chain.
And that will mean that if someone cracked a key
as long as they're not privy to all of the Diffie-Hellman parameters
you will be able to reestablish secrecy from then on.
So this is very nice, when we combine a KDF chain with this Diffie-Hellman ratchet
we've got this kind of "double ratchet"
and that's what happens in Signal and in Whatsapp.
So let's have a look at how this actually works in practice.
(paper ripping)
I'm going to simplify a bit by drawing
these ratchets as sort of actual physical ratchets
rather than keys and key-pairs and things
So, we have our two classic parties that are having a conversation
Alice and Bob.
Now Alice has three KDF chains which she's using
One is a... drawing the ratchet is going to be difficult
so I'm going to draw little circles
Camera: "That's my job, then, right?"
Yeah, that's your job, sorry.
Alice has a Diffie-Hellman ratchet here
which has sort of, you know, got these one-way things on it that mean it can't turn backwards.
She has a sending ratchet: "Send".
and a receiving ratchet: "Receive".
And Bob has the exact same thing.
So he has a Diffie-Hellman ratchet of his own
and he has a sending ratchet and he has a receiving ratchet.
Now, what's going to happen is every time that Alice wants to send a message to Bob
she's going to update this sending ratchet, produce a new output key, and send that to Bob.
So, let's imagine that happens, let's say Alice sends a message to Bob.
So she ticks this ratchet over, she produces another
key in that chain, and
and an output message key, so let's call this "Alice #1".
Alice encrypts a message with "Alice #1" and sends it over to Bob.
Bob, ticks over his receiving chain
Luckily the sending chain of Alice and the receiving chain of Bob started at the same point, so they know what they're doing.
He ticks his over one and produces
that same "A #1" so that he can decrypt the message and read it.
So Alice maybe wants to send another one
so she's going to tick this KDF function again
she's going to produce a new key and "A #2".
She's going to send that to Bob, he's going to tick his receiving function "A #2"
Now Bob wants to send a message, so he's going to tick his...
His is going to be "Bob #1"
Alice gets a message and thinks "Well that means I need to calculate whatever the key was to work out what that message was".
So she's gonna tick this and gonna get "B #1".
And these chains are theoretically going to grow and grow.
And Alice's sending chain
will be in sync with Bob's receiving chain, and vice versa.
Bob will send a message and it will be Alice's receiving chain that has another key.
So all that has to happen, for this to work
is that the sending and receiving chains of both Alice and Bob have to be in sync
and they have to start at the same position
But we know that's easy to do because they started using a Diffie-Hellman key exchange
But we haven't got that future secrecy that we wanted
These won't heal themselves. If someone breaks "A #2"
and knows what this sending key was
they've essentially broken Alice's ratchet
and they can tick along with it and work out all of these messages
So what happens occasionally or whenever they want, is
as part of one of Bob's messages
he will send a new Diffie-Hellman public key.
So this will come over here like this
Alice will use it to tick her Diffie-Hellman ratchet
and that will reset these messages
and Bob will also do the same thing: he will reset his sending or receiving messages as appropriate.
This Diffie-Hellman parameter is used to update the starting positions of these two ratchets
and then they continue with their messages.
Camera: "Presumably Bob's update the moment he sends the Diffie-Hellman."
That's right, so he would have already done that
so that he can then send "B #1" using the latest Diffie-Hellman pair.
So they can send this every message if they want or hardly ever.
In practice, it's sent every message.
So the idea is that we have...
we have loads of really interesting cryptographic properties here
First of all, the Diffie-Hellman means that we have
a sort of self-healing property
If someone breaks one of these intermediate keys
as soon as one of these Diffie-Hellman ratchets ticks over
that gets reset and we lose that ability.
Because of these KDF ratchets, if you break one of these keys down here
you can't find out what all the other messages were.
This method of producing keys will kind of heal itself
and you can't reverse it, you can't go back down the chain and decrypt historic messages.
And also, it deals nicely with asynchronous data.
Alice can send ten messages to Bob
with or without Diffie-Hellman parameters
and as long as they both follow the rules
the exact right amount of keys will be generated
and they will exactly match his receiving keys.
And they can update their Diffie-Hellman parameters, as well, whenever they want.
Camera: "Does the Diffie-Hellman go one-way? Is it only ever Bob-to-Alice?"
No, so remember, the Diffie-Hellman is a conversation between two parties
they both have a public key, so
every time Alice sends a message, she'll send her part
and every time Bob sends a message, he'll send his part.
So essentially you have these, sort of, halfway Diffie-Hellman exchanges which is this ratchet.
So Alice will send, and they'll both update.
Bob will send and they'll both update.
Alice will send and they'll both update.
So keeping these different chains in sync
is a little bit of a brain-melter.
But it can be done as long as you follow the rules and as long as Alice and Bob are doing the exact same thing
you'll find that they know exactly which key handles which message.
Camera: "What happens if one of these messages gets missed?"
Ah, so this is another nice thing about this.
So, if one of these messages gets missed then what essentially happens is, temporarily
these two chains become out of sync.
So maybe Bob sends ten messages to Alice
so this receiving chain is ten long
but Alice has only received two of them so far
and then she receives number nine.
She's gotta be able to work out what key decrypts that message.
Well, in the message Bob will have some information that says I've already sent
eight messages on this chain.
Alice will look at her two and go: "Well that's not right, so I better wait."
"Or, I can tick seven more ticks to get to the right key."
"And hold onto these ones in case those messages come in later."
So they'll both gonna have to be a little bit careful about which keys they delete, which keys they keep
temporarily, until those messages come in.
But as soon as you've used a key to decrypt a message, you delete it.
And they get deleted immediately.
And that way, it's very robust to people capturing a device or something like that.
Camera: "So I know that if I use one of these apps, Signal or Whatsapp or whatever
you get these little ticks to see if somethings delivered or if it's been read."
Camera: "How does that work?"
So if you text me you can see that I've read it but I've not bothered responding.
Yeah, so that's sort of an application layer thing.
So what will happen is, this is kind of very low level
we're talking just above the network protocols
you've got this stuff happening, informing the encryption.
Within that, the message doesn't have to contain an image or a GIF
or a text message.
It could contain a read receipt, or a proof of delivery, or something like this.
And this would depend on the actual application and how they manage these messages.
It really doesn't make a lot of difference.
All that happens is a kind of...
the wrapper around these messages
is going to be these Diffie-Hellman parameters
and whichever message it is in these chains.
Camera: "Do they use this for video as well?"
They do, yeah. So, the packets that get sent when you're performing
end-to-end encryption
in things like Signal or Whatsapp
we use the exact same protocol for that, all encryption is done this way.
Cause this is just generating keys.
The actual encryption will be done with something like
an AEAD cipher, so, for example: ChaCha or AES.
And that will include all the normal symmetric key cryptography stuff
that make sure that messages haven't been tampered with and things like this.
Camera: "With my video head on, I'm wondering how it all gets chunked up, you see, but maybe that's..."
Yeah, that's... that's difficult for me to know without reading the code.
But, you know, it's going to be small...
small packets of normal size, just like TLS data over the Internet.
It's not going to be much different than you watching a streaming video
over an encrypted Internet connection, at that point.
Camera: "What happens if you have more than two people involved? Does it work the same?"
Not quite, it gets... it gets a little bit messy.
(laughter)
Camera: "That's for another video."
Yes.
You gotta train for a long time.
And let's not let Steve off the hook.
Here's Steve, over here.
High value of two, high value of one. Whatever that means.
The interesting thing about this is we're not performing a classification.
Little endian systems.
So that's why we call it "endianness".
It all traces back to eggs...