* [PATCH] hex2bin: make the function hex_to_bin constant-time @ 2022-04-24 20:54 Mikulas Patocka 2022-04-24 21:30 ` Joe Perches 2022-04-24 21:37 ` Linus Torvalds 0 siblings, 2 replies; 33+ messages in thread From: Mikulas Patocka @ 2022-04-24 20:54 UTC (permalink / raw) To: Linus Torvalds, Andy Shevchenko Cc: dm-devel, linux-kernel, linux-crypto, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz The function hex2bin is used to load cryptographic keys into device mapper targets dm-crypt and dm-integrity. It should take constant time independent on the processed data, so that concurrently running unprivileged code can't infer any information about the keys via microarchitectural convert channels. This patch changes the function hex_to_bin so that it contains no branches and no memory accesses. Note that this shouldn't cause performance degradation because the size of the new function is the same as the size of the old function (on x86-64) - and the new function causes no branch misprediction penalties. I compile-tested this function with gcc on aarch64 alpha arm hppa hppa64 i386 ia64 m68k mips32 mips64 powerpc powerpc64 riscv sh4 s390x sparc32 sparc64 x86_64 and with clang on aarch64 arm hexagon i386 mips32 mips64 powerpc powerpc64 s390x sparc32 sparc64 x86_64 to verify that there are no branches in the generated code. Signed-off-by: Mikulas Patocka <mpatocka@redhat.com> Cc: stable@vger.kernel.org --- lib/hexdump.c | 27 +++++++++++++++++++++------ 1 file changed, 21 insertions(+), 6 deletions(-) Index: linux-2.6/lib/hexdump.c =================================================================== --- linux-2.6.orig/lib/hexdump.c 2022-04-24 18:51:20.000000000 +0200 +++ linux-2.6/lib/hexdump.c 2022-04-24 18:51:20.000000000 +0200 @@ -22,15 +22,30 @@ EXPORT_SYMBOL(hex_asc_upper); * * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad * input. + * + * This function is used to load cryptographic keys, so it is coded in such a + * way that there are no conditions or memory accesses that depend on data. + * + * Explanation of the logic: + * (ch - '9' - 1) is negative if ch <= '9' + * ('0' - 1 - ch) is negative if ch >= '0' + * we "and" these two values, so the result is negative if ch is in the range + * '0' ... '9' + * we are only interested in the sign, so we do a shift ">> 8" --- we have -1 if + * ch is in the range '0' ... '9', 0 otherwise + * we "and" this value with (ch - '0' + 1) --- we have a value 1 ... 10 if ch is + * in the range '0' ... '9', 0 otherwise + * we add this value to -1 --- we have a value 0 ... 9 if ch is in the range '0' + * ... '9', -1 otherwise + * the next line is similar to the previous one, but we need to decode both + * uppercase and lowercase letters, so we use (ch & 0xdf), which converts + * lowercase to uppercase */ int hex_to_bin(char ch) { - if ((ch >= '0') && (ch <= '9')) - return ch - '0'; - ch = tolower(ch); - if ((ch >= 'a') && (ch <= 'f')) - return ch - 'a' + 10; - return -1; + return -1 + + ((ch - '0' + 1) & (((ch - '9' - 1) & ('0' - 1 - ch)) >> 8)) + + (((ch & 0xdf) - 'A' + 11) & ((((ch & 0xdf) - 'F' - 1) & ('A' - 1 - (ch & 0xdf))) >> 8)); } EXPORT_SYMBOL(hex_to_bin); ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-24 20:54 [PATCH] hex2bin: make the function hex_to_bin constant-time Mikulas Patocka @ 2022-04-24 21:30 ` Joe Perches 2022-04-24 21:37 ` Linus Torvalds 1 sibling, 0 replies; 33+ messages in thread From: Joe Perches @ 2022-04-24 21:30 UTC (permalink / raw) To: Mikulas Patocka, Linus Torvalds, Andy Shevchenko Cc: dm-devel, linux-kernel, linux-crypto, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Sun, 2022-04-24 at 16:54 -0400, Mikulas Patocka wrote: > This patch changes the function hex_to_bin so that it contains no branches > and no memory accesses. [] > +++ linux-2.6/lib/hexdump.c 2022-04-24 18:51:20.000000000 +0200 [] > + * the next line is similar to the previous one, but we need to decode both > + * uppercase and lowercase letters, so we use (ch & 0xdf), which converts > + * lowercase to uppercase > */ > int hex_to_bin(char ch) > { > - if ((ch >= '0') && (ch <= '9')) > - return ch - '0'; > - ch = tolower(ch); > - if ((ch >= 'a') && (ch <= 'f')) > - return ch - 'a' + 10; > - return -1; > + return -1 + > + ((ch - '0' + 1) & (((ch - '9' - 1) & ('0' - 1 - ch)) >> 8)) + > + (((ch & 0xdf) - 'A' + 11) & ((((ch & 0xdf) - 'F' - 1) & ('A' - 1 - (ch & 0xdf))) >> 8)); probably easier to read using a temporary for ch & 0xdf int CH = ch & 0xdf; return -1 + ((ch - '0' + 1) & (((ch - '9' - 1) & ('0' - 1 - ch)) >> 8)) + ((CH - 'A' + 11) & (((CH - 'F' - 1) & ('A' - 1 - CH)) >> 8)); ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-24 20:54 [PATCH] hex2bin: make the function hex_to_bin constant-time Mikulas Patocka 2022-04-24 21:30 ` Joe Perches @ 2022-04-24 21:37 ` Linus Torvalds 2022-04-24 21:42 ` Linus Torvalds 2022-04-25 12:07 ` [PATCH v2] " Mikulas Patocka 1 sibling, 2 replies; 33+ messages in thread From: Linus Torvalds @ 2022-04-24 21:37 UTC (permalink / raw) To: Mikulas Patocka Cc: Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Sun, Apr 24, 2022 at 1:54 PM Mikulas Patocka <mpatocka@redhat.com> wrote: > > + * > + * Explanation of the logic: > + * (ch - '9' - 1) is negative if ch <= '9' > + * ('0' - 1 - ch) is negative if ch >= '0' True, but... Please, just to make me happier, make the sign of 'ch' be something very explicit. Right now that code uses 'char ch', which could be signed or unsigned. It doesn't really matter in this case, since the arithmetic will be done in 'int', and as long as 'int' is larger than 'char' as a type (to be really nit-picky), it all ends up working ok regardless. But just to make me happier, and to make the algorithm actually do the _same_ thing on every architecture, please use an explicit signedness for that 'ch' type. Because then that 'ch >= X' is well-defined. Again - your code _works_. That's not what I worry about. But when playing these kinds of tricks, please make it have the same behavior across architectures, not just "the end result will be the same regardless". Yes, a 'ch' with the high bit set will always be either >= '0' or <= '9', but note how *which* one it is depends on the exact type, and 'char' is simply not well-defined. Finally, for the same reason - please don't use ">> 8". Because I do not believe that bit 8 is well-defined in your arithmetic. The *sign* bit will be, but I'm not convinced bit 8 is. So use ">> 31" or similar. Also, I do worry that this is *exactly* the kind of trick that a compiler could easily turn back into a conditional. Usually compilers tend to go the other way (ie turn conditionals into arithmetic if possible), but.. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-24 21:37 ` Linus Torvalds @ 2022-04-24 21:42 ` Linus Torvalds 2022-04-25 9:37 ` David Laight 2022-04-25 12:07 ` [PATCH v2] " Mikulas Patocka 1 sibling, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-04-24 21:42 UTC (permalink / raw) To: Mikulas Patocka Cc: Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Sun, Apr 24, 2022 at 2:37 PM Linus Torvalds <torvalds@linux-foundation.org> wrote: > > Finally, for the same reason - please don't use ">> 8". Because I do > not believe that bit 8 is well-defined in your arithmetic. The *sign* > bit will be, but I'm not convinced bit 8 is. Hmm.. I think it's ok. It can indeed overflow in 'char' and change the sign in bit #7, but I suspect bit #8 is always fine. Still, If you want to just extend the sign bit, ">> 31" _is_ the obvious thing to use (yeah, yeah, properly "sizeof(int)*8-1" or whatever, you get my drift). Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* RE: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-24 21:42 ` Linus Torvalds @ 2022-04-25 9:37 ` David Laight 2022-04-25 11:04 ` Mikulas Patocka 0 siblings, 1 reply; 33+ messages in thread From: David Laight @ 2022-04-25 9:37 UTC (permalink / raw) To: 'Linus Torvalds', Mikulas Patocka Cc: Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz From: Linus Torvalds > Sent: 24 April 2022 22:42 > > On Sun, Apr 24, 2022 at 2:37 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: > > > > Finally, for the same reason - please don't use ">> 8". Because I do > > not believe that bit 8 is well-defined in your arithmetic. The *sign* > > bit will be, but I'm not convinced bit 8 is. > > Hmm.. I think it's ok. It can indeed overflow in 'char' and change the > sign in bit #7, but I suspect bit #8 is always fine. > > Still, If you want to just extend the sign bit, ">> 31" _is_ the > obvious thing to use (yeah, yeah, properly "sizeof(int)*8-1" or > whatever, you get my drift). Except that right shifts of signed values are UB. In particular it has always been valid to do an unsigned shift right on a 2's compliment negative number. David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales) ^ permalink raw reply [flat|nested] 33+ messages in thread
* RE: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-25 9:37 ` David Laight @ 2022-04-25 11:04 ` Mikulas Patocka 2022-04-25 12:59 ` David Laight 0 siblings, 1 reply; 33+ messages in thread From: Mikulas Patocka @ 2022-04-25 11:04 UTC (permalink / raw) To: David Laight Cc: 'Linus Torvalds', Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Mon, 25 Apr 2022, David Laight wrote: > From: Linus Torvalds > > Sent: 24 April 2022 22:42 > > > > On Sun, Apr 24, 2022 at 2:37 PM Linus Torvalds > > <torvalds@linux-foundation.org> wrote: > > > > > > Finally, for the same reason - please don't use ">> 8". Because I do > > > not believe that bit 8 is well-defined in your arithmetic. The *sign* > > > bit will be, but I'm not convinced bit 8 is. > > > > Hmm.. I think it's ok. It can indeed overflow in 'char' and change the > > sign in bit #7, but I suspect bit #8 is always fine. > > > > Still, If you want to just extend the sign bit, ">> 31" _is_ the > > obvious thing to use (yeah, yeah, properly "sizeof(int)*8-1" or > > whatever, you get my drift). > > Except that right shifts of signed values are UB. > In particular it has always been valid to do an unsigned > shift right on a 2's compliment negative number. > > David Yes. All the standard versions (C89, C99, C11, C2X) say that right shift of a negative value is implementation-defined. So, we should cast it to "unsigned" before shifting it. Mikulas ^ permalink raw reply [flat|nested] 33+ messages in thread
* RE: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-25 11:04 ` Mikulas Patocka @ 2022-04-25 12:59 ` David Laight 2022-04-25 13:33 ` Mikulas Patocka 0 siblings, 1 reply; 33+ messages in thread From: David Laight @ 2022-04-25 12:59 UTC (permalink / raw) To: 'Mikulas Patocka' Cc: 'Linus Torvalds', Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz From: Mikulas Patocka > Sent: 25 April 2022 12:04 > > On Mon, 25 Apr 2022, David Laight wrote: > > > From: Linus Torvalds > > > Sent: 24 April 2022 22:42 > > > > > > On Sun, Apr 24, 2022 at 2:37 PM Linus Torvalds > > > <torvalds@linux-foundation.org> wrote: > > > > > > > > Finally, for the same reason - please don't use ">> 8". Because I do > > > > not believe that bit 8 is well-defined in your arithmetic. The *sign* > > > > bit will be, but I'm not convinced bit 8 is. > > > > > > Hmm.. I think it's ok. It can indeed overflow in 'char' and change the > > > sign in bit #7, but I suspect bit #8 is always fine. > > > > > > Still, If you want to just extend the sign bit, ">> 31" _is_ the > > > obvious thing to use (yeah, yeah, properly "sizeof(int)*8-1" or > > > whatever, you get my drift). > > > > Except that right shifts of signed values are UB. > > In particular it has always been valid to do an unsigned > > shift right on a 2's compliment negative number. > > > > David > > Yes. All the standard versions (C89, C99, C11, C2X) say that right shift > of a negative value is implementation-defined. > > So, we should cast it to "unsigned" before shifting it. Except that the intent appears to be to replicate the sign bit. If it is 'implementation defined' (rather than suddenly being UB) it might be that the linux kernel requires sign propagating right shifts of negative values. This is typically what happens on 2's compliment systems. But not all small cpu have the required shift instruction. OTOH all the ones bit enough to run Linux probably do. (And gcc doesn't support '1's compliment' or 'sign overpunch' cpus.) The problem is that the compiler writers seem to be entering a mindset where they are optimising code based on UB behaviour. So given: void foo(int x) { if (x >> 1 < 0) return; do_something(); } they decide the test is UB, so can always be assumed to be true and thus do_something() is compiled away. David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales) ^ permalink raw reply [flat|nested] 33+ messages in thread
* RE: [PATCH] hex2bin: make the function hex_to_bin constant-time 2022-04-25 12:59 ` David Laight @ 2022-04-25 13:33 ` Mikulas Patocka 0 siblings, 0 replies; 33+ messages in thread From: Mikulas Patocka @ 2022-04-25 13:33 UTC (permalink / raw) To: David Laight Cc: 'Linus Torvalds', Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Mon, 25 Apr 2022, David Laight wrote: > From: Mikulas Patocka > > Sent: 25 April 2022 12:04 > > > > On Mon, 25 Apr 2022, David Laight wrote: > > > > > From: Linus Torvalds > > > > Sent: 24 April 2022 22:42 > > > > > > > > On Sun, Apr 24, 2022 at 2:37 PM Linus Torvalds > > > > <torvalds@linux-foundation.org> wrote: > > > > > > > > > > Finally, for the same reason - please don't use ">> 8". Because I do > > > > > not believe that bit 8 is well-defined in your arithmetic. The *sign* > > > > > bit will be, but I'm not convinced bit 8 is. > > > > > > > > Hmm.. I think it's ok. It can indeed overflow in 'char' and change the > > > > sign in bit #7, but I suspect bit #8 is always fine. > > > > > > > > Still, If you want to just extend the sign bit, ">> 31" _is_ the > > > > obvious thing to use (yeah, yeah, properly "sizeof(int)*8-1" or > > > > whatever, you get my drift). > > > > > > Except that right shifts of signed values are UB. > > > In particular it has always been valid to do an unsigned > > > shift right on a 2's compliment negative number. > > > > > > David > > > > Yes. All the standard versions (C89, C99, C11, C2X) say that right shift > > of a negative value is implementation-defined. > > > > So, we should cast it to "unsigned" before shifting it. > > Except that the intent appears to be to replicate the sign bit. > > If it is 'implementation defined' (rather than suddenly being UB) The standard says "If E1 has a signed type and a negative value, the resulting value is implementation-defined." So, it's not undefined behavior. > it might be that the linux kernel requires sign propagating > right shifts of negative values. It may be that some code in the Linux kernel already assumes that right shifts keep the sign. It's hard to say if such code exists. BTW. ubsan warns about left shift of negative values, but it doesn't warn about right shift of negative values. > This is typically what happens on 2's compliment systems. > But not all small cpu have the required shift instruction. > OTOH all the ones bit enough to run Linux probably do. > (And gcc doesn't support '1's compliment' or 'sign overpunch' cpus.) > > The problem is that the compiler writers seem to be entering > a mindset where they are optimising code based on UB behaviour. > So given: > void foo(int x) > { > if (x >> 1 < 0) > return; > do_something(); > } > they decide the test is UB, so can always be assumed to be true > and thus do_something() is compiled away. > > David If it's implementation-defined (rather than undefined), the compiler shouldn't do such optimization. The linux kernel uses "-fno-strict-overflow" which disables some of these UB optimizations. Mikulas ^ permalink raw reply [flat|nested] 33+ messages in thread
* [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-04-24 21:37 ` Linus Torvalds 2022-04-24 21:42 ` Linus Torvalds @ 2022-04-25 12:07 ` Mikulas Patocka 2022-04-25 17:53 ` Linus Torvalds 2022-05-04 8:38 ` Stafford Horne 1 sibling, 2 replies; 33+ messages in thread From: Mikulas Patocka @ 2022-04-25 12:07 UTC (permalink / raw) To: Linus Torvalds Cc: Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Sun, 24 Apr 2022, Linus Torvalds wrote: > On Sun, Apr 24, 2022 at 1:54 PM Mikulas Patocka <mpatocka@redhat.com> wrote: > > > > + * > > + * Explanation of the logic: > > + * (ch - '9' - 1) is negative if ch <= '9' > > + * ('0' - 1 - ch) is negative if ch >= '0' > > True, but... > > Please, just to make me happier, make the sign of 'ch' be something > very explicit. Right now that code uses 'char ch', which could be > signed or unsigned. OK, I fixed it, here I'm sending the second version. > Finally, for the same reason - please don't use ">> 8". Because I do > not believe that bit 8 is well-defined in your arithmetic. The *sign* We are subtracting values that are in the 0 ... 255 range. So, the result will be in the -255 ... 255 range. So, the bits 8 to 31 of the result are equivalent. > bit will be, but I'm not convinced bit 8 is. > > So use ">> 31" or similar. We can pick any number between 8 and 28. 31 won't work because the C standard doesn't specify that the right shift keeps the sign bit. To make it standard-compliant, I added a cast that casts the int value to unsigned. We have an unsigned value with bits 8 to 31 equivalent. When we shift it 8 bits to the right, we have either 0 or 0xffffff - and this value is suitable for masking. > Also, I do worry that this is *exactly* the kind of trick that a > compiler could easily turn back into a conditional. Usually compilers > tend to go the other way (ie turn conditionals into arithmetic if > possible), but.. Some old version that I tried used "(ch - '0' + 1) * ((unsigned)(ch - '0') <= 9)" - it worked with gcc, but clang was too smart and turned it into a cmov when compiling for i686 and to a conditional branch when compiling for i586. Another version used "-(c - '0' + 1) * (((unsigned)(c - '0') >= 10) - 1)" - it almost worked, except that clang still turned it into a conditional jump on sparc32 and powerpc32. So, I came up with this version that avoids comparison operators at all and tested it with gcc and clang on all architectures that I could try. Mikulas > Linus > From: Mikulas Patocka <mpatocka@redhat.com> The function hex2bin is used to load cryptographic keys into device mapper targets dm-crypt and dm-integrity. It should take constant time independent on the processed data, so that concurrently running unprivileged code can't infer any information about the keys via microarchitectural convert channels. This patch changes the function hex_to_bin so that it contains no branches and no memory accesses. Note that this shouldn't cause performance degradation because the size of the new function is the same as the size of the old function (on x86-64) - and the new function causes no branch misprediction penalties. I compile-tested this function with gcc on aarch64 alpha arm hppa hppa64 i386 ia64 m68k mips32 mips64 powerpc powerpc64 riscv sh4 s390x sparc32 sparc64 x86_64 and with clang on aarch64 arm hexagon i386 mips32 mips64 powerpc powerpc64 s390x sparc32 sparc64 x86_64 to verify that there are no branches in the generated code. Signed-off-by: Mikulas Patocka <mpatocka@redhat.com> Cc: stable@vger.kernel.org --- include/linux/kernel.h | 2 +- lib/hexdump.c | 32 +++++++++++++++++++++++++------- 2 files changed, 26 insertions(+), 8 deletions(-) Index: linux-2.6/lib/hexdump.c =================================================================== --- linux-2.6.orig/lib/hexdump.c 2022-04-24 18:51:20.000000000 +0200 +++ linux-2.6/lib/hexdump.c 2022-04-25 13:15:26.000000000 +0200 @@ -22,15 +22,33 @@ EXPORT_SYMBOL(hex_asc_upper); * * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad * input. + * + * This function is used to load cryptographic keys, so it is coded in such a + * way that there are no conditions or memory accesses that depend on data. + * + * Explanation of the logic: + * (ch - '9' - 1) is negative if ch <= '9' + * ('0' - 1 - ch) is negative if ch >= '0' + * we "and" these two values, so the result is negative if ch is in the range + * '0' ... '9' + * we are only interested in the sign, so we do a shift ">> 8"; note that right + * shift of a negative value is implementation-defined, so we cast the + * value to (unsigned) before the shift --- we have 0xffffff if ch is in + * the range '0' ... '9', 0 otherwise + * we "and" this value with (ch - '0' + 1) --- we have a value 1 ... 10 if ch is + * in the range '0' ... '9', 0 otherwise + * we add this value to -1 --- we have a value 0 ... 9 if ch is in the range '0' + * ... '9', -1 otherwise + * the next line is similar to the previous one, but we need to decode both + * uppercase and lowercase letters, so we use (ch & 0xdf), which converts + * lowercase to uppercase */ -int hex_to_bin(char ch) +int hex_to_bin(unsigned char ch) { - if ((ch >= '0') && (ch <= '9')) - return ch - '0'; - ch = tolower(ch); - if ((ch >= 'a') && (ch <= 'f')) - return ch - 'a' + 10; - return -1; + unsigned char cu = ch & 0xdf; + return -1 + + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); } EXPORT_SYMBOL(hex_to_bin); Index: linux-2.6/include/linux/kernel.h =================================================================== --- linux-2.6.orig/include/linux/kernel.h 2022-04-21 17:31:39.000000000 +0200 +++ linux-2.6/include/linux/kernel.h 2022-04-25 07:33:43.000000000 +0200 @@ -285,7 +285,7 @@ static inline char *hex_byte_pack_upper( return buf; } -extern int hex_to_bin(char ch); +extern int hex_to_bin(unsigned char ch); extern int __must_check hex2bin(u8 *dst, const char *src, size_t count); extern char *bin2hex(char *dst, const void *src, size_t count); ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-04-25 12:07 ` [PATCH v2] " Mikulas Patocka @ 2022-04-25 17:53 ` Linus Torvalds 2022-05-04 8:38 ` Stafford Horne 1 sibling, 0 replies; 33+ messages in thread From: Linus Torvalds @ 2022-04-25 17:53 UTC (permalink / raw) To: Mikulas Patocka Cc: Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Mon, Apr 25, 2022 at 5:07 AM Mikulas Patocka <mpatocka@redhat.com> wrote: > > We are subtracting values that are in the 0 ... 255 range. Well, except that's not what the original patch did. It was subtracting values that were in the -128 ... 255 range (where the exact range depended on the sign of 'char'). But yeah, I think bit8 was always safe. Probably. Particularly as the possible ranges across different architectures is bigger than the range within one _particular_ architecture (so you'll never see "255 - -128" even when the sign wasn't defined ;) > > Also, I do worry that this is *exactly* the kind of trick that a > > compiler could easily turn back into a conditional. Usually compilers > > tend to go the other way (ie turn conditionals into arithmetic if > > possible), but.. > > Some old version that I tried used "(ch - '0' + 1) * ((unsigned)(ch - '0') > <= 9)" - it worked with gcc, but clang was too smart and turned it into a > cmov when compiling for i686 and to a conditional branch when compiling > for i586. > > Another version used "-(c - '0' + 1) * (((unsigned)(c - '0') >= 10) - 1)" > - it almost worked, except that clang still turned it into a conditional > jump on sparc32 and powerpc32. > > So, I came up with this version that avoids comparison operators at all > and tested it with gcc and clang on all architectures that I could try. Yeah, the thing about those compiler heuristics is that they are often based on almost arbitrary patterns that just happen to be what somebody has found in some benchmark. Hopefully nobody ever uses something like this as a benchmark. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-04-25 12:07 ` [PATCH v2] " Mikulas Patocka 2022-04-25 17:53 ` Linus Torvalds @ 2022-05-04 8:38 ` Stafford Horne 2022-05-04 8:57 ` Mikulas Patocka 2022-05-04 9:42 ` Jason A. Donenfeld 1 sibling, 2 replies; 33+ messages in thread From: Stafford Horne @ 2022-05-04 8:38 UTC (permalink / raw) To: Mikulas Patocka Cc: Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz, Jason On Mon, Apr 25, 2022 at 08:07:48AM -0400, Mikulas Patocka wrote: > From: Mikulas Patocka <mpatocka@redhat.com> > > The function hex2bin is used to load cryptographic keys into device mapper > targets dm-crypt and dm-integrity. It should take constant time > independent on the processed data, so that concurrently running > unprivileged code can't infer any information about the keys via > microarchitectural convert channels. > > This patch changes the function hex_to_bin so that it contains no branches > and no memory accesses. > > Note that this shouldn't cause performance degradation because the size of > the new function is the same as the size of the old function (on x86-64) - > and the new function causes no branch misprediction penalties. > > I compile-tested this function with gcc on aarch64 alpha arm hppa hppa64 > i386 ia64 m68k mips32 mips64 powerpc powerpc64 riscv sh4 s390x sparc32 > sparc64 x86_64 and with clang on aarch64 arm hexagon i386 mips32 mips64 > powerpc powerpc64 s390x sparc32 sparc64 x86_64 to verify that there are no > branches in the generated code. > > Signed-off-by: Mikulas Patocka <mpatocka@redhat.com> > Cc: stable@vger.kernel.org > > --- > include/linux/kernel.h | 2 +- > lib/hexdump.c | 32 +++++++++++++++++++++++++------- > 2 files changed, 26 insertions(+), 8 deletions(-) > > Index: linux-2.6/lib/hexdump.c > =================================================================== > --- linux-2.6.orig/lib/hexdump.c 2022-04-24 18:51:20.000000000 +0200 > +++ linux-2.6/lib/hexdump.c 2022-04-25 13:15:26.000000000 +0200 > @@ -22,15 +22,33 @@ EXPORT_SYMBOL(hex_asc_upper); > * > * hex_to_bin() converts one hex digit to its actual value or -1 in case of bad > * input. > + * > + * This function is used to load cryptographic keys, so it is coded in such a > + * way that there are no conditions or memory accesses that depend on data. > + * > + * Explanation of the logic: > + * (ch - '9' - 1) is negative if ch <= '9' > + * ('0' - 1 - ch) is negative if ch >= '0' > + * we "and" these two values, so the result is negative if ch is in the range > + * '0' ... '9' > + * we are only interested in the sign, so we do a shift ">> 8"; note that right > + * shift of a negative value is implementation-defined, so we cast the > + * value to (unsigned) before the shift --- we have 0xffffff if ch is in > + * the range '0' ... '9', 0 otherwise > + * we "and" this value with (ch - '0' + 1) --- we have a value 1 ... 10 if ch is > + * in the range '0' ... '9', 0 otherwise > + * we add this value to -1 --- we have a value 0 ... 9 if ch is in the range '0' > + * ... '9', -1 otherwise > + * the next line is similar to the previous one, but we need to decode both > + * uppercase and lowercase letters, so we use (ch & 0xdf), which converts > + * lowercase to uppercase > */ > -int hex_to_bin(char ch) > +int hex_to_bin(unsigned char ch) > { > - if ((ch >= '0') && (ch <= '9')) > - return ch - '0'; > - ch = tolower(ch); > - if ((ch >= 'a') && (ch <= 'f')) > - return ch - 'a' + 10; > - return -1; > + unsigned char cu = ch & 0xdf; > + return -1 + > + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + > + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); > } > EXPORT_SYMBOL(hex_to_bin); Hello, Just a heads up it seems this patch is causing some instability with crypto self tests on OpenRISC when using a PREEMPT kernel (no SMP). This was reported by Jason A. Donenfeld as it came up in wireguard testing. I am trying to figure out if this is an OpenRISC PREEMPT issue or something else. The warning I am seeing is a bit random but looks something like the following: [ 0.164000] Freeing initrd memory: 1696K [ 0.188000] xor: measuring software checksum speed [ 0.196000] 8regs : 1343 MB/sec [ 0.204000] 8regs_prefetch : 1347 MB/sec [ 0.212000] 32regs : 1335 MB/sec [ 0.220000] 32regs_prefetch : 1277 MB/sec [ 0.220000] xor: using function: 8regs_prefetch (1347 MB/sec) [ 0.252000] SARU running 25519 tests [ 0.424000] curve25519 self-test 5: FAIL [ 0.496000] curve25519 self-test 7: FAIL [ 1.744000] curve25519 self-test 45: FAIL [ 3.448000] ------------[ cut here ]------------ [ 3.448000] WARNING: CPU: 0 PID: 1 at lib/crypto/curve25519.c:19 curve25519_init+0x38/0x50 [ 3.448000] CPU: 0 PID: 1 Comm: swapper Not tainted 5.18.0-rc4+ #758 [ 3.448000] Call trace: [ 3.448000] [<(ptrval)>] ? __warn+0xe0/0x114 [ 3.448000] [<(ptrval)>] ? curve25519_init+0x38/0x50 [ 3.448000] [<(ptrval)>] ? warn_slowpath_fmt+0x5c/0x94 [ 3.448000] [<(ptrval)>] ? curve25519_init+0x0/0x50 [ 3.452000] [<(ptrval)>] ? curve25519_init+0x38/0x50 [ 3.452000] [<(ptrval)>] ? do_one_initcall+0x98/0x328 [ 3.452000] [<(ptrval)>] ? proc_register+0x4c/0x284 [ 3.452000] [<(ptrval)>] ? ignore_unknown_bootoption+0x0/0x8 [ 3.452000] [<(ptrval)>] ? kernel_init_freeable+0x1fc/0x2a8 [ 3.452000] [<(ptrval)>] ? ignore_unknown_bootoption+0x0/0x8 [ 3.452000] [<(ptrval)>] ? kernel_init+0x0/0x164 [ 3.452000] [<(ptrval)>] ? kernel_init+0x28/0x164 [ 3.452000] [<(ptrval)>] ? schedule_tail+0x18/0xac [ 3.452000] [<(ptrval)>] ? ret_from_fork+0x1c/0x9c [ 3.452000] ---[ end trace 0000000000000000 ]--- [ 3.452000] Serial: 8250/16550 driver, 4 ports, IRQ sharing disabled [ 3.464000] printk: console [ttyS0] disabled [ 3.464000] 90000000.serial: ttyS0 at MMIO 0x90000000 (irq = 2, base_baud = 1250000) is a 16550A Example config: https://xn--4db.cc/cCRlQ1AE The self-test iteration number that fails is always a bit different. I am still in progress of investigating this and will not have a lot of time new the next few days. If anything ring's a bell let me know. -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 8:38 ` Stafford Horne @ 2022-05-04 8:57 ` Mikulas Patocka 2022-05-04 9:20 ` Andy Shevchenko 2022-05-04 9:42 ` Jason A. Donenfeld 1 sibling, 1 reply; 33+ messages in thread From: Mikulas Patocka @ 2022-05-04 8:57 UTC (permalink / raw) To: Stafford Horne Cc: Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz, Jason On Wed, 4 May 2022, Stafford Horne wrote: > On Mon, Apr 25, 2022 at 08:07:48AM -0400, Mikulas Patocka wrote: > > > From: Mikulas Patocka <mpatocka@redhat.com> > > > > -int hex_to_bin(char ch) > > +int hex_to_bin(unsigned char ch) > > { > > - if ((ch >= '0') && (ch <= '9')) > > - return ch - '0'; > > - ch = tolower(ch); > > - if ((ch >= 'a') && (ch <= 'f')) > > - return ch - 'a' + 10; > > - return -1; > > + unsigned char cu = ch & 0xdf; > > + return -1 + > > + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + > > + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); > > } > > EXPORT_SYMBOL(hex_to_bin); > > Hello, > > Just a heads up it seems this patch is causing some instability with crypto self > tests on OpenRISC when using a PREEMPT kernel (no SMP). > > This was reported by Jason A. Donenfeld as it came up in wireguard testing. > > I am trying to figure out if this is an OpenRISC PREEMPT issue or something > else. Hi That patch is so simple that I can't imagine how could it break the curve25519 test. Are you sure that you bisected it correctly? Mikulas ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 8:57 ` Mikulas Patocka @ 2022-05-04 9:20 ` Andy Shevchenko 2022-05-04 9:47 ` Milan Broz 2022-05-04 11:54 ` Mikulas Patocka 0 siblings, 2 replies; 33+ messages in thread From: Andy Shevchenko @ 2022-05-04 9:20 UTC (permalink / raw) To: Mikulas Patocka Cc: Stafford Horne, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz, Jason On Wed, May 04, 2022 at 04:57:35AM -0400, Mikulas Patocka wrote: > On Wed, 4 May 2022, Stafford Horne wrote: > > On Mon, Apr 25, 2022 at 08:07:48AM -0400, Mikulas Patocka wrote: ... > > Just a heads up it seems this patch is causing some instability with crypto self > > tests on OpenRISC when using a PREEMPT kernel (no SMP). > > > > This was reported by Jason A. Donenfeld as it came up in wireguard testing. > > > > I am trying to figure out if this is an OpenRISC PREEMPT issue or something > > else. > That patch is so simple that I can't imagine how could it break the > curve25519 test. Are you sure that you bisected it correctly? Can you provide a test cases for hex_to_bin()? -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:20 ` Andy Shevchenko @ 2022-05-04 9:47 ` Milan Broz 2022-05-04 9:50 ` Jason A. Donenfeld 2022-05-04 11:54 ` Mikulas Patocka 1 sibling, 1 reply; 33+ messages in thread From: Milan Broz @ 2022-05-04 9:47 UTC (permalink / raw) To: Andy Shevchenko, Mikulas Patocka Cc: Stafford Horne, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Jason On 04/05/2022 11:20, Andy Shevchenko wrote: > On Wed, May 04, 2022 at 04:57:35AM -0400, Mikulas Patocka wrote: >> On Wed, 4 May 2022, Stafford Horne wrote: >>> On Mon, Apr 25, 2022 at 08:07:48AM -0400, Mikulas Patocka wrote: > > ... > >>> Just a heads up it seems this patch is causing some instability with crypto self >>> tests on OpenRISC when using a PREEMPT kernel (no SMP). >>> >>> This was reported by Jason A. Donenfeld as it came up in wireguard testing. >>> >>> I am trying to figure out if this is an OpenRISC PREEMPT issue or something >>> else. > >> That patch is so simple that I can't imagine how could it break the >> curve25519 test. Are you sure that you bisected it correctly? > > Can you provide a test cases for hex_to_bin()? BTW we use exactly the same code from Mikulas in cryptsetup now (actually the report was initiated from here :) and I added some tests for this code, you can probably adapt it (we just use generic wrapper around it): https://gitlab.com/cryptsetup/cryptsetup/-/commit/2d8cdb2e356d187658efa6efc7bfa146be5d3f60#d9c94cde02e4509f6d12c3edd40f8a9138696807_0_176 (it calls this: https://gitlab.com/cryptsetup/cryptsetup/-/commit/ff14c17de794fe85299d90e34e12a677e6148b71 ) I do not have OpenRISC available, but it would be interesting to run cryptsetup/tests/vectors-test there... Milan ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:47 ` Milan Broz @ 2022-05-04 9:50 ` Jason A. Donenfeld 0 siblings, 0 replies; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 9:50 UTC (permalink / raw) To: Milan Broz Cc: Andy Shevchenko, Mikulas Patocka, Stafford Horne, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar On Wed, May 4, 2022 at 11:47 AM Milan Broz <gmazyland@gmail.com> wrote: > BTW we use exactly the same code from Mikulas in cryptsetup now (actually the report > was initiated from here :) and I added some tests for this code, > you can probably adapt it (we just use generic wrapper around it): I use something pretty similar in wireguard-tools: https://git.zx2c4.com/wireguard-tools/tree/src/encoding.c#n74 The code is fine. This is looking like a different issue somewhere else in the OpenRISC stack... ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:20 ` Andy Shevchenko 2022-05-04 9:47 ` Milan Broz @ 2022-05-04 11:54 ` Mikulas Patocka 1 sibling, 0 replies; 33+ messages in thread From: Mikulas Patocka @ 2022-05-04 11:54 UTC (permalink / raw) To: Andy Shevchenko Cc: Stafford Horne, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz, Jason On Wed, 4 May 2022, Andy Shevchenko wrote: > On Wed, May 04, 2022 at 04:57:35AM -0400, Mikulas Patocka wrote: > > On Wed, 4 May 2022, Stafford Horne wrote: > > > On Mon, Apr 25, 2022 at 08:07:48AM -0400, Mikulas Patocka wrote: > > ... > > > > Just a heads up it seems this patch is causing some instability with crypto self > > > tests on OpenRISC when using a PREEMPT kernel (no SMP). > > > > > > This was reported by Jason A. Donenfeld as it came up in wireguard testing. > > > > > > I am trying to figure out if this is an OpenRISC PREEMPT issue or something > > > else. > > > That patch is so simple that I can't imagine how could it break the > > curve25519 test. Are you sure that you bisected it correctly? > > Can you provide a test cases for hex_to_bin()? I tested it with this: #include <stdio.h> int hex_to_bin(unsigned char c); int main(void) { int i; for (i = 0; i < 256; i++) printf("%02x - %d\n", i, hex_to_bin(i)); return 0; } Mikulas ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 8:38 ` Stafford Horne 2022-05-04 8:57 ` Mikulas Patocka @ 2022-05-04 9:42 ` Jason A. Donenfeld 2022-05-04 9:44 ` Jason A. Donenfeld 2022-05-04 9:57 ` Jason A. Donenfeld 1 sibling, 2 replies; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 9:42 UTC (permalink / raw) To: Stafford Horne Cc: Mikulas Patocka, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 05:38:28PM +0900, Stafford Horne wrote: > Just a heads up it seems this patch is causing some instability with crypto self > tests on OpenRISC when using a PREEMPT kernel (no SMP). > > This was reported by Jason A. Donenfeld as it came up in wireguard testing. > > I am trying to figure out if this is an OpenRISC PREEMPT issue or something > else. The code of this commit looks fine. And actually the bug goes away if you just add a `pr_err("hello!\n");` to the function. Plus, the function is never called by that test kernel. Actually, the bug even goes away if you change the sign of the input back to naked char (which might be semantically better anyway) and then let the function itself do the sign change (see below). So more likely is that this patch just helps unmask a real issue elsewhere -- linker, compiler, or register restoration after preemption. I don't think there's anything to do with regards to the patch of this thread, as it's clearly fine. Unless you want that sign thing below, but even then, who cares. We should keep digging in on the OpenRISC front. Jason diff --git a/include/linux/kernel.h b/include/linux/kernel.h index fe6efb24d151..a890428bcc1a 100644 --- a/include/linux/kernel.h +++ b/include/linux/kernel.h @@ -285,7 +285,7 @@ static inline char *hex_byte_pack_upper(char *buf, u8 byte) return buf; } -extern int hex_to_bin(unsigned char ch); +extern int hex_to_bin(char ch); extern int __must_check hex2bin(u8 *dst, const char *src, size_t count); extern char *bin2hex(char *dst, const void *src, size_t count); diff --git a/lib/hexdump.c b/lib/hexdump.c index 06833d404398..b636b4dcabe9 100644 --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -43,9 +43,9 @@ EXPORT_SYMBOL(hex_asc_upper); * uppercase and lowercase letters, so we use (ch & 0xdf), which converts * lowercase to uppercase */ -int hex_to_bin(unsigned char ch) +int hex_to_bin(char ch) { - unsigned char cu = ch & 0xdf; + unsigned char cu = ch & 0xdfU; return -1 + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); ^ permalink raw reply related [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:42 ` Jason A. Donenfeld @ 2022-05-04 9:44 ` Jason A. Donenfeld 2022-05-04 9:57 ` Jason A. Donenfeld 1 sibling, 0 replies; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 9:44 UTC (permalink / raw) To: Stafford Horne Cc: Mikulas Patocka, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 11:42:27AM +0200, Jason A. Donenfeld wrote: > (which might be semantically better anyway) and then > let the function itself do the sign change (see below). Actually, probably worse, not better. Didn't realize cu was being used after the masking. ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:42 ` Jason A. Donenfeld 2022-05-04 9:44 ` Jason A. Donenfeld @ 2022-05-04 9:57 ` Jason A. Donenfeld 2022-05-04 10:07 ` Andy Shevchenko 1 sibling, 1 reply; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 9:57 UTC (permalink / raw) To: Stafford Horne Cc: Mikulas Patocka, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 11:42:27AM +0200, Jason A. Donenfeld wrote: > So more likely is that this patch just helps unmask a real issue > elsewhere -- linker, compiler, or register restoration after preemption. > I don't think there's anything to do with regards to the patch of this > thread, as it's clearly fine. The problem even goes away if I just add a nop... diff --git a/lib/hexdump.c b/lib/hexdump.c index 06833d404398..ace74f9b3d5a 100644 --- a/lib/hexdump.c +++ b/lib/hexdump.c @@ -46,6 +46,7 @@ EXPORT_SYMBOL(hex_asc_upper); int hex_to_bin(unsigned char ch) { unsigned char cu = ch & 0xdf; + __asm__("l.nop 0"); return -1 + ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); ^ permalink raw reply related [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 9:57 ` Jason A. Donenfeld @ 2022-05-04 10:07 ` Andy Shevchenko 2022-05-04 10:15 ` Jason A. Donenfeld 0 siblings, 1 reply; 33+ messages in thread From: Andy Shevchenko @ 2022-05-04 10:07 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Stafford Horne, Mikulas Patocka, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 11:57:29AM +0200, Jason A. Donenfeld wrote: > On Wed, May 04, 2022 at 11:42:27AM +0200, Jason A. Donenfeld wrote: > > So more likely is that this patch just helps unmask a real issue > > elsewhere -- linker, compiler, or register restoration after preemption. > > I don't think there's anything to do with regards to the patch of this > > thread, as it's clearly fine. > > The problem even goes away if I just add a nop... Alignment? Compiler bug? HW issue? > diff --git a/lib/hexdump.c b/lib/hexdump.c > index 06833d404398..ace74f9b3d5a 100644 > --- a/lib/hexdump.c > +++ b/lib/hexdump.c > @@ -46,6 +46,7 @@ EXPORT_SYMBOL(hex_asc_upper); > int hex_to_bin(unsigned char ch) > { > unsigned char cu = ch & 0xdf; > + __asm__("l.nop 0"); > return -1 + > ((ch - '0' + 1) & (unsigned)((ch - '9' - 1) & ('0' - 1 - ch)) >> 8) + > ((cu - 'A' + 11) & (unsigned)((cu - 'F' - 1) & ('A' - 1 - cu)) >> 8); > -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 10:07 ` Andy Shevchenko @ 2022-05-04 10:15 ` Jason A. Donenfeld 2022-05-04 18:00 ` Linus Torvalds 0 siblings, 1 reply; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 10:15 UTC (permalink / raw) To: Andy Shevchenko Cc: Stafford Horne, Mikulas Patocka, Linus Torvalds, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 01:07:26PM +0300, Andy Shevchenko wrote: > On Wed, May 04, 2022 at 11:57:29AM +0200, Jason A. Donenfeld wrote: > > On Wed, May 04, 2022 at 11:42:27AM +0200, Jason A. Donenfeld wrote: > > > So more likely is that this patch just helps unmask a real issue > > > elsewhere -- linker, compiler, or register restoration after preemption. > > > I don't think there's anything to do with regards to the patch of this > > > thread, as it's clearly fine. > > > > The problem even goes away if I just add a nop... > > Alignment? Compiler bug? HW issue? Probably one of those, yea. Removing the instruction addresses, the only difference between the two compiles is: https://xn--4db.cc/Rrn8usaX/diff#line-440 So either there's some alignment going on here, a compiler thing I haven't spotted yet, or some very fragile interrupt/preemption behavior that's interacting with this, either on the kernel side or the QEMU side. (I've never touched real HW for this; I just got nerd sniped when wondering why my wireguard CI was failing...) Jason ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 10:15 ` Jason A. Donenfeld @ 2022-05-04 18:00 ` Linus Torvalds 2022-05-04 19:42 ` Jason A. Donenfeld 0 siblings, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 18:00 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Andy Shevchenko, Stafford Horne, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 3:15 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > > Alignment? Compiler bug? HW issue? > > Probably one of those, yea. Removing the instruction addresses, the only > difference between the two compiles is: https://xn--4db.cc/Rrn8usaX/diff#line-440 Well, that address doesn't work for me at all. It turns into א.cc. I'd love to see the compiler problem, since I find those fascinating (mainly because they scare the hell out of me), but those web addresses you use are not working for me. It most definitely looks like an OpenRISC compiler bug - that code doesn't look like it does anything remotely undefined (and with the "unsigned char", nothing implementation-defined either). Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 18:00 ` Linus Torvalds @ 2022-05-04 19:42 ` Jason A. Donenfeld 2022-05-04 19:51 ` Linus Torvalds 2022-05-04 19:57 ` Stafford Horne 0 siblings, 2 replies; 33+ messages in thread From: Jason A. Donenfeld @ 2022-05-04 19:42 UTC (permalink / raw) To: Linus Torvalds Cc: Andy Shevchenko, Stafford Horne, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz Hi Linus, On Wed, May 4, 2022 at 8:00 PM Linus Torvalds <torvalds@linux-foundation.org> wrote: > > On Wed, May 4, 2022 at 3:15 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > > > > Alignment? Compiler bug? HW issue? > > > > Probably one of those, yea. Removing the instruction addresses, the only > > difference between the two compiles is: https://xn--4db.cc/Rrn8usaX/diff#line-440 > > Well, that address doesn't work for me at all. It turns into א.cc. > > I'd love to see the compiler problem, since I find those fascinating > (mainly because they scare the hell out of me), but those web > addresses you use are not working for me. א.cc is correct. If you can't load it, your browser or something in your stack is broken. Choosing a non-ASCII domain like that clearly a bad decision because people with broken stacks can't load it? Yea, maybe. But maybe it's like the arch/alpha/ reordering of dependent loads applied to the web... A bit of stretch. > It most definitely looks like an OpenRISC compiler bug - that code > doesn't look like it does anything remotely undefined (and with the > "unsigned char", nothing implementation-defined either). I'm not so certain it's in the compiler anymore, actually. The bug exhibits itself even when that code isn't actually called. Adding nops to unrelated code also makes the problem go away. And removing these nops [1] makes the problem go away too. So maybe it's looking more like a linker bug (or linker script bug) related to alignment. Or whatever is jumping between contexts in the preemption code and restoring registers and such is assuming certain things about code layout that doesn't always hold. More fiddling is necessary still. Jason [1] https://lore.kernel.org/lkml/20220504110911.283525-1-Jason@zx2c4.com/ ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 19:42 ` Jason A. Donenfeld @ 2022-05-04 19:51 ` Linus Torvalds 2022-05-04 20:00 ` Linus Torvalds 2022-05-04 19:57 ` Stafford Horne 1 sibling, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 19:51 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Andy Shevchenko, Stafford Horne, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 12:43 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > א.cc is correct. If you can't load it, your browser or something in > your stack is broken. It's just google-chrome. And honestly, the last thing I want to ever see is non-ASCII URL's. Particularly from a security person. It's a *HORRIBLE* idea with homoglyphs, and personally I think any browser that refuses to look it up would be doing the right thing. But I don't think that it's the browser, actually. Even 'nslookup' refuses to touch it with ** server can't find א.cc: SERVFAIL and it seems it's literally the local dns caching (dnsmasq?) > Choosing a non-ASCII domain like that clearly a > bad decision because people with broken stacks can't load it? No. It's a bad idea. Full stop. Don't do it. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 19:51 ` Linus Torvalds @ 2022-05-04 20:00 ` Linus Torvalds 2022-05-04 20:12 ` Stafford Horne 0 siblings, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 20:00 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Andy Shevchenko, Stafford Horne, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 12:51 PM Linus Torvalds <torvalds@linux-foundation.org> wrote: > > But I don't think that it's the browser, actually. Even 'nslookup' > refuses to touch it with > > ** server can't find א.cc: SERVFAIL > > and it seems it's literally the local dns caching (dnsmasq?) Looks like Fedora builds dnsmasq with 'no-i18n', although "dnsmasq -v" also shows "IDN2", so who knows.. Maybe it's some default config issue rather than the build configuration. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 20:00 ` Linus Torvalds @ 2022-05-04 20:12 ` Stafford Horne 2022-05-04 20:26 ` Linus Torvalds 0 siblings, 1 reply; 33+ messages in thread From: Stafford Horne @ 2022-05-04 20:12 UTC (permalink / raw) To: Linus Torvalds Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 01:00:36PM -0700, Linus Torvalds wrote: > On Wed, May 4, 2022 at 12:51 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: > > > > But I don't think that it's the browser, actually. Even 'nslookup' > > refuses to touch it with > > > > ** server can't find א.cc: SERVFAIL > > > > and it seems it's literally the local dns caching (dnsmasq?) > > Looks like Fedora builds dnsmasq with 'no-i18n', although "dnsmasq -v" > also shows "IDN2", so who knows.. Maybe it's some default config issue > rather than the build configuration. > > Linus Which version of Fedora? I use a pretty vanilla Fedora 34 install and it seems to be working ok for me. shorne@antec $ dig +short א.cc 147.75.79.213 shorne@antec $ nslookup א.cc Server: 127.0.0.53 Address: 127.0.0.53#53 Non-authoritative answer: Name: א.cc Address: 147.75.79.213 Name: א.cc Address: 2604:1380:1:4d00::5 shorne@antec $ /lib64/ld-linux-x86-64.so.2 --version ld.so (GNU libc) release release version 2.33. Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. shorne@antec $ cat /etc/redhat-release Fedora release 34 (Thirty Four) -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 20:12 ` Stafford Horne @ 2022-05-04 20:26 ` Linus Torvalds 2022-05-04 21:24 ` Linus Torvalds 0 siblings, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 20:26 UTC (permalink / raw) To: Stafford Horne Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 1:12 PM Stafford Horne <shorne@gmail.com> wrote: > > Which version of Fedora? F35 here. But looking further, it's not dnsmasq either. Yes, dnsmasq is built with no-i18n, but as mentioned IDN2 does seem to be enabled, so I think it's just "no i18n messages". It seems to be the upstream dns server. Using 8.8.8.8 explicitly makes it work for me, and that obviously bypasses not just the local dns cache, but also the next dns server hop. Could be anywhere. Xfinity, Nest WiFi, or the cable router. They all are doing their own dns thing. Probably my cable box, since it's likely the oldest thing in the chain. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 20:26 ` Linus Torvalds @ 2022-05-04 21:24 ` Linus Torvalds 0 siblings, 0 replies; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 21:24 UTC (permalink / raw) To: Stafford Horne Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 1:26 PM Linus Torvalds <torvalds@linux-foundation.org> wrote: > > Could be anywhere. Xfinity, Nest WiFi, or the cable router. They all > are doing their own dns thing. > > Probably my cable box, since it's likely the oldest thing in the chain. No, it seems to be my Nest WiFi router. I told it to use google DNS to avoid Xfinity or the cable box, and it still shows the same behavior. Not that I care much, since I consider those IDN names to be dangerous anyway, but I think it would have been less sad if it had been some old cable modem. Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 19:42 ` Jason A. Donenfeld 2022-05-04 19:51 ` Linus Torvalds @ 2022-05-04 19:57 ` Stafford Horne 2022-05-04 20:10 ` Linus Torvalds 1 sibling, 1 reply; 33+ messages in thread From: Stafford Horne @ 2022-05-04 19:57 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Linus Torvalds, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Thu, May 5, 2022 at 4:43 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > Hi Linus, > > On Wed, May 4, 2022 at 8:00 PM Linus Torvalds > <torvalds@linux-foundation.org> wrote: > > > > On Wed, May 4, 2022 at 3:15 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > > > > > > Alignment? Compiler bug? HW issue? > > > > > > Probably one of those, yea. Removing the instruction addresses, the only > > > difference between the two compiles is: https://xn--4db.cc/Rrn8usaX/diff#line-440 > > > > Well, that address doesn't work for me at all. It turns into א.cc. > > > > I'd love to see the compiler problem, since I find those fascinating > > (mainly because they scare the hell out of me), but those web > > addresses you use are not working for me. > > א.cc is correct. If you can't load it, your browser or something in > your stack is broken. Choosing a non-ASCII domain like that clearly a > bad decision because people with broken stacks can't load it? Yea, > maybe. But maybe it's like the arch/alpha/ reordering of dependent > loads applied to the web... A bit of stretch. I have uploaded a diff I created here: https://gist.github.com/54334556f2907104cd12374872a0597c It shows the same output. > > It most definitely looks like an OpenRISC compiler bug - that code > > doesn't look like it does anything remotely undefined (and with the > > "unsigned char", nothing implementation-defined either). > > I'm not so certain it's in the compiler anymore, actually. The bug > exhibits itself even when that code isn't actually called. Adding nops > to unrelated code also makes the problem go away. And removing these > nops [1] makes the problem go away too. So maybe it's looking more > like a linker bug (or linker script bug) related to alignment. Or > whatever is jumping between contexts in the preemption code and > restoring registers and such is assuming certain things about code > layout that doesn't always hold. More fiddling is necessary still. Bisecting definitely came to this patch which is strange. Then reverting e5be15767e7e ("hex2bin: make the function hex_to_bin constant-time") did also fix the problem for me. But it could be any small patch that changes layout could make this go away. I have things to try: - more close look at the produced asembly diff - newer compiler (I fixed a few bugs in gcc 12 for openrisc, and this testing came up in gcc 11) - trying on FPGA's I'll report as I find things. -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 19:57 ` Stafford Horne @ 2022-05-04 20:10 ` Linus Torvalds 2022-05-04 20:38 ` Stafford Horne 0 siblings, 1 reply; 33+ messages in thread From: Linus Torvalds @ 2022-05-04 20:10 UTC (permalink / raw) To: Stafford Horne Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 4, 2022 at 12:58 PM Stafford Horne <shorne@gmail.com> wrote: > > I have uploaded a diff I created here: > https://gist.github.com/54334556f2907104cd12374872a0597c > > It shows the same output. In hex_to_bin itself it seems to only be a difference due to some register allocation (r19 and r3 switched around). But then it gets inlined into hex2bin and there changes there seem to be about instruction and basic block scheduling, so it's a lot harder to see what's going on. And a lot of constant changes, which honestly look just like code code moved around by 16 bytes and offsets changed due to that. So I doubt it's hex_to_bin() that is causing problems, I think it's purely code movement. Which explains why adding a nop or a fake printk fixes things. Some alignment assumption that got broken? Linus ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 20:10 ` Linus Torvalds @ 2022-05-04 20:38 ` Stafford Horne 2022-05-08 0:37 ` Stafford Horne 0 siblings, 1 reply; 33+ messages in thread From: Stafford Horne @ 2022-05-04 20:38 UTC (permalink / raw) To: Linus Torvalds Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Wed, May 04, 2022 at 01:10:03PM -0700, Linus Torvalds wrote: > On Wed, May 4, 2022 at 12:58 PM Stafford Horne <shorne@gmail.com> wrote: > > > > I have uploaded a diff I created here: > > https://gist.github.com/54334556f2907104cd12374872a0597c > > > > It shows the same output. > > In hex_to_bin itself it seems to only be a difference due to some > register allocation (r19 and r3 switched around). > > But then it gets inlined into hex2bin and there changes there seem to > be about instruction and basic block scheduling, so it's a lot harder > to see what's going on. > > And a lot of constant changes, which honestly look just like code code > moved around by 16 bytes and offsets changed due to that. > > So I doubt it's hex_to_bin() that is causing problems, I think it's > purely code movement. Which explains why adding a nop or a fake printk > fixes things. > > Some alignment assumption that got broken? This is what it looks like to me too. I will have to do a deep dive on what is going on with this particular build combination as I can't figure out what it is off the top of my head. This test is using a gcc 11 compiler, I tried with my gcc 12 toolchain and the issue cannot be reproduced. - musl gcc 11 - https://musl.cc/or1k-linux-musl-cross.tgz - openrisc gcc 12 - https://github.com/openrisc/or1k-gcc/releases/tag/or1k-12.0.1-20220210-20220304 But again the difference between the two compiler outputs is a lot of register allocation and offsets changes. Its not easy to see anything that stands out. I checked the change log for the openrisc specific changes from gcc 11 to gcc 12. Nothing seems to stand out, mcount profiler fix for PIC, a new large binary link flag. -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-04 20:38 ` Stafford Horne @ 2022-05-08 0:37 ` Stafford Horne 2022-05-11 12:17 ` Stafford Horne 0 siblings, 1 reply; 33+ messages in thread From: Stafford Horne @ 2022-05-08 0:37 UTC (permalink / raw) To: Linus Torvalds Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Thu, May 05, 2022 at 05:38:58AM +0900, Stafford Horne wrote: > On Wed, May 04, 2022 at 01:10:03PM -0700, Linus Torvalds wrote: > > On Wed, May 4, 2022 at 12:58 PM Stafford Horne <shorne@gmail.com> wrote: > > > > > > I have uploaded a diff I created here: > > > https://gist.github.com/54334556f2907104cd12374872a0597c > > > > > > It shows the same output. > > > > In hex_to_bin itself it seems to only be a difference due to some > > register allocation (r19 and r3 switched around). > > > > But then it gets inlined into hex2bin and there changes there seem to > > be about instruction and basic block scheduling, so it's a lot harder > > to see what's going on. > > > > And a lot of constant changes, which honestly look just like code code > > moved around by 16 bytes and offsets changed due to that. > > > > So I doubt it's hex_to_bin() that is causing problems, I think it's > > purely code movement. Which explains why adding a nop or a fake printk > > fixes things. > > > > Some alignment assumption that got broken? > > This is what it looks like to me too. I will have to do a deep dive on what is > going on with this particular build combination as I can't figure out what it is > off the top of my head. > > This test is using a gcc 11 compiler, I tried with my gcc 12 toolchain and the > issue cannot be reproduced. > > - musl gcc 11 - https://musl.cc/or1k-linux-musl-cross.tgz > - openrisc gcc 12 - https://github.com/openrisc/or1k-gcc/releases/tag/or1k-12.0.1-20220210-20220304 > > But again the difference between the two compiler outputs is a lot of register > allocation and offsets changes. Its not easy to see anything that stands out. > I checked the change log for the openrisc specific changes from gcc 11 to gcc > 12. Nothing seems to stand out, mcount profiler fix for PIC, a new large binary > link flag. Hello, Just an update on this. The issue so far has been traced to the alignment of the crypto multiplication function fe_mul_impl in lib/crypto/curve25519-fiat32.c. This patch e5be15767e7e ("hex2bin: make the function hex_to_bin constant-time") allowed for the alignment to be just right to cause the failure. Without this patch and forcing the alignment we can reproduce the issue. So though the bisect is correct, this patch is not the root cause of the issue. Using some l.nop sliding techniques and some strategically placed .align statements I have been able to reproduce the issue on: - gcc 11 and gcc 12 - preempt and non-preempt kernels I have not been able to reproduce this on my FPGA, so far only QEMU. My hunch now is that since the fe_mul_impl function contains some rather long basic blocks it appears that timer interrupts that interrupt qemu mid basic block execution somehow is causing this. The hypothesis is it may be basic block resuming behavior in qemu that causes incosistent behavior. It will take a bit more time to trace this. Since I maintain OpenRISC QEMU the issue is on me. Again, It's safe to say that patch e5be15767e7e ("hex2bin: make the function hex_to_bin constant-time") is not an issue. -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time 2022-05-08 0:37 ` Stafford Horne @ 2022-05-11 12:17 ` Stafford Horne 0 siblings, 0 replies; 33+ messages in thread From: Stafford Horne @ 2022-05-11 12:17 UTC (permalink / raw) To: Linus Torvalds Cc: Jason A. Donenfeld, Andy Shevchenko, Mikulas Patocka, Andy Shevchenko, device-mapper development, Linux Kernel Mailing List, Linux Crypto Mailing List, Herbert Xu, David S. Miller, Mike Snitzer, Mimi Zohar, Milan Broz On Sun, May 08, 2022 at 09:37:26AM +0900, Stafford Horne wrote: > On Thu, May 05, 2022 at 05:38:58AM +0900, Stafford Horne wrote: > > On Wed, May 04, 2022 at 01:10:03PM -0700, Linus Torvalds wrote: > > > On Wed, May 4, 2022 at 12:58 PM Stafford Horne <shorne@gmail.com> wrote: > > > > > > > > I have uploaded a diff I created here: > > > > https://gist.github.com/54334556f2907104cd12374872a0597c > > > > > > > > It shows the same output. > > > > > > In hex_to_bin itself it seems to only be a difference due to some > > > register allocation (r19 and r3 switched around). > > > > > > But then it gets inlined into hex2bin and there changes there seem to > > > be about instruction and basic block scheduling, so it's a lot harder > > > to see what's going on. > > > > > > And a lot of constant changes, which honestly look just like code code > > > moved around by 16 bytes and offsets changed due to that. > > > > > > So I doubt it's hex_to_bin() that is causing problems, I think it's > > > purely code movement. Which explains why adding a nop or a fake printk > > > fixes things. > > > > > > Some alignment assumption that got broken? > > > > This is what it looks like to me too. I will have to do a deep dive on what is > > going on with this particular build combination as I can't figure out what it is > > off the top of my head. > > > > This test is using a gcc 11 compiler, I tried with my gcc 12 toolchain and the > > issue cannot be reproduced. > > > > - musl gcc 11 - https://musl.cc/or1k-linux-musl-cross.tgz > > - openrisc gcc 12 - https://github.com/openrisc/or1k-gcc/releases/tag/or1k-12.0.1-20220210-20220304 > > > > But again the difference between the two compiler outputs is a lot of register > > allocation and offsets changes. Its not easy to see anything that stands out. > > I checked the change log for the openrisc specific changes from gcc 11 to gcc > > 12. Nothing seems to stand out, mcount profiler fix for PIC, a new large binary > > link flag. > > Hello, > > Just an update on this. The issue so far has been traced to the alignment of > the crypto multiplication function fe_mul_impl in lib/crypto/curve25519-fiat32.c. > > This patch e5be15767e7e ("hex2bin: make the function hex_to_bin constant-time") > allowed for the alignment to be just right to cause the failure. Without > this patch and forcing the alignment we can reproduce the issue. So though the > bisect is correct, this patch is not the root cause of the issue. > > Using some l.nop sliding techniques and some strategically placed .align > statements I have been able to reproduce the issue on: > > - gcc 11 and gcc 12 > - preempt and non-preempt kernels > > I have not been able to reproduce this on my FPGA, so far only QEMU. My > hunch now is that since the fe_mul_impl function contains some rather long basic > blocks it appears that timer interrupts that interrupt qemu mid basic block > execution somehow is causing this. The hypothesis is it may be basic block > resuming behavior in qemu that causes incosistent behavior. > > It will take a bit more time to trace this. Since I maintain OpenRISC QEMU the > issue is on me. > > Again, It's safe to say that patch e5be15767e7e ("hex2bin: make the function > hex_to_bin constant-time") is not an issue. This issue has been fixed. I sent a patch to QEMU for it: - https://lore.kernel.org/qemu-devel/20220511120541.2242797-1-shorne@gmail.com/T/#u The issue was a bug in the OpenRISC emulation in QEMU which was triggered when receiving a TICK TIMER interrupt, in a delay slot, on a page boundary. The fix was simple enough, but investigation took quite some work. Thanks, -Stafford ^ permalink raw reply [flat|nested] 33+ messages in thread
end of thread, other threads:[~2022-05-11 12:17 UTC | newest] Thread overview: 33+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-04-24 20:54 [PATCH] hex2bin: make the function hex_to_bin constant-time Mikulas Patocka 2022-04-24 21:30 ` Joe Perches 2022-04-24 21:37 ` Linus Torvalds 2022-04-24 21:42 ` Linus Torvalds 2022-04-25 9:37 ` David Laight 2022-04-25 11:04 ` Mikulas Patocka 2022-04-25 12:59 ` David Laight 2022-04-25 13:33 ` Mikulas Patocka 2022-04-25 12:07 ` [PATCH v2] " Mikulas Patocka 2022-04-25 17:53 ` Linus Torvalds 2022-05-04 8:38 ` Stafford Horne 2022-05-04 8:57 ` Mikulas Patocka 2022-05-04 9:20 ` Andy Shevchenko 2022-05-04 9:47 ` Milan Broz 2022-05-04 9:50 ` Jason A. Donenfeld 2022-05-04 11:54 ` Mikulas Patocka 2022-05-04 9:42 ` Jason A. Donenfeld 2022-05-04 9:44 ` Jason A. Donenfeld 2022-05-04 9:57 ` Jason A. Donenfeld 2022-05-04 10:07 ` Andy Shevchenko 2022-05-04 10:15 ` Jason A. Donenfeld 2022-05-04 18:00 ` Linus Torvalds 2022-05-04 19:42 ` Jason A. Donenfeld 2022-05-04 19:51 ` Linus Torvalds 2022-05-04 20:00 ` Linus Torvalds 2022-05-04 20:12 ` Stafford Horne 2022-05-04 20:26 ` Linus Torvalds 2022-05-04 21:24 ` Linus Torvalds 2022-05-04 19:57 ` Stafford Horne 2022-05-04 20:10 ` Linus Torvalds 2022-05-04 20:38 ` Stafford Horne 2022-05-08 0:37 ` Stafford Horne 2022-05-11 12:17 ` Stafford Horne
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).