Convert olm.rst to markdown

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

1 files changed, 0 insertions, 358 deletions

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