Smoke Signals or secure crypto?

Since Signal’s unique characteristics revolve around security and privacy, we decided to explore these features more in depth for our fourth and final essay. More specifically, we will examine how these characteristics affect various layers of Signal’s architecture. We look into how Signal manages sessions between users and at how Signal encrypts and decrypts incoming messages from a component perspective.

Liberté, egalité, sécurité

Open, Sesame

In a previous essay, we mentioned that Signal uses session management. This section takes a deeper dive into the workings of this algorithm, called Sesame, in relation to the different layers in the architecture of Signal.

Firstly we will briefly go over what sessions are and how they are implemented. A session is some secret data stored by a device of a user¹. Each session has a UserID and a DeviceID which means that there exists a session per conversation, per device. So if Alice talks to Bob and Charlie, but Bob has two devices on which he uses Signal, Alice has three sessions. A session contains the encryption and decryption keys used for sending and receiving messages. Messages can only successfully be decrypted using a matching session. Signal’s implementation employs the X3DH² key agreement protocol to negotiate key pairs between both devices, these respective session key pairs are stored in the application database. Sesame, however, supports the use of other protocols too, given those meet certain conditions. Session keys can also be updated as two parties communicate by means of a ratcheting algorithm such as Double Ratchet. Concretely, Signal stores a list of UserRecord entries, which are indexed by their UserID. For each UserRecord there is a list of one or more DeviceRecord entries, which are indexed by their DeviceID. A device may contain an ordered list of inactive sessions and/or an active session. A DeviceRecord or UserRecord entry may be marked as ‘stale’ when, for example, a user deletes Signal from one of their devices, or stops using Signal altogether. In this case, the records are not deleted, since there may still be delayed messages that need to be decrypted.

Sending a message Whenever someone sends a message, Sesame is used and is provided with some plain text and a set of recipient UserIDs (the sender of the message is included in this set). The text is then encrypted and the following steps are executed per recipient:

As seen in the figure above, first a check is performed to see if there exists a non-stale UserRecord corresponding to the current UserID. If this is the case, for each DeviceRecord the plain text is encrypted using the corresponding sessions. Should there exist no non-stale UserRecord, the message is not sent. Now the UserID is sent to the server along with a list of encrypted messages and a corresponding list of DeviceIDs. The server first checks if the specified UserID is in-use and if the list of DeviceIDs is up to date. If this check passes, the server sends the messages to the corresponding mailboxes and the process starts over for the next UserID. However if the specified UserID is no longer in use, the server notifies the sender and the sender marks the UserID as stale (the process now starts again for the next UserID). If some of the DeviceIDs are no longer up to date, the server again notifies the sender and sends a current list of DeviceIDs. The sender marks all old DeviceRecords corresponding to the DeviceIDs as stale and gathers the updated information. The process is now started again for the next UserID.

Mapping to layers As we have now seen how sending a message works in Sesame, we will explore how different layers in the application are used to accomplish sending a message. In the second essay, we decomposed Signal as shown below and concluded that it had a layered architecture.

Whenever a user opens a conversation, the conversation component in the UI module is used to visualize it. The UI component forms the presentation layer. When a message is sent, the UserRecord entries with their corresponding DeviceRecords and sessions are fetched from storage via the database component in the Storage module. This module acts as the persistence layer and database layer in the application. With the sessions that have been retrieved, the message component in the Conversation module, which forms the business layer, handles the message encryption using the Signal library. The encrypted messages for each session can now be sent to the server.

What really grinds attackers’ gears

This section will provide the reader with a conceptual understanding of the idea behind Signal’s Double Ratchet³ scheme. It is written to be a high-level abstraction. Therefore, some lower-level details have been omitted as they were unnecessary for this concept. We will take the reader along for a ride through the conceptual development of the double ratchet algorithm. For each step in the development, we will point out the vulnerabilities in the algorithm and how they can be prevented. This section assumes familiarity with symmetric key cryptography⁴ and the Diffie-Hellman protocol⁵.

The figure above shows the interaction between Alice and Bob when Alice sends two messages to Bob using basic symmetric key encryption. We let Ek[m1] denote the encryption of message 1 with the symmetric key k, which Alice and Bob share. If at any point in time an attacker obtains the key, he can read all messages that Alice has ever sent to Bob.

To prevent such an attack, the ratchet scheme below uses Key Derivation Functions (KDFs), which are one-way functions. In short, this means that given an input, the function always returns the same output, but that it is not possible to go back from the output to the input that produced it. Alice starts with an initial chain key. She inputs this key to the KDF, which then produces a new chain key and the encryption key for the first message, Km1. She then encrypts the first message using this key and sends it to Bob.

To send the second message, she uses the chain key that the KDF generated and uses it to create a new chain key and the message key for the second message. If an attacker obtains a single message key Kmx (for any message x), only this message is revealed. However, if an attacker manages to obtain a chain key, he can read all messages that Alice sent after the discovered chain key was used. Due to the one-way nature of the KDF, he can not read messages that have been sent before the chain key was obtained. Bob initializes his own ratchet with the same initial chain key, and can thus obtain the created symmetrical keys to decrypt the messages Alice sends him.

In order to prevent an attacker from reading all subsequent messages after a chain key has been compromised, the scheme introduces the Diffie-Hellman (DH) ratchet. This is another ratchet that uses the DH protocol to share secrets between Alice and Bob. Explaining this protocol is out of scope for this post, as the inner workings of this ratchet are not relevant to the conceptual working of the scheme as depicted below. This scheme is nearly the same as the one we saw before, except that the DH procedure is now used to regularly reset the chain keys. This makes sure that, when an attacker obtains a chain key, he can only read all messages that have been sent until the chain key was reset. As this happens regularly, the amount of messages that an attacker can read is minimal.

Now that we have seen how Signal’s encryption protocol works, we will tie it in to the architecture of the app. We will refer back to the decomposition that was derived in the second essay and that has been mentioned before.

When a new message arrives, it is observed by the IncomingMessageObserver.java, which is included in the Services module. The SignalServiceMessagePipe.java class from the library is then used to read the data from the network and create an envelope around it. Next, the IncomingMessageProcessor.java stores the envelope temporarily in a database and registers a PushDecryptMessageJob. This job decrypts the envelope using the library and registers a PushProcessMessageJob to process the contents of the message. When this job is executed, it creates an IncomingTextMessage (which is included in the communication module) object, and writes it to the database. All classes that have Job in their title are executed asynchronously and are part of the Services component.

When we consider the Services module to also be part of the business layer, we can see that the encrypted messages are decrypted in this layer. They are then passed to the persistence layer in the form of an IncomingTextMessage object, which is a data access object. Finally, they are stored in the database, which belongs to the equally named layer. Opening a chat in the application will pull the messages from the corresponding database table.

Practically Preserving Privacy

The aforementioned protocols and algorithms ensure privacy across Signal’s application. As all messages are end-to-end encrypted using the Sesame sessions, a man-in-the-middle attack or a compromised server does not expose the messages’ contents to an adversary. Moreover, since Signal uses the sealed sender, meaning the sender’s metadata is also encrypted. While the above properties are mainly active in the business layer of Signal, some properties that ensure privacy are also active in the presentation. Signal allows users to verify their safety number with another user from the conversation, to ensure that the session has not been compromised. Alternatively, a QR code can be scanned to verify this number.

By making privacy options visible and available to the user, Signal strives to demonstrate to the user their focus on privacy. However, no system is perfect, and despite their best effort, it is difficult to provide Signal’s services without storing any data on the user. For example, since the sender sends their encrypted message to the Signal server, this server ‘knows’ the IP address from which the message was sent. In practice, this can be circumvented by the use of a Virtual Private Network (VPN).

In conclusion, Signal employs different protocols across their layered architecture to ensure security and privacy for the end user. The protocols and algorithms have been shown to be highly secure, but are not perfect. The Signal team continues to work to keep their services secure and to ensure privacy to the end user, in which their main effort is having to store less user data on their servers. We are thrilled to see Signal improve further, in a future where privacy becomes even more central in our society.