Possible bug of cnd_copy
Hello, Thank you for your work of Nettle. I tested the cnd_copy function with the Compiler Explorer. The input is: == #ifndef MINI_GMP_LIMB_TYPE #define MINI_GMP_LIMB_TYPE long #endif typedef unsigned MINI_GMP_LIMB_TYPE mp_limb_t; typedef long mp_size_t; void cnd_copy (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n) { mp_limb_t mask, keep; mp_size_t i; mask = -(mp_limb_t) (cnd !=0); keep = ~mask; for (i = 0; i < n; i++) rp[i] = (rp[i] & keep) + (ap[i] & mask); } == In the generated code, we can see the conditional jump with the variable CND. x86 msvc v19.0 (WINE): https://godbolt.org/z/f88edPe46 IIUC, it is better to use something like NOT_EQUAL (in nettle/pkcs1-sec-decrypt.c) to compute the mask, too. If it is my misunderstanding (like MSVC actually is not supported), sorry in advance. I'm learning important things from Nettle implementation. (Thanks again for that.) -- signature.asc Description: PGP signature ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
NIIBE Yutaka writes: > In the generated code, we can see the conditional jump with the variable > CND. > > x86 msvc v19.0 (WINE): > https://godbolt.org/z/f88edPe46 > > IIUC, it is better to use something like NOT_EQUAL (in > nettle/pkcs1-sec-decrypt.c) to compute the mask, too. > > If it is my misunderstanding (like MSVC actually is not supported), > sorry in advance. I'm learning important things from Nettle > implementation. (Thanks again for that.) Thanks for the report. I think this deserves fixing (even if 32-bit x86 is not a high priority these days). It's a bit tricky to get the compiler to do the intended thing. It might also help if one could review call sites for cnd_copy and arrange so that they pass always 0 or 1 for cnd argument. I'll be offline the rest of this week, so I will not be able to fix or review stuff until I'm back. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
Hello, again, Today, I found that it would be a bit serious with Clang 17. Niels Möller wrote: > even if 32-bit x86 is not a high priority these days I was not clear enough. It's not only for 32-bit Intel with MSVC, but also for 64-bit Intel with MSVC, as well as ARM and ARM64 with MSVC. Well, for this case, it's not that serious as it's only a conditional jump. * * * I checked other compilers today. With Clang 17, the entire loop is skipped when CND == 0 (64-bit Intel, 32-bit Intel, 64-bit ARM, 32-bit ARM, etc.). For 64-bit Intel, here is the result: x86-64 clang 17.0.1: https://godbolt.org/z/6cYcn6Y1b This would be a bit serious. With GCC 13.2, access to 'ap[i]' may be conditionally executed for some architectures (64-bit Intel, 32-bit Intel, etc., but not for 64-bit ARM and 32-bit ARM), instead of accessed _and_ masked. For 64-bit Intel, here is the result: x86-64 gcc 13.2: https://godbolt.org/z/6En8M5GTz This may affect the cache access pattern. (We can use '-O3 -m32' to see code for 32-bit Intel.) -- ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
NIIBE Yutaka writes: > I checked other compilers today. Thanks for investigating! Questions: 1. Do the changes on branch https://git.lysator.liu.se/nettle/nettle/-/tree/sc-is_zero?ref_type=heads help? 2. If you install valgrind (including header files), do the recently added tests for side-channel silence fail when nettle is built with a problem compiler? They're intended to catch this kind of issues (even if coverage isn't yet that great). If it's too difficult or too brittle to get compilers to do the intended thing, we'll have to add assembly implementation for all archs of interest. I think there were similar issues, in particular with clang, for gmp's mpn_sec_tabselect, and that's now in assembly for the many archs. It's unfortunate if assembly is needed for security, not just performance, but that's already the case for AES, where the generic implementation is leaky. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
Hello, Niels Möller wrote: > 1. Do the changes on branch >https://git.lysator.liu.se/nettle/nettle/-/tree/sc-is_zero?ref_type=heads >help? Yes. It helps. I confirmed the function cnd_copy has no problem with the change (removing != 0, and require callers to use 0/1), for the cases I found, using the Compiler Exprorer. > 2. If you install valgrind (including header files), do the recently >added tests for side-channel silence fail when nettle is built with a >problem compiler? They're intended to catch this kind of issues (even >if coverage isn't yet that great). I don't have theose compilers, but simply use the Compiler Explorer as a network service. Thus, I can't test that way. Well, I just found that Clang 17 is now available in Debian sid (on 2023-10-31), I can test with Clang 17. I'll test. Thank you for your quick reply. -- ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
Hello, NIIBE Yutaka wrote: > I can test with Clang 17. I'll test. The particular tests (using valgrind) do not fail with Clang 17. I checked the assembler output, and confirmed no issues. With artifically modified source (so that it can replicate cnd_copy problem): == diff --git a/cnd-memcpy.c b/cnd-memcpy.c index 4aaee78b..1a7bbcf6 100644 --- a/cnd-memcpy.c +++ b/cnd-memcpy.c @@ -41,10 +41,10 @@ cnd_memcpy(int cnd, volatile void *dst, const volatile void *src, size_t n) const volatile unsigned char *sp = src; volatile unsigned char *dp = dst; volatile unsigned char c; - volatile unsigned char m; + unsigned char m; size_t i; - m = -(unsigned char) cnd; + m = -(unsigned char) (cnd != 0); for (i = 0; i < n; i++) { == Build of Clang 17 with -O3, it correctly detects the problem. == ==71789== Conditional jump or move depends on uninitialised value(s) ==71789==at 0x48C6BBB: nettle_cnd_memcpy (../cnd-memcpy.c:51) ==71789==by 0x10C946: cnd_memcpy_for_test (../../testsuite/cnd-memcpy-test.c:14) ==71789==by 0x10C946: test_main (???:36) ==71789==by 0x10CFC4: main (../../testsuite/testutils.c:173) ==71789== ==71789== ==71789== Exit program on first error (--exit-on-first-error=yes) FAIL: sc-cnd-memcpy [...] ==71811== Conditional jump or move depends on uninitialised value(s) ==71811==at 0x48C6BBB: nettle_cnd_memcpy (../cnd-memcpy.c:51) ==71811==by 0x485EB68: _nettle_pkcs1_sec_decrypt (../pkcs1-sec-decrypt.c:82) ==71811==by 0x10C94E: pkcs1_decrypt_for_test (../../testsuite/pkcs1-sec-decrypt-test.c:14) ==71811==by 0x10C94E: test_main (???:41) ==71811==by 0x10D524: main (../../testsuite/testutils.c:173) ==71811== ==71811== ==71811== Exit program on first error (--exit-on-first-error=yes) FAIL: sc-pkcs1-sec-decrypt == So, I think that the tests itself work well. -- ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
Re: Possible bug of cnd_copy
NIIBE Yutaka writes: > Niels Möller wrote: >> 1. Do the changes on branch >>https://git.lysator.liu.se/nettle/nettle/-/tree/sc-is_zero?ref_type=heads >>help? > > Yes. It helps. I confirmed the function cnd_copy has no problem > with the change (removing != 0, and require callers to use 0/1), > for the cases I found, using the Compiler Exprorer. Thanks for checking. I've now fixed a few compile issues from the CI builds, and merged this branch. Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se