linux-kernel - Re: fix int_sqrt() for very large numbers

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:   Sun, 20 Jan 2019 15:48:49 +1200
From:   Linus Torvalds <torvalds@...ux-foundation.org>
To:     Will Deacon <will.deacon@....com>
Cc:     Florian La Roche <florian.laroche@...glemail.com>,
        Linux List Kernel Mailing <linux-kernel@...r.kernel.org>,
        Crt Mori <cmo@...exis.com>, Joe Perches <joe@...ches.com>,
        Davidlohr Bueso <dave@...olabs.net>,
        Peter Zijlstra <peterz@...radead.org>
Subject: Re: fix int_sqrt() for very large numbers

On Sun, Jan 20, 2019 at 12:01 PM Will Deacon <will.deacon@....com> wrote:
>
> > @@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x)
> >       if (x <= ULONG_MAX)
> >               return int_sqrt((unsigned long) x);
> >
> > -     m = 1ULL << (fls64(x) & ~1ULL);
> > +     m = 1ULL << ((fls64(x) - 1) & ~1ULL);
>
> This just looks like a copy-paste error because there isn't an __fls64().
> But I think your suggestion here is ok, given the previous check against
> ULONG_MAX.

Hmm. We probably *should* add a __fls64().

There looks to be only one user of int_sqrt64(), and that one is
confused. It does int_sqrt64() twice, but since the inner one will
reduce the range to 32 bits, the outer one is just silly.

That one user also had better not be overflowing into the high bit -
it uses "s64" as a type and does seem to use signed operatons, so high
bit set really means negative. sqrt() returning something odd for a
negative number wouldn't be all that odd in that context.

But yes, our current int_sqrt64() does seem buggy as-is, because it's
*supposed* to work on u64's, even if I don't think we really have any
users that care.

And as Will mentioned, the regular int_sqrt() looks perfectly fine,
and subtracting 1 from the __fls() return value would actually
_introduce_ a bug.

            Linus