[PATCH v2] stdlib: Simplify arc4random_uniform
Noah Goldstein
goldstein.w.n@gmail.com
Tue Aug 2 13:06:51 GMT 2022
On Tue, Aug 2, 2022 at 8:08 PM Yann Droneaud <ydroneaud@opteya.com> 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.
Hmm, based on the answer it seems we could shift by `popcnt(n)` (which is
guranteed to be <= bits). If I understand correctly the issue is the consecutive
leading 1s essentially fix ensuing ones but `popcnt(n)` will always clear
those fixed ones. After the first zero, the rest of the bits can be anything
I believe so there will be no bias from them.
>
> This explains why my attempt with rotation leads to dieharder
> complaining. It was so obvious ... Damn
>
>
> Regards.
>
>
> --
>
> Yann Droneaud
>
> OPTEYA
>
>
More information about the Libc-alpha
mailing list