June 20, 2018
The Signal Protocol (formerly TextSecure Protocol) defines a cryptographic encryption protocol for secure end-to-end encryption (E2EE). It was created by Open Whisper Systems for use in their secure messaging app TextSecure but has since been released, open-source, to the wider community. It has become hugely popular amongst consumer applications and has earned its name as the de facto standard for securing messaging and voice and video communications. Some of the largest adopters include Google Allo, Facebook Messenger and WhatsApp, but more and more organizations are embracing E2EE everyday as concerns surrounding privacy, security and surveillance increasingly find themselves centre-stage in the public eye.
In simple terms, E2EE allows us to ensure our data is only visibile to its intended recipient; the data is encrypted on the client on the user’s own device before it is even sent over the wire. This means that all the infrastructure in the middle (routing, messaging servers, databases etc.) will never get to see your data in its raw form! And this is great — it means we can completely eliminate the element of trust between client and server so users no longer have to worry about whether their data is truly safe in the hands of their messaging provider. More importantly though, it means that any third party trying to intercept a user’s communications in transit will surely fail!
As an example let’s say that user A wants to send a message to user B over MindLink — here is how a typical Signal Protocol exchange goes:
1 . When logging in to MindLink for the first time, each user generates several sets of keys: A long-term identity key-pair, a medium-term signed prekey pair and several ephemeral keys. The public keys of these pairs are packaged up into what’s known as a prekey bundle. This bundle is then sent to a Key Exchange server for storage and dissemination.
2 . User A decides to send a message to user B for the first time. User A starts by requesting user B’s prekey bundle from the Key Exchange.
3 . With this, user A builds a new session based on both their keys and user B’s keys in what is referred to as the Extended Triple Diffie-Hellman (X3DH) key agreement protocol.
Note: This sounds like a mouthful, and while I likely won’t do it justice here you can find very detailed information about X3DH and indeed the other defining features of the Signal Protocol at the official website, https://signal.org/docs/.
The Diffie-Hellman (or more specifically the elliptic-curve Diffie-Hellman) protocol describes a novel way of deriving a shared secret amongst two parties over an insecure channel. Using some clever mathematics it can be shown that two users sharing some initial public data and some hidden secret data can exchange a sequence of transformations based on that data and arrive at entirely the same conclusion - the shared secret - without anyone who might be observing this exchange being able to do the same! This shared secret then becomes the starting point of an encrypted session between the two users.
4 . User A encrypts a message using their new session.
This relies on Signal Protocol’s famous Double Ratchet algorithm which combines two types of ratchet - a symmetric-key ratchet and a Diffie-Hellman ratchet - to achieve a means of deriving a series of unique message encryption keys that are totally dissociated from any previous or future encryption keys. This means that if an attacker were to compromise one the Double Ratchet keys, they could not then go on to decrypt any other messages. It is this feature of dynamically evolving cryptography that affords Signal its uber-secure reputation.
The symmetric ratchet uses the shared secret key from the X3DH protocol in combination with user B’s ephemeral keys to generate two symmetric keys: a root key (a secret only the users A and B can posses) and a sending chain key. These keys are passed through a key derivation function (KDF) to derive unique message keys for each message that is sent. When user A sends a message to user B, user A will advance their sending key chain by one step, generating a new sending chain key and a message encryption key, and on receipt of this message user B will advance their receiving key chain one step and generate the corresponding message decryption key. This is good but if an attacker were to steal user B’s sending and receiving chain key they could potentially calculate every future message key and thus every future message. This is where the other half of the Double Ratchet comes in…
The Diffie-Hellman ratchet is “interleaved” with the symmetric ratchet and the output periodically initialises a new set of sending and receiving chain keys and a brand new root key. This means the attacker’s stolen keys are useless after only a single two-way message exchange (the “period” of the DH ratchet)!
This all sounds quite complicated… and that’s because it is! I would encourage anyone who’s really interested to go away and read and this very technical, very in-depth analysis of Signal.
The message itself contains the encrypted ciphertext payload along with the outputs of the DH ratchet at each stage and some additional information for the recipient to advance their receiving key chain correctly. But this is also a special case - being the first message sent in a new session, user A also straps their prekey bundle to the encrypted message so user B can derive a complementary session.
5 . User A sends the encrypted payload over the wire!
6 . User B receives the encrypted message payload. They recognise that they don’t have a matching session for the message, but they DO realise that there’s a prekey bundle attached to the message that they can establish one with. After going through the same steps as user A in #3 and #4 user B ends up with the decrypted plaintext message.
Written by Jamie Matthews.