[PATCH v2] stdlib: Simplify arc4random_uniform
Adhemerval Zanella Netto
adhemerval.zanella@linaro.org
Tue Aug 2 12:14:47 GMT 2022
On 02/08/22 09:08, Yann Droneaud wrote:
> Hi,
>
> Le 01/08/2022 à 21:20, Noah Goldstein a écrit :
>>> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
>>> index 1326dfa593..5aa98d1c13 100644
>>> --- a/stdlib/arc4random_uniform.c
>>> +++ b/stdlib/arc4random_uniform.c
>>>
>>> uint32_t
>>> __arc4random_uniform (uint32_t n)
>>> {
>>> @@ -57,83 +38,33 @@ __arc4random_uniform (uint32_t n)
>>> + while (1)
>>> {
>>> + uint32_t value = __arc4random ();
>>> +
>>> + /* Return if the lower power of 2 minus 1 satisfy the condition. */
>>> + 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;
>> Can this just be shift by 1 and repeat (32 - z) times or does that
>> introduce bias (not seeing exactly why it would)?
>
>
> That was bothering me too, as I was thinking a rotation would be possible instead of shift.
>
> I posted the question https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe
>
> The answer: there's indeed a bias.
>
> This explains why my attempt with rotation leads to dieharder complaining. It was so obvious ... Damn
>
Thanks, I will remove it then. We might evaluate later if using the mask
and compare is indeed better than the other methods (as using by OpenBSD).
More information about the Libc-alpha
mailing list