linux-kernel - Re: [PATCH v2] hex2bin: make the function hex_to

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAHk-=wjhP7EdVkj9V2aWbUtPbC=rNxvJ1R1Bs45jFz4KT3xg-Q@mail.gmail.com>
Date:   Mon, 25 Apr 2022 10:53:22 -0700
From:   Linus Torvalds <torvalds@...ux-foundation.org>
To:     Mikulas Patocka <mpatocka@...hat.com>
Cc:     Andy Shevchenko <andy@...nel.org>,
        device-mapper development <dm-devel@...hat.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Linux Crypto Mailing List <linux-crypto@...r.kernel.org>,
        Herbert Xu <herbert@...dor.apana.org.au>,
        "David S. Miller" <davem@...emloft.net>,
        Mike Snitzer <msnitzer@...hat.com>,
        Mimi Zohar <zohar@...ux.ibm.com>,
        Milan Broz <gmazyland@...il.com>
Subject: Re: [PATCH v2] hex2bin: make the function hex_to_bin constant-time

On Mon, Apr 25, 2022 at 5:07 AM Mikulas Patocka <mpatocka@...hat.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