3.1. Overview
X3DH has three phases:
- Bob publishes his identity key and prekeys to a server.
- Alice fetches a "prekey bundle" from the server, and uses it to send an initial message to Bob.
- Bob receives and processes Alice's initial message.
The following sections explain these phases.
3.2. Publishing keys
Bob publishes a set of elliptic curve public keys to the server, containing:
- Bob's identity key IK_B
- Bob's signed prekey SPK_B
- Bob's prekey signature
Sig(IK_B, Encode(SPK_B)) - A set of Bob's one-time prekeys (OPK_B1, OPK_B2, OPK_B3, ...)
Bob only needs to upload his identity key to the server once. However, Bob may upload new one-time prekeys at other times (e.g. when the server informs Bob that the server's store of one-time prekeys is getting low).
Bob will also upload a new signed prekey and prekey signature at some interval (e.g. once a week, or once a month). The new signed prekey and prekey signature will replace the previous values.
After uploading a new signed prekey, Bob may keep the private key corresponding to the previous signed prekey around for some period of time, to handle messages using it that have been delayed in transit. Eventually, Bob should delete this private key for forward secrecy (one-time prekey private keys will be deleted as Bob receives messages using them; see Section 3.4).
3.3. Sending the initial message
To perform an X3DH key agreement with Bob, Alice contacts the server and fetches a "prekey bundle" containing the following values:
- Bob's identity key IK_B
- Bob's signed prekey SPK_B
- Bob's prekey signature
Sig(IK_B, Encode(SPK_B)) - (Optionally) Bob's one-time prekey OPK_B
The server should provide one of Bob's one-time prekeys if one exists, and then delete it. If all of Bob's one-time prekeys on the server have been deleted, the bundle will not contain a one-time prekey.
Alice verifies the prekey signature and aborts the protocol if verification fails. Alice then generates an ephemeral key pair with public key EK_A.
If the bundle does not contain a one-time prekey, she calculates:
DH1 = DH(IK_A, SPK_B)
DH2 = DH(EK_A, IK_B)
DH3 = DH(EK_A, SPK_B)
SK = KDF(DH1 || DH2 || DH3)
If the bundle does contain a one-time prekey, the calculation is modified to include an additional DH:
DH4 = DH(EK_A, OPK_B)
SK = KDF(DH1 || DH2 || DH3 || DH4)
The following diagram shows the DH calculations between keys. Note that DH1 and DH2 provide mutual authentication, while DH3 and DH4 provide forward secrecy.
IK_A IK_B
\ / |
\ 1 / |
\ __/ |
\ / |
/ \ |
2 / \ |
/ 3 \ |
EK_A -------+--------+--+--- SPK_B
\ |
4 \ |
\ |
\ |
+---+------- OPK_B
|
(4 is optional,
dashed = if OPK exists)
After calculating SK, Alice deletes her ephemeral private key and the DH outputs.
Alice then calculates an "associated data" byte sequence AD that contains identity information for both parties:
AD = Encode(IK_A) || Encode(IK_B)
Alice may optionally append additional information to AD, such as Alice and Bob's usernames, certificates, or other identifying information.
Alice then sends Bob an initial message containing:
- Alice's identity key IK_A
- Alice's ephemeral key EK_A
- Identifiers stating which of Bob's prekeys Alice used
- An initial ciphertext encrypted with some AEAD encryption scheme [4] using AD as associated data and using an encryption key which is either SK or the output from some cryptographic PRF keyed by SK.
The initial ciphertext is typically the first message in some post-X3DH communication protocol. In other words, this ciphertext typically has two roles, serving as the first message within some post-X3DH protocol, and as part of Alice's X3DH initial message.
After sending this, Alice may continue using SK or keys derived from SK within the post-X3DH protocol for communication with Bob, subject to the security considerations in Section 4.
3.4. Receiving the initial message
Upon receiving Alice's initial message, Bob retrieves Alice's identity key and ephemeral key from the message. Bob also loads his identity private key, and the private key(s) corresponding to whichever signed prekey and one-time prekey (if any) Alice used.
Using these keys, Bob repeats the DH and KDF calculations from the previous section to derive SK, and then deletes the DH values.
Bob then constructs the AD byte sequence using IK_A and IK_B, as described in the previous section. Finally, Bob attempts to decrypt the initial ciphertext using SK and AD. If the initial ciphertext fails to decrypt, then Bob aborts the protocol and deletes SK.
If the initial ciphertext decrypts successfully the protocol is complete for Bob. Bob deletes any one-time prekey private key that was used, for forward secrecy. Bob may then continue using SK or keys derived from SK within the post-X3DH protocol for communication with Alice, subject to the security considerations in Section 4.