Re: [PATCH v2] stdlib: Simplify arc4random_uniform

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 02/08/22 09:26, Yann Droneaud wrote:
> Le 02/08/2022 à 14:14, Adhemerval Zanella Netto a écrit :
>>
>> 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).
>>
> It's the proposal to shift by 1 bit which would introduce a bias.
> 
> The implementation used in Glibc is fine.

Hum I understood wrongly then, since it seemed you are answering to Noah question
for glibc implementation itself. I though I has this sort out, but I am not sure
anymore.