From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4-g21.free.fr (smtp4-g21.free.fr [212.27.42.4]) by sourceware.org (Postfix) with ESMTPS id E123A3856DF3 for ; Tue, 2 Aug 2022 12:08:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E123A3856DF3 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=opteya.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=opteya.com Received: from [IPV6:2a01:e35:39f2:1220:64a3:f5aa:b8a4:1c4d] (unknown [IPv6:2a01:e35:39f2:1220:64a3:f5aa:b8a4:1c4d]) by smtp4-g21.free.fr (Postfix) with ESMTPS id BA19D19F733; Tue, 2 Aug 2022 14:08:32 +0200 (CEST) Message-ID: <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> Date: Tue, 2 Aug 2022 14:08:32 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH v2] stdlib: Simplify arc4random_uniform Content-Language: fr-FR To: Noah Goldstein Cc: GNU C Library References: <20220729123211.876374-1-adhemerval.zanella@linaro.org> From: Yann Droneaud Organization: OPTEYA In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.6 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, 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:08:37 -0000 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 Regards. -- Yann Droneaud OPTEYA