Exteded Triple Diffie-Hellman

From CryptoWiki
Jump to: navigation, search

The Extended Triple Diffie-Hellman Key Agreement Protocol is a shared secret key establishment protocol with mutual authentication of parties based on public keys.

Contents

Introduction

Extended Triple Diffie-Hellman (X3DH) complements the standard Diffie-Hellman key agreement protocol to provide mutual authentication of the parties. In addition, X3DH provides forward secrecy and cryptographic deniability.

Extended Triple Diffie-Hellman was designed for asynchronous settings when one of the users (for example, Bob) is not connected to the system, but has previously published some information on the server. Another user (for example, Alice) wants to use this information to send Bob encrypted data and establish a shared secret key for further communication.

Preliminaries

X3DH parameters

An application using the Extended Triple Diffie-Hellman should define the primitives that will be used within the protocol. Three parameters must be set:

  • a group of points on an elliptic curve (curve) - it is recommended to use X25519 or X448;
  • a hash function (hash) - SHA-256 and SHA-512 algorithms are recommended;
  • an application information (info) - ASCII string identifying the application.

For example, an application might set the X25519 curve as the group of points on an elliptic curve, SHA-512 as a hash function, and the string “MyApplication” as the application information.

In addition, an application must define an encoding function Encode (PK) to encode an X25519 or X448 public key PK into a byte sequence. It is recommended to use coding, which specifies the type of the curve in the form of some single-byte constant and encodes the u-coordinates as indicated in [2].

Cryptographic notation

When describing the protocol, the following notation will be used:

  • The concatenation of byte sequences X and Y is X||Y.
  • DH(PK1, PK2) will be understood as a sequence of bytes, which is the key agreed upon an Elliptic Curve Diffie-Hellman function using the public keys PK1 and PK2. X25519 or X448 will be used as the Elliptic Curve Diffie-Hellman function depending on the parameters.
  • By Sig(PK, M) we mean a sequence of bytes, which is an XEdDSA signature of the byte sequence M, verified by the public key PK, and created by signing M with the private key corresponding to the PK key. The signing and verification functions for XEdDSA are defined in [3].
  • By KDF(KM) is meant the result of applying the HMAC based key derivation function (HKDF). A detailed description of the input data is given in the documentation [1].

Roles

The X3DH protocol includes three parties: Alice, Bob, and the server.

  • Alice is a user who wants to send Bob some initial data using encryption, and also set a shared secret key that can be used for two-way messaging.
  • Bob is a user who wants to ensure that other users can establish a shared secret key with him and send him encrypted data. However, Bob may not be online at the time Alice attempts to connect to him. To ensure this, Bob interacts with some server.
  • The server can store messages from Alice to Bob, so that Bob can receive them in the future. This server also allows Bob to publish some data that may be further requested by users (such as Alice).

In some systems the server role can be divided amongst multiple entities, but for simplicity the existence of a single server is assumed.

Keys

X3DH uses the following public keys:

  • IKA -- Alice's identity key;
  • EKA -- Alice's ephemeral key;
  • IKB -- Bob's identity key;
  • SPKB -- Bob's signed prekey;
  • OPKB -- Bob's one-time prekey.

All public keys have a corresponding private key, but for simplicity the public keys will be basically used in the future.

Each party has a long-term identity public key (IKA for Alice and IKB for Bob).

Bob also has a signed prekey SPKBwhich he will change periodically, and many one-time prekeys OPKB, each of which is used when the protocol is running with a new user. ("Prekeys" are named so because they are set before Alice starts the protocol with Bob).

Within each protocol run, Alice generates a new ephemeral key pair with public key EKA.

After a successful protocol run, Alice and Bob will form a shared secret key SK, which can be used within another secure communication protocol (for example, using the double ratchet algorithm).

Protocol Description

Extended Triple Diffie-Hellman has three phases:

  1. Bob publishes his identity key and prekeys to a server.
  2. Alice receives a "prekey bundle" from the server, and uses it to send an initial message to Bob.
  3. Bob receives and processes Alice’s initial message.

Each of these stages will be considered in detail within the framework of this section.

Publishing keys

Bob publishes a set of public keys on the server:

  • Bob's identity key IKB;
  • Bob's signed prekey SPKB;
  • Bob's prekey signature Sig(IKB, Encode(SPKB));
  • A set of Bob's one-time prekeys (OPKB1, OPKB2, OPKB3, ...).

Bob needs to load his identity key only once. At the same time, Bob may periodically download new one-time prekeys (for example, when the server informs Bob that Bob's one-time keys are coming to an end).

Bob also updates the signed prekey and his signature at some interval. After uploading a new signed prekey, Bob can keep the private key corresponding to the previously signed prekey for some time in order to process messages using it but retained for various reasons. Ultimately, Bob must delete this private key to provide perfect forward secrecy.

Sending the initial message

To form a shared secret key with Bob, Alice contacts the server and receives a "prekey bundle" consisting of the following values:

  • Bob's identity key IKB;
  • Bob's signed prekey SPKB;
  • Bob's prekey signature Sig(IKB, Encode(SPKB));
  • (Optionally) Bob's one-time prekey OPKB.

The server must provide one of Bob's one-time prekeys (if they exist), and then delete it. If all Bob’s one-time prekeys on the server have been deleted, then the bundle will not contain a one-time prekey.

Upon receiving a response from the server, Alice verifies the Bob's prekey signature and aborts the protocol if the signature is incorrect. If the signature is correct, Alice will generate a temporary key pair with public key EKA.

If the bundle does not contain a one-time prekey, then she calculates the following:

    DH1 = DH(IKA, SPKB)
    DH2 = DH(EKA, IKB)
    DH3 = DH(EKA, SPKB)
    SK = KDF(DH1 || DH2 || DH3)

If the bundle contains a one-time prekey, the calculations are as follows:

    DH1 = DH(IKA, SPKB)
    DH2 = DH(EKA, IKB)
    DH3 = DH(EKA, SPKB)
    DH4 = DH(EKA, OPKB)
    SK = KDF(DH1 || DH2 || DH3 || DH4)

The figure below demonstrates the set of public key pairs, based on which the Diffie-Hellman output is calculated. It can be noted that DH1 and DH2 provide mutual authentication, while DH3 and DH4 provide forward secrecy.

Picture 1 - Key pairs used in calculating DH1...DH4

After calculating SK , Alice removes her ephemeral private key and DH1...DH3(DH4) values.

Alice then computes a "associated data" byte sequence AD, containing the identification information for both parties:

    AD = Encode(IKA) || Encode(IKB)

Alice can optionally supplement AD with some information, such as logins, certificates, or other identification information.

Finally, Alice sends Bob the initial message, consisting of:

  • Alice's identity key IKA;
  • Alice's ephemeral key EKA;
  • 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 usually the first message in some post-X3DH protocol. In other words, this ciphertext performs two tasks: firstly, it is the first message within some post-X3DH protocol, secondly it is the initial message of the X3DH protocol.

After sending the initial message, Alice may continue to use SK or keys derived from SK within the post-X3DH protocol in order to exchange messages with Bob.

Receiving the initial message

Upon receiving Alice’s initial message, Bob obtains Alice’s identity key and ephemeral key from it. Bob also loads his identity private key, and the private keys corresponding to whichever signed prekey and the one-time prekey used by Alice.

Using these keys, Bob repeats Alice’s calculations from the previous subsection to get SK, and then also deletes the DH1...DH3(DH4) values.

Bob then creates a sequence of ADbytes using IKA and IKB. Finally, Bob tries to decrypt the initial ciphertext using SK and AD. If the initial ciphertext cannot be decrypted, Bob interrupts the protocol and deletes SK. If the message was decrypted, the protocol is complete for Bob. Bob deletes the one-time private key used by Alice, for forward secrecy. From this point on, Bob can use SK or a key derived from it within the post-X3DH protocol for the purpose of secure communication with Alice.

Security Considerations

Authentication

Before or after the keys are agreed, the communication parties can compare their identity public keys IKA and IKB using some authenticated channel. For example, they can compare public key fingerprints manually or by scanning a QR code. Methods for doing this are beyond the scope of this protocol.

If authentication is not performed, the communication parties cannot be sure that they are communicating with the one they assume.

Protocol replay

If Alice’s initial message does not use Bob’s one-time prekey, the initial message can be re-sent to Bob and he will accept it. This may lead Bob to assume that Alice had repeatedly sent him the same message (or messages).

However, this vulnerability can be eliminated through a post-X3DH protocol (for example, a protocol using the Double Ratchet algorithm). These protocols agree on a new key using the shared secret key developed within X3DH and new random key material from Bob.

Bob may also attempt to take other measures, such as maintaining a blacklist of read messages and a high frequency of updating the prekeys signed by Bob.

Replay and key reuse

Another consequence of the re-execution of the protocol described in the previous section is that a successfully replayed initial message may result in Bob’s receiving the same SK in different protocol runs.

For this reason, any post-X3DH protocol must add random data to the encryption key before Bob sends encrypted data. For example, Bob can use the Diffie-Hellman ratchet to combine the SK with a freshly generated Diffie-Hellman output to obtain a randomized encryption key.

Bob’s failure to randomize the encryption key may result in key reuse.

Deniability

X3DH does not provide either Alice or Bob with cryptographic evidence (with the possibility of publication) of the content of their messages or the fact of communication in general. Thus, the fact of communication can only be discovered by Alice, Bob, and a third party who compromised their private keys.

Signatures

The X3DH protocol provides mutual authentication and forward secrecy based on the Diffie-Hellman calculations, and ignoring the signing of the prekey seems fairly acceptable. However, this may result in the malicious server providing Alice with a “fake prekey bundle” and then compromising Bob’s identity key in order to calculate the SK value. It may also be tempting to replace mutual authentication based on the DH1 and DH2 values with the signature from the identity keys. However, this reduces deniability, increases the size of the initial messages, and increases the damage in cases of compromised ephemeral or prekey private keys or finding vulnerabilities in the signature scheme.

Key compromise

Compromise of communication party’s private keys has a catastrophic effect on security, despite the fact that the use of ephemeral keys and one-time prekeys softens the destructive effect. Compromise of a party’s identity key allows to carry on actions on behalf of that party. Compromise of a party’s prekey private keys may affect the security of old or new values of SK depending on a number of conditions.

A complete analysis of all possible compromise scenarios is beyond the scope of the protocol description. A partial analysis of the most likely scenarios is given below:

  • In the case of using a one-time prekey, compromise of Bob’s identity key and the prekey private keys will not result in a compromise of SKin the future, assuming that the private key for this one-time prekey has been deleted.
  • If one-time prekeys were not used in the protocol run, the compromise of Bob's identity and signed prekey may lead to a compromise of the SK calculated on the basis of these keys. Frequent replacement of a signed prekey softens it in the same way as using a ratchet mechanism after the X3DH protocol, since in this case SK is replaced with new keys, also calculated on the basis of random values.

Server trust

A malicious server may cause communication failure between Alice and Bob (for example, due to a failure to deliver messages). If Alice and Bob authenticate each other, then the only additional attack available to the server is the refusal to transfer one-time prekeys, thus forward secrecy will depend on the lifetime of the signed prekey (as described in the previous section). A decrease in the level of forward secrecy can also happen if one of the parties maliciously drains one-time prekeys of another party. In this regard, the server must in some way limit the number of received one-time prekeys.

Identity binding

The authentication described at the beginning of the current section may not necessarily prevent an "identity misbinding" or "unknown key share" attack. This can happen when an attacker (Eve) falsely presents Bob's identity key fingerprint as his (Eve’s) own, and then either redirects Alice’s initial message to Bob, or falsely presents Bob’s contact information as his own. As a result, Alice thinks that she is sending the initial message to Eve, while the real recipient is Bob. To make this attack more difficult the parties may include more identifying information into “attached data” or hash more identifying information in the identity key fingerprint. Such information may include user names, telephone numbers, real names, etc. Eve will have to lie about this additional data, which can be much more difficult. At the same time, there is no reliable way to prevent the possibility of this attack by Eve.

Glossary

References

Go to list of references to the section "Exteded Triple Diffie-Hellman"

Filippov A.I. 2019