[PATCH] stdlib: Remove possible bias in arc4random_uniform
Adhemerval Zanella
adhemerval.zanella@linaro.org
Tue Aug 2 12:25:26 GMT 2022
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_64linuxgnu.
[1] https://crypto.stackexchange.com/questions/101325/uniformrejectionsamplingbyshiftingorrotatingbitsfromcsprngoutputsafe

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
More information about the Libcalpha
mailing list