On Mon, Dec 07, 2015 at 12:49:17AM -0600, Matthew Martin wrote:
>
> Theo's diff inspired me to look for other cases of modulo bias. The
> following diff converts most modulus operations on a random number to
> use arc4random_uniform or & as appropriate. I excluded
>
> lib/libsqlite3/src/resolve.c
> regress/lib/libevent/test-time.c
> usr.sbin/nsd/rrl.c
> usr.sbin/nsd/util.c
> usr.sbin/nsd/xfrd.c
>
> as they seem to have upstreams. The only other case is games/wump/wump.c
> which has
>
> if (arc4random() % 2 == 1)
>
> This is safe and seems obvious enough to me.
>
> - Matthew Martin
Thank you. I was going to do the same :)
I think some of these are ok, but I'm unsure about some of the others.
Here are some of my concerns:
- since arc4random_uniform can potentially loop indefinitely, it
might interfere with predictable timing of some routines. I can't
tell if this is harmless in all cases below. This applies in
particular to the proposed changes in the kernel.
- changing random() to arc4random() in games might have undesired
side-effects like interfering with the reproducibility of tests or
games. I think this might apply to awk for the same reason as in the
shells.
> Index: games/atc/update.c
> ===================================================================
ok
> Index: games/hack/hack.mklev.c
> ===================================================================
> Index: games/hack/rnd.c
> ===================================================================
unsure about these two
> Index: lib/libc/stdlib/rand.c
> ===================================================================
> RCS file: /cvs/src/lib/libc/stdlib/rand.c,v
> retrieving revision 1.15
> diff -u -p -r1.15 rand.c
> --- lib/libc/stdlib/rand.c 13 Sep 2015 08:31:47 -0000 1.15
> +++ lib/libc/stdlib/rand.c 7 Dec 2015 06:42:17 -0000
> @@ -50,7 +50,7 @@ int
> rand(void)
> {
> if (rand_deterministic == 0)
> - return (arc4random() % ((u_int)RAND_MAX + 1));
> + return (arc4random_uniform((u_int)RAND_MAX + 1));
> return (rand_r(&next));
> }
>
this is modulo 2^n, so I think this one is fine as it is.
> Index: sbin/dhclient/dhclient.c
> ===================================================================
I have already done this independently.
> Index: sys/dev/ic/sili.c
> ===================================================================
> Index: sys/netinet6/nd6_rtr.c
> ===================================================================
> Index: sys/ufs/ffs/ffs_alloc.c
> ===================================================================
These must definitely be looked at by somebody else.
> Index: usr.bin/awk/run.c
> ===================================================================
Unsure about this one. I think deterministic sequences might be desired
in some circumstances (this one is deterministic when a seed was given).
> Index: usr.sbin/npppd/common/slist.c
> ===================================================================
> Index: usr.sbin/npppd/l2tp/l2tpd.c
> ===================================================================
> Index: usr.sbin/npppd/pppoe/pppoed.c
> ===================================================================
> Index: usr.sbin/npppd/pptp/pptpd.c
> ===================================================================
These four are ok with me.
