diff options
| -rw-r--r-- | docs/olm.rst | 127 |
1 files changed, 120 insertions, 7 deletions
diff --git a/docs/olm.rst b/docs/olm.rst index 07836f6..db32cdb 100644 --- a/docs/olm.rst +++ b/docs/olm.rst @@ -19,24 +19,137 @@ The setup takes four Curve25519 inputs: Identity 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 (HKDF). +HMAC-based Key Derivation Function (HKDF) with default salt. .. 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(S,\,\text{"OLM\_ROOT"}) + 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, `S` is generated -using Diffie-Hellman on the ratchet keys. The next root key, :math:`R_o`, and +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 an -HMAC-based Key Derivation Function (HKDF). +HMAC-based Key Derivation Function (HKDF) using :math:`R_{i-1}` as the salt. +.. 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 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 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 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 ciphertext, +:math:`X_{0,j}`. If the cipher-text's authentication is correct then Bob can +discard 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 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 reciever 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. |