How the Textsecure Protocol (Signal, WhatsApp, Facebook, Allo) Works

Goals

The goal of TextSecure is to offer "end-to-end security, deniability, forward secrecy, and future secrecy". What this means in practice is that TextSecure wants to construct a stream of messages between two people which keeps key material around for as short a time as possible. Key compromise in the future should not make it possible to decrypt traffic observed today. 

I've covered a critical analysis of the Signal Protocol below. It studies the implemented architecture, notes discovered flaws, and evaluates how well the stated goals are met. A deeper analysis of the goals follows the system description.

Terminology

TextSecure is one name given to the application now called Signal. The codebase and the documentation throughout it use the name TextSecure. In order to maintain consistency with the System, I will refer to the entire system as TextSecure. 

In reality, there are a number of different things here:

The TextSecure Server, referred to as TS in the linked whitepapers (bottom) is the centralized server which coordinates state for the rest of the system. 

The Signal Protocol refers to the more general protocol in use by messaging apps from Facebook Messenger to Google Allo. It implements the functionality described below, but leaves these implementations free to do message routing and metadata tracking however they like.

The Signal application is a mobile application which implements the Signal Protocol using the described TextSecure Server policies analyzed below. This is the original implementation of the protocol. 

Architecture

TextSecure is a modification of the Off-The-Record chat protocol with a focus on asynchronous coordination. Whereas OTR requires an interactive handshake, TextSecure considers the indeterminate latency unacceptable. Having to bring an app into the foreground and carry out a handshake before being able to send a message would offer a terrible user experience.

Instead, copies of the server's role in the key negotiation are stored by a centralized server for potential clients to fetch and use. This server acts as a channel not trusted with key information able to decrypt anything; all encryption is end to end. 

Cryptography

TextSecure uses a small set of cryptographic primitives. Public key cryptography is carried out through elliptic-curve Diffie-Hellman using Curve25519. AES is used for symmetric encryption, for both counter mode without padding and cipher block chaining mode. HMAC-SHA256 is used for message authentication. These are the trusted base.

Double Ratchet:

The core of TextSecure's encryption engine is the Axolotl double ratchet algorithm. The big-picture idea is that there are two ratchets that can move forward: a receive ratchet and a send ratchet. The structure allows for the first half of the key negotiation to be saved and replayed asynchronously later to yield a full handshake. 

The receive ratchet is used when a message is received, which must include new material for the next key negotiation. This material is used to generate new symmetric keys for encryption and message authentication later. 

The sending hash ratchet generates a new set of keys using the keystream generated from the previous set of coordinated shared secrets. This ratchet is reset when the receive ratchet is activated and the shared secrets change.

What is important here to observe is that a sender never has to wait in order to send a message. They can always take a step to send a message which terminates in a bounded amount of time. These messages will all be encrypted with different symmetric keys. This means that the current keys on either person's devices cannot be used to decrypt a message sent in the past. (We see later that this has one caveat.)

Protocol

- Phase 1: Textsecure Registration


Registration starts by having a client tell the server the phone number with which it can be contacted, as well as whether it would prefer to receive a token via phone call or via SMS. This token acts as the proof of ownership which enables the user to store registration information with textsecure. 

The client sends message authentication and encryption symmetric keys ('signaling' keys), and their long-term public key.

It also posts a collection of prekeys, which are one-time copies of the client's half of key negotiation when the client is a recipient. These stored prekeys allow a sender to carry out key negotiation without requiring the client be able to respond, reducing negotiation latency significantly. The client also uploads a "prekey of last resort" which is used last and is shared between all sessions until the recipient pushes new prekeys.

That signal doesn't warn the user about relying on a prekey that's been used by other clients is less than ideal, in my opinion. 

The client then registers with Google Cloud Messaging to get a registration ID to give textsecure. This registration with textsecure includes whether the client wants to receive SMS or only data.


- Phase 2: Key comparison


Textsecure allows for clients to compare the fingerprint of each other's long-term keys to verify each other's identity. It also includes support for displaying keys as QR codes to enable convenient comparison. 


- Phase 3.1: Sending an initial message


The sender starts by requesting a prekey for the recipient. They're given the prekey index, the prekey, the registration ID, and the long-term public key of the recipient. These are used to negotiate a shared secret through the HDKF key derivation algorithm. This is referred to as the root key.

An ephemeral keypair is generated for this message. The root key is used with HDKF to derive a new root key and a chaining key. This chaining key is what is used to generate encryption and MAC keys. 

Lastly, AES counters are initialized. There are two counters: ctr and pctr. The ctr counter is incremented with every sent message while the pctr counter holds the counter of the last message seen. This allows a recipient to enforce an ordering between messages received out of order.

These are used to encrypt the message for the recipient, which is send to the signal server. This message contains the information necessary for the recipient to complete the key negotiation handshake. 

The signal server will check that the Google Cloud Messenger registration ID is right for the phone number in question, and will encrypt the message with the 'signaling' keys before sending the message to the cloud server. This indirection ensures that Google Cloud Messenger does not see the message sender. 


- Phase 3.2: Receiving a message


The sender receives the prekey index and uses it to find the prekey used by the sender. It then uses the information sent to complete the handshake and to find the same root keys as the sender. These generate the keys used to decrypt the sent message.

- Phase 4: Sending a Follow-up Message

If the original sender wants to send a second message before the recipient replies, they generate a new chaining key and use this to find new encryption and message authentication keys.
- Phase 5: Sending a Reply

When the recipient wishes to reply they first choose a new ephemeral keypair. Using the sender's ephemeral public key, and their ephemeral private key, they generate a new shared secret. This is used to find a new chaining key to find new keys for encryption and authorization. This is used to encrypt the message, which is sent along with the new ephemeral public key.

Known Issues

Key Submission

TextSecure uses a shared secret between the TextSecure server and client, the machine-generated "pw", to authenticate upload of new prekeys. This is also used for authenticating sent messages. Leaking the password is then enough to allow someone to both send messages and upload keys on behalf of a user. The encrypted export function allowed a TextSecure client to move accounts between phones, but was removed because the export included the machine-generated password in it. This unencrypted backup was placed on the device's SD card, which meant that other apps on the phone could read it. 

This feature has since been removed. If you noticed it missing, it's not a usability bug. It's a conservative approach to a real problem. 

Unknown Key-Share Attack

This attack is one of forged delivery. If an attacker carries out a UKS attack, they trick someone into crafting a message for another person (the target) when they believe they are communicating with the attacker. 

This is easily done by a powerful attacker by replacing their own public key on the TextSecure server with the target's public key. They can do this by re-registering their number with TextSecure. They then can use QR codes to validate that their fingerprint matches what the sender has. This is the fingerprint of the target's key. 

Then, they must re-register the sender's account and intercept the validation SMS or phone call from reaching the sender. This is trivial to anybody with a permissive-enough warrant. They now can authenticate as the sender and pass along the signed message. 

This attack has not been fixed by TextSecure. They added signing of prekeys, but they are still not cryptographically associated with an identity. They may be passed-off and replayed due to this lack of association.  

A feasible fix would be to have the sender and recipient both mentioned in the encrypted body of the message. 

Goal Evaluation

TextSecure achieves forward security due to it's construction. Forward secrecy states that if long-lived public keys remain secure, that leakage of current symmetric keys forms a security breach which is active for a bounded amount of time. Since the public keys are required in each new ratchet, this is met.

Perfect forward secrecy is defined as the property that seizing the current keys had by a client won't allow an adversary from decrypting messages sent previously. This is enforced by the TextSecure wire protocol but it turns into a bit of a semantics game. Since keys are only stored on the devices, it is unlikely for a key to be disclosed without having access to other keys currently on the app. The long-term key isn't enough to decrypt a message without the short-term keys associated with the ratchet state, but these can be pulled from the phone and used to decrypt messages sent and not yet replied to (messages using the previous ratchet). This is disclosure of a "previous" message technically.

Deniability is much shaker. While it's possible to say that anybody could have created a given message, since the prekeys are published, the centralization of TextSecure poses a threat to that. The TextSecure server authenticates and forwards messages, and may log them. While the content is encrypted end-to-end, the metadata is not.

Sources

Analysis Whitepaper:
http://ieeexplore.ieee.org/document/7467371/


Marlinspike, Moxie (30 March 2016). "Signal on the outside, Signal on the inside". Open Whisper Systems. Retrieved 31 March 2016.