fuzz: Differential fuzzing to compare Bitcoin Core’s and D. J. Bernstein’s implementation of ChaCha20 #22704
pull stratospher wants to merge 2 commits into bitcoin:master from stratospher:diff-fuzz-chacha20 changing 2 files +331 −0-
stratospher commented at 7:28 pm on August 14, 2021: contributorThis PR compares Bitcoin Core’s implementation of ChaCha20 with D. J. Bernstein’s in order to find implementation discrepancies if any.
-
dhruv commented at 7:38 pm on August 14, 2021: contributor
Concept ACK.
We have to implement crypto ourselves to keep the surface area small and avoid bringing in large dependencies. Differential fuzzing against a reference implementation is a great addition to testing the reference test vectors.
Thank you for your work, and welcome to Bitcoin Core!
-
DrahtBot added the label Build system on Aug 14, 2021
-
fanquake removed the label Build system on Aug 15, 2021
-
fanquake added the label Tests on Aug 15, 2021
-
fanquake requested review from maflcko on Aug 15, 2021
-
fanquake commented at 3:28 am on August 15, 2021: member@agroce / @guidovranken this may also interest you.
-
guidovranken commented at 3:48 am on August 15, 2021: contributor
Essentially this is already done by Cryptofuzz which compares it against the Botan implementation, and is running on OSS-Fuzz in the bitcoin-core project
-
stratospher commented at 6:48 pm on August 19, 2021: contributor
Oh..I wasn’t aware of the differential fuzzing for Bitcoin Core cryptographic libraries being done in Cryptofuzz. Crypofuzz is an incredible project! Could you please elaborate more on where the comparison with Botan implementation is happening?
Would there be incremental value in fuzzing against D.J. Bernstein’s reference implementation? And including the Keystream() function too in the Bitcoin Core/Cryptofuzz diferential fuzz tests?
-
in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:292 in a637734393 outdated
287+ // ECRYPT_keysetup() doesn't set the counter and nonce to 0 while SetKey() does 288+ uint8_t iv[8] = {0, 0, 0, 0, 0, 0, 0, 0}; 289+ ECRYPT_ivsetup(&ctx, iv); 290+ } 291+ 292+ while (fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, 100) >= 10) {
maflcko commented at 6:59 pm on August 19, 2021:how is this different from
0 while (fuzzed_data_provider.ConsumeBool()) {
Also, could use
LIMITED_WHILE
to avoid unlimited runtime.
prakash1512 commented at 6:37 am on August 20, 2021:how is this different from
Increased the probability of entering the while loop as
ConsumeBool()
has only 50% chance of returning true whileConsumeIntegralInRange<uint32_t>(0,100) >= 10
will have 90% chance of returning true. Essentially we’re trying to get the test running longer for each fuzz seed so multiple functions are exercised per seed, especially sinceChaCha20
maintains an internal state for each seed.
stratospher commented at 6:57 am on August 20, 2021:Also, could use
LIMITED_WHILE
to avoid unlimited runtime.Great suggestion! Added
LIMITED_WHILE
.
maflcko commented at 7:38 am on August 20, 2021:Essentially we’re trying to get the test running longer
Do you have data to support that claim? Fuzzing engines will store inputs that increase coverage data and once the data is stored, for replay it doesn’t matter whether it was
ConsumeBool
orConsumeIntegralInRange
that evaluated to true.
prakash1512 commented at 9:25 pm on August 20, 2021:Do you have data to support that claim?
Backing the claim with data was indeed a great suggestion, so we generated the data and plots to verify it. Now we have results to dismiss that claim :) Sharing our findings here:
x-axis denotes no of iterations
y-axis denotes frequency of each iteration
maflcko commented at 7:02 pm on August 19, 2021: memberbtw, I don’t mind adding the fuzz test here, even if it is redundant with oss-fuzz. Oss-fuzz is just one fuzzing providre, but I also run my own fuzzing servers to not put all eggs into one basket. I am sure others are running the Bitcoin Core fuzz target, too.dhruv commented at 7:06 pm on August 19, 2021: contributor+1 for what @MarcoFalke said. It’d be nice to be able to run this along with other fuzz targets on personal machines.practicalswift commented at 9:18 pm on August 19, 2021: contributorConcept ACK for the reasons @MarcoFalke mentionedstratospher force-pushed on Aug 20, 2021stratospher force-pushed on Aug 20, 2021stratospher commented at 4:52 am on October 14, 2021: contributorAddedLIMITED_WHILE
and updatedConsumeIntegralInRange()
toConsumeBool()
as per discussion in comments. Ready for further review.DrahtBot commented at 4:20 pm on October 21, 2021: contributorThe following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Conflicts
Reviewers, this pull request conflicts with the following ones:
- #23441 (fuzz: Differential fuzzing for ChaCha20Forward4064-Poly1305@bitcoin cipher suite by stratospher)
- #23322 ([Fuzz] Poly1305 differential fuzzing against Floodyberry’s implementation by prakash1512)
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:45 in 258d751c1c outdated
40+ (p)[3] = U8V((v) >> 24); \ 41+ } while (0) 42+ 43+/* ------------------------------------------------------------------------- */ 44+/* Data structures */ 45+
siv2r commented at 8:34 pm on November 27, 2021:nit: it might be useful to add the definition of
ENCRYPT_ctx
in the comments.0/* 1 * ECRYPT_ctx is the structure containing the representation of the 2 * internal state of your cipher. 3 */
stratospher commented at 6:19 am on December 4, 2021:I’d like to keep D. J. Bernstein’s reference implementation of ChaCha20 as such.in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:93 in 258d751c1c outdated
92+ d = ROTATE(XOR(d, a), 8); \ 93+ c = PLUS(c, d); \ 94+ b = ROTATE(XOR(b, c), 7); 95+ 96+static const char sigma[] = "expand 32-byte k"; 97+static const char tau[] = "expand 16-byte k";
siv2r commented at 8:50 pm on November 27, 2021:0static const char sigma[16] = "expand 32-byte k"; 1static const char tau[16] = "expand 16-byte k";
stratospher commented at 6:19 am on December 4, 2021:Since this is actually 16 characters + ‘\0’, we’d have to put a number ≥17. There’s a discussion here which talks about the change needed in the reference implementation. This is the only place where such a change was made.
siv2r commented at 3:19 pm on December 4, 2021:Ah, I see. Thanks!in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:94 in 258d751c1c outdated
89+ c = PLUS(c, d); \ 90+ b = ROTATE(XOR(b, c), 12); \ 91+ a = PLUS(a, b); \ 92+ d = ROTATE(XOR(d, a), 8); \ 93+ c = PLUS(c, d); \ 94+ b = ROTATE(XOR(b, c), 7);
siv2r commented at 10:20 pm on November 27, 2021:0 a = PLUS(a, b); d = ROTATE(XOR(d, a), 16); \ 1 c = PLUS(c, d); b = ROTATE(XOR(b, c), 12); \ 2 a = PLUS(a, b); d = ROTATE(XOR(d, a), 8); \ 3 c = PLUS(c, d); b = ROTATE(XOR(b, c), 7);
nit: this pattern of defining the
QUATERROUND
macro is following in many places (chacha20.cpp).
stratospher commented at 6:19 am on December 4, 2021:Thanks! I’ve made the changes.siv2r commented at 10:28 pm on November 27, 2021: noneutACK 258d751. I compared this code change against DJ Bernstein’s chacha20 implementation. The changes look good!
I am yet to test the changes on my local machine. Feel free to ignore the nits that I suggested :)
siv2r commented at 10:28 pm on November 27, 2021: noneutACK 258d751. I compared this code change against DJ Bernstein’s chacha20 implementation. The changes look good!
I am yet to test the changes on my local machine. Feel free to ignore the nits that I suggested :)
stratospher force-pushed on Dec 4, 2021stratospher commented at 6:20 am on December 4, 2021: contributorAddressed #22704(comment). (Thanks @siv2r!) Ready for further review.laanwj commented at 9:32 pm on December 10, 2021: memberYou might want to set a different author name for your commits than “root” if you want to be credited properly in the release notes.[fuzz] Add D. J. Bernstein's implementation of ChaCha20
Co-authored-by: Prakash Choudhary <44579179+prakash1512@users.noreply.github.com>
[fuzz] Add fuzzing harness to compare both implementations of ChaCha20
Co-authored-by: Prakash Choudhary <44579179+prakash1512@users.noreply.github.com>
stratospher force-pushed on Dec 11, 2021stratospher commented at 3:12 am on December 11, 2021: contributorYou might want to set a different author name for your commits than “root” if you want to be credited properly in the release notes.
Thank you for letting me know! I’ve updated the author name.
laanwj commented at 3:53 pm on December 17, 2021: memberCode review ACK 4d0ac72f3ae78e3c6a0d5dc4f7e809583abd0546laanwj merged this on Dec 17, 2021laanwj closed this on Dec 17, 2021
in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:318 in 4d0ac72f3a
313+ std::vector<uint8_t> output(integralInRange); 314+ chacha20.Keystream(output.data(), output.size()); 315+ std::vector<uint8_t> djb_output(integralInRange); 316+ ECRYPT_keystream_bytes(&ctx, djb_output.data(), djb_output.size()); 317+ if (output.data() != NULL && djb_output.data() != NULL) { 318+ assert(memcmp(output.data(), djb_output.data(), integralInRange) == 0);
maflcko commented at 4:02 pm on December 17, 2021:any reason to use a low level function, when https://en.cppreference.com/w/cpp/container/vector/operator_cmp could be used?
stratospher commented at 5:47 pm on December 17, 2021:I went with this because some of the crypto unit tests used memcmp. I feel you’re right though and memcmp doesn’t really provide any added advantage.in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:317 in 4d0ac72f3a
312+ uint32_t integralInRange = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096); 313+ std::vector<uint8_t> output(integralInRange); 314+ chacha20.Keystream(output.data(), output.size()); 315+ std::vector<uint8_t> djb_output(integralInRange); 316+ ECRYPT_keystream_bytes(&ctx, djb_output.data(), djb_output.size()); 317+ if (output.data() != NULL && djb_output.data() != NULL) {
maflcko commented at 4:03 pm on December 17, 2021:when would this fail?
stratospher commented at 5:47 pm on December 17, 2021:I meant this as a check to not pass a null pointer(In a situation whereintegralInRange
is 0) to memcmp since it would exhibit undefined behaviour. This can be removed if memcmp is removed.in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:327 in 4d0ac72f3a
322+ uint32_t integralInRange = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096); 323+ std::vector<uint8_t> output(integralInRange); 324+ const std::vector<uint8_t> input = ConsumeFixedLengthByteVector(fuzzed_data_provider, output.size()); 325+ chacha20.Crypt(input.data(), output.data(), input.size()); 326+ std::vector<uint8_t> djb_output(integralInRange); 327+ ECRYPT_encrypt_bytes(&ctx, input.data(), djb_output.data(), input.size());
maflcko commented at 4:04 pm on December 17, 2021:
stratospher commented at 5:47 pm on December 17, 2021:Nice catch. Thanks! I can open a follow up PR to include these suggestions.stratospher commented at 5:56 pm on December 17, 2021: contributorThanks for the review @MarcoFalke. I’ve opened #23806 to address your comments.sidhujag referenced this in commit 61a9614645 on Dec 18, 2021maflcko referenced this in commit 98a2ddcd6e on Dec 18, 2021sidhujag referenced this in commit 946b51d208 on Dec 18, 2021maflcko commented at 11:37 am on December 24, 2021: member0# FUZZ=crypto_diff_fuzz_chacha20 /root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610 1INFO: Running with entropic power schedule (0xFF, 100). 2INFO: Seed: 3283247107 3INFO: Loaded 1 modules (306045 inline 8-bit counters): 306045 [0x55c5b9987bc0, 0x55c5b99d273d), 4INFO: Loaded 1 PC tables (306045 PCs): 306045 [0x55c5b99d2740,0x55c5b9e7df10), 5/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz: Running 1 inputs 1 time(s) each. 6Running: ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610 7test/fuzz/crypto_diff_fuzz_chacha20.cpp:179:13: runtime error: left shift of 268500992 by 8 places cannot be represented in type 'unsigned int' 8 [#0](/bitcoin-bitcoin/0/) 0x55c5b722ff9b in ECRYPT_encrypt_bytes(ECRYPT_ctx*, unsigned char const*, unsigned char*, unsigned int) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:179:13 9 [#1](/bitcoin-bitcoin/1/) 0x55c5b723a342 in ECRYPT_keystream_bytes(ECRYPT_ctx*, unsigned char*, unsigned int) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:265:5 10 [#2](/bitcoin-bitcoin/2/) 0x55c5b723a342 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_3::operator()() const src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:316:17 11 [#3](/bitcoin-bitcoin/3/) 0x55c5b723a342 in unsigned long CallOneOf<crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_0, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_1, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_2, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_3, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_4>(FuzzedDataProvider&, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_0, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_1, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_2, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_3, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_4) src/./test/fuzz/util.h:49:27 12 [#4](/bitcoin-bitcoin/4/) 0x55c5b72393d5 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:289:9 13 [#5](/bitcoin-bitcoin/5/) 0x55c5b7167628 in std::_Function_handler<void (Span<unsigned char const>), void (*)(Span<unsigned char const>)>::_M_invoke(std::_Any_data const&, Span<unsigned char const>&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:300:2 14 [#6](/bitcoin-bitcoin/6/) 0x55c5b80f997d in std::function<void (Span<unsigned char const>)>::operator()(Span<unsigned char const>) const /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:688:14 15 [#7](/bitcoin-bitcoin/7/) 0x55c5b80f9628 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:91:5 16 [#8](/bitcoin-bitcoin/8/) 0x55c5b7076fb3 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1461fb3) 17 [#9](/bitcoin-bitcoin/9/) 0x55c5b706037f in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x144b37f) 18 [#10](/bitcoin-bitcoin/10/) 0x55c5b706615c in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x145115c) 19 [#11](/bitcoin-bitcoin/11/) 0x55c5b7090d72 in main (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x147bd72) 20 [#12](/bitcoin-bitcoin/12/) 0x7f395fca90b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16 21 [#13](/bitcoin-bitcoin/13/) 0x55c5b705ab0d in _start (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1445b0d) 22 23SUMMARY: UndefinedBehaviorSanitizer: invalid-shift-base test/fuzz/crypto_diff_fuzz_chacha20.cpp:179:13 in
0# base64 ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610 19tXRyA==
in src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:302 in 4d0ac72f3a
297+ ECRYPT_ivsetup(&ctx, iv); 298+ }, 299+ [&] { 300+ uint64_t iv = fuzzed_data_provider.ConsumeIntegral<uint64_t>(); 301+ chacha20.SetIV(iv); 302+ ctx.input[14] = iv;
maflcko commented at 11:43 am on December 24, 2021:0test/fuzz/crypto_diff_fuzz_chacha20.cpp:302:33: runtime error: implicit conversion from type 'uint64_t' (aka 'unsigned long') of value 270751369970 (64-bit, unsigned) to type 'u32' (aka 'unsigned int') changed the value to 168430322 (32-bit, unsigned) 1 [#0](/bitcoin-bitcoin/0/) 0x55b2974ba838 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_1::operator()() const src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:302:33 2 [#1](/bitcoin-bitcoin/1/) 0x55b2974ba838 in unsigned long CallOneOf<crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_0, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_1, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_2, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_3, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_4>(FuzzedDataProvider&, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_0, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_1, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_2, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_3, crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>)::$_4) src/./test/fuzz/util.h:49:27 3 [#2](/bitcoin-bitcoin/2/) 0x55b2974b93d5 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:289:9 4 [#3](/bitcoin-bitcoin/3/) 0x55b2973e7628 in std::_Function_handler<void (Span<unsigned char const>), void (*)(Span<unsigned char const>)>::_M_invoke(std::_Any_data const&, Span<unsigned char const>&&) /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:300:2 5 [#4](/bitcoin-bitcoin/4/) 0x55b29837997d in std::function<void (Span<unsigned char const>)>::operator()(Span<unsigned char const>) const /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/std_function.h:688:14 6 [#5](/bitcoin-bitcoin/5/) 0x55b298379628 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:91:5 7 [#6](/bitcoin-bitcoin/6/) 0x55b2972f6fb3 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1461fb3) 8 [#7](/bitcoin-bitcoin/7/) 0x55b2972f6709 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1461709) 9 [#8](/bitcoin-bitcoin/8/) 0x55b2972f7ef9 in fuzzer::Fuzzer::MutateAndTestOne() (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1462ef9) 10 [#9](/bitcoin-bitcoin/9/) 0x55b2972f8a75 in fuzzer::Fuzzer::Loop(std::vector<fuzzer::SizedFile, std::allocator<fuzzer::SizedFile> >&) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1463a75) 11 [#10](/bitcoin-bitcoin/10/) 0x55b2972e6288 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1451288) 12 [#11](/bitcoin-bitcoin/11/) 0x55b297310d72 in main (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x147bd72) 13 [#12](/bitcoin-bitcoin/12/) 0x7fcb06fc90b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16 14 [#13](/bitcoin-bitcoin/13/) 0x55b2972dab0d in _start (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1445b0d) 15 16SUMMARY: UndefinedBehaviorSanitizer: implicit-unsigned-integer-truncation test/fuzz/crypto_diff_fuzz_chacha20.cpp:302:33 in 17MS: 4 ShuffleBytes-CrossOver-ChangeBinInt-CopyPart-; base unit: 47966b9379790c601d5e098f1ba5ccae76f25861 180xf2,0xa,0xa,0xa,0x3f,0x38,0x1b,0xf4, 19\362\012\012\012?8\033\364 20artifact_prefix='./'; Test unit written to ./crash-ce471b8e19b31491ff5f4a3669aefa84b1848f06 21Base64: 8goKCj84G/Q=
bitcoin locked this on Dec 24, 2022stratospher deleted the branch on Jul 17, 2024
github-metadata-mirror
This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-17 15:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me