| Message ID | alpine.LRH.2.02.2204250723120.26714@file01.intranet.prod.int.rdu2.redhat.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Delegated to: | Herbert Xu |
| Headers | show |
| Series | [v2] hex2bin: make the function hex_to_bin constant-time | expand |
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
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
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
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()?
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);
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.
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
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...
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);
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); >
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
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
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
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/
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
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
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
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
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
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
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
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
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
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
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);