From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ua1-x929.google.com (mail-ua1-x929.google.com [IPv6:2607:f8b0:4864:20::929]) by sourceware.org (Postfix) with ESMTPS id 8603C3856DE8 for ; Tue, 2 Aug 2022 12:29:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8603C3856DE8 Received: by mail-ua1-x929.google.com with SMTP id 5so5712606uay.5 for ; Tue, 02 Aug 2022 05:29:20 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:organization:in-reply-to :content-transfer-encoding; bh=rH3oP7cP9OWl3pYGWmSujDkLVYsCvrT/KXWU0f0WajQ=; b=Z098OJ7oneuWQqQw+v/t8tXso/UsyY/GXKoSzetTvFaWPPhZ+rjt9cM/xX2s+aNunu jmyux2fCmex+XeYlskJxj2v0jGGOdSpzol5ENFTDntPbei0Y7/dLg2n/RqUVvWSkTL3b NqOY8uzZVMxaOWBEqyeDwc7PeunPw0tRN8R+xo9n9tzUvKMqrXG0nWsykQHRm0OAHIve xJcvfVevqHG++/vL9+kmHx/CTXBbr20F0l8c+klUFUspMOJt8ZCKWO4iVHbmBgzLTqeH P194FRG2kSebfG0SiVqYY0nRA30T4Vvw6ufEPjApsIJewynhK6Ain6DuoYS7mJE2GyYS DMZA== X-Gm-Message-State: ACgBeo2DJZk/ncdCfy/ycYaDDDTHZDgwktCRhgmI+uLt6ko12pT11fDa PkFsm+/WRN2W2v8SV7EwGBzEQw== X-Google-Smtp-Source: AA6agR5Vry3vP4qaJhHRDZa3JwvJIfLw5/WwZnaKaeFhfy8BKX9POwwuwP3oJkuBAXb/JX/N/TSiHw== X-Received: by 2002:ab0:32d8:0:b0:384:cced:87fb with SMTP id f24-20020ab032d8000000b00384cced87fbmr7608698uao.52.1659443359961; Tue, 02 Aug 2022 05:29:19 -0700 (PDT) Received: from ?IPV6:2804:431:c7cb:1e34:a813:f55c:8e00:64cd? ([2804:431:c7cb:1e34:a813:f55c:8e00:64cd]) by smtp.gmail.com with ESMTPSA id j14-20020a0561023e0e00b00386ecd2e38dsm2270533vsv.33.2022.08.02.05.29.18 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 02 Aug 2022 05:29:19 -0700 (PDT) Message-ID: <25dbcc12-eca6-123b-5da1-ef1b1c86ff74@linaro.org> Date: Tue, 2 Aug 2022 09:29:17 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.1.0 Subject: Re: [PATCH v2] stdlib: Simplify arc4random_uniform Content-Language: en-US To: Yann Droneaud , Noah Goldstein Cc: GNU C Library References: <20220729123211.876374-1-adhemerval.zanella@linaro.org> <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> <7f3fcfef-e37b-f455-c740-86eef4f23366@opteya.com> From: Adhemerval Zanella Netto Organization: Linaro In-Reply-To: <7f3fcfef-e37b-f455-c740-86eef4f23366@opteya.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 02 Aug 2022 12:29:22 -0000 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.