February 27, 2021#technical

Reimplementing Signal's Key Exchange Algorithm

I had a bit of free time this week, as I took a break after last week's barrage of midterms. A friend of mine introduced me to Elixir, and I noticed that one of their demo projects was a real-time clone of Twitter. I drew inspiration from this and thought about making a short demo of a real-time chat app, which reminded me of Signal's end-to-end encryption, which is advertised as 100% deniable. I didn't end up making the chat demo, but I did go down a rabbit-hole and reimplement Signal's key exchange algorithm.

Signal uses the X3DH Key Agreement Protocol, which was designed by the Signal team in 2016. The premise of the algorithm is extremely complicated, but I'll attempt to summarize it below. See the very end for a link to my attempt to recreate this exchange in Python.

Parameters

Basically, every user of the app has a unique set of keypairs. This set consists of an identity key, a signed prekey, and a collection of one-time-use prekeys. All keys use the same curve (either X25519 or X448) and the app also chooses a hash function (either 256-bit or 512-bit). All associated public keys are uploaded to the server, in order to facilitate key agreements. In addition, each user uses their identity key to sign a hashed version of their signed prekey public key. We don't want to create a brand new keypair for signing, so Signal specifies the XEdDSA signature scheme, which translates the identity key into an Ed25519 key, which can be used for signing and verification. We do so, and upload the signature of the signed prekey to the server along with all the other public keys.

Let's define some variables. We'll use the X25519 curve and the SHA-512 hash function. We'll also define some info parameter, which you'll see why shortly. Let's say that Bob has uploaded his public keys to the server, and Alice wishes to communicate with him.

Beginning the Exchange

The first thing that happens is that Alice asks the server for Bob's prekey bundle. This prekey bundle consists of Bob's identity public key, signed prekey public key, signature, and one of Bob's one-time-use prekeys. After the server sends this information to Alice, it deletes the one-time-use prekey it forwarded. It also gives Alice some way to identify which of the one-time-use prekeys was sent, so that Alice can send this information to Bob later.

Alice begins by translating the identity public key to an Ed25519 public key, and uses this public key to verify the signature in Bob's bundle. If the signature doesn't match the hashed signed prekey (which Alice can regenerate, since she has this prekey), Alice aborts the process and deletes all the data she has on Bob.

Next, Alice generates a new keypair. This is an ephemeral key, and will not persist beyond this exchange. Then, Alice exchanges her identity private key with Bob's signed prekey public key. She also exchanges her new ephemeral private key with each of (1) Bob's identity key, (2) Bob's signed prekey, and (3) the one-time-use prekey. All of these are done separately, and then Alice concatenates them in order (left to right). She then takes this concatenated information and uses the HKDF algorithm to generate a shared key that will form the basis of their communication moving forward. The input to the HKDF algorithm is actually not directly the concatenated information -- it is the information left-padded with 0xFF (32 bytes if using X25519, 57 if using X448). The information passed into the HKDF algorithm is exactly the info parameter we defined before.

Alice proceeds to hash her identity public key, hash Bob's identity public key, and concatenate the two (left to right). This is the associated data for their interaction. She then uses an AEAD encryption scheme to encrypt this data using the shared key she generated.

Alice's job is now done. She bundles up her identity public key, her ephemeral public key, the identifier of Bob's one-time-use prekey, and the AEAD-encrypted information. She deletes the ephemeral key from her local storage, and sends this package to the server. The server forwards this package to Bob.

Receiving the Handshake

The server passes the information it receives from Alice directly to Bob. Bob determines which of his one-time-use prekeys was used by Alice, and then performs the reverse of the exchanges that Alice performed to derive the shared key. That is, Bob exchanges his signed prekey private key with Alice's identity public key, and his (1) identity private key, (2) signed prekey, and (3) one-time-use prekey with the ephemeral key Alice provided. He concatenates these in order (left to right) and uses the HKDF algorithm to generate the same shared key as Alice. This way, both Bob and Alice can derive the same shared key without having to send it over a server, and the server thus never learns their shared key. Without the shared key, the server cannot recreate their handshake (especially since the one-time-use prekey is deleted right after being sent to Alice), which helps ensure deniability on the part of the server managers.

After deriving the shared key, Bob deletes the intermediate values he derives from exchanges. Then, he creates the same associated data as Alice: by hashing Alice's identity public key and his own, and concatenating them (left to right). He then uses an AEAD decryption scheme to decrypt the AEAD-encrypted information that Alice sent using the shared key he derived. If the information does not decrypt the way it should, Bob aborts the handshake and deletes the shared key.

If the decryption is successful, Bob deletes the one-time-use prekey for forward secrecy (the idea that session information cannot be compromised in the long run, since the keys used for the initial handshake are no longer completely available). Now, Bob can use the shared key or a key derived from the shared key for communication with Alice. The Signal app uses the Double-Ratchet Algorithm for subsequent communication encryption, but I haven't gotten around to understanding this algorithm just yet. [edit 3/22: I got around to it]

I found this process fairly complex, but that made it fun to digest. I actually went ahead and tried to implement this procedure in Python, and you can check out the source code for that here. Cheers!