Olm: A Cryptographic Ratchet ============================ An implementation of the cryptographic ratchet described by https://github.com/trevp/axolotl/wiki. Notation -------- This document uses :math:`\parallel` to represent string concatenation. When :math:`\parallel` appears on the right hand side of an :math:`=` it means that the inputs are concatenated. When :math:`\parallel` appears on the left hand side of an :math:`=` it means that the output is split. When this document uses :math:`ECDH\left(K_A,\,K_B\right)` it means that each party computes a Diffie-Hellman agreement using their private key and the remote party's public key. So party :math:`A` computes :math:`ECDH\left(K_B_public,\,K_A_private\right)` and party :math:`B` computes :math:`ECDH\left(K_A_public,\,K_B_private\right)` The Olm Algorithm ----------------- Initial setup ~~~~~~~~~~~~~ The setup takes four Curve25519_ inputs: Identity keys for Alice and Bob, :math:`I_A` and :math:`I_B`, and ephemeral keys for Alice and Bob, :math:`E_A` and :math:`E_B`. A shared secret, :math:`S`, is generated using `Triple Diffie-Hellman`_. The initial 256 bit root key, :math:`R_0`, and 256 bit chain key, :math:`C_{0,0}`, are derived from the shared secret using an HMAC-based Key Derivation Function using SHA-256_ as the hash function (HKDF-SHA-256_) with default salt and ``"OLM_ROOT"`` as the info. .. math:: \begin{align} S&=ECDH\left(I_A,\,E_B\right)\;\parallel\;ECDH\left(E_A,\,I_B\right)\; \parallel\;ECDH\left(E_A,\,E_B\right)\\ R_0\;\parallel\;C_{0,0}&=HKDF\left(S,\,\text{"OLM\_ROOT"}\right) \end{align} Advancing the root key ~~~~~~~~~~~~~~~~~~~~~~ Advancing a root key takes the previous root key, :math:`R_{i-1}`, and two Curve25519 inputs: the previous ratchet key, :math:`T_{i-1}`, and the current ratchet key :math:`T_i`. The even ratchet keys are generated by Alice. The odd ratchet keys are generated by Bob. A shared secret is generated using Diffie-Hellman on the ratchet keys. The next root key, :math:`R_i`, and chain key, :math:`C_{i,0}`, are derived from the shared secret using HKDF-SHA-256_ using :math:`R_{i-1}` as the salt and ``"OLM_RATCHET"`` as the info. .. math:: \begin{align} R_i\;\parallel\;C_{i,0}&=HKDF\left( ECDH\left(T_{i-1},\,T_i\right),\, R_{i-1},\, \text{"OLM\_RATCHET"} \right) \end{align} Advancing the chain key ~~~~~~~~~~~~~~~~~~~~~~~ Advancing a root key takes the previous chain key, :math:`C_{i,j-i}`. The next chain key, :math:`C_{i,j}`, is the HMAC-SHA-256_ of ``"\x02"`` using the previous chain key as the key. .. math:: \begin{align} C_{i,j}&=HMAC\left(C_{i,j-1},\,\text{"\textbackslash x02"}\right) \end{align} Creating a message key ~~~~~~~~~~~~~~~~~~~~~~ Creating a message key takes the current chain key, :math:`C_{i,j}`. The message key, :math:`M_{i,j}`, is the HMAC-SHA-256_ of ``"\x01"`` using the current chain key as the key. The message keys where :math:`i` is even are used by Alice to encrypt messages. The message keys where :math:`i` is odd are used by Bob to encrypt messages. .. math:: \begin{align} M_{i,j}&=HMAC\left(C_{i,j},\,\text{"\textbackslash x01"}\right) \end{align} The Olm Protocol ---------------- Creating an outbound session ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Bob publishes his identity key, :math:`I_B`, and some single-use one-time keys :math:`E_B`. Alice downloads Bob's identity key, :math:`I_B`, and a one-time key, :math:`E_B`. Alice takes her identity key, :math:`I_A`, and generates a new single-use key, :math:`E_A`. Alice computes a root key, :math:`R_0`, and a chain key :math:`C_{0,0}`. Alice generates a new ratchet key :math:`T_0`. Sending the first pre-key messages ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Alice computes a message key, :math:`M_{0,j}`, using the current chain key, :math:`C_{0,j}`. Alice replaces the current chain key with :math:`C_{0,j+1}`. Alice encrypts her plain-text with the message key, :math:`M_{0,j}`, using an authenticated encryption scheme (see below) to get a cipher-text, :math:`X_{0,j}`. Alice sends her identity key, :math:`I_A`, her single-use key, :math:`E_A`, Bob's single-use key, :math:`E_B`, the current chain index, :math:`j`, her ratchet key, :math:`T_0`, and the cipher-text, :math:`X_{0,j}`, to Bob. Alice will continue to send pre-key messages until she receives a message from Bob. Creating an inbound session from a pre-key message ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Bob receives a pre-key message with Alice's identity key, :math:`I_A`, Alice's single-use key, :math:`E_A`, the public part of his single-use key, :math:`E_B`, the current chain index, :math:`j`, Alice's ratchet key, :math:`T_0`, and the cipher-text, :math:`X_{0,j}`. Bob looks up the private part of the single-use key, :math:`E_B`. Bob computes the root key :math:`R_0`, and the chain key :math:`C_{0,0}`. Bob then advances the chain key to compute the chain key used by the message, :math:`C_{0,j}`. Bob then creates the message key, :math:`M_{0,j}`, and attempts to decrypt the cipher-text, :math:`X_{0,j}`. If the cipher-text's authentication is correct then Bob can discard the private part of his single-use one-time key, :math:`E_B`. Sending messages ~~~~~~~~~~~~~~~~ To send a message the user checks if they have a sender chain key, :math:`C_{i,j}`. Alice use chain keys where :math:`i` is even. Bob uses chain keys where :math:`i` is odd. If the chain key doesn't exist then a new ratchet key :math:`T_i` is generated and a the chain key, :math:`C_{i,0}`, is computed using :math:`R_{i-1}`, :math:`T_{i-1}` and :math:`T_i`. A message key, :math:`M_{i,j}` is computed from the current chain key, :math:`C_{i,j}`, and the chain key is replaced with the next chain key, :math:`C_{i,j+1}`. The plain-text is encrypted with :math:`M_{i,j}`, using an authenticated encryption scheme (see below) to get a cipher-text, :math:`X_{i,j}`. Then user sends the current chain index, :math:`j`, the ratchet key, :math:`T_i`, and the cipher-text, :math:`X_{i,j}`, to the other user. Receiving messages ~~~~~~~~~~~~~~~~~~ The user receives a message with the current chain index, :math:`j`, the ratchet key, :math:`T_i`, and the cipher-text, :math:`X_{i,j}`, from the other user. The user checks if they have a receiver chain with the correct :math:`i` by comparing the ratchet key, :math:`T_i`. If the chain doesn't exist then they compute a new receiver chain, :math:`C_{i,0}`, using :math:`R_{i-1}`, :math:`T_{i-1}` and :math:`T_i`. If the :math:`j` of the message is less than the current chain index on the receiver then the message may only be decrypted if the receiver has stored a copy of the message key :math:`M_{i,j}`. Otherwise the receiver computes the chain key, :math:`C_{i,j}`. The receiver computes the message key, :math:`M_{i,j}`, from the chain key and attempts to decrypt the cipher-text, :math:`X_{i,j}`. If the decryption succeeds the receiver updates the chain key for :math:`T_i` with :math:`C_{i,j+1}` and stores the message keys that were skipped in the process so that they can decode out of order messages. If the receiver created a new receiver chain then they discard their current sender chain so that they will create a new chain when they next send a message. The Olm Message Format ---------------------- Normal Messages ~~~~~~~~~~~~~~~ Olm messages start with a one byte version followed by a variable length payload followed by a fixed length message authentication code. .. code:: +--------------+------------------------------------+-----------+ | Version Byte | Payload Bytes | MAC Bytes | +--------------+------------------------------------+-----------+ The version byte is ``"\x01"``. The payload consists of key-value pairs where the keys are integers and the values are integers and strings. The keys are encoded as a variable length integer tag where the 3 lowest bits indicates the type of the value: 0 for integers, 2 for strings. If the value is an integer then the tag is followed by the value encoded as a variable length integer. If the value is a string then the tag is followed by the length of the string encoded as a variable length integer followed by the string itself. Olm uses a variable length encoding for integers. Each integer is encoded as a sequence of bytes with the high bit set followed by a byte with the high bit clear. The seven low bits of each byte store the bits of the integer. The least significant bits are stored in the first byte. =========== ===== ======== ================================================ Name Tag Type Meaning =========== ===== ======== ================================================ Ratchet-Key 0x0A String The public part of the ratchet key, :math:`T_{i}`, of the message Chain-Index 0x10 Integer The chain index, :math:`j`, of the message Cipher-Text 0x22 String The cipher-text, :math:`X_{i,j}`, of the message =========== ===== ======== ================================================ The length of the MAC is determined by the authenticated encryption algorithm being used. The MAC protects all of the bytes preceding the MAC. Pre-Key Messages ~~~~~~~~~~~~~~~~ Olm pre-key messages start with a one byte version followed by a variable length payload. .. code:: +--------------+------------------------------------+ | Version Byte | Payload Bytes | +--------------+------------------------------------+ The version byte is ``"\x01"``. The payload uses the same key-value format as for normal messages. ============ ===== ======== ================================================ Name Tag Type Meaning ============ ===== ======== ================================================ One-Time-Key 0x0A String The public part of Bob's single-use key, :math:`E_b`. Base-Key 0x12 String The public part of Alice's single-use key, :math:`E_a`. Identity-Key 0x1A String The public part of Alice's identity key, :math:`I_a`. Message 0x22 String An embedded Olm message with its own version and MAC. ============ ===== ======== ================================================ Olm Authenticated Encryption ---------------------------- Version 1 ~~~~~~~~~ Version 1 of Olm uses AES-256_ in CBC_ mode with `PCKS#7`_ padding for encryption and HMAC-SHA-256_ for authentication. The 256 bit AES key, 256 bit HMAC key, and 128 bit AES IV are derived from the message key using HKDF-SHA-256_ using the default salt and an info of ``"OLM_KEYS"``. First the plain-text is encrypted to get the cipher-text, :math:`X_{i,j}`. Then the entire message, both the headers and cipher-text, are HMAC'd and the MAC is appended to the message. .. math:: \begin{align} AES\_KEY_{i,j}\;\parallel\;HMAC\_KEY_{i,j}\;\parallel\;AES\_IV_{i,j} &= HKDF\left(M_{i,j},\,\text{"OLM\_KEYS"}\right) \\ \end{align} IPR --- The Olm specification (this document) is hereby placed in the public domain. Feedback -------- Can be sent to mark at matrix.org. Acknowledgements ---------------- The ratchet that Olm implements was designed by Trevor Perrin and Moxie Marlinspike - details at https://github.com/trevp/axolotl/wiki. Olm is an entirely a new implementation written by the Matrix.org team. .. _`Curve25519`: http://cr.yp.to/ecdh.html .. _`Triple Diffie-Hellman`: https://whispersystems.org/blog/simplifying-otr-deniability/ .. _`HKDF-SHA-256`: https://tools.ietf.org/html/rfc5869 .. _`HMAC-SHA-256`: https://tools.ietf.org/html/rfc2104 .. _`SHA-256`: https://tools.ietf.org/html/rfc6234 .. _`AES-256`: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf .. _`CBC`: http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf .. _`PCKS#7`: https://tools.ietf.org/html/rfc2315