Demystifying the Signal Protocol for End-to-End Encryption (E2EE)
Many people merrily go about their life without worrying at all about encryption. Posting photos on Facebook and Instagram, Snapchat, and sharing private information over a multitude of messaging apps seems so natural to most millennials! Why should we even care that most of these apps do not implement end-to-end encryption? What is end-to-end encryption, and how does it work?
Implementing end-to-end encryption 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). Without E2EE, your message may be encrypted while it’s being transmitted to the server, but the server might be able to read it. For example, some service providers might do this to generate ads that are more specific to a user.
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 becoming an important issue. Signal, a messaging app by Open Whisper Systems (OWS), is gaining popularity every day among people all over the world, as it provides end-to-end encryption to its patrons. It uses the Signal Protocol, an open-source end-to-end encryption protocol, also developed by OWS. So let’s dive in and talk in detail about how this protocol works!
How It Works!
Key Generation and Registration with Signal Protocol
The first step in establishing an end-to-end encrypted connection between two users using Open Whisper System’s Signal Protocol is generating a set of long-term identity key pair, medium-term signed prekey pair, and several ephemeral prekey pairs. These keys are generated on the client side and stored locally somewhere secure. The second step involves packaging all of the public keys and registration ID into an object (known as the “key bundle”) and registering it with a Key Distribution Center. 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 center and request Bob’s key bundle.
Starting a Session
Once Alice receives Bob’s key bundle from the Key Distribution, she then uses her own identity and medium-term private keys and Bob’s set of private keys to compute a master shared secret. This master secret is then used to start a session with Bob. Once Alice computes the master shared secret she then sends it to Bob so that he can decipher it and validate it. Upon validation of the master shared secret on Bob’s machine, any of the two users can start sending each other messages.
Sending Messages
Once a session is established, Alice can start sending messages to Bob. This process relies heavily on the X3DH key agreement and is what gives Signal Protocol the ability to provide forward secrecy and cryptographic deniability. This also has an additional benefit of asynchronicity and thus the 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. Thus, each message that is sent leads to the creation of a new set of one-time session (ephemeral) keys that are then used to encrypt/decrypt any future messages.
Let’s follow the white rabbit!
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 plays:
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:
- Bob
- Alice
- Server
X3DH has 3 phases:
- Bob registers his identity key and prekeys to a server
- Alice retrieves Bob’s “prekey bundle” from the server — uses it to start a session and send an initial message to Bob
- 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.
We hope that this post was helpful to you in understanding some of the intricacies of the Signal Protocol! It is a great tool and without a doubt it will continue to play a big role in the exciting field of encryption.
This post was done in collaboration with my colleagues Janelle Wong and Ksenia Kozhukhovskaya.
Sources:
