memcmp may be miscompiled by GCC

[real-or-random]

What about the other memcmp's we have in actual production code? (bip340 tag, tweak add check, scratch impl, sha256 selftest) does this bug affect those too?

Originally posted by @elichai in https://github.com/bitcoin-core/secp256k1/pull/822#issuecomment-697221468

context: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189

[real-or-random]

AFAIU (and I'm not 100% sure) this affects comparisons with fixed byte arrays which include zero bytes. The check may then early terminate at the first zero byte.

• BIP340 tag: Strictly speaking yes, here we compare with a fixed string including zero bytes. Even though it will be weird if someone passed BIP0340/nonce\0AB or something like this. (and see #757 , maybe that's not a great API anyway).
• Tweak add check: probably not, no constants here.
• scratch: here the byte array is scratch so this should be fine.
• sha256 selftest: no zero byte in the outpur either.

In the tests we have many many memcmp calls, some even with the all-zero arrays.

[elichai]

• BIP340 tag: Strictly speaking yes, here we compare with a fixed string including zero bytes. Even though it will be weird if someone passed BIP0340/nonce\0AB or something like this. (and see #757 , maybe that's not a great API anyway).

I don't think it's explicit anywhere that the tag even needs to be a string, someone could use the timestamp of their product launch datetime, or their birthday as the tag, and that will contain zeros. (I have 0 idea if this is realistic or not, I do not know of products that use tagged hashes so don't know if they used string/int/bytes as tag)

[real-or-random]

@elichai Indeed but I believe the bug only occurs with the zeros in the constant. We may want to verify/test this.

[roconnor-blockstream]

Is it sufficient to add a -fno-builtin-memcmp flag if it exists, (and maybe disable it if some autotools stuff has run and was unable to find the bug)?

(I have verified that my tests in https://github.com/bitcoin-core/secp256k1/pull/822 pass when -fno-builtin-memcmp is used.)

[real-or-random]

If "-fno-builtin-memcmp" is sufficient that sounds good. I think it would still be advisable to include an explicit memcmp test if no-builtin-memcmp is the solution

We could even include a self-test but I'm not sure about this.

And I'm still not sure if shipping our function is just better, even though it's "extremely dumb" as to your adequate summary. Pragmatically, the implementation is trivial and will just work everywhere without any compiler detection magic etc. edit: Moreover, if the fix is in the code and not in the compiler flags, it's possible to use check the GCC version in the preprocessor, if we want to do this.

[roconnor-blockstream]

If we do that will we be able to detect indirect calls to memcmp (I'm thinking via other libc calls)? In that sense -fno-builtin-memcmp is more robust.

[roconnor-blockstream]

how does a secp256k1_memcmp help change behaviour in other compilation units?

[sipa]

(I'm thinking via other libc calls)

Well we're not going to be able to re-build libc. If there is an indirect bug due to libc being compiled with gcc and its memcmp calls working incorrectly, that would be a bug in the resulting libc library, and nothing we can do about that (except minimizing how much we rely on libc).

The compiler can in some cases "emit" memcmp calls automatically, though. I don't know if that's the case in our codebase, and I don't know if that's strictly for situations where a builtin wouldn't/can't be used - but if that is somehow subject to the same bug, having a custom memcmp function may not be enough.

[sipa]

Parallel Bitcoin Core issue: https://github.com/bitcoin/bitcoin/issues/20005

[roconnor-blockstream]

Oh sorry I didn't mean fixing libc. I mean that the compiler hypothetically inlining some call to libc that in turn calls memcmp, that then gets optimized. I'm not familiar enough with C to have anything in particular in mind, so maybe it just isn't a thing to worry about. TBH I was really thinking of something analogous to std::lexicographical_compare.

[sipa]

The compiler can't inline calls to libc, as it doesn't know what is in the called functions.

What is possible is that some functionality is implemented in libc headers, through inline functions or other builtins, that directly call memcmp/__builtin_memcmp. I can't find any instances of this in my system C headers (except the definition of memcmp itself), though there are a few in STL C++ headers.

[roconnor-blockstream]

That is good to hear.

[elichai]

The compiler can't inline calls to libc, as it doesn't know what is in the called functions.

I don't believe this is true, a compiler target also encodes the exact libc variant that is used, and the compiler can use that knowledge to its advantage (see #/776 for example) a few examples of how without headers the compiler can remove calls to libc and replace them with equivalent instructions while assuming those calls don't have side effects. (and are well known) https://godbolt.org/z/EKe4rx

EDIT: I see now that @sipa probably commented on this sentence by @roconnor-blockstream

I mean that the compiler hypothetically inlining some call to libc that in turn calls memcmp

I still believe this could happen, just like gcc turns this code into a "return 0":

#include <stddef.h>
void *calloc(size_t nmemb, size_t size);
int zeroed_alloc(int num) {
    int* p = calloc(num, sizeof(int));
    int ret = *p;
    free(p);
    return ret;
}

[real-or-random]

Given that we have some evidence that this does not happen when the GCC knows that the return value is compared with != 0 or == 0, I tend towards ignoring the issue. This bug looked very bad but in the end the scope is very limited. As long as our code is not affected, this is not much different from hundreds of other compiler bugs (e.g. #585).

Of course #825 is a simple fix but it's somewhat arbitrary then.

See also https://github.com/bitcoin/bitcoin/issues/20005#issuecomment-699078122, which does not show any potential issues in secp256k1.

[sipa]

@elichai Sure, the compiler may know things about how C standard library functions behave (because they're specified by the standard, or because it knows additional promises the specifically used C standard library used makes). But (in general) it cannot actually look at the compiled library object code and inline it (in theory LTO could change that, but there is no LTO done for glibc IIRC). So just the fact that a particular function inside glibc is written using memcmp isn't relevant - except to the extent that it may be miscompiled inside glibc itself - and there is nothing we can do about that.

[sipa]

@real-or-random I don't know - even with evidence that the current codebase is unaffected, it's still scary - evidenced by the fact that we hit it randomly in PR #822 (thankfully in test-only code, but it could have been elsewhere).

[real-or-random]

If people feel we should do #825, then I'm not against this. It certainly won't hurt.

[elichai]

@roconnor-blockstream

I rebuilt bitcoin-0.20.1 (including libsecp256k1) using emit_diagnostic, and I also did not get any miscompiled memcmp messages.

Can you also try this on libsecp with all the features on + tests?

[roconnor-blockstream]

We can make secp256k1_memcmp, but is solving the issue for libsecp256k1 meaningful if we don't solve it for bitcoin?

[roconnor-blockstream]

Still nothing prevents reintroduction of memcmp other than diligence.

[sipa]

Let's keep this open to discuss how an accidental memcmp can be prevent.

CI could do a simple grep for the word memcmp in the source code?

[roconnor-blockstream]

For reference real-or-random posted a clang-query command at https://github.com/bitcoin-core/secp256k1/pull/825#issuecomment-703624238.

[real-or-random]

If there is some CI test it could check if any function outside of the library is called, except for whitelisted ones (memset, memcpy, malloc, and free, I believe), no? Maybe also make sure that malloc and free are only called via the wrapper functions. That might be useful independently of the memcmp concerns.

Hm, do we really want to restrict ourselves to a small list of standard library functions? I don't think the standard library is bad per se. Compiler bugs can happen everywhere, not only in calls to the standard library. Moreover, new calls are easily spotted in code review. I think memcmp is simply different because one needs to remember that memcmp is special.

If you want to give it a try: clang-query src/secp256k1.c -c 'match callExpr(allOf(unless(isExpansionInSystemHeader()), callee(functionDecl(isExpansionInSystemHeader()))))' This matches all calls to functions declared in system headers, unless the call itself happens in a system header.

[roconnor-blockstream]

If we are going to whitelist standard library functions, and I'm not arguing here that we should or shouldn't, one possible solution is to write our own header of standard library prototypes from our whitelist and disallow all system include files. That said I don't know how to enforce that system includes are disallowed.

[elichai]

That said I don't know how to enforce that system includes are disallowed.

-nostdinc :), the main problem is stdint.h, which we want to manage for us all the int types in different targets

[real-or-random]

See also #833

[roconnor-blockstream]

As fanquake noted in https://github.com/bitcoin/bitcoin/issues/20005#issuecomment-1205264613, this is fixed in GCC 10.3 and above.

[benma]

I just lost an afternoon trying to debug a valgrind false positive.

https://github.com/bitcoin-core/secp256k1/pull/1140/files#diff-3fe8f8fa0b765ad49f70d6c32f6a865be48faeb3c8d6dd5f8c274ca546ef5b61R1111 (click 'Load diff' on tests_impl.h).

The line

           CHECK(memcmp(output, input, sizeof(output)) == 0);

resulted in this CI failure:

https://github.com/bitcoin-core/secp256k1/actions/runs/11285462388/job/31388294841

==9263== Memcheck, a memory error detector
==9263== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
==9263== Using Valgrind-3.24.0.GIT-lbmacos and LibVEX; rerun with -h for copyright info
==9263== Command: ./tests
==9263== 
test count = 2
random seed = ae250b1a3ee1ceb09ad0acfab0d10ecd
Skipping run_sha256_known_output_tests 1000000 (iteration count too low)
Skipping test_ecmult_constants_sha 2048 (iteration count too low)
Skipping test_ecmult_constants_2bit (iteration count too low)
==9263== Conditional jump or move depends on uninitialised value(s)
==9263==    at 0x7FF81B8D5D07: ???
==9263==    by 0x10001A8C4: ??? (in ./tests)
==9263==    by 0x10001CA1D: ??? (in ./tests)
==9263==    by 0x10003DA27: ??? (in ./tests)
==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
==9263== 
==9263== Use of uninitialised value of size 8
==9263==    at 0x7FF81B8D5D23: ???
==9263==    by 0x10001A8C4: ??? (in ./tests)
==9263==    by 0x10001CA1D: ??? (in ./tests)
==9263==    by 0x10003DA27: ??? (in ./tests)
==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
==9263== 
==9263== Use of uninitialised value of size 8
==9263==    at 0x7FF81B8D5D28: ???
==9263==    by 0x10001A8C4: ??? (in ./tests)
==9263==    by 0x10001CA1D: ??? (in ./tests)
==9263==    by 0x10003DA27: ??? (in ./tests)
==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
==9263== 
==9263== Conditional jump or move depends on uninitialised value(s)
==9263==    at 0x10001A8C7: ??? (in ./tests)
==9263==    by 0x10001CA1D: ??? (in ./tests)
==9263==    by 0x10003DA27: ??? (in ./tests)
==9263==    by 0x10026952D: (below main) (in /usr/lib/dyld)
==9263== 
random run = ae7d7478f2fc4fde34e2625d2948ce83
no problems found
==9263== 
==9263== HEAP SUMMARY:
==9263==     in use at exit: 8,586 bytes in 169 blocks
==9263==   total heap usage: 28,425 allocs, 28,256 frees, 98,898,807,326 bytes allocated
==9263== 
==9263== LEAK SUMMARY:
==9263==    definitely lost: 4,160 bytes in 130 blocks
==9263==    indirectly lost: 0 bytes in 0 blocks
==9263==      possibly lost: 600 bytes in 3 blocks
==9263==    still reachable: 3,826 bytes in 36 blocks
==9263==         suppressed: 0 bytes in 0 blocks
==9263== Rerun with --leak-check=full to see details of leaked memory
==9263== 
==9263== Use --track-origins=yes to see where uninitialised values come from
==9263== For lists of detected and suppressed errors, rerun with: -s
==9263== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 123 from 19)
FAIL tests (exit status: 42)

I could not get valgrind to point me to the right line, so bisecting the line took a very long time. I don't think anything is actually wrong with the code there.

In the end changing memcmp to secp256k1_memcmp_var fixed it.

This happened on macOS x86 for both gcc and clang. The valgrind check on linux worked fine.

Consider adding a CI check that forbids the use uf memcmp(), so no one else has to go through the pain of debugging something like this again :see_no_evil:

edit:

@real-or-random

above you mention

Moreover, new calls are easily spotted in code review. I think memcmp is simply different because one needs to remember that memcmp is special.

This turned out to be a wrong assumption - in my case, no one pointed it out to me in review, and it was very hard for me to figure this one out. If the CI check had been added as discussed above, I would not have lost so much time on this.