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

[Kees Cook]

On Thu, Oct 19, 2017 at 1:56 PM, Jason A. Donenfeld <Jason@xxxxxxxxx> wrote:
> On Thu, Oct 19, 2017 at 10:42 PM, Kees Cook <keescook@xxxxxxxxxxxx> 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@xxxxxxxxxxxx>

> 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