fuzz: Differential fuzzing to compare Bitcoin Core's and D. J. Bernstein's implementation of ChaCha20 #22704

stratospher · 2021-08-14T19:28:18Z

This PR compares Bitcoin Core's implementation of ChaCha20 with D. J. Bernstein's in order to find implementation discrepancies if any.

dhruv · 2021-08-14T19:38:48Z

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!

fanquake · 2021-08-15T03:28:16Z

@agroce / @guidovranken this may also interest you.

guidovranken · 2021-08-15T03:48:35Z

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

https://github.com/guidovranken/cryptofuzz/blob/6dddb6bb97a2cd8d7bf915bca00d0411ccf5e1c0/modules/bitcoin/module.cpp#L417-L420

stratospher · 2021-08-19T18:48:32Z

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?

maflcko

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.

siv2r

utACK 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 :)

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp

siv2r

utACK 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 · 2021-12-04T06:20:42Z

Addressed #22704(comment). (Thanks @siv2r!) Ready for further review.

laanwj · 2021-12-10T21:32:03Z

You might want to set a different author name for your commits than "root" if you want to be credited properly in the release notes.

Co-authored-by: Prakash Choudhary <44579179+prakash1512@users.noreply.github.com>

stratospher · 2021-12-11T03:12:00Z

You 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 · 2021-12-17T15:53:49Z

Code review ACK 4d0ac72

maflcko · 2021-12-17T16:02:53Z

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp

+                std::vector<uint8_t> djb_output(integralInRange);
+                ECRYPT_keystream_bytes(&ctx, djb_output.data(), djb_output.size());
+                if (output.data() != NULL && djb_output.data() != NULL) {
+                    assert(memcmp(output.data(), djb_output.data(), integralInRange) == 0);


any reason to use a low level function, when https://en.cppreference.com/w/cpp/container/vector/operator_cmp could be used?

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.

maflcko · 2021-12-17T16:03:57Z

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp

+                chacha20.Keystream(output.data(), output.size());
+                std::vector<uint8_t> djb_output(integralInRange);
+                ECRYPT_keystream_bytes(&ctx, djb_output.data(), djb_output.size());
+                if (output.data() != NULL && djb_output.data() != NULL) {


when would this fail?

I meant this as a check to not pass a null pointer(In a situation where integralInRange is 0) to memcmp since it would exhibit undefined behaviour. This can be removed if memcmp is removed.

maflcko · 2021-12-17T16:04:12Z

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp

+                const std::vector<uint8_t> input = ConsumeFixedLengthByteVector(fuzzed_data_provider, output.size());
+                chacha20.Crypt(input.data(), output.data(), input.size());
+                std::vector<uint8_t> djb_output(integralInRange);
+                ECRYPT_encrypt_bytes(&ctx, input.data(), djb_output.data(), input.size());


missing https://en.cppreference.com/w/cpp/container/vector/operator_cmp ?

Nice catch. Thanks!
I can open a follow up PR to include these suggestions.

stratospher · 2021-12-17T17:56:48Z

Thanks for the review @MarcoFalke. I've opened #23806 to address your comments.

…re's and D. J. Bernstein's implementation of ChaCha20 4d0ac72 [fuzz] Add fuzzing harness to compare both implementations of ChaCha20 (stratospher) 65ef932 [fuzz] Add D. J. Bernstein's implementation of ChaCha20 (stratospher) Pull request description: This PR compares Bitcoin Core's implementation of ChaCha20 with D. J. Bernstein's in order to find implementation discrepancies if any. ACKs for top commit: laanwj: Code review ACK 4d0ac72 Tree-SHA512: f826144b4db61b9cbdd7efaaca8fa9cbb899953065bc8a26820a566303b2ab6a17431e7c114635789f0a63fbe3b65cb0bf2ab85baf882803a5ee172af4881544

8f79831 Refactor the chacha20 differential fuzz test (stratospher) Pull request description: This PR addresses [comments from #22704](https://github.com/bitcoin/bitcoin/pull/22704/files#discussion_r771510963) to make the following changes in `src/test/fuzz/crypto_diff_fuzz_chacha20.cpp`: - replace `memcmp()` with == - add a missing assert statement to compare the encrypted bytes Top commit has no ACKs. Tree-SHA512: 02338460fb3a89e732558bf00f3aebf8f04daba194e03ae0e3339bb2ff6ba35d06841452585b739047a29f8ec64f36b1b4ce2dfa39a08f6ad44a6a937e7b3acb

8f79831 Refactor the chacha20 differential fuzz test (stratospher) Pull request description: This PR addresses [comments from bitcoin#22704](https://github.com/bitcoin/bitcoin/pull/22704/files#discussion_r771510963) to make the following changes in `src/test/fuzz/crypto_diff_fuzz_chacha20.cpp`: - replace `memcmp()` with == - add a missing assert statement to compare the encrypted bytes Top commit has no ACKs. Tree-SHA512: 02338460fb3a89e732558bf00f3aebf8f04daba194e03ae0e3339bb2ff6ba35d06841452585b739047a29f8ec64f36b1b4ce2dfa39a08f6ad44a6a937e7b3acb

maflcko · 2021-12-24T11:37:39Z

# FUZZ=crypto_diff_fuzz_chacha20 /root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610 
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 3283247107
INFO: Loaded 1 modules   (306045 inline 8-bit counters): 306045 [0x55c5b9987bc0, 0x55c5b99d273d), 
INFO: Loaded 1 PC tables (306045 PCs): 306045 [0x55c5b99d2740,0x55c5b9e7df10), 
/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz: Running 1 inputs 1 time(s) each.
Running: ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610
test/fuzz/crypto_diff_fuzz_chacha20.cpp:179:13: runtime error: left shift of 268500992 by 8 places cannot be represented in type 'unsigned int'
    #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
    #1 0x55c5b723a342 in ECRYPT_keystream_bytes(ECRYPT_ctx*, unsigned char*, unsigned int) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:265:5
    #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
    #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
    #4 0x55c5b72393d5 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:289:9
    #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
    #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
    #7 0x55c5b80f9628 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:91:5
    #8 0x55c5b7076fb3 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1461fb3)
    #9 0x55c5b706037f in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x144b37f)
    #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)
    #11 0x55c5b7090d72 in main (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x147bd72)
    #12 0x7f395fca90b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16
    #13 0x55c5b705ab0d in _start (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1445b0d)

SUMMARY: UndefinedBehaviorSanitizer: invalid-shift-base test/fuzz/crypto_diff_fuzz_chacha20.cpp:179:13 in

# base64 ./scratch/fuzz_gen/code/crash-03f91945a7518033b0df73bf35c2caa452126610 
9tXRyA==

maflcko · 2021-12-24T11:43:01Z

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp

+            [&] {
+                uint64_t iv = fuzzed_data_provider.ConsumeIntegral<uint64_t>();
+                chacha20.SetIV(iv);
+                ctx.input[14] = iv;


test/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) #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 #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 #2 0x55b2974b93d5 in crypto_diff_fuzz_chacha20_fuzz_target(Span<unsigned char const>) src/test/fuzz/crypto_diff_fuzz_chacha20.cpp:289:9 #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 #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 #5 0x55b298379628 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:91:5 #6 0x55b2972f6fb3 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1461fb3) #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) #8 0x55b2972f7ef9 in fuzzer::Fuzzer::MutateAndTestOne() (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1462ef9) #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) #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) #11 0x55b297310d72 in main (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x147bd72) #12 0x7fcb06fc90b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16 #13 0x55b2972dab0d in _start (/root/fuzz_dir/scratch/fuzz_gen/code/src/test/fuzz/fuzz+0x1445b0d) SUMMARY: UndefinedBehaviorSanitizer: implicit-unsigned-integer-truncation test/fuzz/crypto_diff_fuzz_chacha20.cpp:302:33 in MS: 4 ShuffleBytes-CrossOver-ChangeBinInt-CopyPart-; base unit: 47966b9379790c601d5e098f1ba5ccae76f25861 0xf2,0xa,0xa,0xa,0x3f,0x38,0x1b,0xf4, \362\012\012\012?8\033\364 artifact_prefix='./'; Test unit written to ./crash-ce471b8e19b31491ff5f4a3669aefa84b1848f06 Base64: 8goKCj84G/Q=

DrahtBot added the Build system label Aug 14, 2021

fanquake added Tests and removed Build system labels Aug 15, 2021

fanquake requested a review from maflcko August 15, 2021 03:26

maflcko reviewed Aug 19, 2021

View reviewed changes

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp Outdated Show resolved Hide resolved

stratospher force-pushed the diff-fuzz-chacha20 branch 2 times, most recently from 48b07c2 to 258d751 Compare August 20, 2021 20:59

DrahtBot mentioned this pull request Oct 21, 2021

[Fuzz] Poly1305 differential fuzzing against Floodyberry's implementation #23322

Closed

DrahtBot mentioned this pull request Nov 5, 2021

fuzz: Differential fuzzing for ChaCha20Forward4064-Poly1305@bitcoin cipher suite #23441

Closed

siv2r reviewed Nov 27, 2021

View reviewed changes

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp Show resolved Hide resolved

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp Show resolved Hide resolved

src/test/fuzz/crypto_diff_fuzz_chacha20.cpp Outdated Show resolved Hide resolved

siv2r reviewed Nov 27, 2021

View reviewed changes

stratospher force-pushed the diff-fuzz-chacha20 branch from 258d751 to c0554c7 Compare December 4, 2021 06:12

stratospher and others added 2 commits December 11, 2021 08:29

[fuzz] Add D. J. Bernstein's implementation of ChaCha20

65ef932

Co-authored-by: Prakash Choudhary <44579179+prakash1512@users.noreply.github.com>

[fuzz] Add fuzzing harness to compare both implementations of ChaCha20

4d0ac72

Co-authored-by: Prakash Choudhary <44579179+prakash1512@users.noreply.github.com>

stratospher force-pushed the diff-fuzz-chacha20 branch from c0554c7 to 4d0ac72 Compare December 11, 2021 03:01

laanwj merged commit 4ad5904 into bitcoin:master Dec 17, 2021

maflcko reviewed Dec 17, 2021

View reviewed changes

maflcko reviewed Dec 24, 2021

View reviewed changes

maflcko mentioned this pull request Dec 24, 2021

test: Add missing suppressions for crypto_diff_fuzz_chacha20.cpp #23859

Merged

dhruv mentioned this pull request Jun 13, 2022

[crypto] Reduce wasted pseudorandom bytes in ChaCha20 #25354

Closed

bitcoin locked and limited conversation to collaborators Dec 24, 2022

stratospher deleted the diff-fuzz-chacha20 branch July 17, 2024 06:41

fuzz: Differential fuzzing to compare Bitcoin Core's and D. J. Bernstein's implementation of ChaCha20 #22704

fuzz: Differential fuzzing to compare Bitcoin Core's and D. J. Bernstein's implementation of ChaCha20 #22704

Uh oh!

Conversation

stratospher commented Aug 14, 2021

Uh oh!

dhruv commented Aug 14, 2021

Uh oh!

fanquake commented Aug 15, 2021

Uh oh!

guidovranken commented Aug 15, 2021

Uh oh!

stratospher commented Aug 19, 2021

Uh oh!

maflcko left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

maflcko commented Aug 19, 2021

Uh oh!

dhruv commented Aug 19, 2021

Uh oh!

practicalswift commented Aug 19, 2021

Uh oh!

agroce commented Aug 19, 2021

Uh oh!

stratospher commented Oct 14, 2021

Uh oh!

DrahtBot commented Oct 21, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

siv2r left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

siv2r left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

stratospher commented Dec 4, 2021

Uh oh!

laanwj commented Dec 10, 2021

Uh oh!

stratospher commented Dec 11, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

laanwj commented Dec 17, 2021

Uh oh!

maflcko Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

stratospher Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

stratospher Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

stratospher Dec 17, 2021

Choose a reason for hiding this comment

Uh oh!

stratospher commented Dec 17, 2021

Uh oh!

maflcko commented Dec 24, 2021

Uh oh!

maflcko Dec 24, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

DrahtBot commented Oct 21, 2021 •

edited

Loading

siv2r left a comment •

edited

Loading

stratospher commented Dec 11, 2021 •

edited

Loading

maflcko Dec 24, 2021 •

edited

Loading