diff --git a/lib/libc/gen/arc4random.3 b/lib/libc/gen/arc4random.3 index 1d5b3b9f43cb..1b042f15f000 100644 --- a/lib/libc/gen/arc4random.3 +++ b/lib/libc/gen/arc4random.3 @@ -1,162 +1,173 @@ .\" $OpenBSD: arc4random.3,v 1.37 2019/09/29 16:30:35 jmc Exp $ .\" .\" Copyright 1997 Niels Provos .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. All advertising materials mentioning features or use of this software .\" must display the following acknowledgement: .\" This product includes software developed by Niels Provos. .\" 4. The name of the author may not be used to endorse or promote products .\" derived from this software without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" .\" Manual page, using -mandoc macros .\" -.Dd April 13, 2020 +.Dd November 18, 2024 .Dt ARC4RANDOM 3 .Os .Sh NAME .Nm arc4random , .Nm arc4random_buf , .Nm arc4random_uniform .Nd random number generator .Sh LIBRARY .Lb libc .Sh SYNOPSIS .In stdlib.h .Ft uint32_t .Fn arc4random "void" .Ft void .Fn arc4random_buf "void *buf" "size_t nbytes" .Ft uint32_t .Fn arc4random_uniform "uint32_t upper_bound" .Sh DESCRIPTION This family of functions provides higher quality data than those described in .Xr rand 3 , .Xr random 3 , and .Xr rand48 3 . .Pp Use of these functions is encouraged for almost all random number consumption because the other interfaces are deficient in either quality, portability, standardization, or availability. These functions can be called in almost all coding environments, including .Xr pthread 3 and .Xr chroot 2 . .Pp High quality 32-bit pseudo-random numbers are generated very quickly. On each call, a cryptographic pseudo-random number generator is used to generate a new result. One data pool is used for all consumers in a process, so that consumption under program flow can act as additional stirring. The subsystem is re-seeded from the kernel .Xr random 4 subsystem using .Xr getentropy 3 on a regular basis, and also upon .Xr fork 2 . .Pp The .Fn arc4random function returns a single 32-bit value. The .Fn arc4random function returns pseudo-random numbers in the range of 0 to .if t 2\u\s731\s10\d\(mi1, .if n (2**32)\(mi1, and therefore has twice the range of .Xr rand 3 and .Xr random 3 . .Pp .Fn arc4random_buf fills the region .Fa buf of length .Fa nbytes with random data. .Pp .Fn arc4random_uniform will return a single 32-bit value, uniformly distributed but less than .Fa upper_bound . This is recommended over constructions like .Dq Li arc4random() % upper_bound as it avoids "modulo bias" when the upper bound is not a power of two. In the worst case, this function may consume multiple iterations to ensure uniformity; see the source code to understand the problem and solution. .Sh RETURN VALUES These functions are always successful, and no return value is reserved to indicate an error. .Sh EXAMPLES The following produces a drop-in replacement for the traditional .Fn rand and .Fn random functions using .Fn arc4random : .Pp .Dl "#define foo4random() (arc4random_uniform(RAND_MAX + 1))" .Sh SEE ALSO .Xr rand 3 , .Xr rand48 3 , .Xr random 3 .Rs .%A Daniel J. Bernstein .%T ChaCha, a variant of Salsa20 .%D 2008-01-28 .%O Document ID: 4027b5256e17b9796842e6d0f68b0b5e .%U http://cr.yp.to/papers.html#chacha .Re +.Rs +.%A Daniel Lemire +.%T Fast Random Integer Generation in an Interval +.%D January 2019 +.%J ACM Trans. Model. Comput. Simul. +.%I Association for Computing Machinery +.%C New York, NY, USA +.%V vol. 29 +.%N no. 1 +.%P pp. 1\(en12 +.Re .Sh HISTORY These functions first appeared in .Ox 2.1 . .Fn arc4random first appeared in .Fx 3.0 . .Fn arc4random_buf and .Fn arc4random_uniform first appeared in .Fx 8.0 . .Fn arc4random_stir was removed in .Fx 12.0 . .Pp The original version of this random number generator used the RC4 (also known as ARC4) algorithm. In .Ox 5.5 it was replaced with the ChaCha20 cipher, and it may be replaced again in the future as cryptographic techniques advance. A good mnemonic is .Dq A Replacement Call for Random . .Pp The .Fn arc4random random number generator was first introduced in .Fx 2.2.6 . The ChaCha20 based implementation was introduced in .Fx 12.0 , with obsolete stir and addrandom interfaces removed at the same time. diff --git a/lib/libc/gen/arc4random_uniform.c b/lib/libc/gen/arc4random_uniform.c index 06cd29c6dbe4..23455e545899 100644 --- a/lib/libc/gen/arc4random_uniform.c +++ b/lib/libc/gen/arc4random_uniform.c @@ -1,56 +1,47 @@ -/* $OpenBSD: arc4random_uniform.c,v 1.3 2019/01/20 02:59:07 bcook Exp $ */ - -/* - * Copyright (c) 2008, Damien Miller +/*- + * SPDX-License-Identifier: 0BSD * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. + * Copyright (c) Robert Clausecker + * Based on a publication by Daniel Lemire. + * Public domain where applicable. * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * Daniel Lemire, "Fast Random Integer Generation in an Interval", + * Association for Computing Machinery, ACM Trans. Model. Comput. Simul., + * no. 1, vol. 29, pp. 1--12, New York, NY, USA, January 2019. */ #include #include -/* - * Calculate a uniformly distributed random number less than upper_bound - * avoiding "modulo bias". - * - * Uniformity is achieved by generating new random numbers until the one - * returned is outside the range [0, 2**32 % upper_bound). This - * guarantees the selected random number will be inside - * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) - * after reduction modulo upper_bound. - */ uint32_t arc4random_uniform(uint32_t upper_bound) { - uint32_t r, min; - - if (upper_bound < 2) - return 0; - - /* 2**32 % x == (2**32 - x) % x */ - min = -upper_bound % upper_bound; + uint64_t product; /* - * This could theoretically loop forever but each retry has - * p > 0.5 (worst case, usually far better) of selecting a - * number inside the range we need, so it should rarely need - * to re-roll. + * The paper uses these variable names: + * + * L -- log2(UINT32_MAX+1) + * s -- upper_bound + * x -- arc4random() return value + * m -- product + * l -- (uint32_t)product + * t -- threshold */ - for (;;) { - r = arc4random(); - if (r >= min) - break; + + if (upper_bound <= 1) + return (0); + + product = upper_bound * (uint64_t)arc4random(); + + if ((uint32_t)product < upper_bound) { + uint32_t threshold; + + /* threshold = (2**32 - upper_bound) % upper_bound */ + threshold = -upper_bound % upper_bound; + while ((uint32_t)product < threshold) + product = upper_bound * (uint64_t)arc4random(); } - return r % upper_bound; + return (product >> 32); }