linux-kernel - Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

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: <CAGXu5jLE+RzLqby3icnHGdAeGQV_vBxDMsNkEtuXhEkWRFWF+A@mail.gmail.com>
Date:   Thu, 19 Oct 2017 14:04:02 -0700
From:   Kees Cook <keescook@...omium.org>
To:     "Jason A. Donenfeld" <Jason@...c4.com>
Cc:     Michael Davidson <md@...gle.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Ingo Molnar <mingo@...nel.org>,
        David Miller <davem@...emloft.net>,
        Matthew Wilcox <mawilcox@...rosoft.com>,
        LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

On Thu, Oct 19, 2017 at 1:56 PM, Jason A. Donenfeld <Jason@...c4.com> wrote:
> On Thu, Oct 19, 2017 at 10:42 PM, Kees Cook <keescook@...omium.org> wrote:
>> Maybe a stupid question, but is this function ultimately used by any
>> crypto that expects it to be constant-time for safety?
>
> Indeed constant time functions for crypto are important. But in this
> case, it's unlikely this function would ever be used for real crypto,
> which usually works over "bigints" -- integers that are much wider
> than a single unsigned long. The algorithm here is just for a single
> int. (By the way, if you're into fast integer arithmetic, check cut
> this amazing Quake-era inverse squareroot algorithm:
> https://en.wikipedia.org/wiki/Fast_inverse_square_root )

Oh nice; that's a fun read. :) (And on a related note, hey everyone,
go donate to Wikipedia!)

> I haven't analyzed all the other call sites for side channel
> potentials, but a quick cursory look indicates it's pretty boring and
> likely uneventful.

Okay, that was my quick assessment too.

FWIW:

Acked-by: Kees Cook <keescook@...omium.org>

> One use of int_sqrt that caught my eye was lib/prime_numbers.c, which
> itself exposes two functions -- is_prime_number, which is unused, and
> next_prime_number, which is only used by some selftests in the i915
> drm stuff, but not any actual real kernel code. Talk about bloat.

Heh.

-Kees

-- 
Kees Cook
Pixel Security