Articles

Instant Messaging and the Signal Protocol – Computerphile

September 13, 2019


A lot of people are communicating over the internet on their phone now not just SMS, you know
Messages like signal whatsapp Facebook Messenger, they all have some kind of end-to-end encryption these days
so this is not the same as when you go online to let’s say an online shop and
You immediately have a conversation and set up an encrypted connection. This is much slower than that and much more asynchronous
So there’s a lot of difficulties when using instant messaging or you know
Application based messaging because we don’t know really what’s going on between between the two parties
So I send you a message theoretically some trustworthy server takes that message or forwards its on onto your your phone, right?
Theoretically right how much do we trust the server? I suppose it depends on the app
but
But in any case maybe we want to try and use a protocol that means even if we don’t trust a server
There’s not a lot the server can do right and that’s what the signal protocol uses and by association
What’s app, facebook instant messenger and things like this?
I’ll put my phone down and we’ll talk about Allison Bob again because we always talk about Allison Bob, right?
So they want to have a conversation via a server
Between themselves, right? Now the problem is that maybe Bob installed the application?
so he installed signal or whatsapp or something like this six months ago and
He’s just waiting patiently for some friend to turn up and install the app as well, right?
I get lots of invites to install various different chat apps
Most of them I turned down because I don’t want that many icons on my phone
So what will happen is Bob will start by installing the app and completely aside from whoever he wants to talk to later
He’s going to send a few things to the server. He’s going to send a public key. That’s his identity
So that’s his identity public key for Bob
This is going to be a public key on an elliptic curve
Like lots of the ones we’ve talked about and it’ll have a private component or a private key associated with it
That will be kept to himself
He’s also going to sign a public key to
Verify that he’s in control of his private key
That’s kind of standard in cryptography and then he’s going to produce a list of one-time pre keys
remember that what he wants to do is have key exchange conversations between
Alice or Charlie or anyone else that comes along and he wants to do that not knowing when they’re going to come along
So he’s gonna send his parts of her messages ahead of time to the server
So he’s going to have you know, one use public key here and another one
another one
And he’s gonna numbered Eve or something like this. So this is one two, three and number four
So these are all public keys of which he has the private keys stashed on his phone ,right? On his application
Now the server is going to do this for anyone that installs the application, right? This will happen between your your
Your signal app and their service or your whatsapp and their servers and so on
What will happen next is some time down the line
Hopefully Bob’s made some friends and they’ve agreed to talk to him on their phones
So Alice comes along and she wants to set up a communication with Bob now the exact same problems that Bob faced she faces
Right. The first one is the Bob might have his phone switched off so she can’t start up a conversation
Right, and she also doesn’t know where Bob is
So the server does have a server based on Bob mobile phone number or IP address or something?
We’ll know how to get in contact with him
So she goes to the server and says I’d like to talk to Bob, but can I have a pre key bundle?
And this is a set of parameters from Bob or she can use to form a communication
So the server is going to send to Alice Bob’s identity key
Bob’s signed pre-key and one
Either at random or sequentially of these let’s say number three of these one use keys is is going to be sent three
different public keys from Bob, right? Alice is going to generate an identity key of her own for Alice and
she’s going to generate an ephemeral key, which is like a one use session key
Which is very common in diffie hellman for herself there. All right, what do all B’s going to do?
Well, let’s let’s get rid of this paper or just move for sort of flopping around
So we’ve got a I seem to change pens, but it’s not worry about that
I’ve got Bob’s identity key that should identify him
Like if we know that Bob has the private key and we know that’s Bob the fact that this key has been used means it
Must be Bob on the other end of a line
All right. That’s a really good thing to know his sign pre key for Bob
This stops the server messing about of his pre keys because he signed it and a server can’t do that and a one use
Public key for Bob and what that’s going to do is make sure that no one can replay attack Bob by sending this whole conversation again later
Bob is gonna delete this when he’s seen it for the first time
So when you fetch a pre-key bundle and you use it to talk to someone on one of these apps
They will delete that pre-key so that they can never use it again, and we’ve got Alice
We’ve got the identity key from Alice and her a femoral key now. I’m going to use a different pen
We’ve got five different public keys here
right, and we’re going to perform four Diffie-Hellman, right, which is again a little bit hairy, but you know
Bear with me to remind you
we did a video on Diffie-Hellman which you might like to watch but
What difficult as you both send public key to each other you exchange them you use your secrets to calculate a shared secret
So any of these two?
Public keys can be combined to create a shared secret, right?
But if you only use two of them, you’re not getting the whole picture and you’re not, you know, for example
If you only use Bob’s identity key and Alice is a ephemeral key
You aren’t guaranteeing the identity of Alice by verifying this particular identity key here. Every public version has a private one
So there’s going to be a little little private identity key for Alice
Little private ephemeral key for Alice and there you get used within the mathematic and the same on the other side
So there’s a little one for Bob. So this is identity key
for Bob
I’ve gone out too many and this one is that it’s let’s say number. This was number three, wasn’t it?
So so let’s put in number three here. Bob’s got a whole list of these right?
So he’s got a whole list of these one two, three
And this is the one he’s going to use. Alice is gonna perform Diffie-Hellman exchange four times, right?
So he’s gonna do this one here. She’s going to do this one here. She’s going to do this one here
That’s number three and she’s going to do this one here number four, right?
So she’s bringing all the keys into play then she’s going to produce one master key
Shall we say with all of these pre master secrets? So she’s going to take one and she’s going to append it to two
She’s gonna append it to three append it to four. She’s gonna put that through something called a key derivation function
Which for the sake of simplicity we’ll just say the very similar to a hash function and that’s going to produce her master secret
She can then use that to encrypt things and
theoretically when she sends a message to Bob, Bob would be able to do the same thing and no one else will
Right, so she’ll send a message including something encrypted
Her identity key and her ephemeral key
Bob will do the exact same procedure
And then he will be able to send her a message back the way that the signal protocol works with
With Alice and Bob and the server in between is called triple. Diffie-hellman
Why are we doing all these Diffie-Hellman, right?
In previous video, we just had a public key for Alice and a public key for Bob
We seem to be wasting a lot of time
Well, each of these different Diffie-Hellman exchanges gives us something different
But the really important ones I want to talk about are the ones involving these identity keys here the identity keys prove who you are
But of course if I’m Alice and you’re Bob and I send you an identity key for myself
It doesn’t prove who I am at all. I’ve just it’s just a number. It doesn’t say anything, right?
So, how do I actually how do you actually know that the message came from me?
Right and the answer is actually what you need to do is look at this number off line
Out-of-band you need to go outside of the normal line of communication over the Internet and face-to-face
Look at this number and if you see that, it’s right, then, you know, they must have been me having this conversation
Okay, so I can send you a message using signal right? You’ve installed signal your Bob. I’m Alice in this case, right?
So you’ve already sent your pre keys to the server. Just waiting to go
I
My met my phone will send a message a server and say can I get a pre key bundle and then we’ll perform an exchange
Right something like that. So I’m gonna send you a message. It’s not going to be interesting. Hello
All right, so I send you a message
Hopefully it pops up on your phone. It does. There we go. I mean this is good evidence, but it was me
I literally sent a message and it appeared on your phone, but that didn’t always happen in instant messaging so sometimes
I’m not around or you’re not around at a time
So how did you know when it pops up my name on here?
but it is me and the answer is you don’t write someone could have the server or someone else could have
Intercepted these messages and performed a man-in-the-middle attack, right the only way we can verify it
Is to check out each other’s public keys by our identity keys
so the way that signal does this is it takes the identity public key of alice and the identity public key of
Bob and it combines them using a hash function into a safety number right that safety number is essentially a summary of our two
Public identity keys, right if we have the same safety number, that means we’re having a conversation with the text
Same two identity keys, which means it must be a conversation just between us – that’s the idea. So, let’s have a look
I’m gonna go into my safety number and they’re the same and
In in signal actually, you can press this a verified button, which says we’ve looked at these out-of-band
This is called an out-of-band communication because we’re not using the normal encryption to verify our keys
So now actually when we send messages it will show as verified. So in whatsapp. It’s not called a safety number
It’s just called a security code, but you can see it’s absolutely the same now, of course what most people don’t do
It’s right. Most people say messages in assume
There isn’t a man in the middle and in all likelihood there probably isn’t but if you want to be really sure
Maybe have a look at your safety number
We’ve only covered half the story we talked about this pre key bundles and this this initial triple. Diffie-hellman
I mean, we all have phones we talk about batteries all the time. So
If you hypothetically picked four words that were in the top 500

You Might Also Like

98 Comments

  • Reply voltagedrop November 16, 2018 at 7:46 pm

    I saw a guy do a Triple Diffie Helman at the Coney Island pier years ago…

  • Reply minj4ever November 16, 2018 at 7:56 pm

    FINALLY some recognition for Axotl

  • Reply fdagpigj E November 16, 2018 at 8:00 pm

    does Telegram use this too?

  • Reply I am THE ZUCC November 16, 2018 at 8:01 pm

    We always talk about bob 🌚
    Show bob

  • Reply Lysergesaure1 November 16, 2018 at 8:12 pm

    So, ”security codes” are the PGP equivalent of sharing key fingerprints in person. Is there something similar to a web of trust (or a “strong set”) in Signal?

  • Reply Fabrizio Lungo November 16, 2018 at 8:17 pm

    For the avoidance of doubt, Facebook messenger does not use this (or any form of end-to-end encryption) in normal messenger conversations; it is only used when you start a "Secret Conversation".

  • Reply Jonathan Wolf November 16, 2018 at 8:21 pm

    Neat stuff but can we talk about what's happening on that whiteboard? I see a line formula the rest doesn't seem to correlate…

  • Reply Rocreex Creekston November 16, 2018 at 8:23 pm

    Did I miss the part where Mike wanted to explain why we have to deal with this large number of keys?

  • Reply Andrew Hendricks November 16, 2018 at 8:24 pm

    And then one of the Signal users screenshots their phone and sends it to a Tacoma Cop. (realworld event)

  • Reply The Dude November 16, 2018 at 8:40 pm

    but don't all these keys still get handed out to the other people through the server? can't a malicious server still get your data since it is giving alice's keys to bob and the other way around?

  • Reply cinIALVEspO w November 16, 2018 at 8:49 pm

    Messenger isn't end to end encrypted. Facebook reads all your data. Messenger has an option for end to end encryption, which none of my friends use.

  • Reply suicidal.banana November 16, 2018 at 8:52 pm

    SMS does not go over the internet….

  • Reply Ashish Gupta November 16, 2018 at 8:56 pm

    those one time pre keys are valid for 1 session or a single message?

  • Reply Vertedex November 16, 2018 at 8:58 pm

    Major key alert 🔑
    Ans another one 🔑

  • Reply Aurimas B November 16, 2018 at 8:59 pm

    Signal needs to be more popular, I hate using messenger, sms to communicate with friends.

  • Reply durnsidh ` November 16, 2018 at 9:18 pm

    Talk about the double ratchet!

  • Reply Hugo Woesthuis November 16, 2018 at 9:25 pm

    Finally some attention for Signal and OWS!

  • Reply Wolfram Stahl November 16, 2018 at 10:00 pm

    It's scary to think about how one day Alice or Bob may die and then all communication protocols will need to be reworked…

  • Reply Level Up Workshop November 16, 2018 at 10:26 pm

    Can't a man in the middle figure out the shared secret as well when the first contact is made and the initial keys are exchanged?

  • Reply Julian Soto November 16, 2018 at 10:26 pm

    Was this a massive advert for signal?

  • Reply americanswan November 16, 2018 at 10:27 pm

    Threema is so 👍 Deimler uses it in house. Try it out.

  • Reply Matt Whitlock November 16, 2018 at 10:51 pm

    The safety number isn't generated by a hash function. It's actually just the concatenation of a part of each party's identity key fingerprint (lesser part first). You can check this for yourself by comparing your safety numbers from two different conversations. Half of the digit string will be the same in every conversation on your phone. That half corresponds to your identity key.

  • Reply Newjorciks November 16, 2018 at 11:30 pm

    It may be safe against other parties doing the MITM attack, but nothing stops the actual service(For example WhatsApp) to do MITM on the messages. The only way to verify is with the "security key", but nothing is stopping WhatsApp from just generating a number, sending it to both phones and displaying that number.

  • Reply Cookie Wookie November 16, 2018 at 11:57 pm

    "Because I don't want that many icons on my phone" oh poor iPhone user doesn't have an app drawer

  • Reply Tom Ormiston November 17, 2018 at 12:41 am

    I'm feeling very thick after listening to this…

  • Reply Modelmat November 17, 2018 at 12:45 am

    The way that when the paper is cropped with a background is really disconcerting. It's also more pixelated.

  • Reply heyandy x November 17, 2018 at 12:48 am

    very interesting to hear about the multiple layers of diffie-hellman and the out-of-band verification – it seems to me that the OOB is falling back to symmetric cryptography – isn't that amusing? perhaps there is something fundamental about message passing as we know it that requires a symmetric verification. otherwise you would get the "byzantine general's problem" I suppose.

  • Reply Praveen b November 17, 2018 at 1:11 am

    So there's only a finite amount of backlog messages that the server can receive for me when I'm offline, since there's a finite number of one-time keys that it has for me?

  • Reply Joshua Hillerup November 17, 2018 at 1:18 am

    The real question is how do you know that the app for Signal/WhatsApp/Facebook isn't secretly forwarding on your private keys?

  • Reply Warwagon November 17, 2018 at 2:43 am

    He's a really great teacher.

  • Reply Dylan T November 17, 2018 at 3:33 am

    back in my day a "triple diffie hellman" involved a barf bag, vaseline, and a lot of toilet paper.

  • Reply Yeezy westy November 17, 2018 at 3:36 am

    real-time messaging.

  • Reply Angel Torres November 17, 2018 at 3:58 am

    We need federated IM. Why should we all be on the same chat service just to communicate?

  • Reply Jane Weber November 17, 2018 at 7:07 am

    Maybe I missed something obvious, but what does that safety number prove? Can't anyone see the public identity keys, meaning other people might have it as well, since it was generated in a deterministic way (since you both ended up with the same key)?

  • Reply InNoTime November 17, 2018 at 7:25 am

    It's time that this guy takes over the channel

  • Reply fire November 17, 2018 at 7:35 am

    If WhatsApp messages are end to end encrypted, how come when I broke my phone and got a new one I could simply restore all the messages? Are these backups not encrypted?

  • Reply John Francis Doe November 17, 2018 at 8:09 am

    What does the multiple DH do that isn't already achieved by Bob and Alice signing each of his ephemeral public keys and destroying the ephemeral private keys after one use?

  • Reply TOBImue1 November 17, 2018 at 8:10 am

    How does the protocol work for multiple devices? Like Whatsapp Web or the signal desktop app?

  • Reply Hrnek Bezucha November 17, 2018 at 8:30 am

    Facebook is just removing the man-in-the-middle to get your data

  • Reply Raj Parekh November 17, 2018 at 8:31 am

    Dr. Mike Pound is the best in explaining!

  • Reply LoneTech November 17, 2018 at 8:59 am

    Signal's safety number isn't one hash of both keys; it's a hash of each key, so a pair of fingerprints, sorted so it looks the same on both screens. One half is always your fingerprint.

  • Reply Dielfon Elletab November 17, 2018 at 9:28 am

    Why not just use Bob's public key to encrypt the messages? To mitigate the problems of private keys being leaked?

  • Reply fsxelw November 17, 2018 at 9:34 am

    How do we know if the safety number itself is even generated correctly?

  • Reply Arthur Khazbs November 17, 2018 at 10:55 am

    Telegram))

  • Reply Marcel Robitaille November 17, 2018 at 11:46 am

    Signal does this key exchange for every message, right? Is it possible to only do the key exchange once or to do it via SMS (no server)? I miss being able to text without data.

  • Reply Reckless Roges November 17, 2018 at 1:10 pm

    something something Moxie pun

  • Reply Dérson Manhique November 17, 2018 at 1:12 pm

    Its all about Alice and Bob.

  • Reply Jess November 17, 2018 at 2:16 pm

    Love Signal!

  • Reply Martin Rocket November 17, 2018 at 2:17 pm

    And if you are using whatsapp, your private keys will be forwarded to the NSA. Or will they not? How will we ever know if it is closed source.

    And that's why cool kids use XMPP with conversations or quicksy.

  • Reply Deanveloper November 17, 2018 at 2:27 pm

    Can there be a video on Telegram's MTProto?

  • Reply Derek Konigsberg November 17, 2018 at 3:10 pm

    Thanks for making this video. I'm always looking for better ways to try and explain the Signal Protocol to other people, and this makes an excellent starting point. I've personally focused so much on the ratcheting process (hopefully to be covered well in the next video) that I've almost forgotten about the nuances of the session setup process.

  • Reply Briko November 17, 2018 at 3:29 pm

    Transcriber disabled… what a pity!

  • Reply Black Hermit November 17, 2018 at 4:22 pm

    Bring forth the true Signal Protocol!

  • Reply Sourav Goswami November 17, 2018 at 5:47 pm

    A question for you:

    Why can't we just open whatsapp-web and do whatsapp on the computer without an internet connection on the phone?

  • Reply Nelson Perez November 17, 2018 at 6:45 pm

    So I assume we would have one pre-key bundle for each conversation, is that right?

  • Reply James Billsin November 17, 2018 at 8:34 pm

    Will you make a video on the weakness in public WiFi ie hotspots like coffee shops hotel airport WiFi

  • Reply Mare November 17, 2018 at 8:56 pm

    i have a question: what happens in group messaging? like in whatsapp groups? if everyone is end-to-end encryped with everyone how can i read what happens between 2 group members?

  • Reply bouhannache abdallah November 18, 2018 at 12:15 am

    you've killed my trust on the messaging communications hh

  • Reply Dustin Brookens November 18, 2018 at 5:38 am

    Oooo sneak preview of the next episode in the end credits

  • Reply Nabeel KnockBorn November 18, 2018 at 9:42 am

    All the encryption processes

    Bob to Alice: "Sup?"

  • Reply kkg T November 18, 2018 at 10:24 am

    Can we trust the apps to do this??

  • Reply Thomas Crabtree November 18, 2018 at 7:30 pm

    And all of this is completely pointless anyway because the NSA and GCHQ have backdoors into your Android and iOS keyboards anyway and are keylogging you directly via the OS or screen overlays recording your screen.

  • Reply TheVergile November 18, 2018 at 11:23 pm

    Shouldn't it be possible to do key exchange for a new contact with a one-time message over the phone network, skipping the privately owned server? Then you could verify each other based on the phone number.

  • Reply JJ Williamson November 18, 2018 at 11:23 pm

    Check out Matrix for Instant Messaging! It's a messaging protocol so people can use different apps to talk to each other, Riot.fm is a popular client on Android and iOS.

  • Reply erejnion November 18, 2018 at 11:42 pm

    Ever heard of tox?

  • Reply Fredinchy November 19, 2018 at 12:22 am

    WHY DOES HE WRITE ON PAPER WHEN HE'S GOT A GIANT BOARD BEHIND HIM?? THE SOUND GIVES ME THE SHIVERS.. Just why…

  • Reply William Hebert November 19, 2018 at 12:35 am

    Please consider allowing automatic captioning. Thank you!

  • Reply tasoftworks November 19, 2018 at 9:39 am

    Why is it called triple Diffie-Hellman if it uses four Diffie-Hellmans?

  • Reply graymalkinmendel November 19, 2018 at 3:27 pm

    So the messaging application server functions as a CA here?

  • Reply graymalkinmendel November 19, 2018 at 3:39 pm

    Also, does the security number prevent a man in the beggining attack, where somone hijacks the initial handshake with the server?

  • Reply James T Joseph November 19, 2018 at 3:51 pm

    What does Telegram do?

  • Reply Uzeyir Veli November 19, 2018 at 4:27 pm

    Guys could you do it a video on RSA? It would be interesting to see how it is used in the real world (with real examples), and also I am doing a project on it so it would be really helpful 😀

  • Reply Dhuvs GG November 19, 2018 at 5:10 pm

    what about group chats? How are encryption keys generated in a group chat. What happens when you add a member or remove a member from the group. Does the whole key change? This would make a very informative video

  • Reply Suraj November 19, 2018 at 8:29 pm

    Is this the same as Cryptography?

  • Reply Eliot Swank November 20, 2018 at 6:45 pm

    Please do a video on SpiNNaker.

  • Reply Halil Şen November 20, 2018 at 10:23 pm

    Digital angle change of the camera is soooooo distracting and it has no contribution.

  • Reply Rorick Jager November 21, 2018 at 1:56 am

    I had no idea that instant messaging was so complicated, learn something new every day. Thanks for taking the time to educate us pleb's. 😀

  • Reply Aop Stoar November 21, 2018 at 9:13 pm

    If Android and iOS are keylogging or the application installed is doing keylogging it does not matter if the data is encrypted when transferred out of your phone because at the side you clear text is encrypted and sent to the total surveillance network…

  • Reply LD Wyze November 21, 2018 at 10:37 pm

    Just can't get your face cleared up huh?

  • Reply Epicurus November 22, 2018 at 7:31 am

    Can you explain WeChat’s mathematical backdoor?

  • Reply Jouke November 22, 2018 at 4:03 pm

    Very informative! Didn't knew end-to-end is so complicated!

  • Reply Sean Byrne November 22, 2018 at 6:44 pm

    Once you're done with the Signal protocol, can you cover the Noise protocol framework?

    Thanks!

  • Reply R Williams November 24, 2018 at 1:08 am

    Are whatsapp guys geniuses and this why get $millions for working this encryption out or are they using fairly standard practices?

  • Reply Starlin Grimes November 24, 2018 at 8:58 am

    Is this the same concept as secure business communications with public and private keys, and if not how do does one go about learning this thanks.

  • Reply Jonathan Harris November 24, 2018 at 5:00 pm

    What ensures the server deletes the OPKb and what could happen if the didn't?

  • Reply Sina Madani November 25, 2018 at 12:19 am

    Too many keys! I still don't get why it needs to be this complicated

  • Reply Vibhav Sinha November 25, 2018 at 6:24 pm

    How is this method better than simply sharing the public keys over the Network? The server can just act as a relay of public keys and the encrypted messages. You can still verify the against MITM with an "out-of-band" check by comparing public keys. Can someone give example for how Eve will attack a situation with a single public-private key pair for each user?

  • Reply BISKIT Garcia December 4, 2018 at 10:25 pm

    Is the append symbol a plus sign not double pipe?

  • Reply Joseph Peters December 19, 2018 at 6:09 pm

    Thiefing coder

  • Reply XClann January 30, 2019 at 5:08 am

    So to ensure IP_kB belongs to Bob, you had to do it out of band, most likely meeting in person. Then, why not just form a shared key, or a sequence of shared keys at that point? I guess the advantage of doing it this way is so that the OP_kB can be updated with more keys without meeting out of band again after the first time…

  • Reply Hoa Phung Van February 3, 2019 at 1:59 pm

    Engsub please 🙁

  • Reply Stephan Hinselmann February 8, 2019 at 12:58 pm

    So cool. I'd love to see videos about mobile or satelite communication one day 🙂

  • Reply Anushasan poudel February 9, 2019 at 4:05 pm

    Do you look like Jared from Silicon Valley ?

  • Reply FamousNATE187 February 20, 2019 at 2:16 am

    SIGNAL❤💯👨‍💻

  • Reply LEO March 28, 2019 at 7:15 am

    I'm having problems sending files. Tried to send an audio file but it keeps failing.

  • Reply Peter Suwara May 8, 2019 at 4:31 pm

    I would love to see outtakes of these videos 😀

  • Reply Nunyo Bidness May 21, 2019 at 11:27 pm

    You don’t really talk about the protocol. Is it TCP? UDP? What port?

  • Reply Daniel F. May 24, 2019 at 9:33 pm

    1:52 How does that work? does Bob produce a second public key and encrypt it with the private key from the identity key?

  • Reply Mads Mikkel July 9, 2019 at 12:18 pm

    We are using MyChat enterprise messenger at the office. It does not require a phone number and can work without the Internet. Perfect for us for now. It also has own server, so… heck no more public messengers 😀

  • Leave a Reply