aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/olm/megolm.h72
-rw-r--r--src/megolm.c132
-rw-r--r--tests/test_megolm.cpp85
3 files changed, 289 insertions, 0 deletions
diff --git a/include/olm/megolm.h b/include/olm/megolm.h
new file mode 100644
index 0000000..784597e
--- /dev/null
+++ b/include/olm/megolm.h
@@ -0,0 +1,72 @@
+/* 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.
+ */
+
+#ifndef OLM_MEGOLM_H_
+#define OLM_MEGOLM_H_
+
+/**
+ * implementation of the Megolm multi-part ratchet used in group chats.
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * number of bytes in each part of the ratchet; this should be the same as
+ * the length of the hash function used in the HMAC (32 bytes for us, as we
+ * use HMAC-SHA-256)
+ */
+#define MEGOLM_RATCHET_PART_LENGTH 32 /* SHA256_OUTPUT_LENGTH */
+
+/**
+ * number of parts in the ratchet; the advance() implementations rely on
+ * this being 4.
+ */
+#define MEGOLM_RATCHET_PARTS 4
+
+#define MEGOLM_RATCHET_LENGTH (MEGOLM_RATCHET_PARTS * MEGOLM_RATCHET_PART_LENGTH)
+
+typedef struct Megolm {
+ uint8_t data[MEGOLM_RATCHET_PARTS][MEGOLM_RATCHET_PART_LENGTH];
+ uint32_t counter;
+} Megolm;
+
+/**
+ * initialize the megolm ratchet. random_data should be at least
+ * MEGOLM_RATCHET_LENGTH bytes of randomness.
+ */
+void megolm_init(Megolm *megolm, uint8_t const *random_data, uint32_t counter);
+
+/** advance the ratchet by one step */
+void megolm_advance(Megolm *megolm);
+
+/**
+ * get the key data in the ratchet. The returned data is
+ * MEGOLM_RATCHET_LENGTH bytes long.
+ */
+#define megolm_get_data(megolm) ((const uint8_t *)((megolm)->data))
+
+/** advance the ratchet to a given count */
+void megolm_advance_to(Megolm *megolm, uint32_t advance_to);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif /* OLM_MEGOLM_H_ */
diff --git a/src/megolm.c b/src/megolm.c
new file mode 100644
index 0000000..36b0cc2
--- /dev/null
+++ b/src/megolm.c
@@ -0,0 +1,132 @@
+/* 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.
+ */
+
+
+#include "olm/megolm.h"
+
+#include <string.h>
+
+#include "olm/crypto.h"
+
+/* the seeds used in the HMAC-SHA-256 functions for each part of the ratchet.
+ */
+#define HASH_KEY_SEED_LENGTH 1
+static uint8_t HASH_KEY_SEEDS[MEGOLM_RATCHET_PARTS][HASH_KEY_SEED_LENGTH] = {
+ {0x00},
+ {0x01},
+ {0x02},
+ {0x03}
+};
+
+static void rehash_part(
+ uint8_t data[MEGOLM_RATCHET_PARTS][MEGOLM_RATCHET_PART_LENGTH],
+ int rehash_from_part, int rehash_to_part,
+ uint32_t old_counter, uint32_t new_counter
+) {
+ _olm_crypto_hmac_sha256(
+ data[rehash_from_part],
+ MEGOLM_RATCHET_PART_LENGTH,
+ HASH_KEY_SEEDS[rehash_to_part], HASH_KEY_SEED_LENGTH,
+ data[rehash_to_part]
+ );
+}
+
+
+
+void megolm_init(Megolm *megolm, uint8_t const *random_data, uint32_t counter)
+{
+ megolm->counter = counter;
+ memcpy(megolm->data, random_data, MEGOLM_RATCHET_LENGTH);
+}
+
+
+/* simplistic implementation for a single step */
+void megolm_advance(Megolm *megolm) {
+ uint32_t mask = 0x00FFFFFF;
+ int h = 0;
+ int i;
+
+ megolm->counter++;
+
+ /* figure out how much we need to rekey */
+ while (h < (int)MEGOLM_RATCHET_PARTS) {
+ if (!(megolm->counter & mask))
+ break;
+ h++;
+ mask >>= 8;
+ }
+
+ /* now update R(h)...R(3) based on R(h) */
+ for (i = MEGOLM_RATCHET_PARTS-1; i >= h; i--) {
+ rehash_part(megolm->data, h, i, megolm->counter-1, megolm->counter);
+ }
+}
+
+void megolm_advance_to(Megolm *megolm, uint32_t advance_to) {
+ int j;
+
+ /* starting with R0, see if we need to update each part of the hash */
+ for (j = 0; j < (int)MEGOLM_RATCHET_PARTS; j++) {
+ int shift = (MEGOLM_RATCHET_PARTS-j-1) * 8;
+ uint32_t increment = 1 << shift;
+ uint32_t next_counter;
+
+ /* how many times to we need to rehash this part? */
+ int steps = (advance_to >> shift) - (megolm->counter >> shift);
+ if (steps == 0) {
+ continue;
+ }
+
+ megolm->counter = megolm->counter & ~(increment - 1);
+ next_counter = megolm->counter + increment;
+
+ /* for all but the last step, we can just bump R(j) without regard
+ * to R(j+1)...R(3).
+ */
+ while (steps > 1) {
+ rehash_part(megolm->data, j, j, megolm->counter, next_counter);
+ megolm->counter = next_counter;
+ steps --;
+ next_counter = megolm->counter + increment;
+ }
+
+ /* on the last step (except for j=3), we need to bump at least R(j+1);
+ * depending on the target count, we may also need to bump R(j+2) and
+ * R(j+3).
+ */
+ int k;
+ switch(j) {
+ case 0:
+ if (!(advance_to & 0xFFFF00)) { k = 3; }
+ else if (!(advance_to & 0xFF00)) { k = 2; }
+ else { k = 1; }
+ break;
+ case 1:
+ if (!(advance_to & 0xFF00)) { k = 3; }
+ else { k = 2; }
+ break;
+ case 2:
+ case 3:
+ k = 3;
+ break;
+ }
+
+ while (k >= j) {
+ rehash_part(megolm->data, j, k, megolm->counter, next_counter);
+ k--;
+ }
+ megolm->counter = next_counter;
+ }
+}
diff --git a/tests/test_megolm.cpp b/tests/test_megolm.cpp
new file mode 100644
index 0000000..871de36
--- /dev/null
+++ b/tests/test_megolm.cpp
@@ -0,0 +1,85 @@
+/* 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.
+ */
+#include "olm/megolm.h"
+#include "olm/memory.hh"
+
+#include "unittest.hh"
+
+
+int main() {
+
+std::uint8_t random_bytes[] =
+ "0123456789ABCDEF0123456789ABCDEF"
+ "0123456789ABCDEF0123456789ABCDEF"
+ "0123456789ABCDEF0123456789ABCDEF"
+ "0123456789ABCDEF0123456789ABCDEF";
+
+{
+ TestCase test_case("Megolm::advance");
+
+ Megolm mr;
+
+ megolm_init(&mr, random_bytes, 0);
+ // single-step advance
+ megolm_advance(&mr);
+ const std::uint8_t expected1[] = {
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,
+ 0xba, 0x9c, 0xd9, 0x55, 0x74, 0x1d, 0x1c, 0x16, 0x23, 0x23, 0xec, 0x82, 0x5e, 0x7c, 0x5c, 0xe8,
+ 0x89, 0xbb, 0xb4, 0x23, 0xa1, 0x8f, 0x23, 0x82, 0x8f, 0xb2, 0x09, 0x0d, 0x6e, 0x2a, 0xf8, 0x6a
+ };
+ assert_equals(1U, mr.counter);
+ assert_equals(expected1, megolm_get_data(&mr), MEGOLM_RATCHET_LENGTH);
+
+ // repeat with complex advance
+ megolm_init(&mr, random_bytes, 0);
+ megolm_advance_to(&mr, 1);
+ assert_equals(1U, mr.counter);
+ assert_equals(expected1, megolm_get_data(&mr), MEGOLM_RATCHET_LENGTH);
+
+ megolm_advance_to(&mr, 0x1000000);
+ const std::uint8_t expected2[] = {
+ 0x54, 0x02, 0x2d, 0x7d, 0xc0, 0x29, 0x8e, 0x16, 0x37, 0xe2, 0x1c, 0x97, 0x15, 0x30, 0x92, 0xf9,
+ 0x33, 0xc0, 0x56, 0xff, 0x74, 0xfe, 0x1b, 0x92, 0x2d, 0x97, 0x1f, 0x24, 0x82, 0xc2, 0x85, 0x9c,
+ 0x70, 0x04, 0xc0, 0x1e, 0xe4, 0x9b, 0xd6, 0xef, 0xe0, 0x07, 0x35, 0x25, 0xaf, 0x9b, 0x16, 0x32,
+ 0xc5, 0xbe, 0x72, 0x6d, 0x12, 0x34, 0x9c, 0xc5, 0xbd, 0x47, 0x2b, 0xdc, 0x2d, 0xf6, 0x54, 0x0f,
+ 0x31, 0x12, 0x59, 0x11, 0x94, 0xfd, 0xa6, 0x17, 0xe5, 0x68, 0xc6, 0x83, 0x10, 0x1e, 0xae, 0xcd,
+ 0x7e, 0xdd, 0xd6, 0xde, 0x1f, 0xbc, 0x07, 0x67, 0xae, 0x34, 0xda, 0x1a, 0x09, 0xa5, 0x4e, 0xab,
+ 0xba, 0x9c, 0xd9, 0x55, 0x74, 0x1d, 0x1c, 0x16, 0x23, 0x23, 0xec, 0x82, 0x5e, 0x7c, 0x5c, 0xe8,
+ 0x89, 0xbb, 0xb4, 0x23, 0xa1, 0x8f, 0x23, 0x82, 0x8f, 0xb2, 0x09, 0x0d, 0x6e, 0x2a, 0xf8, 0x6a,
+ };
+ assert_equals(0x1000000U, mr.counter);
+ assert_equals(expected2, megolm_get_data(&mr), MEGOLM_RATCHET_LENGTH);
+
+ megolm_advance_to(&mr, 0x1041506);
+ const std::uint8_t expected3[] = {
+ 0x54, 0x02, 0x2d, 0x7d, 0xc0, 0x29, 0x8e, 0x16, 0x37, 0xe2, 0x1c, 0x97, 0x15, 0x30, 0x92, 0xf9,
+ 0x33, 0xc0, 0x56, 0xff, 0x74, 0xfe, 0x1b, 0x92, 0x2d, 0x97, 0x1f, 0x24, 0x82, 0xc2, 0x85, 0x9c,
+ 0x55, 0x58, 0x8d, 0xf5, 0xb7, 0xa4, 0x88, 0x78, 0x42, 0x89, 0x27, 0x86, 0x81, 0x64, 0x58, 0x9f,
+ 0x36, 0x63, 0x44, 0x7b, 0x51, 0xed, 0xc3, 0x59, 0x5b, 0x03, 0x6c, 0xa6, 0x04, 0xc4, 0x6d, 0xcd,
+ 0x5c, 0x54, 0x85, 0x0b, 0xfa, 0x98, 0xa1, 0xfd, 0x79, 0xa9, 0xdf, 0x1c, 0xbe, 0x8f, 0xc5, 0x68,
+ 0x19, 0x37, 0xd3, 0x0c, 0x85, 0xc8, 0xc3, 0x1f, 0x7b, 0xb8, 0x28, 0x81, 0x6c, 0xf9, 0xff, 0x3b,
+ 0x95, 0x6c, 0xbf, 0x80, 0x7e, 0x65, 0x12, 0x6a, 0x49, 0x55, 0x8d, 0x45, 0xc8, 0x4a, 0x2e, 0x4c,
+ 0xd5, 0x6f, 0x03, 0xe2, 0x44, 0x16, 0xb9, 0x8e, 0x1c, 0xfd, 0x97, 0xc2, 0x06, 0xaa, 0x90, 0x7a
+ };
+ assert_equals(0x1041506U, mr.counter);
+ assert_equals(expected3, megolm_get_data(&mr), MEGOLM_RATCHET_LENGTH);
+}
+
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 18:39:00 +0000