From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oi1-x232.google.com (mail-oi1-x232.google.com [IPv6:2607:f8b0:4864:20::232]) by sourceware.org (Postfix) with ESMTPS id 31D6C3858C53 for ; Wed, 20 Apr 2022 12:38:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 31D6C3858C53 Received: by mail-oi1-x232.google.com with SMTP id s16so1912806oie.0 for ; Wed, 20 Apr 2022 05:38:17 -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:in-reply-to :content-transfer-encoding; bh=toUzc85GWLFCYshXXuO+LF/tFyTRPkd2CFSiKlIUDy8=; b=YQKIoIM4nNPMve7GYbQ3/2Enk5j+nqDi3dm5JvL+44Qu3UJw3plp3zHOKBqBV9/seO jaya/WS1evQxMGxCY5JN5xTDxYTCC8aTKSRmojJmzZQwFE62KdPaMJhE+nS9ob8zgZeW BBzJIBmzojrD00/352YrJ9RpjF/zXKcknvMl6obvNJQ6qdH+q4NcqhlQkBzt1SnQbezr f/hQugDrr3Fhd6yVuMfYFz25MK4Jerh5on9Msdw9DV4nvnqHtzUzD55Kryjv4S07d+AC tYY/HN7XtKHnltmGkLU98TGhXEMfh75O1hdWZQPGZQ6DNNEuc/nlf0M8vDOyAmQLlGzP sLPg== X-Gm-Message-State: AOAM532/L8oFOMd7EZxatu/pnJADUZ71NRDexZX8QYY9N0w+2M2xRerf BTj44YWSs/bkoErTv4Hw7Mf0tg== X-Google-Smtp-Source: ABdhPJz2e38W/UAp4wix0GZrddw3yNH0xXkwQZMyIRANZe3DnQ1b4GdTun8JZIQkuq4PktGlAUTTEg== X-Received: by 2002:a05:6808:1201:b0:2f9:ef08:1a4f with SMTP id a1-20020a056808120100b002f9ef081a4fmr1595787oil.192.1650458296354; Wed, 20 Apr 2022 05:38:16 -0700 (PDT) Received: from ?IPV6:2804:431:c7ca:c9d0:24b1:bd98:2ef4:714c? ([2804:431:c7ca:c9d0:24b1:bd98:2ef4:714c]) by smtp.gmail.com with ESMTPSA id z82-20020aca3355000000b002ef73b018absm6163284oiz.9.2022.04.20.05.38.14 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 20 Apr 2022 05:38:15 -0700 (PDT) Message-ID: Date: Wed, 20 Apr 2022 09:38:13 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.0 Subject: Re: [PATCH v3 1/9] stdlib: Add arc4random, arc4random_buf, and arc4random_uniform (BZ #4417) Content-Language: en-US To: "H.J. Lu" Cc: GNU C Library , Florian Weimer References: <20220419212812.2688764-1-adhemerval.zanella@linaro.org> <20220419212812.2688764-2-adhemerval.zanella@linaro.org> From: Adhemerval Zanella In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-15.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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: Wed, 20 Apr 2022 12:38:19 -0000 On 19/04/2022 18:52, H.J. Lu wrote: > On Tue, Apr 19, 2022 at 2:29 PM Adhemerval Zanella via Libc-alpha > wrote: >> >> >> diff --git a/NEWS b/NEWS >> index 4b6d9de2b5..4d9d95b35b 100644 >> --- a/NEWS >> +++ b/NEWS >> @@ -9,7 +9,9 @@ Version 2.36 >> >> Major new features: >> >> - [Add new features here] >> +* The functions arc4random, arc4random_buf, arc4random_uniform have been >> + added. The functions use a cryptographic pseudo-random number generator >> + based on ChaCha20 initilized with entropy from kernel. > ^^^^^^^^ Typo. >> >> Deprecated and removed features, and other changes affecting compatibility: Ack. >> + >> +/* Besides the cipher state 'ctx', it keeps two counters: 'have' is the >> + current valid bytes not yet consumed in 'buf', while 'count' is the maximum >> + number of bytes until a reseed. >> + >> + Both the initial seed an reseed tries to obtain entropy from the kernel > ^^^^^^^^^^^^^^^^ Typo? >> + and abort the process if none could be obtained. >> + >> + The state 'buf' improves the usage of the cipher call, allowing to call >> + optimized implementations (if the archictecture provides it) and optimize > ^^^^^^^^^^^^ Typo? Ack. >> + >> + /* The general case. This algorithm follows Jérémie Lumbroso, >> + Optimal Discrete Uniform Generation from Coin Flips, and >> + Applications (2013), who credits Donald E. Knuth and Andrew >> + C. Yao, The complexity of nonuniform random number generation >> + (1976), for solving the general case. >> + >> + The implementation below unrolls the initialization stage of the >> + loop, where v is less than n. */ >> + >> + /* Use 64-bit variables even though the intermediate results are >> + never larger that 33 bits. This ensures the code easier to > than Ack. >> + compile on 64-bit architectures. */ >> + uint64_t v; >> + uint64_t c; >> + >> + /* Initialize v and c. v is the smallest power of 2 which is larger >> + than n.*/ >> + { >> + uint32_t log2p1 = 32 - __builtin_clz (n); >> + v = 1ULL << log2p1; >> + c = bits & (v - 1); >> + bits >>= log2p1; >> + bits_length -= log2p1; >> + } >> + >> + /* At the start of the loop, c is uniformly distributed within the >> + half-open interval [0, v), and v < 2n < 2**33. */ >> + while (true) >> + { >> + if (v >= n) >> + { >> + /* If the candidate is less than n, accept it. */ >> + if (c < n) >> + /* c is uniformly distributed on [0, n). */ >> + return c; >> + else >> + { >> + /* c is uniformly distributed on [n, v). */ >> + v -= n; >> + c -= n; >> + /* The distribution was shifted, so c is uniformly >> + distributed on [0, v) again. */ >> + } >> + } >> + /* v < n here. */ >> + >> + /* Replenish the bit source if necessary. */ >> + if (bits_length == 0) >> + { >> + /* Overwrite the least significant byte. */ >> + random_bytes (&bits, 1); >> + bits_length = CHAR_BIT; >> + } >> + >> + /* Double the range. No overflow because v < n < 2**32. */ >> + v *= 2; >> + /* v < 2n here. */ >> + >> + /* Extract a bit and append it to c. c remains less than v and >> + thus 2**33. */ >> + c = (c << 1) | (bits & 1); >> + bits >>= 1; >> + --bits_length; >> + >> + /* At this point, c is uniformly distributed on [0, v) again, >> + and v < 2n < 2**33. */ >> + } >> +} >> + >> +__libc_lock_define (extern , __arc4random_lock attribute_hidden) >> + >> +uint32_t >> +__arc4random_uniform (uint32_t upper_bound) >> +{ >> + uint32_t r; >> + __libc_lock_lock (__arc4random_lock); >> + r = compute_uniform (upper_bound); >> + __libc_lock_unlock (__arc4random_lock); >> + return r; >> +} >> +libc_hidden_def (__arc4random_uniform) >> +weak_alias (__arc4random_uniform, arc4random_uniform) >> diff --git a/stdlib/chacha20.c b/stdlib/chacha20.c >> new file mode 100644 >> index 0000000000..af4ffa9860 >> --- /dev/null >> +++ b/stdlib/chacha20.c >> @@ -0,0 +1,163 @@ >> +/* Generic ChaCha20 implementation (used on arc4random). >> + Copyright (C) 2022 Free Software Foundation, Inc. >> + This file is part of the GNU C Library. >> + >> + The GNU C Library is free software; you can redistribute it and/or >> + modify it under the terms of the GNU Lesser General Public >> + License as published by the Free Software Foundation; either >> + version 2.1 of the License, or (at your option) any later version. >> + >> + The GNU C Library is distributed in the hope that it will be useful, >> + but WITHOUT ANY WARRANTY; without even the implied warranty of >> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU >> + Lesser General Public License for more details. >> + >> + You should have received a copy of the GNU Lesser General Public >> + License along with the GNU C Library; if not, see >> + . */ >> + >> +#include >> +#include >> +#include >> +#include >> +#include >> + >> +/* 32-bit stream position, then 96-bit nonce. */ >> +#define CHACHA20_IV_SIZE 16 >> +#define CHACHA20_KEY_SIZE 32 >> + >> +#define CHACHA20_BLOCK_SIZE 64 >> +#define CHACHA20_BLOCK_WORDS (CHACHA20_BLOCK_SIZE / sizeof (uint32_t)) >> + >> +#define CHACHA20_STATE_LEN 16 >> + >> +/* Defining CHACHA20_XOR_FINAL issues the final XOR using the input as defined >> + Sby RFC8439. Since the input stream will either zero bytes (initial state) > by Ack.