netdev - Re: [PATCH 16/18] net: mpls: prevent bounds-check bypass via speculative execution

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]

Date:   Tue, 9 Jan 2018 16:48:24 -0800
From:   Dan Williams <dan.j.williams@...el.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     "Eric W. Biederman" <ebiederm@...ssion.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        linux-arch@...r.kernel.org, Peter Zijlstra <peterz@...radead.org>,
        Netdev <netdev@...r.kernel.org>,
        Greg KH <gregkh@...uxfoundation.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        "David S. Miller" <davem@...emloft.net>,
        Elena Reshetova <elena.reshetova@...el.com>,
        Alan Cox <alan@...ux.intel.com>
Subject: Re: [PATCH 16/18] net: mpls: prevent bounds-check bypass via
 speculative execution

On Mon, Jan 8, 2018 at 8:13 PM, Linus Torvalds
<torvalds@...ux-foundation.org> wrote:
>
> On Mon, Jan 8, 2018 at 7:42 PM, Dan Williams <dan.j.williams@...el.com> wrote:
> >
> > originally from Linus and tweaked by Alexei and I:
>
> Sadly, that tweak - while clever - is wrong.
>
> >         unsigned long _mask = ~(long)(_m - 1 - _i) >> BITS_PER_LONG - 1;\
>
> Why?
>
> Because "(long)(_m-1-_i)" is not negative just because "i >= m". It
> can still be positive.
>
> Think "m = 100", "i=bignum". The subtraction will overflow and become
> positive again, the shift will shift to zero, and then the mask will
> become ~0.
>
> Now, you can fix it, but you need to be a tiny bit more clever.  In
> particular, just make sure that you retain the high bit of "_i",
> basically making the rule be that a negative index is not ever valid.
>
> And then instead of "(_m - 1 - _i)", you use "(_i | (_m - 1 - _i))".
> Now the sign bit is set if _i had it set, _or_ if the subtraction
> turned negative, and you don't have to worry about the overflow
> situation.
>
> But it does require that extra step to be trustworthy. Still purely
> cheap arithmetic operations, although there is possibly some
> additional register pressure there.
>
> Somebody might be able to come up with something even more minimal (or
> find a fault in my fix of your tweak).

I looks like there is another problem, or I'm misreading the
cleverness. We want the mask to be ~0 in the ok case and 0 in the
out-of-bounds case. As far as I can see we end up with ~0 in the ok
case, and ~1 in the bad case. Don't we need to do something like the
following, at which point are we getting out of the realm of "cheap
ALU instructions"?

#define __nospec_array_ptr(base, idx, sz)                               \
({                                                                      \
        union { typeof(&base[0]) _ptr; unsigned long _bit; } __u;       \
        unsigned long _i = (idx);                                       \
        unsigned long _s = (sz);                                        \
        unsigned long _v = (long)(_i | _s - 1 - _i)                     \
                                        >> BITS_PER_LONG - 1;           \
        unsigned long _mask = _v * ~0UL;                                 \
        OPTIMIZER_HIDE_VAR(_mask);                                      \
        __u._ptr = &base[_i & _mask];                                   \
        __u._bit &= _mask;                                              \
        __u._ptr;                                                       \
})

        elem = nospec_array_ptr(array, idx, 3);
 106:   b8 02 00 00 00          mov    $0x2,%eax
 10b:   48 63 ff                movslq %edi,%rdi
 10e:   48 29 f8                sub    %rdi,%rax
 111:   48 09 f8                or     %rdi,%rax
 114:   48 c1 e8 3f             shr    $0x3f,%rax
 118:   48 21 c7                and    %rax,%rdi
 11b:   48 8d 54 bc 04          lea    0x4(%rsp,%rdi,4),%rdx
 120:   48 21 d0                and    %rdx,%rax