Demystifying the Signal protocol used for End-to-End Encryption (E2EE)

Image source: dowo.digital

PRIVACY

Using Facebook, Instagram, and Snapchat to share private information seems so natural to most of us. Why should we care that most of these apps do not implement end-to-end encryption (E2EE)? What is E2EE, and how does it work?

Implementing E2EE in a messaging service means that the contents of any given message are only available to you (the sender) and your friend (the intended recipient). Your message may be encrypted while it’s being sent to the server, but without E2EE, the server might be able to decrypt and read it.

With E2EE, your message is encrypted at all times as it makes its way through any possible intermediaries. No one except the intended recipient has the key to decrypt it. With a good E2EE protocol, neither intermediaries (messaging app server, database), nor anyone with malicious intents would be able to read the messages you send.

With the amount of sensitive information we might be sharing via text/instant messages, this is only becoming more of an issue. Signal, a messaging app developed by Open Whisper Systems (OWS), is gaining global recognition, as it provides E2EE to its users for free. It uses the Signal Protocol, an open-source E2EE protocol, also developed by OWS. So let’s dive in and talk in detail about how this protocol works!

SIGNAL PROTOCOL

Key Generation and Registration with Signal Protocol

The first step in establishing an E2EE connection between two users using Open Whisper System’s Signal Protocol is by generating a set of 1) long-term identity key pair, 2) medium-term signed prekey pair, and 3) several ephemeral prekey pairs. These keys are generated on the client side and stored locally. The second step involves bundling all of the public keys and registration ID into an object (known as the “key bundle”) and registering it with a Key Distribution Centre. In order for Alice to send messages to Bob, Alice must know and have access to Bob’s registration ID and public keys to start a session. Thus, Alice must first generate her own keys and register herself with the key distribution centre and request Bob’s key bundle.

Starting a Session

Once Alice receives Bob’s key bundle from the Key Distribution Centre, she then uses her own identity and medium-term private keys and request Bob’s set of private keys from the server to generate a master shared secret. This master secret is then used to start a session with Bob. Once Alice generates the master shared secret, she sends it to Bob, so that he can decipher it and verify it. Upon validation of the master shared secret on Bob’s machine, the two users can then start sending each other messages.

Sending Messages

The process of encrypting messages relies heavily on the Extended Triple Diffie-Hellman(X3DH) key agreement, and provides the Signal Protocol to perform forward secrecy and cryptographic deniability. This also has an additional benefit of asynchronicity, thus having ability of sending messages while being offline. While the session is active, Alice encrypts and sends messages to Bob using the master shared secret and Bob’s ephemeral keys. This step creates a root key, a corresponding chain key, and a message chain. These are critical for maintaining forward secrecy and privacy. For every message sent, a new set of one-time session (ephemeral) keys are generated, so that none of the previous or future messages can be decrypted by any third-parties.

SIGNAL SECURITY

On a higher level, the Signal Protocol is a security library on steroids. Despite its novelty and growing importance, there has been few formal analyses of this protocol, whilst it has been a driving force in the world of cybersecurity. So, what makes it so powerful?

The Signal Protocol amalgamates the Extended Triple Diffie-Hellman (X3DH) key agreement protocol, Double Ratchet algorithm, pre-keys, and uses Curve25519, AES-256, and HMAC-SHA256 as cryptographic primitives. These are all well-established, low-level cryptographic algorithms that are frequently used to build computer security systems.

Let’s break this down further, so that we can understand what role each of these algorithms play:

X3DH (Key Agreement Protocol)

This kicks things off, by generating all the necessary keys between two parties to communicate. It establishes the crucial shared secret key between the two parties who mutually authenticate each other based on their public key pairs. X3DH also allows for key exchange to occur where one party is “offline”, and will instead exchange it through a third party server.

X3DH involves 3 primary parties:

1. Bob
2. Alice
3. Server

X3DH has 3 phases:

1. Bob registers his identity key and prekeys to a server
2. Alice retrieves Bob’s “prekey bundle” from the server — uses it to start a session and send an initial message to Bob
3. Bob receives and decrypts Alice’s message

Double Ratchet Algorithm (Key Management Algorithm)

This is used as part of a cryptographic protocol to provide E2EE based on a shared secret key derived from X3DH. Once both parties agree on a shared secret key via X3DH, parties can then use the Double Ratchet Algorithm to send and receive encrypted messages.

>>Key Derivation Chain (KDF)

The key exchange from X3DH outputs a master secret, which in turn is used to derive two symmetric keys: “root key” and “sending chain key”. As messages are being sent and received, these keys that are attached to the messages continuously change via KDF. When Alice encrypts her message for Bob, she advances her sending chain by one step, deriving a replacement sending chain key, along with a message encryption key. When she receives a message from Bob, she advances her receiving chain to generate a decryption key. The root chain is advanced when the session is initialised, which generates an ephemeral key (“ratchet key”). She then attaches this to her messages, so that each message carries a continuously changing ephemeral key, therefore making it impossible for third party snoopers to decrypt previous and future messages.

Curve25519

Given Bob’s 32-byte private key, Curve25519 generates his 32-byte public key. Given Bob’s 32-byte private key and Alice’s 32-byte public key, Curve25519 generates the master secret key shared by the two parties. The secret is subsequently used to authenticate and start encrypting messages between them. This algorithm was carefully designed to allow all 32-byte strings as Diffie-Hellman public keys. The Signal protocol leverages Curve25519 for all asymmetric cryptographic operations.

AES-256 (Advanced Encryption Standard)

This is a symmetric block cipher to protect and encrypt sensitive data. This cipher encrypts and decrypts data in blocks of 256-bits. Symmetric ciphers use the same key for encrypting and decrypting data, therefore Bob and Alice must both know, and use, the same secret key. There are a total of 14 rounds of 256-bit keys — one round consisting of several processing steps that include substitution, transposition, and randomly mixing the plaintext (before encryption) to output a ciphertext (encrypted text).

HMAC-SHA256 (Hash-Based Message Authentication Code)

This is a specific type of message authentication code involving a cryptographic hash function and a secret cryptographic key. It also verifies the data integrity, as well as the authentication of a message. This type of keyed hash algorithm is constructed from the SHA-256 hash function. This algorithm mixes a master secret key with the message data, hashes the result with the hash function then mixes that hash value with the secret key again, and finally invokes the hash function again. The output hash is 256 bits in length.

I am very excited to see how Open Whisper Systems will continue to play a leading role in the age of mass surveillance.

Finally, I hope that this post has piqued your interest in exploring other security protocols!

Resources

1. A Formal Security Analysis of the Signal Messaging Protocol (Cohn-Gordon, Cas Cremers, et al, 2016) https://eprint.iacr.org/2016/1013.pdf
2. Open Whisper Systems https://whispersystems.org