[bug] Treemath isn't sound

[OtaK]

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

[tomleavy]

Thanks for submitting! We will take a look

[mulmarta]

Thanks @OtaK for finding the bug!

Maybe a better solution than making all operations checked would be to set a reasonable upper bound on the leaf / node indices, for example 2^28? I don't think MLS can actually deal with groups that large. For example just 2^31 X25519 public keys is almost 70GB of data. mls-rs would load this to RAM which wouldn't work (unless you have a cluster). I guess groups that huge would require a specialized implementation.

[OtaK]

Hi @mulmarta!

Sorry for the late reply.
Honestly I think the upper bound would be fine but philosophically it sounds more like a bandaid fix than anything else, and might introduce other footguns (i.e. things like pub(crate) that might allow the crate to violate its own invariants) that can bite later on, when everyone forgot about this, in say, 4-5 years.

Fixing the treemath to be checked/saturating would probably do the right thing. I don't remember if the epoch math is sound, but from experience, something as simple as reaching epoch == u64::MAX - 1 is usually an issue in many implementations, and the recommended thing in this case (again, from experience) is forcing clients to ReInit as the very last commit before reaching that point in order to avoid hardlocking groups.

I really think fixing all the math once and for all is the right approach so that all of these can be left behind 🎉