Switch to our own memcmp function

real-or-random commented at 10:16 am on September 24, 2020: contributor

Fixes #823.

Fwiw, I considered to make this a constant-time function but didn’t do it in the end. Most constant-time memcmp replacements are actually only inequality checks but we need a real memcmp which outputs which one of the arguments is larger.

If you look at crypto libraries, there are a few candidates but I found this overkill for our use case https://github.com/jedisct1/libsodium/blob/a8fa837aacd310bc08fa72705a738fafc2513125/src/libsodium/sodium/utils.c#L239 https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/string/timingsafe_memcmp.c?rev=1.1&content-type=text/x-cvsweb-markup

If we need a constant-time function in the future, it’ll probably be only for equality/inequality, and then we can add the standard “OR of byte-wise XOR” implementation.

Switch to our own memcmp function

Fixes #823.

f5f1202b62

real-or-random cross-referenced this on Sep 25, 2020 from issue memcmp may be miscompiled by GCC by real-or-random

in src/util.h:221 in f5f1202b62

215@@ -216,6 +216,21 @@ static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {
216     }
217 }
218 
219+/** Semantics like memcmp. Variable-time.
220+   We use this to avoid possible compiler bugs with memcmp, e.g., a bug in certain versions of GCC 9 and 10. */
221+int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n) {

sipa commented at 6:25 pm on September 26, 2020:

Make static please.

roconnor-blockstream commented at 10:09 am on October 5, 2020:

Are we required to follow the const void * signature? Should we make it const unsigned char *?

sipa commented at 6:15 pm on October 11, 2020:

It seems that would need more code changes, as callers in some places expect to be able to pass a pointer to other objects.

roconnor-blockstream commented at 6:30 pm on October 11, 2020:

Oh I see. This void thing is really subversive.

in src/util.h:220 in f5f1202b62

215@@ -216,6 +216,21 @@ static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {
216     }
217 }
218 
219+/** Semantics like memcmp. Variable-time.
220+   We use this to avoid possible compiler bugs with memcmp, e.g., a bug in certain versions of GCC 9 and 10. */

sipa commented at 6:25 pm on September 26, 2020:

Link to the bug? So that it’s easy to re-assess in the future whether this is still needed.

real-or-random cross-referenced this on Sep 29, 2020 from issue Increase precision of g1 and g2. by roconnor-blockstream

roconnor-blockstream commented at 10:07 am on October 5, 2020: contributor

Wasn’t the plan to get rid of string.h entirely? Thus needed to replace memset as well?

real-or-random commented at 10:47 am on October 5, 2020: contributor

Wasn’t the plan to get rid of string.h entirely? Thus needed to replace memset as well? @gmaxwell said in #823: (perhaps even memcpy too, and eliminate the string.h usage)

But this was not discussed further, so I sticked to only memcmp for this PR.

I think I’d like to see some benchmarks before we decide to get rid of more functions. memcpy is used in the hashing code, and memset will be used a lot in cleaning up secret after #636 (which I have been procrastinating on for too long, I know…). And this can make a difference, see e.g., #636 (comment).

roconnor-blockstream commented at 11:53 am on October 5, 2020: contributor

I don’t understand what this PR is trying to achieve. You are replacing occurrences of memcmp that are not believed to be miscompiled by GCC 9 & 10.

real-or-random commented at 12:06 pm on October 5, 2020: contributor

I don’t understand what this PR is trying to achieve. You are replacing occurrences of memcmp that are not believed to be miscompiled by GCC 9 & 10.

I’m not the best person to answer this because I tend to agree, see #823 (comment). But since this PR does not make our code worse (no performance penalty, small amount of added code), I’m ok with working on it.

roconnor-blockstream commented at 12:12 pm on October 5, 2020: contributor

I think the worry is about introducing code that unwittingly encounters this bug in the future (https://github.com/bitcoin-core/secp256k1/issues/823#issuecomment-699459852). I thought maybe removing string.h might help achieving that because without the header file, it is difficult to use memcmp (though how to stop the reintroduction of the header?). Otherwise, it seems like we need a linter step or something to disallow memcmp added to this PR.

real-or-random commented at 1:08 pm on October 5, 2020: contributor

Well we could add some linter script that uses grep to check whether all instances of the memcmp string are actually secp256k1_memcmp. But that’s … weird. It doesn’t understands comments, other identifiers, etc. Real linting is only possible in the compiler. It would be interesting to look into tools like clang-query which can give you a lot of insights that are normally internal to the compiler, and I’d love to use this as a linter for some other stuff, e.g., integer divisions. But this sounds like it’s not in the scope of this PR. :P

real-or-random commented at 1:15 pm on October 5, 2020: contributor

It would be interesting to look into tools like clang-query which can give you a lot of insights that are normally internal to the compiler, and I’d love to use this as a linter for some other stuff, e.g., integer divisions. But this sounds like it’s not in the scope of this PR. :P

If someone wants to give it a try, this looks like a nice start: https://stackoverflow.com/a/31740134 maybe it’s indeed a one-liner.

edit: yes:

0clang-query src/secp256k1.c -c 'match callExpr(callee(functionDecl(hasName("memcmp"))))'

sipa commented at 3:56 pm on October 5, 2020: contributor

You could also define memcmp to be a macro that just turns into an #error “Use secp256k1_memcmp_var instead please”.

real-or-random commented at 3:59 pm on October 5, 2020: contributor

You could also define memcmp to be a macro that just turns into an #error “Use secp256k1_memcmp_var instead please”.

Indeed. I’m not sure if I like this because that’s UB according to the standard. Though I don’t think any sane compiler in this world will have any issues with this.

roconnor-blockstream commented at 4:37 pm on October 6, 2020: contributor

Technically the existence of a function named memczero is also UB, so I don’t know by what measure we characterize some forms of UB over others.

real-or-random commented at 5:50 pm on October 6, 2020: contributor

Technically the existence of a function named memczero is also UB, so I don’t know by what measure we characterize some forms of UB over others.

If I had known that this is UB when it we introduced memczero, I would have pointed this out.

gmaxwell commented at 7:34 pm on October 6, 2020: contributor

Damnit, I forgot that “mem[lowercase]” was reserved, fix it– don’t just gripe.

Some kinds of “technically not proper” may be excusable when its the only way to accomplish an intentional end and also extremely unlikely to cause problems – I’d put e.g. using a macro that is never used past definition to nuke a function that shouldn’t be called into that bin – but using a reserved pattern to name a function that we do call I wouldn’t. That memczero could just as easily be secp256k1_memczero even though it has no external linkage. It’s also extremely likely to cause problems, but its an entirely unforced error. If some day a sufficiently smart linter or compiler flag starts complaining about something like it would have to get fixed anyways to satisfy the linter.

roconnor-blockstream commented at 8:07 pm on October 6, 2020: contributor

I didn’t mean to sound like I was griping. I didn’t know about the “mem[lowercase]” reserved function name thing until today. … My reaction upon reading about it (and function names beginning with “is[lowercase]” and “to[lowercase]”) was C’s definition of UB was simply reaching absurd proportions and that it wasn’t worth fixing. From your reaction, it would seem that it isn’t as absurd as I thought.

I’ve filed #829 to begin with.

sipa cross-referenced this on Oct 11, 2020 from issue Rip out non-endomorphism code + dependencies by sipa

sipa commented at 6:15 pm on October 11, 2020: contributor

PR that merges this (with some comments addressed) with #822 and #826: #830

sipa cross-referenced this on Oct 11, 2020 from issue Rip out non-endomorphism code by sipa

real-or-random commented at 8:51 am on October 13, 2020: contributor

Closing in favor of #830

real-or-random closed this on Oct 13, 2020

sipa referenced this in commit c6b6b8f1bb on Oct 14, 2020

Switch to our own memcmp function #825