diff options
Diffstat (limited to 'docs/olm.rst')
| -rw-r--r-- | docs/olm.rst | 143 |
1 files changed, 91 insertions, 52 deletions
diff --git a/docs/olm.rst b/docs/olm.rst index 0fb0602..99417e0 100644 --- a/docs/olm.rst +++ b/docs/olm.rst @@ -1,8 +1,8 @@ Olm: A Cryptographic Ratchet ============================ -An implementation of the cryptographic ratchet described by -https://github.com/trevp/axolotl/wiki. +An implementation of the double cryptographic ratchet described by +https://github.com/trevp/double_ratchet/wiki. Notation -------- @@ -16,7 +16,12 @@ 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)` +and party :math:`B` computes :math:`ECDH\left(K_A_public,\,K_B_private\right)`. + +Where this document uses :math:`HKDF\left(salt,\,IKM,\,info,\,L\right)` it +refers to the `HMAC-based key derivation function`_ with a salt value of +:math:`salt`, input key material of :math:`IKM`, context string :math:`info`, +and output keying material length of :math:`L` bytes. The Olm Algorithm ----------------- @@ -36,7 +41,8 @@ HMAC-based Key Derivation Function using SHA-256_ as the hash function \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) + R_0\;\parallel\;C_{0,0}&= + HKDF\left(0,\,S,\,\text{"OLM\_ROOT"},\,64\right) \end{align} Advancing the root key @@ -54,9 +60,10 @@ 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"} + ECDH\left(T_{i-1},\,T_i\right),\, + \text{"OLM\_RATCHET"},\, + 64 \right) \end{align} @@ -64,7 +71,7 @@ info. Advancing the chain key ~~~~~~~~~~~~~~~~~~~~~~~ -Advancing a root key takes the previous chain key, :math:`C_{i,j-i}`. The next +Advancing a chain 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. @@ -94,25 +101,32 @@ 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`. +Bob publishes the public parts of 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`. +:math:`E_B`. She generates a new single-use key, :math:`E_A`, and computes a +root key, :math:`R_0`, and a chain key :math:`C_{0,0}`. She also 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 computes a message key, :math:`M_{0,j}`, and a new chain key, +:math:`C_{0,j+1}`, using the current chain key. She replaces the current chain +key with the new one. + 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. +:math:`X_{0,j}`. + +She then sends the following to Bob: + * The public part of her identity key, :math:`I_A` + * The public part of her single-use key, :math:`E_A` + * The public part of Bob's single-use key, :math:`E_B` + * The current chain index, :math:`j` + * The public part of her ratchet key, :math:`T_0` + * The cipher-text, :math:`X_{0,j}` Alice will continue to send pre-key messages until she receives a message from Bob. @@ -120,41 +134,58 @@ 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 +Bob receives a pre-key message as above. + +Bob looks up the private part of his single-use key, :math:`E_B`. He can now +compute the root key, :math:`R_0`, and the chain key, :math:`C_{0,0}`, from +:math:`I_A`, :math:`E_A`, :math:`I_B`, and :math:`E_B`. + +Bob then advances the chain key :math:`j` times, to compute the chain key used +by the message, :math:`C_{0,j}`. He now 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 -~~~~~~~~~~~~~~~~ +Bob stores Alice's initial ratchet key, :math:`T_0`, until he wants to +send a message. + +Sending normal 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 +Once a message has been received from the other side, a session is considered +established, and a more compact form is used. + +To send a message, the user checks if they have a sender chain key, +:math:`C_{i,j}`. Alice uses 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, +key :math:`T_i` is generated and a new root key :math:`R_i` and chain key +:math:`C_{i,0}` are 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. +scheme (see below) to get a cipher-text, :math:`X_{i,j}`. + +The user then sends the following to the recipient: + * The current chain index, :math:`j` + * The public part of the current ratchet key, :math:`T_i` + * The cipher-text, :math:`X_{i,j}` 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 +The user receives a message as above with the sender's current chain index, :math:`j`, +the sender's ratchet key, :math:`T_i`, and the cipher-text, :math:`X_{i,j}`. + +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 +then they compute a new root key, :math:`R_i`, and a new receiver chain, with +chain key :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 @@ -170,6 +201,9 @@ they will create a new chain when they next send a message. The Olm Message Format ---------------------- +Olm uses two types of messages. The underlying transport protocol must provide +a means for recipients to distinguish between them. + Normal Messages ~~~~~~~~~~~~~~~ @@ -182,7 +216,7 @@ payload followed by a fixed length message authentication code. | Version Byte | Payload Bytes | MAC Bytes | +--------------+------------------------------------+-----------+ -The version byte is ``"\x01"``. +The version byte is ``"\x03"``. 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 @@ -207,7 +241,8 @@ 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. +being used. (Olm version 1 uses HMAC-SHA-256, truncated to 8 bytes). The +MAC protects all of the bytes preceding the MAC. Pre-Key Messages ~~~~~~~~~~~~~~~~ @@ -221,7 +256,7 @@ length payload. | Version Byte | Payload Bytes | +--------------+------------------------------------+ -The version byte is ``"\x01"``. +The version byte is ``"\x03"``. The payload uses the same key-value format as for normal messages. @@ -245,21 +280,24 @@ 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. +encryption and HMAC-SHA-256_ (truncated to 64 bits) 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"``. .. 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) \\ + &= HKDF\left(0,\,M_{i,j},\text{"OLM\_KEYS"},\,80\right) \\ \end{align} +The plain-text is encrypted with AES-256, using the key :math:`AES\_KEY_{i,j}` +and the IV :math:`AES\_IV_{i,j}` to give the cipher-text, :math:`X_{i,j}`. + +Then the entire message (including the Version Byte and all Payload Bytes) are +passed through HMAC-SHA-256. The first 8 bytes of the MAC are appended to the message. + IPR --- @@ -274,11 +312,12 @@ 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 new implementation written by the Matrix.org team. +Marlinspike - details at https://github.com/trevp/double_ratchet/wiki. Olm is +an entirely 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/ +.. _`HMAC-based key derivation function`: https://tools.ietf.org/html/rfc5869 .. _`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 |