search

signalapp / libsignal

Home to the Signal Protocol as well as other cryptographic primitives which make Signal possible.
GNU Affero General Public License v3.0
3.63k stars 420 forks source link

[Rust][Fuzzing] ERROR libsignal_protocol::session_cipher No valid session for recipient #514

Open expiringplatform opened 1 year ago

expiringplatform commented 1 year ago

Hello,

I run the fuzz target 'interaction' for some time and it found the following error. Unfortunately I'm not skilled enough to investigate what is the cause, but you can find the crashing input and the output attached. I used the libsignal version 0.22.2.

Crashing input: crash-4499e6206c8ecced15c06fa9496883de298fb0f9.zip

~/libsignal/rust/protocol/fuzz$ cargo fuzz run interaction artifacts/interaction/crash-4499e6206c8ecced15c06fa9496883de298fb0f9 Finished release [optimized] target(s) in 0.07s Finished release [optimized] target(s) in 0.07s Running target/x86_64-unknown-linux-gnu/release/interaction -artifact_prefix=/home/fuzzing/libsignal/rust/protocol/fuzz/artifacts/interaction/ artifacts/interaction/crash-4499e6206c8ecced15c06fa9496883de298fb0f9 INFO: Running with entropic power schedule (0xFF, 100). INFO: Seed: 3921737387 INFO: Loaded 1 modules (293861 inline 8-bit counters): 293861 [0x55bb3d6449d0, 0x55bb3d68c5b5), INFO: Loaded 1 PC tables (293861 PCs): 293861 [0x55bb3d68c5b8,0x55bb3db08408), target/x86_64-unknown-linux-gnu/release/interaction: Running 1 inputs 1 time(s) each. Running: artifacts/interaction/crash-4499e6206c8ecced15c06fa9496883de298fb0f9 [2023-02-23T20:33:44Z ERROR libsignal_protocol::session_cipher] No valid session for recipient: +14151111111.1, current session base key 96cdd8a820f18f14e007d2f676843d0ebdfe4eaf72ffa029238b185d46a90f73, number of previous states: 40 [2023-02-23T20:33:44Z ERROR libsignal_protocol::session_cipher] Message from +14151111111.1 failed to decrypt; sender ratchet public key fca1ecd7876fc4c55ab6a15fe0750e0d36b8bc94a9a84b00c4e7bbe2215a2070 message counter 0 Candidate session 0 failed with 'invalid Whisper message: MAC verification failed', had 2 receiver chains Receiver chain with sender ratchet public key 053aac3dcdbd55c74fac8f5c1768bfadd0a7e3c25d24e9f685cc912081f4aeb843 chain key index 0 Receiver chain with sender ratchet public key 057795f70bc2a6158303d24d7053713722f8bd9f99a24d99066729524fd9951318 chain key index 7 Candidate session 1 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05ef7e4ad9511674b08cd6a4ff76e64164b2a7fdac6feb1d6eb2f47d13d6d8e71a chain key index 13 Candidate session 2 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05e9e55c4265b68c3e908d901d3f430c417437ae7dbd743337c0bb8cc5e7c7712a chain key index 2 Candidate session 3 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05af5a9ff8a17c2272b4102d9a25d194d5999eb41be3fa53e41d1278c697d27d55 chain key index 2 Candidate session 4 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05f319d3184eb8c6e54f00f91c14672897801e21af61426d212024c628d0da9b50 chain key index 10 Candidate session 5 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05852d6ae6d63fd2c05aba72e1ed6625a8532becaceb602792601d4d77b2bff403 chain key index 7 Candidate session 6 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0568037e82e85fb242c0d6095c7d2e4599d97e6ce6b1821ac1c91bbae61e001217 chain key index 11 Candidate session 7 failed with 'invalid Whisper message: MAC verification failed', had 2 receiver chains Receiver chain with sender ratchet public key 05a494d62c68a4e63ce5efa96bad74b9017eea4be54bd96025e654df75e8e16416 chain key index 0 Receiver chain with sender ratchet public key 05c0c71ce56914ba8b9ee2d425c882f82f9d16b43f28b4d13dcdbeba8dd6f4c47a chain key index 1 Candidate session 8 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05e13ccacd57cfcb854f896f7de7e18e0a1a79060d5dd66c5fd621f665ea94c30c chain key index 2 Candidate session 9 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0562c4724d7658dc5a47da6103c2eb6a158fe0c53a6327dd9483b200cfa188780b chain key index 2 Candidate session 10 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05cdc1567bc630a2a700b579fc94bf0e1f48cc1b377c75b674f1daa80fab190256 chain key index 7 Candidate session 11 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05c99ae1a659d7da9a163fa711c000b03998a5280f48c5214f3dd946923ebf4462 chain key index 2 Candidate session 12 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0529fcfec3fa17aa39ddf8e65a0ceff5c63a660c3369cc304d2ab9cc7ffa29537d chain key index 7 Candidate session 13 failed with 'invalid Whisper message: MAC verification failed', had 2 receiver chains Receiver chain with sender ratchet public key 05205a13f827bb9f71fe5bdccc535a3bb3e61475516bbd9867baa780c11f5f223c chain key index 0 Receiver chain with sender ratchet public key 05f1dd5f8a2549409857a833800470edac8841ab0207668d87066379f772d8432f chain key index 1 Candidate session 14 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05403b3c29d33155aa4fe537a12b243c23e24f60b64d3b5e6848a1c9e5faa6df06 chain key index 1 Candidate session 15 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 050ffce19620ab85ba7cf662738788132b0b85c220401290c846d0e309dca69b30 chain key index 0 Candidate session 16 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05afdf8c9a1ba542226686194cc8ae0752f1d6958a8b2c6649d8f180a5b528e253 chain key index 0 Candidate session 17 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 052fc3a692d0d41502de7ae69c1b63b6476738d7d3078848a331249cdc0b81750d chain key index 0 Candidate session 18 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05c9e6a08650a1013efbbe256ead035fa67a232c114af4e8a709a4aeb4a32cd132 chain key index 0 Candidate session 19 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0568d87a792a5c4f2391b81d153fd5879ebee4cf4822b07fc2acfdaaedeea2c033 chain key index 0 Candidate session 20 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05dfc8f3914b6479bf3c2e3db60bebb454d50e2baf6fba866156776f96922f8656 chain key index 0 Candidate session 21 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 051ccca952cd5a8a03a6320f1f3eb71e5fb4213fe76e3bb6ffc5182ebba5aabd38 chain key index 0 Candidate session 22 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0504c12a5c397933490d680ecd7997125f12f616691faba806d53fbb1739fb5b2d chain key index 0 Candidate session 23 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05e3cff6eea82306a328ddf2868c1e631a6c7a53d7ef2471bdb44f3ad6b4025d15 chain key index 0 Candidate session 24 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0580344df55e701e28d7b76924e3cffc9ace47328985447a8ebc7bd653db825b04 chain key index 0 Candidate session 25 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0526b8e5c27627229a7f316838d51d9396a5eb06facf6e7450e5ecd9b358826b73 chain key index 0 Candidate session 26 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 059b4e2162f10c484e13101139bff44f610307755bbd8be8f8c43220fde3a97c63 chain key index 0 Candidate session 27 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05fed5ff43d9bdb1931f56ef14809514dd3ee3cdb11b6082b88914cea045f9784d chain key index 0 Candidate session 28 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05d49625561786141ac62cfb74d9ce6703993e967e981c07693ac9b32edbf73d28 chain key index 0 Candidate session 29 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 053488893aa697abb5b1b5731ae733a4693a6920cef913ec861c9f423a2ff53a0f chain key index 0 Candidate session 30 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 058455e1cd3df2a3a854d82612efd4b27249a27c4a6476a844a07a591e155f7531 chain key index 0 Candidate session 31 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 057138cb8e8118f6b92a9117b83aa2540e6fa612c3034275c6e8efc23414b36d34 chain key index 0 Candidate session 32 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05928b4da6d76bf3be7102a6199c2eb5aad92558e469ec86c9506b0ba33b6a1b17 chain key index 0 Candidate session 33 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 051a130b5adb2b447c17ef40e003d3c583444d7dd45320ce54b2c54a403ddd8064 chain key index 0 Candidate session 34 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05076c481a9054a6ccd8cf51a720136a4923a35a14e4376e5fb75e6131c40b4202 chain key index 0 Candidate session 35 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 058d75a1f55b33c699b7d25e5b42c2c13e8bc489ffa5176e37826eb3ebe364df05 chain key index 0 Candidate session 36 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05037b41d6b9978b5d8fd6980a6ffc9c82dbc5c5fdf38a684cd234cca2724d7105 chain key index 0 Candidate session 37 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05b90197fae80d77e8b365f4895e9e3e701944c059ec045257d852f865cd758230 chain key index 0 Candidate session 38 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 0585eabca8eff186d6060da9b0586713e4331455ea7f7ba0c523d57ffd67a0e531 chain key index 0 Candidate session 39 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 05e551451a76e0a1ad706bcf35a9c6ffa0c58184c55b26cf23db50bc2ca7647332 chain key index 0 Candidate session 40 failed with 'invalid Whisper message: MAC verification failed', had 1 receiver chains Receiver chain with sender ratchet public key 053dff17e6d6e40a16f2bfff6e82cce4ba71fc0666496b72262343cbface81ee5b chain key index 0 thread '' panicked at 'called Result::unwrap() on an Err value: InvalidMessage(Whisper, "decryption failed")', fuzz_targets/interaction.rs:163:14 note: run with RUST_BACKTRACE=1 environment variable to display a backtrace ==2607429== ERROR: libFuzzer: deadly signal

0 0x55bb3c2d6a71 (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x89da71) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)

#1 0x55bb3d1724b0  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17394b0) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#2 0x55bb3d157f95  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x171ef95) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#3 0x7efd7035113f  (/lib/x86_64-linux-gnu/libpthread.so.0+0x1313f) (BuildId: 255e355c207aba91a59ae1f808e3b4da443abf0c)
#4 0x7efd70055ce0  (/lib/x86_64-linux-gnu/libc.so.6+0x38ce0) (BuildId: b503275bf9fee51581fdceef97533b194035b4f7)
#5 0x7efd7003f536  (/lib/x86_64-linux-gnu/libc.so.6+0x22536) (BuildId: b503275bf9fee51581fdceef97533b194035b4f7)
#6 0x55bb3d1fc346  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17c3346) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#7 0x55bb3c2455d6  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x80c5d6) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#8 0x55bb3d12b673  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16f2673) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#9 0x55bb3d1f143c  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17b843c) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#10 0x55bb3d1f11b6  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17b81b6) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#11 0x55bb3d1ee57b  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17b557b) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#12 0x55bb3d1f0ed1  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x17b7ed1) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#13 0x55bb3c248d52  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x80fd52) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#14 0x55bb3c249012  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x810012) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#15 0x55bb3c3afe65  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x976e65) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#16 0x55bb3c3b5e5b  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x97ce5b) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#17 0x55bb3c30e6ce  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x8d56ce) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#18 0x55bb3c3b3507  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x97a507) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#19 0x55bb3c3b2414  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x979414) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#20 0x55bb3d126b1f  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16edb1f) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#21 0x55bb3d12b8a7  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16f28a7) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#22 0x55bb3d12ac95  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16f1c95) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#23 0x55bb3d1584d4  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x171f4d4) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#24 0x55bb3d130aa3  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16f7aa3) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#25 0x55bb3d138916  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x16ff916) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#26 0x55bb3c249272  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x810272) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)
#27 0x7efd70040d09  (/lib/x86_64-linux-gnu/libc.so.6+0x23d09) (BuildId: b503275bf9fee51581fdceef97533b194035b4f7)
#28 0x55bb3c249419  (/home/fuzzing/libsignal/rust/protocol/fuzz/target/x86_64-unknown-linux-gnu/release/interaction+0x810419) (BuildId: 9fa172dc5a3a11acf03f0f30a488c7986c965f85)

NOTE: libFuzzer has rudimentary signal handlers. Combine libFuzzer with AddressSanitizer or similar for better crash reports. SUMMARY: libFuzzer: deadly signal ────────────────────────────────────────────────────────────────────────────────

Error: Fuzz target exited with exit status: 77

jrose-signal commented 1 year ago

Thanks for reporting this! The interaction fuzz target is a bit weak, and you've found one of its weaknesses: it doesn't handle excessive session archiving very well. This is an expected limitation: if Alice tries to send Bob a message on a very, very old session, Bob isn't expected to be able to respond.

You can see there's a line that attempts to guard against this:

                0 => {
                    if me.archive_count < 40 {
                        // Only archive if it can't result in old sessions getting expired.
                        // We're not testing that.
                        me.archive_session(&them.address).await
                    }
                }

But it's not a very good check, because you've found a case that gets past this guard. Looking at the output from running under RUST_LOG=interaction=info, it becomes clear that the "problem" is something like this:

  1. A bunch of stuff happens between Alice and Bob.
  2. Alice sends a message A1 to Bob on an existing session S (but Bob doesn't receive it yet).
  3. Alice archives-and-resets her session with Bob.
  4. Alice sends a message A2 to Bob on the new session.
  5. Bob archives-and-resets sessions 39 times. S is now the oldest session.
  6. Bob processes A2, which sets up a new session and pushes S out of the storage.
  7. Bob processes A1.

The 40-reset limit hasn't been reached on either side, but only because processing the first message on a new session also behaves as a reset.

Changing the condition to me.archive_count + them.archive_count < 40 makes this test case pass, but I'd like to think a little more about whether that's the correct condition before making any changes.

Thank you again for reporting this; that's exactly what we want if someone finds an interesting result from one of our fuzzers! And we can both be glad it's not an actual problem.

jrose-signal commented 1 year ago

P.S. The "interaction" fuzzer is designed to find cases where some exchange of messages results in Bob not being able to receive messages from Alice; in that sense it did its job. :-) But it's never a security issue as long as the "failure" panic comes from the test harness rather than somewhere within libsignal-protocol.

expiringplatform commented 1 year ago

Hello, thanks for the fast answer and the detailed explaination! Nice to hear, that it's not an actual bug in libsignal :) . A little off topic, but if I might ask: do you have a way to view/monitor the coverage of the rust fuzz targets? I mean not only the coverage number that is reported, but rather which lines of code are covered. I tried to follow some online manuals but couldn't get it working. One more thing: Do you have some kind of automation that runs all the fuzz tests regularly or maybe even on every code change? AFAIK this can be useful to detect regressions. I think you might be qualified for the google OSS-Fuzz, where google would run your fuzz targets in their cloud for free. Is this something you would be interested in?

expiringplatform commented 1 year ago

Changing the condition to me.archive_count + them.archive_count < 40 makes this test case pass, but I'd like to think a little more about whether that's the correct condition before making any changes.

I tried changing the condition and can confirm that it fixes the test case. But after running the (modified) fuzz target for a few more hours it found another test case that triggers a crash that looks quite similar to the one above.

Fixing this edge cases of the fuzz target is probably not the top priority on your todo list, which I fully understand and agree with since it is not critical for the functionality or security of libsignal. Just thought it might safe you some work :-) Here the new crashing input:

crash-65c7888c15186076f0f6c963910da1faa5a87975.zip

moodyjon commented 1 year ago

Hi all, I have been doing some investigation on this.

The 40-reset limit hasn't been reached on either side, but only because processing the first message on a new session also behaves as a reset.

I tried to detect when decrypt_message() grows previous_sessions, and accounting for that in archive_count. I think it did fix one or more failures for me.

However, I happened across a very short crashing input:

crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be.zip

It seems to crash also on the original code with my code changes removed.

swdev2@Jonathans-Mini fuzz % env RUST_LOG=interaction=info,libsignal_protocol=info RUST_BACKTRACE=full cargo fuzz run interaction artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be
   Compiling libsignal-protocol-fuzz v0.0.0 (/Users/swdev2/libsignal/rust/protocol/fuzz)
    Finished release [optimized] target(s) in 4.78s
    Finished release [optimized] target(s) in 0.05s
     Running `target/aarch64-apple-darwin/release/interaction -artifact_prefix=/Users/swdev2/libsignal/rust/protocol/fuzz/artifacts/interaction/ artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be`
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 894999463
INFO: Loaded 1 modules   (297289 inline 8-bit counters): 297289 [0x105bce5c0, 0x105c16f09), 
INFO: Loaded 1 PC tables (297289 PCs): 297289 [0x105c16f10,0x1060a03a0), 
target/aarch64-apple-darwin/release/interaction: Running 1 inputs 1 time(s) each.
Running: artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be
[2023-05-05T20:33:57Z INFO  interaction] bob: sending message
[2023-05-05T20:33:57Z INFO  interaction] bob:   processing a new pre-key bundle
[2023-05-05T20:33:57Z INFO  libsignal_protocol::session] set_unacknowledged_pre_key_message for: +14151111111.1 with preKeyId: 0
[2023-05-05T20:33:57Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:57Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:57Z INFO  interaction] bob: sending message
[2023-05-05T20:33:57Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:57Z INFO  interaction] bob: receiving messages
[2023-05-05T20:33:57Z INFO  interaction] alice: receiving messages
[2023-05-05T20:33:57Z WARN  libsignal_protocol::session] processing PreKey message from +14151111112.1 which had no one-time prekey
[2023-05-05T20:33:57Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:57Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:57Z INFO  libsignal_protocol::session_cipher] +14151111112.1 creating new chains.
[2023-05-05T20:33:57Z WARN  libsignal_protocol::protocol] Bad Mac! Their Mac: c46cc6a518b44dd1 Our Mac: 67af598631c81839
[2023-05-05T20:33:57Z WARN  libsignal_protocol::session_cipher] Failed to decrypt PreKey message with ratchet key: 96ae90189891d8cc0236da4ca37b2d9eb5437e19b1f41b4b308284e899b1e10b and counter: 0. Session loaded for +14151111112.1. Local session has base key: 8d6915867a34eb5135b17e449d6faab3121ae33585ee660b5557cd66aeb6791d and counter: 0. invalid PreKey message: MAC verification failed
[2023-05-05T20:33:57Z ERROR libsignal_protocol::session_cipher] No valid session for recipient: +14151111112.1, current session base key ec993eb50b580a0ff9995ea82f8be675e73151d8b091fbb211e97c5ae281ef1d, number of previous states: 0
[2023-05-05T20:33:57Z ERROR libsignal_protocol::session_cipher] Message from +14151111112.1 failed to decrypt; sender ratchet public key 96ae90189891d8cc0236da4ca37b2d9eb5437e19b1f41b4b308284e899b1e10b message counter 0
    Candidate session 0 failed with 'invalid PreKey message: MAC verification failed', had 0 receiver chains
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: InvalidMessage(PreKey, "decryption failed")', fuzz_targets/interaction.rs:163:14

One clue I have is that use_one_time_pre_key == false will allow it to pass:

swdev2@Jonathans-Mini fuzz % git diff
diff --git a/rust/protocol/fuzz/fuzz_targets/interaction.rs b/rust/protocol/fuzz/fuzz_targets/interaction.rs
index d3eed7e4..33396e8a 100644
--- a/rust/protocol/fuzz/fuzz_targets/interaction.rs
+++ b/rust/protocol/fuzz/fuzz_targets/interaction.rs
@@ -111,7 +111,7 @@ impl Participant {
             .map(|session| !session.has_current_session_state())
             .unwrap_or(true)
         {
-            self.process_pre_key(them, rng.gen_bool(0.75), rng).await;
+            self.process_pre_key(them, rng.gen_bool(0.0), rng).await;
         }

         let length = rng.gen_range(0, 140);
swdev2@Jonathans-Mini fuzz % env RUST_LOG=interaction=info,libsignal_protocol=info RUST_BACKTRACE=full cargo fuzz run interaction artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be
    Finished release [optimized] target(s) in 0.05s
    Finished release [optimized] target(s) in 0.05s
     Running `target/aarch64-apple-darwin/release/interaction -artifact_prefix=/Users/swdev2/libsignal/rust/protocol/fuzz/artifacts/interaction/ artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be`
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 882072864
INFO: Loaded 1 modules   (297274 inline 8-bit counters): 297274 [0x1022725c0, 0x1022baefa), 
INFO: Loaded 1 PC tables (297274 PCs): 297274 [0x1022baf00,0x1027442a0), 
target/aarch64-apple-darwin/release/interaction: Running 1 inputs 1 time(s) each.
Running: artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be
[2023-05-05T20:33:44Z INFO  interaction] bob: sending message
[2023-05-05T20:33:44Z INFO  interaction] bob:   processing a new pre-key bundle
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session] set_unacknowledged_pre_key_message for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  interaction] bob: sending message
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  interaction] bob: receiving messages
[2023-05-05T20:33:44Z INFO  interaction] alice: receiving messages
[2023-05-05T20:33:44Z WARN  libsignal_protocol::session] processing PreKey message from +14151111112.1 which had no one-time prekey
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] +14151111112.1 creating new chains.
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] decrypted PreKey message from +14151111112.1 with current session state (base key eeff52d1637142535cc373f233deb66378702bf859843eb4040e45eb23e24949)
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] decrypted PreKey message from +14151111112.1 with current session state (base key eeff52d1637142535cc373f233deb66378702bf859843eb4040e45eb23e24949)
[2023-05-05T20:33:44Z INFO  interaction] bob: receiving messages
[2023-05-05T20:33:44Z INFO  interaction] bob: sending message
[2023-05-05T20:33:44Z INFO  interaction] bob:   processing a new pre-key bundle
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session] set_unacknowledged_pre_key_message for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  interaction] bob: sending message
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] Building PreKeyWhisperMessage for: +14151111111.1 with preKeyId: <none>
[2023-05-05T20:33:44Z INFO  interaction] bob: receiving messages
[2023-05-05T20:33:44Z INFO  interaction] alice: receiving messages
[2023-05-05T20:33:44Z WARN  libsignal_protocol::session] processing PreKey message from +14151111112.1 which had no one-time prekey
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::state::session] Skipping archive, current session state is fresh
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] +14151111112.1 creating new chains.
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] decrypted PreKey message from +14151111112.1 with current session state (base key eeff52d1637142535cc373f233deb66378702bf859843eb4040e45eb23e24949)
[2023-05-05T20:33:44Z INFO  libsignal_protocol::session_cipher] decrypted PreKey message from +14151111112.1 with current session state (base key eeff52d1637142535cc373f233deb66378702bf859843eb4040e45eb23e24949)
[2023-05-05T20:33:44Z INFO  interaction] bob: receiving messages
Executed artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be in 9 ms
expiringplatform commented 1 year ago

Thanks @moodyjon for creating the fix PR! :) I can confirm that the PR combined with setting use_one_time_pre_key == false as you descibed above does fix the crash crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be. But this also doesn't seem to fix all problems, since I found a input that also crashes this.

Crash log

crash-36aee4c5debf2e8fa843e6e0433c7d2fada00818.zip

Sorry if that is obvious or if I misunderstood something, I don't have a deep understanding of the code and merely run the fuzz test.

moodyjon commented 1 year ago

I can confirm that the PR combined with setting use_one_time_pre_key == false as you descibed above does fix the crash crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be.

use_one_time_pre_key == false was a temporary hack. The pull request #521 has a more complete fix.

However, I see that crash-36aee4c5debf2e8fa843e6e0433c7d2fada00818 will cause a failure on even on the latest attempt to fix. Will investigate that.

moodyjon commented 1 year ago

I believe it's an off-by-one issue. The condition should be if me.archive_count + them.archive_count + 1 < 40

I'm testing with the following:

                    let mut estimated_prev_states = 0;
                    // The set of previous session states grows in two ways:
                    // 1) The current session state of "me" is archived explicitly.
                    estimated_prev_states += me.archive_count;
                    // 2) A pre-key message is received from "them" and displaces
                    //    the current session state.
                    estimated_prev_states += 1 + them.archive_count;
                    if estimated_prev_states < 40 {
moodyjon commented 1 year ago

With latest changes from #521 

swdev2@Jonathans-Mini fuzz % env RUST_BACKTRACE=full cargo fuzz run interaction crash-* artifacts/interaction/crash-*
    Finished release [optimized] target(s) in 0.13s
    Finished release [optimized] target(s) in 0.12s
     Running `target/aarch64-apple-darwin/release/interaction -artifact_prefix=/Users/swdev2/libsignal/rust/protocol/fuzz/artifacts/interaction/ crash-36aee4c5debf2e8fa843e6e0433c7d2fada00818 crash-4499e6206c8ecced15c06fa9496883de298fb0f9 crash-65c7888c15186076f0f6c963910da1faa5a87975 artifacts/interaction/crash-4be9d64c8223c7a21e51eb4c989ec1ec390cb75b artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be artifacts/interaction/crash-c6f826eb839298e1db43bf7b3f72ee12e3e1ba82 artifacts/interaction/crash-e6169a5d2c307f63f1c4ac9fb840847984ca413c`
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 2390052038
INFO: Loaded 1 modules   (305221 inline 8-bit counters): 305221 [0x106214610, 0x10625ee55), 
INFO: Loaded 1 PC tables (305221 PCs): 305221 [0x10625ee58,0x1067072a8), 
target/aarch64-apple-darwin/release/interaction: Running 7 inputs 1 time(s) each.
Running: crash-36aee4c5debf2e8fa843e6e0433c7d2fada00818
Executed crash-36aee4c5debf2e8fa843e6e0433c7d2fada00818 in 344 ms
Running: crash-4499e6206c8ecced15c06fa9496883de298fb0f9
Executed crash-4499e6206c8ecced15c06fa9496883de298fb0f9 in 249 ms
Running: crash-65c7888c15186076f0f6c963910da1faa5a87975
Executed crash-65c7888c15186076f0f6c963910da1faa5a87975 in 66 ms
Running: artifacts/interaction/crash-4be9d64c8223c7a21e51eb4c989ec1ec390cb75b
Executed artifacts/interaction/crash-4be9d64c8223c7a21e51eb4c989ec1ec390cb75b in 36 ms
Running: artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be
Executed artifacts/interaction/crash-9b8155d6c9e9134a09dcb9b12d62893408ee83be in 3 ms
Running: artifacts/interaction/crash-c6f826eb839298e1db43bf7b3f72ee12e3e1ba82
Executed artifacts/interaction/crash-c6f826eb839298e1db43bf7b3f72ee12e3e1ba82 in 35 ms
Running: artifacts/interaction/crash-e6169a5d2c307f63f1c4ac9fb840847984ca413c
Executed artifacts/interaction/crash-e6169a5d2c307f63f1c4ac9fb840847984ca413c in 38 ms
***
*** NOTE: fuzzing was not performed, you have only
***       executed the target code on a fixed set of inputs.
***
moodyjon commented 1 year ago

Latest:

                    let mut estimated_prev_states = 0;
                    // The set of previous session states grows in two ways:
                    // 1) The current session state of "me" is archived explicitly.
                    estimated_prev_states += me.archive_count;
                    // 2) A pre-key message is received from "them" and displaces the
                    //    current session state. They may send one pre-key message initially.
                    //    Additional pre-key messages from "them" follow explicit archiving.
                    estimated_prev_states += 1 + them.archive_count;
                    if estimated_prev_states < 40 {

My limited understanding of the protocol is that they may send one initial "pre key" message PLUS a number of additional ones that each follow an explicit archive step. That's why the first try was off by one.

expiringplatform commented 1 year ago

Hi, I fuzzed the proposed changed code (#521 ) and ran the fuzzer for ~23h with no crash being found

#8766247: cov: 18551 ft: 28933 corp: 986 exec/s 13 oom/timeout/crash: 0/0/0 time: 82634s job: 2062 dft_time: 0

stale[bot] commented 1 year ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.