X-Git-Url: https://gitweb.ps.run/matrix_esp_thesis/blobdiff_plain/21c6e8484b0bd05c27e5a91f2884d431926adc61..da776f86b42946715c27edd64f7558b9d5080df1:/ext/olm/src/ratchet.cpp diff --git a/ext/olm/src/ratchet.cpp b/ext/olm/src/ratchet.cpp new file mode 100644 index 0000000..1d284a6 --- /dev/null +++ b/ext/olm/src/ratchet.cpp @@ -0,0 +1,625 @@ +/* Copyright 2015, 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. + */ +#include "olm/ratchet.hh" +#include "olm/message.hh" +#include "olm/memory.hh" +#include "olm/cipher.h" +#include "olm/pickle.hh" + +#include + +namespace { + +static const std::uint8_t PROTOCOL_VERSION = 3; +static const std::uint8_t MESSAGE_KEY_SEED[1] = {0x01}; +static const std::uint8_t CHAIN_KEY_SEED[1] = {0x02}; +static const std::size_t MAX_MESSAGE_GAP = 2000; + + +/** + * Advance the root key, creating a new message chain. + * + * @param root_key previous root key R(n-1) + * @param our_key our new ratchet key T(n) + * @param their_key their most recent ratchet key T(n-1) + * @param info table of constants for the ratchet function + * @param new_root_key[out] returns the new root key R(n) + * @param new_chain_key[out] returns the first chain key in the new chain + * C(n,0) + */ +static void create_chain_key( + olm::SharedKey const & root_key, + _olm_curve25519_key_pair const & our_key, + _olm_curve25519_public_key const & their_key, + olm::KdfInfo const & info, + olm::SharedKey & new_root_key, + olm::ChainKey & new_chain_key +) { + olm::SharedKey secret; + _olm_crypto_curve25519_shared_secret(&our_key, &their_key, secret); + std::uint8_t derived_secrets[2 * olm::OLM_SHARED_KEY_LENGTH]; + _olm_crypto_hkdf_sha256( + secret, sizeof(secret), + root_key, sizeof(root_key), + info.ratchet_info, info.ratchet_info_length, + derived_secrets, sizeof(derived_secrets) + ); + std::uint8_t const * pos = derived_secrets; + pos = olm::load_array(new_root_key, pos); + pos = olm::load_array(new_chain_key.key, pos); + new_chain_key.index = 0; + olm::unset(derived_secrets); + olm::unset(secret); +} + + +static void advance_chain_key( + olm::ChainKey const & chain_key, + olm::ChainKey & new_chain_key +) { + _olm_crypto_hmac_sha256( + chain_key.key, sizeof(chain_key.key), + CHAIN_KEY_SEED, sizeof(CHAIN_KEY_SEED), + new_chain_key.key + ); + new_chain_key.index = chain_key.index + 1; +} + + +static void create_message_keys( + olm::ChainKey const & chain_key, + olm::KdfInfo const & info, + olm::MessageKey & message_key) { + _olm_crypto_hmac_sha256( + chain_key.key, sizeof(chain_key.key), + MESSAGE_KEY_SEED, sizeof(MESSAGE_KEY_SEED), + message_key.key + ); + message_key.index = chain_key.index; +} + + +static std::size_t verify_mac_and_decrypt( + _olm_cipher const *cipher, + olm::MessageKey const & message_key, + olm::MessageReader const & reader, + std::uint8_t * plaintext, std::size_t max_plaintext_length +) { + return cipher->ops->decrypt( + cipher, + message_key.key, sizeof(message_key.key), + reader.input, reader.input_length, + reader.ciphertext, reader.ciphertext_length, + plaintext, max_plaintext_length + ); +} + + +static std::size_t verify_mac_and_decrypt_for_existing_chain( + olm::Ratchet const & session, + olm::ChainKey const & chain, + olm::MessageReader const & reader, + std::uint8_t * plaintext, std::size_t max_plaintext_length +) { + if (reader.counter < chain.index) { + return std::size_t(-1); + } + + /* Limit the number of hashes we're prepared to compute */ + if (reader.counter - chain.index > MAX_MESSAGE_GAP) { + return std::size_t(-1); + } + + olm::ChainKey new_chain = chain; + + while (new_chain.index < reader.counter) { + advance_chain_key(new_chain, new_chain); + } + + olm::MessageKey message_key; + create_message_keys(new_chain, session.kdf_info, message_key); + + std::size_t result = verify_mac_and_decrypt( + session.ratchet_cipher, message_key, reader, + plaintext, max_plaintext_length + ); + + olm::unset(new_chain); + return result; +} + + +static std::size_t verify_mac_and_decrypt_for_new_chain( + olm::Ratchet const & session, + olm::MessageReader const & reader, + std::uint8_t * plaintext, std::size_t max_plaintext_length +) { + olm::SharedKey new_root_key; + olm::ReceiverChain new_chain; + + /* They shouldn't move to a new chain until we've sent them a message + * acknowledging the last one */ + if (session.sender_chain.empty()) { + return std::size_t(-1); + } + + /* Limit the number of hashes we're prepared to compute */ + if (reader.counter > MAX_MESSAGE_GAP) { + return std::size_t(-1); + } + olm::load_array(new_chain.ratchet_key.public_key, reader.ratchet_key); + + create_chain_key( + session.root_key, session.sender_chain[0].ratchet_key, + new_chain.ratchet_key, session.kdf_info, + new_root_key, new_chain.chain_key + ); + std::size_t result = verify_mac_and_decrypt_for_existing_chain( + session, new_chain.chain_key, reader, + plaintext, max_plaintext_length + ); + olm::unset(new_root_key); + olm::unset(new_chain); + return result; +} + +} // namespace + + +olm::Ratchet::Ratchet( + olm::KdfInfo const & kdf_info, + _olm_cipher const * ratchet_cipher +) : kdf_info(kdf_info), + ratchet_cipher(ratchet_cipher), + last_error(OlmErrorCode::OLM_SUCCESS) { +} + + +void olm::Ratchet::initialise_as_bob( + std::uint8_t const * shared_secret, std::size_t shared_secret_length, + _olm_curve25519_public_key const & their_ratchet_key +) { + std::uint8_t derived_secrets[2 * olm::OLM_SHARED_KEY_LENGTH]; + _olm_crypto_hkdf_sha256( + shared_secret, shared_secret_length, + nullptr, 0, + kdf_info.root_info, kdf_info.root_info_length, + derived_secrets, sizeof(derived_secrets) + ); + receiver_chains.insert(); + receiver_chains[0].chain_key.index = 0; + std::uint8_t const * pos = derived_secrets; + pos = olm::load_array(root_key, pos); + pos = olm::load_array(receiver_chains[0].chain_key.key, pos); + receiver_chains[0].ratchet_key = their_ratchet_key; + olm::unset(derived_secrets); +} + + +void olm::Ratchet::initialise_as_alice( + std::uint8_t const * shared_secret, std::size_t shared_secret_length, + _olm_curve25519_key_pair const & our_ratchet_key +) { + std::uint8_t derived_secrets[2 * olm::OLM_SHARED_KEY_LENGTH]; + _olm_crypto_hkdf_sha256( + shared_secret, shared_secret_length, + nullptr, 0, + kdf_info.root_info, kdf_info.root_info_length, + derived_secrets, sizeof(derived_secrets) + ); + sender_chain.insert(); + sender_chain[0].chain_key.index = 0; + std::uint8_t const * pos = derived_secrets; + pos = olm::load_array(root_key, pos); + pos = olm::load_array(sender_chain[0].chain_key.key, pos); + sender_chain[0].ratchet_key = our_ratchet_key; + olm::unset(derived_secrets); +} + +namespace olm { + + +static std::size_t pickle_length( + const olm::SharedKey & value +) { + return olm::OLM_SHARED_KEY_LENGTH; +} + + +static std::uint8_t * pickle( + std::uint8_t * pos, + const olm::SharedKey & value +) { + return olm::pickle_bytes(pos, value, olm::OLM_SHARED_KEY_LENGTH); +} + + +static std::uint8_t const * unpickle( + std::uint8_t const * pos, std::uint8_t const * end, + olm::SharedKey & value +) { + return olm::unpickle_bytes(pos, end, value, olm::OLM_SHARED_KEY_LENGTH); +} + + +static std::size_t pickle_length( + const olm::SenderChain & value +) { + std::size_t length = 0; + length += olm::pickle_length(value.ratchet_key); + length += olm::pickle_length(value.chain_key.key); + length += olm::pickle_length(value.chain_key.index); + return length; +} + + +static std::uint8_t * pickle( + std::uint8_t * pos, + const olm::SenderChain & value +) { + pos = olm::pickle(pos, value.ratchet_key); + pos = olm::pickle(pos, value.chain_key.key); + pos = olm::pickle(pos, value.chain_key.index); + return pos; +} + + +static std::uint8_t const * unpickle( + std::uint8_t const * pos, std::uint8_t const * end, + olm::SenderChain & value +) { + pos = olm::unpickle(pos, end, value.ratchet_key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.chain_key.key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.chain_key.index); UNPICKLE_OK(pos); + return pos; +} + +static std::size_t pickle_length( + const olm::ReceiverChain & value +) { + std::size_t length = 0; + length += olm::pickle_length(value.ratchet_key); + length += olm::pickle_length(value.chain_key.key); + length += olm::pickle_length(value.chain_key.index); + return length; +} + + +static std::uint8_t * pickle( + std::uint8_t * pos, + const olm::ReceiverChain & value +) { + pos = olm::pickle(pos, value.ratchet_key); + pos = olm::pickle(pos, value.chain_key.key); + pos = olm::pickle(pos, value.chain_key.index); + return pos; +} + + +static std::uint8_t const * unpickle( + std::uint8_t const * pos, std::uint8_t const * end, + olm::ReceiverChain & value +) { + pos = olm::unpickle(pos, end, value.ratchet_key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.chain_key.key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.chain_key.index); UNPICKLE_OK(pos); + return pos; +} + + +static std::size_t pickle_length( + const olm::SkippedMessageKey & value +) { + std::size_t length = 0; + length += olm::pickle_length(value.ratchet_key); + length += olm::pickle_length(value.message_key.key); + length += olm::pickle_length(value.message_key.index); + return length; +} + + +static std::uint8_t * pickle( + std::uint8_t * pos, + const olm::SkippedMessageKey & value +) { + pos = olm::pickle(pos, value.ratchet_key); + pos = olm::pickle(pos, value.message_key.key); + pos = olm::pickle(pos, value.message_key.index); + return pos; +} + + +static std::uint8_t const * unpickle( + std::uint8_t const * pos, std::uint8_t const * end, + olm::SkippedMessageKey & value +) { + pos = olm::unpickle(pos, end, value.ratchet_key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.message_key.key); UNPICKLE_OK(pos); + pos = olm::unpickle(pos, end, value.message_key.index); UNPICKLE_OK(pos); + return pos; +} + + +} // namespace olm + + +std::size_t olm::pickle_length( + olm::Ratchet const & value +) { + std::size_t length = 0; + length += olm::OLM_SHARED_KEY_LENGTH; + length += olm::pickle_length(value.sender_chain); + length += olm::pickle_length(value.receiver_chains); + length += olm::pickle_length(value.skipped_message_keys); + return length; +} + +std::uint8_t * olm::pickle( + std::uint8_t * pos, + olm::Ratchet const & value +) { + pos = pickle(pos, value.root_key); + pos = pickle(pos, value.sender_chain); + pos = pickle(pos, value.receiver_chains); + pos = pickle(pos, value.skipped_message_keys); + return pos; +} + + +std::uint8_t const * olm::unpickle( + std::uint8_t const * pos, std::uint8_t const * end, + olm::Ratchet & value, + bool includes_chain_index +) { + pos = unpickle(pos, end, value.root_key); UNPICKLE_OK(pos); + pos = unpickle(pos, end, value.sender_chain); UNPICKLE_OK(pos); + pos = unpickle(pos, end, value.receiver_chains); UNPICKLE_OK(pos); + pos = unpickle(pos, end, value.skipped_message_keys); UNPICKLE_OK(pos); + + // pickle v 0x80000001 includes a chain index; pickle v1 does not. + if (includes_chain_index) { + std::uint32_t dummy; + pos = unpickle(pos, end, dummy); UNPICKLE_OK(pos); + } + return pos; +} + + +std::size_t olm::Ratchet::encrypt_output_length( + std::size_t plaintext_length +) const { + std::size_t counter = 0; + if (!sender_chain.empty()) { + counter = sender_chain[0].chain_key.index; + } + std::size_t padded = ratchet_cipher->ops->encrypt_ciphertext_length( + ratchet_cipher, + plaintext_length + ); + return olm::encode_message_length( + counter, CURVE25519_KEY_LENGTH, padded, ratchet_cipher->ops->mac_length(ratchet_cipher) + ); +} + + +std::size_t olm::Ratchet::encrypt_random_length() const { + return sender_chain.empty() ? CURVE25519_RANDOM_LENGTH : 0; +} + + +std::size_t olm::Ratchet::encrypt( + std::uint8_t const * plaintext, std::size_t plaintext_length, + std::uint8_t const * random, std::size_t random_length, + std::uint8_t * output, std::size_t max_output_length +) { + std::size_t output_length = encrypt_output_length(plaintext_length); + + if (random_length < encrypt_random_length()) { + last_error = OlmErrorCode::OLM_NOT_ENOUGH_RANDOM; + return std::size_t(-1); + } + if (max_output_length < output_length) { + last_error = OlmErrorCode::OLM_OUTPUT_BUFFER_TOO_SMALL; + return std::size_t(-1); + } + + if (sender_chain.empty()) { + sender_chain.insert(); + _olm_crypto_curve25519_generate_key(random, &sender_chain[0].ratchet_key); + create_chain_key( + root_key, + sender_chain[0].ratchet_key, + receiver_chains[0].ratchet_key, + kdf_info, + root_key, sender_chain[0].chain_key + ); + } + + MessageKey keys; + create_message_keys(sender_chain[0].chain_key, kdf_info, keys); + advance_chain_key(sender_chain[0].chain_key, sender_chain[0].chain_key); + + std::size_t ciphertext_length = ratchet_cipher->ops->encrypt_ciphertext_length( + ratchet_cipher, + plaintext_length + ); + std::uint32_t counter = keys.index; + _olm_curve25519_public_key const & ratchet_key = + sender_chain[0].ratchet_key.public_key; + + olm::MessageWriter writer; + + olm::encode_message( + writer, PROTOCOL_VERSION, counter, CURVE25519_KEY_LENGTH, + ciphertext_length, + output + ); + + olm::store_array(writer.ratchet_key, ratchet_key.public_key); + + ratchet_cipher->ops->encrypt( + ratchet_cipher, + keys.key, sizeof(keys.key), + plaintext, plaintext_length, + writer.ciphertext, ciphertext_length, + output, output_length + ); + + olm::unset(keys); + return output_length; +} + + +std::size_t olm::Ratchet::decrypt_max_plaintext_length( + std::uint8_t const * input, std::size_t input_length +) { + olm::MessageReader reader; + olm::decode_message( + reader, input, input_length, + ratchet_cipher->ops->mac_length(ratchet_cipher) + ); + + if (!reader.ciphertext) { + last_error = OlmErrorCode::OLM_BAD_MESSAGE_FORMAT; + return std::size_t(-1); + } + + return ratchet_cipher->ops->decrypt_max_plaintext_length( + ratchet_cipher, reader.ciphertext_length); +} + + +std::size_t olm::Ratchet::decrypt( + std::uint8_t const * input, std::size_t input_length, + std::uint8_t * plaintext, std::size_t max_plaintext_length +) { + olm::MessageReader reader; + olm::decode_message( + reader, input, input_length, + ratchet_cipher->ops->mac_length(ratchet_cipher) + ); + + if (reader.version != PROTOCOL_VERSION) { + last_error = OlmErrorCode::OLM_BAD_MESSAGE_VERSION; + return std::size_t(-1); + } + + if (!reader.has_counter || !reader.ratchet_key || !reader.ciphertext) { + last_error = OlmErrorCode::OLM_BAD_MESSAGE_FORMAT; + return std::size_t(-1); + } + + std::size_t max_length = ratchet_cipher->ops->decrypt_max_plaintext_length( + ratchet_cipher, + reader.ciphertext_length + ); + + if (max_plaintext_length < max_length) { + last_error = OlmErrorCode::OLM_OUTPUT_BUFFER_TOO_SMALL; + return std::size_t(-1); + } + + if (reader.ratchet_key_length != CURVE25519_KEY_LENGTH) { + last_error = OlmErrorCode::OLM_BAD_MESSAGE_FORMAT; + return std::size_t(-1); + } + + ReceiverChain * chain = nullptr; + + for (olm::ReceiverChain & receiver_chain : receiver_chains) { + if (0 == std::memcmp( + receiver_chain.ratchet_key.public_key, reader.ratchet_key, + CURVE25519_KEY_LENGTH + )) { + chain = &receiver_chain; + break; + } + } + + std::size_t result = std::size_t(-1); + + if (!chain) { + result = verify_mac_and_decrypt_for_new_chain( + *this, reader, plaintext, max_plaintext_length + ); + } else if (chain->chain_key.index > reader.counter) { + /* Chain already advanced beyond the key for this message + * Check if the message keys are in the skipped key list. */ + for (olm::SkippedMessageKey & skipped : skipped_message_keys) { + if (reader.counter == skipped.message_key.index + && 0 == std::memcmp( + skipped.ratchet_key.public_key, reader.ratchet_key, + CURVE25519_KEY_LENGTH + ) + ) { + /* Found the key for this message. Check the MAC. */ + + result = verify_mac_and_decrypt( + ratchet_cipher, skipped.message_key, reader, + plaintext, max_plaintext_length + ); + + if (result != std::size_t(-1)) { + /* Remove the key from the skipped keys now that we've + * decoded the message it corresponds to. */ + olm::unset(skipped); + skipped_message_keys.erase(&skipped); + return result; + } + } + } + } else { + result = verify_mac_and_decrypt_for_existing_chain( + *this, chain->chain_key, + reader, plaintext, max_plaintext_length + ); + } + + if (result == std::size_t(-1)) { + last_error = OlmErrorCode::OLM_BAD_MESSAGE_MAC; + return std::size_t(-1); + } + + if (!chain) { + /* They have started using a new ephemeral ratchet key. + * We need to derive a new set of chain keys. + * We can discard our previous ephemeral ratchet key. + * We will generate a new key when we send the next message. */ + + chain = receiver_chains.insert(); + olm::load_array(chain->ratchet_key.public_key, reader.ratchet_key); + + // TODO: we've already done this once, in + // verify_mac_and_decrypt_for_new_chain(). we could reuse the result. + create_chain_key( + root_key, sender_chain[0].ratchet_key, chain->ratchet_key, + kdf_info, root_key, chain->chain_key + ); + + olm::unset(sender_chain[0]); + sender_chain.erase(sender_chain.begin()); + } + + while (chain->chain_key.index < reader.counter) { + olm::SkippedMessageKey & key = *skipped_message_keys.insert(); + create_message_keys(chain->chain_key, kdf_info, key.message_key); + key.ratchet_key = chain->ratchet_key; + advance_chain_key(chain->chain_key, chain->chain_key); + } + + advance_chain_key(chain->chain_key, chain->chain_key); + + return result; +}