[RFC v1 1/2] Add arc4random_range(min, max)

Signed-off-by: Alejandro Colomar <alx@kernel.org>
---

Hi,

The patch to the manual page is still a draft; I know it has formatting
issues; I don't know mdoc(7) enough to write in it. I CCd Ingo so that
he may help me improve it.

Theo, and any others, please consider the addition of this function,
since it helps make some of these bugs shallow. My audit of the
existing code is incomplete, since I don't have much knowledge of
OpenBSD's internals. Moreover, this patch set is only a draft for
discussion, and I didn't yet even attempt to compile; I may have written
typos and may fail to even compile. I just want to start the discussion
with facts and code, and when there's some agreement, I'll be try to
compile this.

Cheers,

Alex


include/stdlib.h | 1 +
lib/libc/crypt/arc4random.3 | 35 ++++++++++++++++++++++++++++-
lib/libc/crypt/arc4random_uniform.c | 12 ++++++++++
sys/dev/rnd.c | 11 +++++++++
sys/sys/systm.h | 1 +
5 files changed, 59 insertions(+), 1 deletion(-)

diff --git a/include/stdlib.h b/include/stdlib.h
index ab8a2ae90c3..16b7dc43afc 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -313,6 +313,7 @@ u_quad_t strtouq(const char *__restrict, char **__restrict, int);

uint32_t arc4random(void);
uint32_t arc4random_uniform(uint32_t);
+uint32_t arc4random_uniform(uint32_t, uint32_t);
void arc4random_buf(void *, size_t)
__attribute__((__bounded__ (__buffer__,1,2)));

diff --git a/lib/libc/crypt/arc4random.3 b/lib/libc/crypt/arc4random.3
index 411860c28f2..78b4c18b3da 100644
--- a/lib/libc/crypt/arc4random.3
+++ b/lib/libc/crypt/arc4random.3
@@ -46,6 +46,8 @@
.Fn arc4random_buf "void *buf" "size_t nbytes"
.Ft uint32_t
.Fn arc4random_uniform "uint32_t upper_bound"
+.Ft uint32_t
+.Fn arc4random_uniform "uint32_t min" "uint32_t max"
.Sh DESCRIPTION
This family of functions provides higher quality data than those
described in
@@ -95,16 +97,47 @@
In the worst case, this function may consume multiple iterations
to ensure uniformity; see the source code to understand the problem
and solution.
+.Pp
+.Fn arc4random_range
+is similar to
+.Fn arc4random_uniform ,
+and will return a single 32-bit value,
+uniformly distributed,
+within the inclusive range
+.Pf [ Fa min ,
+.Fa max ].
+If the arguments are reversed,
+that is,
+if
+.Fa max
+<
+.Fa min ,
+it will return a single 32-bit value,
+uniformly distributed,
+outside of the exclusive range
+.Pf ( Fa max ,
+.Fa min ).
.Sh RETURN VALUES
These functions are always successful, and no return value is
reserved to indicate an error.
+.Sh CAVEATS
+.Fn arc4random_range
+doesn't produce correct output when
+.Fa max
+==
+.Fa min
+- 1.
.Sh SEE ALSO
.Xr rand 3 ,
.Xr rand48 3 ,
.Xr random 3
.Sh HISTORY
These functions first appeared in
-.Ox 2.1 .
+.Ox 2.1 ,
+except
+.Fn arc4random_range ,
+which appeared in
+.Ox XXX .
.Pp
The original version of this random number generator used the
RC4 (also known as ARC4) algorithm.
diff --git a/lib/libc/crypt/arc4random_uniform.c b/lib/libc/crypt/arc4random_uniform.c
index a18b5b12381..40957910b96 100644
--- a/lib/libc/crypt/arc4random_uniform.c
+++ b/lib/libc/crypt/arc4random_uniform.c
@@ -2,6 +2,7 @@

/*
* Copyright (c) 2008, Damien Miller <djm@openbsd.org>
+ * Copyright (c) 2022, Alejandro Colomar <alx@kernel.org>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
@@ -55,3 +56,14 @@ arc4random_uniform(uint32_t upper_bound)
return r % upper_bound;
}
DEF_WEAK(arc4random_uniform);
+
+/*
+ * Calculate a uniformly-distributed random number in the range [min, max],
+ * avoiding bias.
+ */
+uint32_t
+arc4random_range(uint32_t min, uint32_t max)
+{
+ return arc4random_uniform(max - min + 1) + min;
+}
+DEF_WEAK(arc4random_range);
diff --git a/sys/dev/rnd.c b/sys/dev/rnd.c
index 5139d4288c9..0ac0c380430 100644
--- a/sys/dev/rnd.c
+++ b/sys/dev/rnd.c
@@ -5,6 +5,7 @@
* Copyright (c) 2008 Damien Miller.
* Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
* Copyright (c) 2013 Markus Friedl.
+ * Copyright (c) 2022 Alejandro Colomar <alx@kernel.org>
* Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
* All rights reserved.
*
@@ -616,6 +617,16 @@ arc4random_uniform(u_int32_t upper_bound)
return r % upper_bound;
}

+/*
+ * Calculate a uniformly distributed random number in the range [min, max],
+ * avoiding bias.
+ */
+u_int32_t
+arc4random_range(u_int32_t min, u_int32_t max)
+{
+ return arc4random_uniform(max - min + 1) + min;
+}
+
/* ARGSUSED */
void
rnd_init(void *null)
diff --git a/sys/sys/systm.h b/sys/sys/systm.h
index 75c99a6dd9b..624b2ced0e8 100644
--- a/sys/sys/systm.h
+++ b/sys/sys/systm.h
@@ -224,6 +224,7 @@ void arc4random_ctx_free(struct arc4random_ctx *);
void arc4random_ctx_buf(struct arc4random_ctx *, void *, size_t);
u_int32_t arc4random(void);
u_int32_t arc4random_uniform(u_int32_t);
+u_int32_t arc4random_range(u_int32_t, u_int32_t);

struct timeval;
struct timespec;
--
2.39.0