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 #822 (comment)

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 Nonce functions #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 Nonce functions #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 #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: bitcoin/bitcoin#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.