Constant-time behaviour test using valgrind memtest. #708

1. 
   gmaxwell commented at 12:05 pm on January 8, 2020: contributor

   Valgrind does bit-level tracking of the “uninitialized” status of memory, property tracks memory which is tainted by any uninitialized memory, and warns if any branch or array access depends on an uninitialized bit.

   That is exactly the verification we need on secret data to test for constant-time behaviour. All we need to do is tell valgrind our secret key is actually uninitialized memory.

   This adds a valgrind_ctime_test which is compiled if valgrind is installed:

   Run it with libtool –mode=execute: $ libtool –mode=execute valgrind ./valgrind_ctime_test

2. 
   gmaxwell commented at 12:07 pm on January 8, 2020: contributor

   Not completely yet mostly because it finds real but irrelevant non-constant time behaviour!

   I used this approach a couple years ago to originally test the constant time keygen/signing code– I’m not sure if back then it didn’t have checks on the keys being in-range or if I just ignored these because they’re irrelevant.

   Manually ignoring them isn’t an option for a CI runnable shipped test, however.

   It could be suppressed via valgrind suppressions, but I’d actually prefer to fix it if it can be done without making too much of a mess. E.g. if the key is invalid, cmov in a dummy key to sign with then at the end cmov in an empty signature.

   Valgrind suppressions would have a disadvantage of needing to be kept in sync with the code. I also believe the presence of them weakens the valgrind tracing somewhat (the result of the suppressed branch isn’t taint tracked, I think) and could hide issues. (plus, I personally feel like suppressions send a signal of low quality work)

3. 
   gmaxwell commented at 12:08 pm on January 8, 2020: contributor

   Here is the current output:

    0==84274== Conditional jump or move depends on uninitialised value(s)
    1==84274==    at 0x485B060: secp256k1_ec_pubkey_create (secp256k1.c:521)
    2==84274==    by 0x401214: main (valgrind_ctime_test.c:39)
    3==84274== 
    4==84274== Conditional jump or move depends on uninitialised value(s)
    5==84274==    at 0x485B08C: secp256k1_ec_pubkey_create (secp256k1.c:521)
    6==84274==    by 0x401214: main (valgrind_ctime_test.c:39)
    7==84274== 
    8==84274== Conditional jump or move depends on uninitialised value(s)
    9==84274==    at 0x485A98D: secp256k1_ecdsa_sign (secp256k1.c:465)
   10==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   11==84274== 
   12==84274== Conditional jump or move depends on uninitialised value(s)
   13==84274==    at 0x485A9AF: secp256k1_ecdsa_sign (secp256k1.c:465)
   14==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   15==84274== 
   16==84274== Conditional jump or move depends on uninitialised value(s)
   17==84274==    at 0x485AA66: secp256k1_ecdsa_sign (secp256k1.c:475)
   18==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   19==84274== 
   20==84274== Conditional jump or move depends on uninitialised value(s)
   21==84274==    at 0x485AA88: secp256k1_ecdsa_sign (secp256k1.c:475)
   22==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   23==84274== 
   24==84274== Conditional jump or move depends on uninitialised value(s)
   25==84274==    at 0x485AD9D: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:307)
   26==84274==    by 0x485AD9D: secp256k1_ecdsa_sign (secp256k1.c:476)
   27==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   28==84274== 
   29==84274== Conditional jump or move depends on uninitialised value(s)
   30==84274==    at 0x485AE20: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:310)
   31==84274==    by 0x485AE20: secp256k1_ecdsa_sign (secp256k1.c:476)
   32==84274==    by 0x40134B: main (valgrind_ctime_test.c:45)
   33==84274== 
   

4. 
   gmaxwell commented at 12:12 pm on January 8, 2020: contributor

   Here is a demonstration that it can find real bugs– e.g.

   0--- a/src/ecmult_gen_impl.h
   1+++ b/src/ecmult_gen_impl.h
   2@@ -152 +152 @@ static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp25
   3-        secp256k1_gej_add_ge(r, r, &add);
   4+        secp256k1_gej_add_ge_var(r, r, &add, NULL);
   

   0==84996== Conditional jump or move depends on uninitialised value(s)
   1==84996==    at 0x484AAB9: secp256k1_fe_normalizes_to_zero_var (field_5x52_impl.h:206)
   2==84996==    by 0x484FDDC: secp256k1_gej_add_ge_var.constprop.0 (group_impl.h:443)
   3==84996==    by 0x48503F3: secp256k1_ecmult_gen (ecmult_gen_impl.h:152)
   4==84996==    by 0x4859152: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:284)
   5==84996==    by 0x4859152: secp256k1_ecdsa_sign (secp256k1.c:476)
   6==84996==    by 0x40134B: main (valgrind_ctime_test.c:45)
   

5. 
   gmaxwell commented at 12:34 pm on January 8, 2020: contributor

   And a demonstration that it catches secrets in array indexes:

   0--- a/src/ecmult_gen_impl.h
   1+++ b/src/ecmult_gen_impl.h
   2@@ -137,0 +138 @@ static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp25
   3+        adds = (*ctx->prec)[j][bits];
   4@@ -149 +150 @@ static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp25
   5-            secp256k1_ge_storage_cmov(&adds, &(*ctx->prec)[j][i], i == bits);
   6+            /*secp256k1_ge_storage_cmov(&adds, &(*ctx->prec)[j][i], i == bits);*/
   

   0==86172== Use of uninitialised value of size 8
   1==86172==    at 0x4850C3E: secp256k1_ecmult_gen (ecmult_gen_impl.h:138)
   2==86172==    by 0x485AD12: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:284)
   3==86172==    by 0x485AD12: secp256k1_ecdsa_sign (secp256k1.c:476)
   4==86172==    by 0x40134B: main (valgrind_ctime_test.c:45)
   

6. 
   gmaxwell commented at 12:45 pm on January 8, 2020: contributor

   So one possibility for the s==0 loop in signing would be to add a VALGRIND_MAKE_MEM_DEFINED to libsecp256k1.c on the result of the is_zero test. I think that would be cleanest.

   E.g. if the library is compile with valgrind headers available, it could make_defined the result of the zero comparison. This behaviour could even be controlled by a flag stored in the context, so as to not diminish test sensitivity outside of CT tests. The valgrind macros add ~6 instructions to the code… and this would not be inside a performance critical loop.

   The overflow case I think should just be handled by running on dummy data.

7. 
   gmaxwell commented at 3:45 pm on January 8, 2020: contributor

   See #709.
8. 
   gmaxwell commented at 6:29 am on January 9, 2020: contributor

   todo: freeking valgrind m4 script doesn’t actually check if the valgrind headers are available.
9. 
   gmaxwell commented at 6:11 pm on January 9, 2020: contributor

   The integer divide instruction is variable time essentially everywhere. Normally division by a constant gets converted into something else by the compiler, but not every compiler or every optimization does in every case.

   In ECDH there was an unsigned /2 where GCC emits an idiv when compiled with -Os. I modified valgrind memcheck to throw an error on undefined input into divisions and this successfully detects the case in ECDH and none elsewhere in the code.

   Unfortunately depending on a modified valgrind starts creating the same problem that other constant time analysis tools have– they’re hard to keep working. This PR is still highly useful without this functionality, I just wanted to make a note of this limitation and the fact that it’s not particularly hard to work around.

10. 
    gmaxwell commented at 6:13 pm on January 10, 2020: contributor

    I updated with the ECDH and randomization tests.
11. 
    gmaxwell commented at 8:25 pm on January 12, 2020: contributor

    GCC 9.2.1 on POWER9 emits a lot of branches for carries in the 32-bit scalar code. :( The issue seems to be similar to the one in the ECDH code. Those comparisons aren’t reliably turned into constant time assembly.
12. 
    practicalswift commented at 10:54 pm on January 14, 2020: contributor

    Concept ACK

    Very nice and thanks for implementing!

    DJB demoed this clever technique in the “High-assurance crypto software” talk at 36C3:

    

    

13. 
    sipa commented at 11:22 pm on January 14, 2020: contributor

    @practicalswift Yes, that’s where we learned about it.
14. 
    gmaxwell commented at 8:37 am on January 15, 2020: contributor

    @sipa no it isn’t. I first used it on libsecp256k1 years ago (long before the ECDH module was written), you just don’t remember.

    https://moderncrypto.org/mail-archive/curves/2015/000641.html

    I was unaware of the video/talk. I’ll check it out.

    This PR was created because I was surprised that no one had tested the ECDH code but were talking about making it non-experimental and thought that packaging up the test would be the only way to make it likely that anyone would bother testing in the future.

15. 
    sipa commented at 3:57 pm on January 15, 2020: contributor

    @gmaxwell Ah, interesting coincidence in that case.
16. 
    sipa commented at 3:59 pm on January 15, 2020: contributor

    Concept and code review ACK. What is still WIP about this?
17. 
    gmaxwell commented at 6:27 pm on January 15, 2020: contributor

    I added tests for the remaining seckey operations. I also changed it to just check for the memcheck header directly instead of including the big valgrind m4 macro that didn’t actually check for the header. I think this is done now, but it probably doesn’t make sense to merge it until it tests clean (so as to not confuse someone doing a bisection). See #710.
18. gmaxwell renamed this:
    [WIP] Constant-time behaviour test using valgrind memtest.
    Constant-time behaviour test using valgrind memtest.
    on Jan 15, 2020
19. 
    gmaxwell commented at 6:47 pm on January 15, 2020: contributor

    @practicalswift Looks like from the video that DJB may be unaware of the memcheck macros. The issue with the approach he’s using is that (1) valgrind can incorrectly think the memory is initialized, particularly its a stack variable, and (2) the compiler may be smart enough to realize the memory is uninitialized and optimize in ways that undermine the tests. Use of the memcheck macros addresses both of those issues.
20. 
    real-or-random commented at 11:18 pm on January 18, 2020: contributor

    Do you think it makes sense to add tests for the tweak functions? The secret key is clearly a secret in those function but I supposed they should be constant-time in also the tweak?

    edit: This could also be done in a second PR of course.

21. 
    gmaxwell commented at 3:52 am on January 19, 2020: contributor

    @real-or-random I did three days ago.

    (also fixes to them in the other PR)

22. 
    real-or-random commented at 10:30 am on January 19, 2020: contributor

    @real-or-random I did three days ago.

    Nevermind, I missed it.

23. 
    gmaxwell commented at 1:11 am on February 11, 2020: contributor

    I rebased this on #710 because I intend for it to be merged after.
24. gmaxwell cross-referenced this on Feb 11, 2020 from issue Eliminate harmless non-constant time operations on secret data. by gmaxwell
25. in Makefile.am:96 in bc53580baa outdated

    92@@ -93,6 +93,12 @@ if USE_TESTS
    93 noinst_PROGRAMS += tests
    94 tests_SOURCES = src/tests.c
    95 tests_CPPFLAGS = -DSECP256K1_BUILD -I$(top_srcdir)/src -I$(top_srcdir)/include $(SECP_INCLUDES) $(SECP_TEST_INCLUDES)
    96+if VALGRIND_ENABLED
    

    ---

    ---

    

    jonasnick commented at 4:57 pm on February 11, 2020:

    Ideally we’d print the value VALGRIND_ENABLED option along with the other options at the end of the configure script.

    ---

    

    gmaxwell commented at 0:00 am on February 12, 2020:

    done
26. in src/valgrind_ctime_test.c:46 in bc53580baa outdated

    41+        msg[i] = i + 1;
    42+    }
    43+
    44+    ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_DECLASSIFY);
    45+
    46+    /* Test keygen. */
    

    ---

    ---

    

    jonasnick commented at 4:58 pm on February 11, 2020:

    We should also test seckey_verify

    ---

    

    gmaxwell commented at 11:57 pm on February 11, 2020:

    It’s there, right after ECDH.
27. 
    jonasnick commented at 5:02 pm on February 11, 2020: contributor

    obvious concept ACK is obious

    How about we add this to make check? That way travis would also run it.

    valgrind_ctime_test should be in .gitignore

28. 
    gmaxwell commented at 0:13 am on February 12, 2020: contributor

    It’s not clear to me how to override the TESTS_ENVIROMENT for only a single test w/ make check, and I doubt we want to make all the tests run in valgrind by default (a make check-valgrind however would be fine).
29. 
    gmaxwell commented at 3:11 am on February 12, 2020: contributor

    FWIW, the tests passes on 32-bit arm with and without asm for me. Though I note that when openssl tests are enable all the test libraries are getting linked to libcrypto and that makes the old version of valgrind I have on my 32bit arm die with an unknown instruction error.
30. 
    jonasnick commented at 5:00 pm on February 13, 2020: contributor

    It’s not clear to me how to override the TESTS_ENVIROMENT for only a single test w/ make check

    In that case I’m fine with leaving as is for now. If make check-valgrind runs everything make check under valgrind it’s too inflexible because the valgrind_ctime_test finishes much faster than valground tests. I created a commit that runs valgrind_ctime_test in all travis test configurations (excluding BUILD=distcheck) https://github.com/jonasnick/secp256k1/pull/12. Feel free to cherry-pick.

    Would be helpful to mention valgrind_ctime_test in the README.

31. Constant-time behaviour test using valgrind memtest.

    Valgrind does bit-level tracking of the "uninitialized" status of memory,
     property tracks memory which is tainted by any uninitialized memory, and
     warns if any branch or array access depends on an uninitialized bit.
    
    That is exactly the verification we need on secret data to test for
     constant-time behaviour. All we need to do is tell valgrind our
     secret key is actually uninitialized memory.
    
    This adds a valgrind_ctime_test which is compiled if valgrind is installed:
    
    Run it with libtool --mode=execute:
    $ libtool --mode=execute valgrind ./valgrind_ctime_test

    3d2302257f
32. Run valgrind_ctime_test in travis 08fb6c4926
33. jonasnick approved
34. 
    jonasnick commented at 9:31 pm on February 27, 2020: contributor

    ACK 2da822de64a3482befc0de53cc56b9e8904ad68d
35. 
    sipa commented at 7:54 pm on February 29, 2020: contributor

    ACK 08fb6c49261f8aefaaa8ea2ca6d84a53e037e812
36. 
    real-or-random commented at 11:10 am on March 1, 2020: contributor

    ACK 2da822d

    That’s not the current commit. :p

    I’ll have a look next week.

37. jonasnick approved
38. 
    jonasnick commented at 3:12 pm on March 1, 2020: contributor

    ACK 08fb6c49261f8aefaaa8ea2ca6d84a53e037e812
39. 
    real-or-random commented at 3:47 pm on March 3, 2020: contributor

    ACK 08fb6c49261f8aefaaa8ea2ca6d84a53e037e812
40. real-or-random approved
41. real-or-random merged this on Mar 3, 2020
42. real-or-random closed this on Mar 3, 2020

    ---

43. 
    real-or-random commented at 10:05 am on March 4, 2020: contributor

    @gmaxwell We forgot secp256k1_ecdsa_sign_recoverable here. Do you want to open a second PR for this? https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/main_impl.h#L123

    I think the code is (or now: was) very similar to the ordinary signing. I wonder if we should move more of the common code to ecdsa_impl.h and make the public API functions just very thin wrappers. This avoids code duplication, and without code duplication we probably wouldn’t have missed secp256k1_ecdsa_sign_recoverable here.

44. real-or-random cross-referenced this on Mar 4, 2020 from issue Erroneous comment and VERIFY_CHECK in ecdsa_sig_sign by LLFourn
45. 
    jonasnick commented at 8:35 pm on March 12, 2020: contributor

    @real-or-random abstracting away the common code of sign and sign_recoverable is also useful for sign-to-contract. The PR even contains what you’re suggesting https://github.com/bitcoin-core/secp256k1/pull/669/commits/ab4fd520cc9f995fb1d2ffe825a2747671b9848d.
46. 
    gmaxwell commented at 9:31 am on March 13, 2020: contributor

    @real-or-random Seems I missed it, sorry. :( I don’t think I have the time or energy to see another PR through to completion here right now. Exploiting a refactor that increases code sharing sounds like a good idea.
47. jonasnick cross-referenced this on Mar 23, 2020 from issue Make use of constant time ecdsa_sign code in ecdsa_sign_recoverable by jonasnick
48. 
    prusnak commented at 10:38 am on March 26, 2020: none

    Just a side note to give a broader picture to the topic: these tests are great, but they don’t guarantee the execution is really constant time. This depends on the processor implementation.

    For example, ARM Cortex-M3 does not have a constant-time multiply instruction: it takes 1-2 cycles less if both multiplicands fit into 16 bites, or either multiplicand is 0, or either multiplicand is 2^n. ARM Cortex-M4 is not affected.

    More info about different architectures: https://www.bearssl.org/ctmul.html

49. 
    elichai commented at 10:47 am on March 26, 2020: contributor

    Just a side note to give a broader picture to the topic: these tests are great, but they don’t guarantee the execution is really constant time. This depends on the processor implementation.

    Yep. same in MSVC: #711 altough that’s at the OS level, but yeah there’s also the CPU level, but that’s quite harder to check and fix

50. 
    gmaxwell commented at 11:16 am on March 26, 2020: contributor

    prusnak: indeed, we were aware. It’s not terribly difficult to modify valgrind to consider whatever conditions you want (I used a modified version that also catches div/mod non-constant timeness, for example). Getting constant time behaviour on that arm m3 stuff though seems like a performance killing nightmare…
51. 
    real-or-random commented at 12:28 pm on March 26, 2020: contributor

    @prusnak Indeed we’re aware but it seems very hard to protect against this. I’m curious if you had implemented any countermeasures against this on Cortex-M3 (before the switch to our library here)?
52. 
    prusnak commented at 12:34 pm on March 26, 2020: none

    For us, this is not a big problem because you can’t do signing in a non-interactive way and you need to enter the PIN on boot anyway.
53. deadalnix referenced this in commit 1147a52772 on Mar 29, 2020
54. deadalnix referenced this in commit 3767e4c2f8 on Mar 30, 2020
55. practicalswift cross-referenced this on Apr 16, 2020 from issue Integrating with OSS-Fuzz by Google-Autofuzz
56. benma cross-referenced this on Apr 21, 2020 from issue rebase on bitcoin-core/secp256k1 by benma
57. elichai cross-referenced this on May 27, 2020 from issue Recovery signing: add to constant time test, and eliminate non ct operators by elichai
58. real-or-random referenced this in commit 2ed54da18a on Jun 8, 2020
59. sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa
60. fanquake referenced this in commit 8c97780db8 on Jun 13, 2020
61. sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020
62. ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020
63. gmaxwell cross-referenced this on Jul 24, 2020 from issue Add valgrind constant-time test to `make check` by real-or-random
64. real-or-random cross-referenced this on Jul 24, 2020 from issue Constant-time code on POWER9 by real-or-random
65. real-or-random cross-referenced this on Sep 13, 2020 from issue Enable configuring Valgrind support by luke-jr
66. UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021
67. 5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021
68. real-or-random cross-referenced this on Dec 3, 2021 from issue -Wunused-parameter warnings when cross-compiling for riscv64-linux-gnu by hebasto
69. gades referenced this in commit d855cc511d on May 8, 2022

Contributors
gmaxwell practicalswift sipa real-or-random jonasnick prusnak elichai