From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x32e.google.com (mail-ot1-x32e.google.com [IPv6:2607:f8b0:4864:20::32e]) by sourceware.org (Postfix) with ESMTPS id 015C13858D1E for ; Tue, 26 Apr 2022 12:36:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 015C13858D1E Received: by mail-ot1-x32e.google.com with SMTP id c17-20020a056830349100b00605ca7d1deeso1381336otu.3 for ; Tue, 26 Apr 2022 05:36:19 -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:from:to:cc:references:in-reply-to :content-transfer-encoding; bh=xZCyrYvRoCIOS+t1o6yq+vDNP2NWXY9bNrJDUNYMT8M=; b=ov4vICJ196xBXRfBFj/uvgrBzSnFBn6W00uyyAJtSWdbXRTsdtOdk1ROj4EwWv3zov 98Pg9lTMpWsqXItr6HOQcigw6KQZ8C8Kuzm9ulvhkwpbRFdbXiy8MBOaw4/fpW7Xyeff u3mEGtFiuyRhvCvYKyaGiEqoKZDOs3nQW/1BSTJSMMnVqzkZOfA8ZSneJ4X33wsuSOPG dUCcnZ9wEH/IYXaKxig0IGkxSILNdgd/pnX1jfxV8EeP44x9FLEvQhvlMYkeKYjiW7FI XBDxSWwZTv7TnIWjCDy7OHCnb3RfRFQoZK4aZag4NU10fEe207dJisNoeNKaZx490/9+ 3asQ== X-Gm-Message-State: AOAM531no1NTtwQ+xP75OEtfYlZLbYmPciMC7M6bdPIAab+N9wA2u/Wg mvAw/k0xgw0KiXzfWDrqe+9dX40cssl7+A== X-Google-Smtp-Source: ABdhPJyfN7Zbxq/RIquRZQBwylzUJIblG+ErxT9lM5if3H7bIvpmwya39KX5fwMJFUuFPO0ovoUmEQ== X-Received: by 2002:a05:6830:3182:b0:604:5728:523f with SMTP id p2-20020a056830318200b006045728523fmr8128533ots.273.1650976578970; Tue, 26 Apr 2022 05:36:18 -0700 (PDT) Received: from ?IPV6:2804:431:c7ca:4214:1cb8:b955:7538:328c? ([2804:431:c7ca:4214:1cb8:b955:7538:328c]) by smtp.gmail.com with ESMTPSA id m16-20020a9d7e90000000b006054bb3bc6csm4829910otp.72.2022.04.26.05.36.17 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 26 Apr 2022 05:36:18 -0700 (PDT) Message-ID: Date: Tue, 26 Apr 2022 09:36:15 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 Subject: Re: [PATCH v4 1/9] stdlib: Add arc4random, arc4random_buf, and arc4random_uniform (BZ #4417) Content-Language: en-US From: Adhemerval Zanella To: libc-alpha@sourceware.org, "H.J. Lu" Cc: Florian Weimer References: <20220425130156.1062525-1-adhemerval.zanella@linaro.org> <20220425130156.1062525-2-adhemerval.zanella@linaro.org> In-Reply-To: <20220425130156.1062525-2-adhemerval.zanella@linaro.org> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-7.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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, 26 Apr 2022 12:36:21 -0000 On 25/04/2022 10:01, Adhemerval Zanella wrote: > The implementation is based on scalar Chacha20, with global cache and > locking. It uses getrandom or /dev/urandom as fallback to get the > initial entropy, and reseeds the internal state on every 16MB of > consumed buffer. > > It maintains an internal buffer which consumes at maximum one page on > most systems (assuming minimum of 4k pages). The internal buf optimizes > the cipher encrypt calls, by amortizing arc4random calls (where both > function call and lock cost are the dominating factor). > > The ChaCha20 implementation is based on RFC8439 [1], omitting the final > XOR of the keystream with the plaintext because the plaintext is a > stream of zeros. This strategy is similar to what OpenBSD arc4random > does. > > The arc4random_uniform is based on previous work by Florian Weimer, > where the algorithm is based on Jérémie Lumbroso paper Optimal Discrete > Uniform Generation from Coin Flips, and Applications (2013) [2], who > credits Donald E. Knuth and Andrew C. Yao, The complexity of nonuniform > random number generation (1976), for solving the general case. > > The main advantage of this method is the that the unit of randomness is not > the uniform random variable (uint32_t), but a random bit. It optimizes the > internal buffer sampling by initially consuming a 32-bit random variable > and then sampling byte per byte. Depending of the upper bound requested, > it might lead to better CPU utilization. > > Checked on x86_64-linux-gnu, aarch64-linux, and powerpc64le-linux-gnu. > > Co-authored-by: Florian Weimer > > [1] https://datatracker.ietf.org/doc/html/rfc8439 > [2] https://arxiv.org/pdf/1304.1916.pdf And I forgot to address H.J review [1] for this one. I fixed them locally. [1] https://sourceware.org/pipermail/libc-alpha/2022-April/137973.html