diff mbox series

stdlib: Remove possible bias in arc4random_uniform

Message ID 20220802122526.1235666-1-adhemerval.zanella@linaro.org
State New
Headers show
Series stdlib: Remove possible bias in arc4random_uniform | expand

Commit Message

Adhemerval Zanella Aug. 2, 2022, 12:25 p.m. UTC 
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(-)

Comments

Adhemerval Zanella Aug. 2, 2022, 12:34 p.m. UTC | #1 
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.
diff mbox series

Patch

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)