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]

Date:   Thu, 19 Oct 2017 22:56:31 +0200
From:   "Jason A. Donenfeld" <Jason@...c4.com>
To:     Kees Cook <keescook@...omium.org>
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 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 )

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.

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.