[PATCH] hex2bin: make the function hex_to_bin constant-time

[PATCH] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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);
 

Re: [PATCH] hex2bin: make the function hex_to_bin constant-time

[Joe Perches]

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));

Re: [PATCH] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

RE: [PATCH] hex2bin: make the function hex_to_bin constant-time

[David Laight]

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)

RE: [PATCH] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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

[PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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);
 

RE: [PATCH] hex2bin: make the function hex_to_bin constant-time

[David Laight]

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)

RE: [PATCH] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Andy Shevchenko]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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);

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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.

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Milan Broz]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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...

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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);

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Andy Shevchenko]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Mikulas Patocka]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Jason A. Donenfeld]

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/

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Linus Torvalds]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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

Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

[Stafford Horne]

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