lib/int_sqrt.c: optimize for small argument values
PATCH 1/1 lib/int_sqrt.c: optimize for small argument values
int_sqrt() currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is.
--- lib/int_sqrt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/int_sqrt.c +1 -1
@@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)if (x <=1 )return x; - m =1UL << (BITS_PER_LONG -2 ); + m =1UL << (__fls (x) & ~1UL );while (m !=0 ) { b = y + m; y >>=1 ;
Signature · 1 line
2.15.0.rc1.287.g2b38de12cc-goog
Quoted 6 lines · Michael Davidson
int_sqrt()currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is.
Maybe a stupid question, but is this function ultimately used by any crypto that expects it to be constant-time for safety?
Also, is there a specific workload that is meaningfully sped up by this change?
-Kees
Quoted 22 lines
Signed-off-by Michael Davidson <[email protected]>--- lib/int_sqrt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/int_sqrt.c +1
-2@@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)if (x <=1 )return x; - m =1UL << (BITS_PER_LONG -2 ); + m =1UL << (__fls (x) & ~1UL );while (m !=0 ) { b = y + m; y >>=1 ; --2.15.0.rc1.287.g2b38de12cc-goog
Signature · 2 lines
Kees Cook Pixel Security
Quoted 2 lines · Kees Cook
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.
Kees Cook
Acked-byQuoted 11 lines · Jason A. Donenfeld
Quoted 2 lines · Kees Cook
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!)
Quoted 3 lines
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:
Quoted 4 lines
One use of
int_sqrtthat caught my eye waslib/prime_numbers.c, which itself exposes two functions --is_prime_number, which is unused, andnext_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
Signature · 2 lines
Kees Cook Pixel Security
Quoted 6 lines · Michael Davidson
int_sqrt()currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is.
Quoted 9 lines · Joe Perches
Quoted 6 lines · Michael Davidson
int_sqrt()currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is.
Ah! Cool. I don't see this version queued up for -next. Where does Peter's version stand?
-Kees
Signature · 2 lines
Kees Cook Pixel Security
Quoted 9 lines · Kees Cook
Quoted 8 lines · Joe Perches
Quoted 6 lines · Michael Davidson
int_sqrt()currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is.
Quoted 4 lines
Quoted 1 line
Ah! Cool. I don't see this version queued up for -next. Where does Peter's version stand?
Oh, crud, forgot all about it. I'd have to double check I addressed the concerns Linus had with my Changelogs, but other than that he seemed to be OK.