From: Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>
To: Yann Droneaud <ydroneaud@opteya.com>,
Noah Goldstein <goldstein.w.n@gmail.com>
Cc: GNU C Library <libc-alpha@sourceware.org>
Subject: Re: [PATCH v2] stdlib: Simplify arc4random_uniform
Date: Tue, 2 Aug 2022 09:14:47 -0300 [thread overview]
Message-ID: <d3ca9a1d-f41b-d77b-5b31-169e7ae123f6@linaro.org> (raw)
In-Reply-To: <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com>
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).
next prev parent reply other threads:[~2022-08-02 12:14 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-29 12:32 Adhemerval Zanella
2022-08-01 17:45 ` Adhemerval Zanella Netto
2022-08-01 19:20 ` Noah Goldstein
2022-08-02 12:08 ` Yann Droneaud
2022-08-02 12:14 ` Adhemerval Zanella Netto [this message]
2022-08-02 12:26 ` Yann Droneaud
2022-08-02 12:29 ` Adhemerval Zanella Netto
2022-08-02 13:06 ` Noah Goldstein
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d3ca9a1d-f41b-d77b-5b31-169e7ae123f6@linaro.org \
--to=adhemerval.zanella@linaro.org \
--cc=goldstein.w.n@gmail.com \
--cc=libc-alpha@sourceware.org \
--cc=ydroneaud@opteya.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).