[bug] Treemath isn't sound

Hi folks,

I was playing around a bit with fuzzing and I found some cases where the unchecked treemath present pretty much everywhere might cause some sneaky bugs, particularily in the Group::process_incoming_message() entrypoint;

For example, the following backtrace is caused by this very line:

thread '<unnamed>' panicked at $HOME/dev/mls-rs/src/tree_kem/node.rs:54:38:
attempt to multiply with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/std/src/panicking.rs:658:5
   1: core::panicking::panic_fmt
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/core/src/panicking.rs:74:14
   2: core::panicking::panic_const::panic_const_mul_overflow
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/core/src/panicking.rs:181:21
   3: mls_rs::tree_kem::node::<impl core::convert::From<mls_rs::tree_kem::node::LeafIndex> for u32>::from
             at ./src/tree_kem/node.rs:54:38
   4: mls_rs::tree_kem::node::NodeVec::borrow_as_leaf
             at ./src/tree_kem/node.rs:303:26
   5: mls_rs::group::util::validate_group_info_common
             at ./src/group/util.rs:46:24
   6: mls_rs::group::util::validate_group_info_member
             at ./src/group/util.rs:62:5
   7: mls_rs::group::message_processor::MessageProcessor::get_event_from_incoming_message
             at ./src/group/message_processor.rs:489:17
   8: mls_rs::group::message_processor::MessageProcessor::process_incoming_message_with_time
             at ./src/group/message_processor.rs:465:32
   9: mls_rs::group::message_processor::MessageProcessor::process_incoming_message
             at ./src/group/message_processor.rs:450:9
  10: mls_rs::group::Group<C>::process_incoming_message
             at ./src/group/mod.rs:1302:9
  11: process_bytes::process_bytes::_::__libfuzzer_sys_run
             at ./fuzz/fuzz_targets/process_bytes.rs:15:13
  12: rust_fuzzer_test_input
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/src/lib.rs:224:17
  13: libfuzzer_sys::test_input_wrap::{{closure}}
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/src/lib.rs:61:9
  14: std::panicking::try::do_call
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/std/src/panicking.rs:553:40
  15: ___rust_try
  16: std::panicking::try
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/std/src/panicking.rs:517:19
  17: std::panic::catch_unwind
             at /rustc/d7f6ebacee13b6c03623c4b74197280454ede8de/library/std/src/panic.rs:350:14
  18: LLVMFuzzerTestOneInput
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/src/lib.rs:59:22
  19: _ZN6fuzzer6Fuzzer15ExecuteCallbackEPKhm
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/libfuzzer/FuzzerLoop.cpp:612:13
  20: _ZN6fuzzer10RunOneTestEPNS_6FuzzerEPKcm
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/libfuzzer/FuzzerDriver.cpp:324:6
  21: _ZN6fuzzer12FuzzerDriverEPiPPPcPFiPKhmE
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/libfuzzer/FuzzerDriver.cpp:860:9
  22: main
             at $HOME/.cargo/registry/src/index.crates.io-6f17d22bba15001f/libfuzzer-sys-0.4.7/libfuzzer/FuzzerMain.cpp:20:10

Obviously, the crashes do not happen when ran with --release but instead the overflowing multiplication would wrap, which would cause wrong indexes being calculated (i.e. a LeafIndex = (u32::MAX / 2 + 1) * 2 would give a NodeIndex = 1) and cause things like signature verification errors, weird behaviors, and basically indexing bugs everywhere.

After looking a bit everywhere where there is treemath involved, it seems there's a lot of unchecked math being used, especially where appropriate - index calculations through additions/multiplications/subtractions/left shifts - and should be using [checked|saturating]_[op].

I could make a (big) PR fixing all of those if you'd like, but that would cause quite some internal API breakage (checked_mul returns an Option<T> for example).

I added some fuzz inputs that cause those issues in the processbytes_test.zip file. You can run them using cargo fuzz run process_bytes crash-[hash].

Feel free to ask for more details; Keep in mind that this isn't a security issue but rather a functional bug - this doesn't compromise the security properties of MLS but rather mls-rs's functionality on large groups.

processbytes_test.zip

awslabs / mls-rs

[bug] Treemath isn't sound #173