Convert olm.rst to markdown

Signed-off-by: Aaron Raimist <aaron@raim.ist>

2 files changed, 328 insertions, 358 deletions

diff --git a/docs/olm.md b/docs/olm.md
new file mode 100644
index 0000000..e9bb4ae
--- /dev/null
+++ b/docs/olm.md
@@ -0,0 +1,328 @@
+# Olm: A Cryptographic Ratchet
+
+An implementation of the double cryptographic ratchet described by
+https://whispersystems.org/docs/specifications/doubleratchet/.
+
+## Notation
+
+This document uses $`\parallel`$ to represent string concatenation. When
+$`\parallel`$ appears on the right hand side of an $`=`$ it means that
+the inputs are concatenated. When $`\parallel`$ appears on the left hand
+side of an $`=`$ it means that the output is split.
+
+When this document uses $`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 $`A`$ computes $`ECDH\left(K_B^{public},\,K_A^{private}\right)`$
+and party $`B`$ computes $`ECDH\left(K_A^{public},\,K_B^{private}\right)`$.
+
+Where this document uses $`HKDF\left(salt,\,IKM,\,info,\,L\right)`$ it
+refers to the [HMAC-based key derivation function][] with a salt value of
+$`salt`$, input key material of $`IKM`$, context string $`info`$,
+and output keying material length of $`L`$ bytes.
+
+## The Olm Algorithm
+
+### Initial setup
+
+The setup takes four [Curve25519][] inputs: Identity keys for Alice and Bob,
+$`I_A`$ and $`I_B`$, and one-time keys for Alice and Bob,
+$`E_A`$ and $`E_B`$. A shared secret, $`S`$, is generated using
+[Triple Diffie-Hellman][]. The initial 256 bit root key, $`R_0`$, and 256
+bit chain key, $`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{aligned}
+    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(0,\,S,\,\text{"OLM\_ROOT"},\,64\right)
+\end{aligned}
+```
+
+### Advancing the root key
+
+Advancing a root key takes the previous root key, $`R_{i-1}`$, and two
+Curve25519 inputs: the previous ratchet key, $`T_{i-1}`$, and the current
+ratchet key $`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, $`R_i`$, and
+chain key, $`C_{i,0}`$, are derived from the shared secret using
+[HKDF-SHA-256][] using $`R_{i-1}`$ as the salt and ``"OLM_RATCHET"`` as the
+info.
+
+```math
+\begin{aligned}
+    R_i\;\parallel\;C_{i,0}&=HKDF\left(
+        R_{i-1},\,
+        ECDH\left(T_{i-1},\,T_i\right),\,
+        \text{"OLM\_RATCHET"},\,
+        64
+    \right)
+\end{aligned}
+```
+
+### Advancing the chain key
+
+Advancing a chain key takes the previous chain key, $`C_{i,j-1}`$. The next
+chain key, $`C_{i,j}`$, is the [HMAC-SHA-256][] of ``"\x02"`` using the
+previous chain key as the key.
+
+```math
+\begin{aligned}
+    C_{i,j}&=HMAC\left(C_{i,j-1},\,\text{"\x02"}\right)
+\end{aligned}
+```
+
+### Creating a message key
+
+Creating a message key takes the current chain key, $`C_{i,j}`$. The
+message key, $`M_{i,j}`$, is the [HMAC-SHA-256][] of ``"\x01"`` using the
+current chain key as the key. The message keys where $`i`$ is even are used
+by Alice to encrypt messages. The message keys where $`i`$ is odd are used
+by Bob to encrypt messages.
+
+```math
+\begin{aligned}
+    M_{i,j}&=HMAC\left(C_{i,j},\,\text{"\x01"}\right)
+\end{aligned}
+```
+
+## The Olm Protocol
+
+### Creating an outbound session
+
+Bob publishes the public parts of his identity key, $`I_B`$, and some
+single-use one-time keys $`E_B`$.
+
+Alice downloads Bob's identity key, $`I_B`$, and a one-time key,
+$`E_B`$. She generates a new single-use key, $`E_A`$, and computes a
+root key, $`R_0`$, and a chain key $`C_{0,0}`$. She also generates a
+new ratchet key $`T_0`$.
+
+### Sending the first pre-key messages
+
+Alice computes a message key, $`M_{0,j}`$, and a new chain key,
+$`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, $`M_{0,j}`$, using an
+authenticated encryption scheme (see below) to get a cipher-text,
+$`X_{0,j}`$.
+
+She then sends the following to Bob:
+ * The public part of her identity key, $`I_A`$
+ * The public part of her single-use key, $`E_A`$
+ * The public part of Bob's single-use key, $`E_B`$
+ * The current chain index, $`j`$
+ * The public part of her ratchet key, $`T_0`$
+ * The cipher-text, $`X_{0,j}`$
+
+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 as above.
+
+Bob looks up the private part of his single-use key, $`E_B`$. He can now
+compute the root key, $`R_0`$, and the chain key, $`C_{0,0}`$, from
+$`I_A`$, $`E_A`$, $`I_B`$, and $`E_B`$.
+
+Bob then advances the chain key $`j`$ times, to compute the chain key used
+by the message, $`C_{0,j}`$. He now creates the
+message key, $`M_{0,j}`$, and attempts to decrypt the cipher-text,
+$`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, $`E_B`$.
+
+Bob stores Alice's initial ratchet key, $`T_0`$, until he wants to
+send a message.
+
+### Sending normal messages
+
+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,
+$`C_{i,j}`$. Alice uses chain keys where $`i`$ is even. Bob uses chain
+keys where $`i`$ is odd. If the chain key doesn't exist then a new ratchet
+key $`T_i`$ is generated and a new root key $`R_i`$ and chain key
+$`C_{i,0}`$ are computed using $`R_{i-1}`$, $`T_{i-1}`$ and
+$`T_i`$.
+
+A message key,
+$`M_{i,j}`$ is computed from the current chain key, $`C_{i,j}`$, and
+the chain key is replaced with the next chain key, $`C_{i,j+1}`$. The
+plain-text is encrypted with $`M_{i,j}`$, using an authenticated encryption
+scheme (see below) to get a cipher-text, $`X_{i,j}`$.
+
+The user then sends the following to the recipient:
+ * The current chain index, $`j`$
+ * The public part of the current ratchet key, $`T_i`$
+ * The cipher-text, $`X_{i,j}`$
+
+### Receiving messages
+
+The user receives a message as above with the sender's current chain index, $`j`$,
+the sender's ratchet key, $`T_i`$, and the cipher-text, $`X_{i,j}`$.
+
+The user checks if they have a receiver chain with the correct
+$`i`$ by comparing the ratchet key, $`T_i`$. If the chain doesn't exist
+then they compute a new root key, $`R_i`$, and a new receiver chain, with
+chain key $`C_{i,0}`$, using $`R_{i-1}`$, $`T_{i-1}`$ and
+$`T_i`$.
+
+If the $`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 $`M_{i,j}`$. Otherwise
+the receiver computes the chain key, $`C_{i,j}`$. The receiver computes the
+message key, $`M_{i,j}`$, from the chain key and attempts to decrypt the
+cipher-text, $`X_{i,j}`$.
+
+If the decryption succeeds the receiver updates the chain key for $`T_i`$
+with $`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
+
+Olm uses two types of messages. The underlying transport protocol must provide
+a means for recipients to distinguish between them.
+
+### Normal Messages
+
+Olm messages start with a one byte version followed by a variable length
+payload followed by a fixed length message authentication code.
+
+```
+ +--------------+------------------------------------+-----------+
+ | Version Byte | Payload Bytes                      | MAC Bytes |
+ +--------------+------------------------------------+-----------+
+```
+
+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
+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, Ti, of the message
+Chain-Index|0x10|Integer|The chain index, j, of the message
+Cipher-Text|0x22|String|The cipher-text, Xi, j, of the message
+
+The length of the MAC is determined by the authenticated encryption algorithm
+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
+
+Olm pre-key messages start with a one byte version followed by a variable
+length payload.
+
+```
+ +--------------+------------------------------------+
+ | Version Byte | Payload Bytes                      |
+ +--------------+------------------------------------+
+```
+
+The version byte is ``"\x03"``.
+
+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, Eb.
+Base-Key|0x12|String|The public part of Alice's single-use key, Ea.
+Identity-Key|0x1A|String|The public part of Alice's identity key, Ia.
+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 [PKCS#7][] padding for
+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{aligned}
+    AES\_KEY_{i,j}\;\parallel\;HMAC\_KEY_{i,j}\;\parallel\;AES\_IV_{i,j}
+    &= HKDF\left(0,\,M_{i,j},\text{"OLM\_KEYS"},\,80\right) \\
+\end{aligned}
+```
+
+The plain-text is encrypted with AES-256, using the key $`AES\_KEY_{i,j}`$
+and the IV $`AES\_IV_{i,j}`$ to give the cipher-text, $`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.
+
+## Message authentication concerns
+
+To avoid unknown key-share attacks, the application must include identifying
+data for the sending and receiving user in the plain-text of (at least) the
+pre-key messages. Such data could be a user ID, a telephone number;
+alternatively it could be the public part of a keypair which the relevant user
+has proven ownership of.
+
+### Example attacks
+
+1. Alice publishes her public [Curve25519][] identity key, $`I_A`$. Eve
+   publishes the same identity key, claiming it as her own. Bob downloads
+   Eve's keys, and associates $`I_A`$ with Eve. Alice sends a message to
+   Bob; Eve intercepts it before forwarding it to Bob. Bob believes the
+   message came from Eve rather than Alice.
+
+   This is prevented if Alice includes her user ID in the plain-text of the
+   pre-key message, so that Bob can see that the message was sent by Alice
+   originally.
+
+2. Bob publishes his public [Curve25519][] identity key, $`I_B`$. Eve
+   publishes the same identity key, claiming it as her own. Alice downloads
+   Eve's keys, and associates $`I_B`$ with Eve. Alice sends a message to
+   Eve; Eve cannot decrypt it, but forwards it to Bob. Bob believes the
+   Alice sent the message to him, wheras Alice intended it to go to Eve.
+
+   This is prevented by Alice including the user ID of the intended recpient
+   (Eve) in the plain-text of the pre-key message. Bob can now tell that the
+   message was meant for Eve rather than him.
+
+## IPR
+
+The Olm specification (this document) is hereby placed in the public domain.
+
+## Feedback
+
+Can be sent to olm at matrix.org.
+
+## Acknowledgements
+
+The ratchet that Olm implements was designed by Trevor Perrin and Moxie
+Marlinspike - details at https://whispersystems.org/docs/specifications/doubleratchet/. 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
+[AES-256]: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
+[CBC]: http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf
+[PKCS#7]: https://tools.ietf.org/html/rfc2315
diff --git a/docs/olm.rst b/docs/olm.rst
deleted file mode 100644
index 9c13478..0000000
--- a/docs/olm.rst
+++ /dev/null
@@ -1,358 +0,0 @@
-Olm: A Cryptographic Ratchet
-============================
-
-An implementation of the double cryptographic ratchet described by
-https://whispersystems.org/docs/specifications/doubleratchet/.
-
-
-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)`.
-
-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
------------------
-
-Initial setup
-~~~~~~~~~~~~~
-
-The setup takes four Curve25519_ inputs: Identity keys for Alice and Bob,
-:math:`I_A` and :math:`I_B`, and one-time 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(0,\,S,\,\text{"OLM\_ROOT"},\,64\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(
-            R_{i-1},\,
-            ECDH\left(T_{i-1},\,T_i\right),\,
-            \text{"OLM\_RATCHET"},\,
-            64
-        \right)
-    \end{align}
-
-
-Advancing the chain key
-~~~~~~~~~~~~~~~~~~~~~~~
-
-Advancing a chain key takes the previous chain key, :math:`C_{i,j-1}`. 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 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`. 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}`, 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}`.
-
-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.
-
-Creating an inbound session from a pre-key message
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-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`.
-
-Bob stores Alice's initial ratchet key, :math:`T_0`, until he wants to
-send a message.
-
-Sending normal messages
-~~~~~~~~~~~~~~~~~~~~~~~
-
-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 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}`.
-
-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 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 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
-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
-----------------------
-
-Olm uses two types of messages. The underlying transport protocol must provide
-a means for recipients to distinguish between them.
-
-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 ``"\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
-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. (Olm version 1 uses HMAC-SHA-256, truncated to 8 bytes). 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 ``"\x03"``.
-
-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 `PKCS#7`_ padding for
-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(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.
-
-Message authentication concerns
--------------------------------
-
-To avoid unknown key-share attacks, the application must include identifying
-data for the sending and receiving user in the plain-text of (at least) the
-pre-key messages. Such data could be a user ID, a telephone number;
-alternatively it could be the public part of a keypair which the relevant user
-has proven ownership of.
-
-.. admonition:: Example attacks
-
-   1. Alice publishes her public Curve25519 identity key, :math:`I_A`. Eve
-      publishes the same identity key, claiming it as her own. Bob downloads
-      Eve's keys, and associates :math:`I_A` with Eve. Alice sends a message to
-      Bob; Eve intercepts it before forwarding it to Bob. Bob believes the
-      message came from Eve rather than Alice.
-
-      This is prevented if Alice includes her user ID in the plain-text of the
-      pre-key message, so that Bob can see that the message was sent by Alice
-      originally.
-
-   2. Bob publishes his public Curve25519 identity key, :math:`I_B`. Eve
-      publishes the same identity key, claiming it as her own. Alice downloads
-      Eve's keys, and associates :math:`I_B` with Eve. Alice sends a message to
-      Eve; Eve cannot decrypt it, but forwards it to Bob. Bob believes the
-      Alice sent the message to him, wheras Alice intended it to go to Eve.
-
-      This is prevented by Alice including the user ID of the intended recpient
-      (Eve) in the plain-text of the pre-key message. Bob can now tell that the
-      message was meant for Eve rather than him.
-
-IPR
----
-
-The Olm specification (this document) is hereby placed in the public domain.
-
-Feedback
---------
-
-Can be sent to olm at matrix.org.
-
-Acknowledgements
-----------------
-
-The ratchet that Olm implements was designed by Trevor Perrin and Moxie
-Marlinspike - details at https://whispersystems.org/docs/specifications/doubleratchet/.  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
-.. _`AES-256`: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
-.. _`CBC`: http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf
-.. _`PKCS#7`: https://tools.ietf.org/html/rfc2315