From patchwork Tue Aug 2 12:25:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 56495 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4358D3850843 for ; Tue, 2 Aug 2022 12:25:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4358D3850843 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1659443151; bh=nYfhLl2WEo3JhCxCvApdC3mTEJFrOhZSv7QH4EcYB4I=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=pm619h+6Nb9T0RwjiolncYv1mPCm0u01K5SFXB/Lk/BCxv6Hw0ldRKs9srZ75GbBL R5ZBSZGHxzZcS2tr8LvQred9N8dEVmKbAZzjLQ4STBFgbiB3bUvS9F3b3A2Iklqc0a OrtQ0dvivAD2KPOTyLJn+SCo3WjQp7kJ+lMpYRY0= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-vs1-xe2e.google.com (mail-vs1-xe2e.google.com [IPv6:2607:f8b0:4864:20::e2e]) by sourceware.org (Postfix) with ESMTPS id 69C003856DE8 for ; Tue, 2 Aug 2022 12:25:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 69C003856DE8 Received: by mail-vs1-xe2e.google.com with SMTP id l68so14366545vsc.0 for ; Tue, 02 Aug 2022 05:25:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=nYfhLl2WEo3JhCxCvApdC3mTEJFrOhZSv7QH4EcYB4I=; b=QKYJWeFVVxb1vhOTb7VXGks9GP441jRSLMPXqxru3ODKucvqPjeN3eUqf7GsMHC/qP OzbCIFG6GZBYwoB4leuXUjXtKYkzcRtWsEMnvgd9jyGyR3ZMCJhlv4jikn78nEtF2nqD 7PIMjppn3VL7DmIxuZ5JOlZmCwinga6D1XYqX45sNfzjhwNcASUjGZHdMMk+Uyp5O+gL WJUsNEKVP96Lmk/Z4fqjnovNPI8ZsMNIdkDWd0TcfeVAASnQbkJGTJ3ufgJW+/c2+34S sO0Bh+JiqNxvprbs8rZG7Kl9r9BUroMfcxq6yHSkI5vK+RGVfY6WpzTnSa7OGhdtU8lJ K38w== X-Gm-Message-State: ACgBeo1wSrzsjRBTn6W6wINBtLyHY1IsUUNupFL6HppXWbaZtZ/OFstR k5s6cGdTUQeL3a/LItrQYPUjWiPiYh9S9w== X-Google-Smtp-Source: AA6agR5naJgm0oeeqxBTBqfDNjvaJzjc3DRBKKbQ/NCFeapduK2zLvxgOU9BO4R3mq1fTP181H9+qA== X-Received: by 2002:a67:1c46:0:b0:386:6221:7099 with SMTP id c67-20020a671c46000000b0038662217099mr3112865vsc.10.1659443129611; Tue, 02 Aug 2022 05:25:29 -0700 (PDT) Received: from mandiga.. ([2804:431:c7cb:1e34:2331:a60b:db1e:6436]) by smtp.gmail.com with ESMTPSA id g16-20020ab072d0000000b00384ddcfcf6asm8487737uap.8.2022.08.02.05.25.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 02 Aug 2022 05:25:29 -0700 (PDT) To: libc-alpha@sourceware.org, Yann Droneaud Subject: [PATCH] stdlib: Remove possible bias in arc4random_uniform Date: Tue, 2 Aug 2022 09:25:26 -0300 Message-Id: <20220802122526.1235666-1-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Spam-Status: No, score=-12.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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-Patchwork-Original-From: Adhemerval Zanella via Libc-alpha From: Adhemerval Zanella Reply-To: Adhemerval Zanella Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" It turned out that the shift optimziation to reuse the discarded bits might introduce bias [1]. This patch removes is and just issue another round if the condition can not be satisfied. Checked on x86_64-linux-gnu. [1] https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe --- stdlib/arc4random_uniform.c | 17 +---------------- 1 file changed, 1 insertion(+), 16 deletions(-) diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c index 5aa98d1c13..342937e5a6 100644 --- a/stdlib/arc4random_uniform.c +++ b/stdlib/arc4random_uniform.c @@ -25,9 +25,6 @@ N, successively queries new random values, and rejects values outside of the request range. - For reject values, it also tries if the remaining entropy could fit on - the asked range after range adjustment. - The algorithm avoids modulo and divide operations, which might be costly depending on the architecture. */ uint32_t @@ -43,9 +40,7 @@ __arc4random_uniform (uint32_t n) return __arc4random () & (n - 1); /* mask is the smallest power of 2 minus 1 number larger than n. */ - int z = __builtin_clz (n); - uint32_t mask = ~UINT32_C(0) >> z; - int bits = CHAR_BIT * sizeof (uint32_t) - z; + uint32_t mask = ~UINT32_C(0) >> __builtin_clz (n); while (1) { @@ -55,16 +50,6 @@ __arc4random_uniform (uint32_t n) 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; - r = value & mask; - if (r < n) - return r; - } } } libc_hidden_def (__arc4random_uniform)