From 68d3c7bfa9d0d2f8a44edcd2d277c4a516ed6ed5 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Wed, 27 Apr 2016 17:16:55 +0100 Subject: Implementation of the megolm ratchet --- src/megolm.c | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 132 insertions(+) create mode 100644 src/megolm.c (limited to 'src/megolm.c') 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 + +#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; + } +} -- cgit v1.2.3 From caaed796ad54de3f8ee1e56123973ae9ace346b9 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 17 May 2016 11:52:06 +0100 Subject: Implementation of an outbound group session --- src/megolm.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 36b0cc2..58fe725 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -18,8 +18,22 @@ #include +#include "olm/cipher.h" #include "olm/crypto.h" +const struct _olm_cipher *megolm_cipher() { + static const uint8_t CIPHER_KDF_INFO[] = "MEGOLM_KEYS"; + static struct _olm_cipher *cipher; + static struct _olm_cipher_aes_sha_256 OLM_CIPHER; + if (!cipher) { + cipher = _olm_cipher_aes_sha_256_init( + &OLM_CIPHER, + CIPHER_KDF_INFO, sizeof(CIPHER_KDF_INFO) - 1 + ); + } + return cipher; +} + /* the seeds used in the HMAC-SHA-256 functions for each part of the ratchet. */ #define HASH_KEY_SEED_LENGTH 1 -- cgit v1.2.3 From c058554132a0f97e8e8ae3a402605220f8fdaed4 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 17 May 2016 18:53:00 +0100 Subject: Implement pickling/unpickling for outbound group sessions --- src/megolm.c | 25 +++++++++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 58fe725..7567894 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -20,6 +20,7 @@ #include "olm/cipher.h" #include "olm/crypto.h" +#include "olm/pickle.h" const struct _olm_cipher *megolm_cipher() { static const uint8_t CIPHER_KDF_INFO[] = "MEGOLM_KEYS"; @@ -59,12 +60,32 @@ static void rehash_part( -void megolm_init(Megolm *megolm, uint8_t const *random_data, uint32_t counter) -{ +void megolm_init(Megolm *megolm, uint8_t const *random_data, uint32_t counter) { megolm->counter = counter; memcpy(megolm->data, random_data, MEGOLM_RATCHET_LENGTH); } +size_t megolm_pickle_length(const Megolm *megolm) { + size_t length = 0; + length += _olm_pickle_bytes_length(megolm_get_data(megolm), MEGOLM_RATCHET_LENGTH); + length += _olm_pickle_uint32_length(megolm->counter); + return length; + +} + +uint8_t * megolm_pickle(const Megolm *megolm, uint8_t *pos) { + pos = _olm_pickle_bytes(pos, megolm_get_data(megolm), MEGOLM_RATCHET_LENGTH); + pos = _olm_pickle_uint32(pos, megolm->counter); + return pos; +} + +const uint8_t * megolm_unpickle(Megolm *megolm, const uint8_t *pos, + const uint8_t *end) { + pos = _olm_unpickle_bytes(pos, end, (uint8_t *)(megolm->data), + MEGOLM_RATCHET_LENGTH); + pos = _olm_unpickle_uint32(pos, end, &megolm->counter); + return pos; +} /* simplistic implementation for a single step */ void megolm_advance(Megolm *megolm) { -- cgit v1.2.3 From a919a149fbb192e3fae7aba921ca28e02d9c0d10 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 24 May 2016 14:54:01 +0100 Subject: Update megolm_cipher as a global struct Initialise megolm_cipher via the preprocessor macro, instead of with a function. --- src/megolm.c | 15 +++------------ 1 file changed, 3 insertions(+), 12 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 7567894..110f939 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -22,18 +22,9 @@ #include "olm/crypto.h" #include "olm/pickle.h" -const struct _olm_cipher *megolm_cipher() { - static const uint8_t CIPHER_KDF_INFO[] = "MEGOLM_KEYS"; - static struct _olm_cipher *cipher; - static struct _olm_cipher_aes_sha_256 OLM_CIPHER; - if (!cipher) { - cipher = _olm_cipher_aes_sha_256_init( - &OLM_CIPHER, - CIPHER_KDF_INFO, sizeof(CIPHER_KDF_INFO) - 1 - ); - } - return cipher; -} +static const struct _olm_cipher_aes_sha_256 MEGOLM_CIPHER = + OLM_CIPHER_INIT_AES_SHA_256("MEGOLM_KEYS"); +const struct _olm_cipher *megolm_cipher = OLM_CIPHER_BASE(&MEGOLM_CIPHER); /* the seeds used in the HMAC-SHA-256 functions for each part of the ratchet. */ -- cgit v1.2.3 From f3c0dd76d73368a872d7acb2ffa293330f875089 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 24 May 2016 17:03:42 +0100 Subject: megolm.c: Remove spurious arguments to rehash_part These were left over from when rehash_part did a bunch of logging. --- src/megolm.c | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 110f939..efefc11 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -38,8 +38,7 @@ static uint8_t HASH_KEY_SEEDS[MEGOLM_RATCHET_PARTS][HASH_KEY_SEED_LENGTH] = { 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 + int rehash_from_part, int rehash_to_part ) { _olm_crypto_hmac_sha256( data[rehash_from_part], @@ -96,7 +95,7 @@ void megolm_advance(Megolm *megolm) { /* 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); + rehash_part(megolm->data, h, i); } } @@ -122,7 +121,7 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { * to R(j+1)...R(3). */ while (steps > 1) { - rehash_part(megolm->data, j, j, megolm->counter, next_counter); + rehash_part(megolm->data, j, j); megolm->counter = next_counter; steps --; next_counter = megolm->counter + increment; @@ -150,7 +149,7 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { } while (k >= j) { - rehash_part(megolm->data, j, k, megolm->counter, next_counter); + rehash_part(megolm->data, j, k); k--; } megolm->counter = next_counter; -- cgit v1.2.3 From ef8d24f4839352963f8d0b53919016c35f492a22 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 24 May 2016 17:33:41 +0100 Subject: megolm.c: rewrite counter update We no longer need to keep track of intermediate values of the counter, which means we can update it much more easily. --- src/megolm.c | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index efefc11..9e28f8d 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -105,26 +105,21 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { /* 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; + uint32_t mask = (~(uint32_t)0) << shift; /* 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; steps --; - next_counter = megolm->counter + increment; } /* on the last step (except for j=3), we need to bump at least R(j+1); @@ -152,6 +147,6 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { rehash_part(megolm->data, j, k); k--; } - megolm->counter = next_counter; + megolm->counter = advance_to & mask; } } -- cgit v1.2.3 From 1f31427139acdef00f24aac13b67224fa915f9e7 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 24 May 2016 16:58:51 +0100 Subject: megolm_advance_to: Remove excessive optimisation There was some slightly overcomplex logic designed to save a couple of hash operations when R(0) and R(1) were advanced, but the extra code was hard to understand and didn't save much. --- src/megolm.c | 29 +++++++---------------------- 1 file changed, 7 insertions(+), 22 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 9e28f8d..6d8af08 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -106,6 +106,7 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { for (j = 0; j < (int)MEGOLM_RATCHET_PARTS; j++) { int shift = (MEGOLM_RATCHET_PARTS-j-1) * 8; uint32_t mask = (~(uint32_t)0) << shift; + int k; /* how many times to we need to rehash this part? */ int steps = (advance_to >> shift) - (megolm->counter >> shift); @@ -122,30 +123,14 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { steps --; } - /* 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). + /* on the last step we also need to bump R(j+1)...R(3). + * + * (Theoretically, we could skip bumping R(j+2) if we're going to bump + * R(j+1) again, but the code to figure that out is a bit baroque and + * doesn't save us much). */ - 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) { + for (k = 3; k >= j; k--) { rehash_part(megolm->data, j, k); - k--; } megolm->counter = advance_to & mask; } -- cgit v1.2.3 From 01ea3d4b9a3c6f3e0303c2d421a248715a96af99 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Tue, 24 May 2016 17:52:35 +0100 Subject: Fix handling of integer wraparound in megolm.c --- src/megolm.c | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index 6d8af08..a969b36 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -108,8 +108,12 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { uint32_t mask = (~(uint32_t)0) << shift; int k; - /* how many times to we need to rehash this part? */ - int steps = (advance_to >> shift) - (megolm->counter >> shift); + /* how many times do we need to rehash this part? + * + * '& 0xff' ensures we handle integer wraparound correctly + */ + unsigned int steps = + ((advance_to >> shift) - (megolm->counter >> shift)) & 0xff; if (steps == 0) { continue; -- cgit v1.2.3 From 19a7fb5df5ec3445201ce5fbe475a08faf6319fc Mon Sep 17 00:00:00 2001 From: Mark Haines Date: Wed, 25 May 2016 15:00:05 +0100 Subject: Fix an integer wrap around bug and add a couple more tests --- src/megolm.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index a969b36..affd3cb 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -116,7 +116,11 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { ((advance_to >> shift) - (megolm->counter >> shift)) & 0xff; if (steps == 0) { - continue; + if (advance_to < megolm->counter) { + steps = 0x100; + } else { + continue; + } } /* for all but the last step, we can just bump R(j) without regard -- cgit v1.2.3 From fae8dacab5233c46f09e7d869afadaead2842609 Mon Sep 17 00:00:00 2001 From: Richard van der Hoff Date: Wed, 25 May 2016 15:44:39 +0100 Subject: Add a comment explaining Mark's latest fix --- src/megolm.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/megolm.c') diff --git a/src/megolm.c b/src/megolm.c index affd3cb..3395449 100644 --- a/src/megolm.c +++ b/src/megolm.c @@ -116,6 +116,11 @@ void megolm_advance_to(Megolm *megolm, uint32_t advance_to) { ((advance_to >> shift) - (megolm->counter >> shift)) & 0xff; if (steps == 0) { + /* deal with the edge case where megolm->counter is slightly larger + * than advance_to. This should only happen for R(0), and implies + * that advance_to has wrapped around and we need to advance R(0) + * 256 times. + */ if (advance_to < megolm->counter) { steps = 0x100; } else { -- cgit v1.2.3