aboutsummaryrefslogtreecommitdiff
path: root/docs
diff options
context:
space:
mode:
Diffstat (limited to 'docs')
-rw-r--r--docs/megolm.rst290
-rw-r--r--docs/olm.rst143
2 files changed, 381 insertions, 52 deletions
diff --git a/docs/megolm.rst b/docs/megolm.rst
new file mode 100644
index 0000000..7853963
--- /dev/null
+++ b/docs/megolm.rst
@@ -0,0 +1,290 @@
+.. Copyright 2016 OpenMarket Ltd
+..
+.. Licensed under the Apache License, Version 2.0 (the "License");
+.. you may not use this file except in compliance with the License.
+.. You may obtain a copy of the License at
+..
+.. http://www.apache.org/licenses/LICENSE-2.0
+..
+.. Unless required by applicable law or agreed to in writing, software
+.. distributed under the License is distributed on an "AS IS" BASIS,
+.. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+.. See the License for the specific language governing permissions and
+.. limitations under the License.
+
+
+Megolm group ratchet
+====================
+
+An AES-based cryptographic ratchet intended for group communications.
+
+.. contents::
+
+Background
+----------
+
+The Megolm ratchet is intended for encrypted messaging applications where there
+may be a large number of recipients of each message, thus precluding the use of
+peer-to-peer encryption systems such as `Olm`_.
+
+It also allows a receipient to decrypt received messages multiple times. For
+instance, in client/server applications, a copy of the ciphertext can be stored
+on the (untrusted) server, while the client need only store the session keys.
+
+Overview
+--------
+
+Each participant in a conversation uses their own outbound session for
+encrypting messages. A session consists of a ratchet and an `Ed25519`_ keypair.
+
+Secrecy is provided by the ratchet, which can be wound forwards but not
+backwards, and is used to derive a distinct message key for each message.
+
+Authenticity is provided via Ed25519 signatures.
+
+The value of the ratchet, and the public part of the Ed25519 key, are shared
+with other participants in the conversation via secure peer-to-peer
+channels. Provided that peer-to-peer channel provides authenticity of the
+messages to the participants and deniability of the messages to third parties,
+the Megolm session will inherit those properties.
+
+The Megolm ratchet algorithm
+----------------------------
+
+The Megolm ratchet :math:`R_i` consists of four parts, :math:`R_{i,j}` for
+:math:`j \in {0,1,2,3}`. The length of each part depends on the hash function
+in use (256 bits for this version of Megolm).
+
+The ratchet is initialised with cryptographically-secure random data, and
+advanced as follows:
+
+.. math::
+ \begin{align}
+ R_{i,0} &=
+ \begin{cases}
+ H_0\left(R_{2^24(n-1),0}\right) &\text{if }\exists n | i = 2^24n\\
+ R_{i-1,0} &\text{otherwise}
+ \end{cases}\\
+ R_{i,1} &=
+ \begin{cases}
+ H_1\left(R_{2^24(n-1),0}\right) &\text{if }\exists n | i = 2^24n\\
+ H_1\left(R_{2^16(m-1),1}\right) &\text{if }\exists m | i = 2^16m\\
+ R_{i-1,1} &\text{otherwise}
+ \end{cases}\\
+ R_{i,2} &=
+ \begin{cases}
+ H_2\left(R_{2^24(n-1),0}\right) &\text{if }\exists n | i = 2^24n\\
+ H_2\left(R_{2^16(m-1),1}\right) &\text{if }\exists m | i = 2^16m\\
+ H_2\left(R_{2^8(p-1),2}\right) &\text{if }\exists p | i = 2^8p\\
+ R_{i-1,2} &\text{otherwise}
+ \end{cases}\\
+ R_{i,3} &=
+ \begin{cases}
+ H_3\left(R_{2^24(n-1),0}\right) &\text{if }\exists n | i = 2^24n\\
+ H_3\left(R_{2^16(m-1),1}\right) &\text{if }\exists m | i = 2^16m\\
+ H_3\left(R_{2^8(p-1),2}\right) &\text{if }\exists p | i = 2^8p\\
+ H_3\left(R_{i-1,3}\right) &\text{otherwise}
+ \end{cases}
+ \end{align}
+
+where :math:`H_0`, :math:`H_1`, :math:`H_2`, and :math:`H_3` are different hash
+functions. In summary: every :math:`2^8` iterations, :math:`R_{i,3}` is
+reseeded from :math:`R_{i,2}`. Every :math:`2^16` iterations, :math:`R_{i,2}`
+and :math:`R_{i,3}` are reseeded from :math:`R_{i,1}`. Every :math:`2^24`
+iterations, :math:`R_{i,1}`, :math:`R_{i,2}` and :math:`R_{i,3}` are reseeded
+from :math:`R_{i,0}`.
+
+The complete ratchet value, :math:`R_{i}`, is hashed to generate the keys used
+to encrypt each message. This scheme allows the ratchet to be advanced an
+arbitrary amount forwards while needing at most 1023 hash computations. A
+client can decrypt chat history onwards from the earliest value of the ratchet
+it is aware of, but cannot decrypt history from before that point without
+reversing the hash function.
+
+This allows a participant to share its ability to decrypt chat history with
+another from a point in the conversation onwards by giving a copy of the
+ratchet at that point in the conversation.
+
+
+The Megolm protocol
+-------------------
+
+Session setup
+~~~~~~~~~~~~~
+
+Each participant in a conversation generates their own Megolm session. A
+session consists of three parts:
+
+* a 32 bit counter, :math:`i`.
+* an `Ed25519`_ keypair, :math:`K`.
+* a ratchet, :math:`R_i`, which consists of four 256-bit values,
+ :math:`R_{i,j}` for :math:`j \in {0,1,2,3}`.
+
+The counter :math:`i` is initialised to :math:`0`. A new Ed25519 keypair is
+generated for :math:`K`. The ratchet is simply initialised with 1024 bits of
+cryptographically-secure random data.
+
+A single participant may use multiple sessions over the lifetime of a
+conversation. The public part of :math:`K` is used as an identifier to
+discriminate between sessions.
+
+Sharing session data
+~~~~~~~~~~~~~~~~~~~~
+
+To allow other participants in the conversation to decrypt messages, the
+session data is formatted as described in `Session-sharing format`_. It is then
+shared with other participants in the conversation via a secure peer-to-peer
+channel (such as that provided by `Olm`_).
+
+When the session data is received from other participants, the recipient first
+checks that the signature matches the public key. They then store their own
+copy of the counter, ratchet, and public key.
+
+Message encryption
+~~~~~~~~~~~~~~~~~~
+
+This version of Megolm uses AES-256_ in CBC_ mode with `PCKS#7`_ padding and
+HMAC-SHA-256_ (truncated to 64 bits). The 256 bit AES key, 256 bit HMAC key,
+and 128 bit AES IV are derived from the megolm ratchet :math:`R_i`:
+
+.. math::
+
+ \begin{align}
+ AES\_KEY_{i}\;\parallel\;HMAC\_KEY_{i}\;\parallel\;AES\_IV_{i}
+ &= HKDF\left(0,\,R_{i},\text{"MEGOLM\_KEYS"},\,80\right) \\
+ \end{align}
+
+where :math:`\parallel` represents string splitting, and
+:math:`HKDF\left(salt,\,IKM,\,info,\,L\right)` refers to the `HMAC-based key
+derivation function`_ using using `SHA-256`_ as the hash function
+(`HKDF-SHA-256`_) 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 plain-text is encrypted with AES-256, using the key :math:`AES\_KEY_{i}`
+and the IV :math:`AES\_IV_{i}` to give the cipher-text, :math:`X_{i}`.
+
+The ratchet index :math:`i`, and the cipher-text :math:`X_{i}`, are then packed
+into a message as described in `Message format`_. Then the entire message
+(including the version bytes and all payload bytes) are passed through
+HMAC-SHA-256. The first 8 bytes of the MAC are appended to the message.
+
+Finally, the authenticated message is signed using the Ed25519 keypair; the 64
+byte signature is appended to the message.
+
+The complete signed message, together with the public part of :math:`K` (acting
+as a session identifier), can then be sent over an insecure channel. The
+message can then be authenticated and decrypted only by recipients who have
+received the session data.
+
+Advancing the ratchet
+~~~~~~~~~~~~~~~~~~~~~
+
+After each message is encrypted, the ratchet is advanced. This is done as
+described in `The Megolm ratchet algorithm`_, using the following definitions:
+
+.. math::
+ \begin{align}
+ H_0(A) &\equiv HMAC(A,\text{"\textbackslash x00"}) \\
+ H_1(A) &\equiv HMAC(A,\text{"\textbackslash x01"}) \\
+ H_2(A) &\equiv HMAC(A,\text{"\textbackslash x02"}) \\
+ H_3(A) &\equiv HMAC(A,\text{"\textbackslash x03"}) \\
+ \end{align}
+
+where :math:`HMAC(A, T)` is the HMAC-SHA-256_ of ``T``, using ``A`` as the
+key.
+
+For outbound sessions, the updated ratchet and counter are stored in the
+session.
+
+In order to maintain the ability to decrypt conversation history, inbound
+sessions should store a copy of their earliest known ratchet value (unless they
+explicitly want to drop the ability to decrypt that history). They may also
+choose to cache calculated ratchet values, but the decision of which ratchet
+states to cache is left to the application.
+
+Data exchange formats
+---------------------
+
+Session-sharing format
+~~~~~~~~~~~~~~~~~~~~~~
+
+The Megolm key-sharing format is as follows:
+
+.. code::
+
+ +---+----+--------+--------+--------+--------+------+-----------+
+ | V | i | R(i,0) | R(i,1) | R(i,2) | R(i,3) | Kpub | Signature |
+ +---+----+--------+--------+--------+--------+------+-----------+
+ 0 1 5 37 69 101 133 165 229 bytes
+
+The version byte, ``V``, is ``"\x02"``.
+
+This is followed by the ratchet index, :math:`i`, which is encoded as a
+big-endian 32-bit integer; the ratchet values :math:`R_{i,j}`; and the public
+part of the Ed25519 keypair :math:`K`.
+
+The data is then signed using the Ed25519 keypair, and the 64-byte signature is
+appended.
+
+Message format
+~~~~~~~~~~~~~~
+
+Megolm messages consist of a one byte version, followed by a variable length
+payload, a fixed length message authentication code, and a fixed length
+signature.
+
+.. code::
+
+ +---+------------------------------------+-----------+------------------+
+ | V | Payload Bytes | MAC Bytes | Signature Bytes |
+ +---+------------------------------------+-----------+------------------+
+ 0 1 N N+8 N+72 bytes
+
+The version byte, ``V``, is ``"\x03"``.
+
+The payload uses a format based on the `Protocol Buffers encoding`_. It
+consists of the following key-value pairs:
+
+============= ===== ======== ================================================
+ Name Tag Type Meaning
+============= ===== ======== ================================================
+Message-Index 0x08 Integer The index of the ratchet, :math:`i`
+Cipher-Text 0x12 String The cipher-text, :math:`X_{i}`, of the message
+============= ===== ======== ================================================
+
+Within the payload, integers are encoded using a variable length encoding. 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.
+
+Strings are encoded as a variable-length integer followed by the string itself.
+
+Each key-value pair is encoded as a variable-length integer giving the tag,
+followed by a string or variable-length integer giving the value.
+
+The payload is followed by the MAC. The length of the MAC is determined by the
+authenticated encryption algorithm being used (8 bytes in this version of the
+protocol). The MAC protects all of the bytes preceding the MAC.
+
+The length of the signature is determined by the signing algorithm being used
+(64 bytes in this version of the protocol). The signature covers all of the
+bytes preceding the signaure.
+
+License
+-------
+
+The Megolm specification (this document) is licensed under the `Apache License,
+Version 2.0 <http://www.apache.org/licenses/LICENSE-2.0>`_.
+
+
+.. _`Ed25519`: http://ed25519.cr.yp.to/
+.. _`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
+.. _`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
+.. _`Olm`: ./olm.html
+.. _`Protocol Buffers encoding`: https://developers.google.com/protocol-buffers/docs/encoding
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