[PATCH] stdlib: Remove possible bias in arc4random_uniform

[PATCH] stdlib: Remove possible bias in arc4random_uniform

[Adhemerval Zanella]

It turned out that the shift optimziation to reuse the discarded bits
might introduce bias [1].  This patch removes is and just issue another
round if the condition can not be satisfied.

Checked on x86_64-linux-gnu.

[1] https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe
---
 stdlib/arc4random_uniform.c | 17 +----------------
 1 file changed, 1 insertion(+), 16 deletions(-)

diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
index 5aa98d1c13..342937e5a6 100644
--- a/stdlib/arc4random_uniform.c
+++ b/stdlib/arc4random_uniform.c
@@ -25,9 +25,6 @@
    N, successively queries new random values, and rejects values outside of
    the request range.
 
-   For reject values, it also tries if the remaining entropy could fit on
-   the asked range after range adjustment.
-
    The algorithm avoids modulo and divide operations, which might be costly
    depending on the architecture.  */
 uint32_t
@@ -43,9 +40,7 @@ __arc4random_uniform (uint32_t n)
     return __arc4random () & (n - 1);
 
   /* mask is the smallest power of 2 minus 1 number larger than n.  */
-  int z = __builtin_clz (n);
-  uint32_t mask = ~UINT32_C(0) >> z;
-  int bits = CHAR_BIT * sizeof (uint32_t) - z;
+  uint32_t mask = ~UINT32_C(0) >> __builtin_clz (n);
 
   while (1)
     {
@@ -55,16 +50,6 @@ __arc4random_uniform (uint32_t n)
       uint32_t r = value & mask;
       if (r < n)
 	return r;
-
-      /* Otherwise check if remaining bits of entropy provides fits in the
-	 bound.  */
-      for (int bits_left = z; bits_left >= bits; bits_left -= bits)
-	{
-	  value >>= bits;
-	  r = value & mask;
-	  if (r < n)
-	    return r;
-	}
     }
 }
 libc_hidden_def (__arc4random_uniform)
-- 
2.34.1

Re: [PATCH] stdlib: Remove possible bias in arc4random_uniform

[Adhemerval Zanella Netto]

On 02/08/22 09:25, Adhemerval Zanella wrote:
> It turned out that the shift optimziation to reuse the discarded bits
> might introduce bias [1].  This patch removes is and just issue another
> round if the condition can not be satisfied.
> 
> Checked on x86_64-linux-gnu.
> 
> [1] https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe

I understand wrongly the question on the crypto.stackexchange, the issues is to
reuse the already discarded bits after the test, which is not the case in glibc
implementation.