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

[Jason A. Donenfeld]

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 )

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.