stdlib: Remove possible bias in arc4random_uniform
Checks
| Context |
Check |
Description |
| dj/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
| dj/TryBot-32bit |
success
|
Build for i686
|
Commit Message
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
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.
@@ -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)