Mercurial > hg > dhcpcd

changeset 2494:9ee5781a9a80 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Should use arc4random_uniform when wanting a randon number between 1 and N. Improve the compat arc4random function a little and re-stir on fork.
author Roy Marples <roy@marples.name>
date Sat, 24 May 2014 19:58:50 +0000
parents ec2af7c0334d
children 8a285cbcdd74
files arp.c compat/arc4random.c compat/arc4random.h dhcp.c dhcp.h dhcp6.c ipv4ll.c ipv6nd.c
diffstat 8 files changed, 83 insertions(+), 62 deletions(-) [+]
line wrap: on
line diff
--- a/arp.c	Sat May 24 13:08:29 2014 +0000
+++ b/arp.c	Sat May 24 19:58:50 2014 +0000
@@ -280,7 +280,8 @@
 		state->probes = 0;
 		state->claims = 0;
 		tv.tv_sec = state->interval - DHCP_RAND_MIN;
-		tv.tv_usec = arc4random() % (DHCP_RAND_MAX_U - DHCP_RAND_MIN_U);
+		tv.tv_usec = (suseconds_t)arc4random_uniform(
+		    (DHCP_RAND_MAX - DHCP_RAND_MIN) * 1000000);
 		timernorm(&tv);
 		eloop_timeout_add_tv(ifp->ctx->eloop, &tv, dhcp_discover, ifp);
 	} else {
@@ -330,7 +331,8 @@
 	}
 	if (++state->probes < PROBE_NUM) {
 		tv.tv_sec = PROBE_MIN;
-		tv.tv_usec = arc4random() % (PROBE_MAX_U - PROBE_MIN_U);
+		tv.tv_usec = (suseconds_t)arc4random_uniform(
+		    (PROBE_MAX - PROBE_MIN) * 1000000);
 		timernorm(&tv);
 		eloop_timeout_add_tv(ifp->ctx->eloop, &tv, arp_probe, ifp);
 	} else {
--- a/compat/arc4random.c	Sat May 24 13:08:29 2014 +0000
+++ b/compat/arc4random.c	Sat May 24 19:58:50 2014 +0000
@@ -35,24 +35,26 @@
 	uint8_t i;
 	uint8_t j;
 	uint8_t s[256];
+	size_t count;
+	pid_t stir_pid;
 };
 
-static int rs_initialized;
-static struct arc4_stream rs;
-static int arc4_count;
+#define S(n) (n)
+#define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3)
+#define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12)
+#define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48)
+#define S256 S64(0), S64(64), S64(128), S64(192)
 
-static void
-arc4_init(struct arc4_stream *as)
-{
-	int n;
+static struct arc4_stream rs = { .i = 0xff, .j = 0, .s = { S256 },
+                    .count = 0, .stir_pid = 0 };
 
-	for (n = 0; n < 256; n++)
-		as->s[n] = n;
-	as->i = 0;
-	as->j = 0;
-}
+#undef S
+#undef S4
+#undef S16
+#undef S64
+#undef S256
 
-static void
+static inline void
 arc4_addrandom(struct arc4_stream *as, unsigned char *dat, int datlen)
 {
 	int n;
@@ -69,7 +71,7 @@
 	as->j = as->i;
 }
 
-static uint8_t
+static inline uint8_t
 arc4_getbyte(struct arc4_stream *as)
 {
 	uint8_t si, sj;
@@ -83,7 +85,7 @@
 	return (as->s[(si + sj) & 0xff]);
 }
 
-static uint32_t
+static inline uint32_t
 arc4_getword(struct arc4_stream *as)
 {
 	uint32_t val;
@@ -104,7 +106,7 @@
 		unsigned int rnd[(128 - sizeof(struct timeval)) /
 			sizeof(unsigned int)];
 	}       rdat;
-	int n;
+	size_t n;
 
 	gettimeofday(&rdat.tv, NULL);
 	fd = open("/dev/urandom", O_RDONLY);
@@ -122,37 +124,63 @@
 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 	 * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
 	 */
-	for (n = 0; n < 256 * 4; n++)
+	for (n = 0; n < 256 * sizeof(uint32_t); n++)
 		arc4_getbyte(as);
-	arc4_count = 1600000;
+	as->count = 1600000;
 }
 
-void
-arc4random_stir()
+static inline void
+arc4_stir_if_needed(struct arc4_stream *as)
 {
+	pid_t pid;
 
-	if (!rs_initialized) {
-		arc4_init(&rs);
-		rs_initialized = 1;
-	}
-	arc4_stir(&rs);
-}
-
-void
-arc4random_addrandom(unsigned char *dat, int datlen)
-{
-
-	if (!rs_initialized)
-		arc4random_stir();
-	arc4_addrandom(&rs, dat, datlen);
+	pid = getpid();
+	if (as->count <= sizeof(uint32_t) || !as->stir_pid != pid) {
+		as->stir_pid = pid;
+		arc4_stir(as);
+	} else
+		as->count -= sizeof(uint32_t);
 }
 
 uint32_t
 arc4random()
 {
 
-	arc4_count -= 4;
-	if (!rs_initialized || arc4_count <= 0)
-		arc4random_stir();
+	arc4_stir_if_needed(&rs);
 	return arc4_getword(&rs);
 }
+
+/*
+ * 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;
+
+	/*
+	 * 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.
+	 */
+	do
+		r = arc4random();
+	while (r < min);
+
+	return r % upper_bound;
+}
+
--- a/compat/arc4random.h	Sat May 24 13:08:29 2014 +0000
+++ b/compat/arc4random.h	Sat May 24 19:58:50 2014 +0000
@@ -1,6 +1,6 @@
 /*
  * dhcpcd - DHCP client daemon
- * Copyright (c) 2006-2010 Roy Marples <roy@marples.name>
+ * Copyright (c) 2006-2014 Roy Marples <roy@marples.name>
  * All rights reserved
 
  * Redistribution and use in source and binary forms, with or without
@@ -30,7 +30,6 @@
 
 #include <stdint.h>
 
-void arc4random_stir(void);
-void arc4random_addrandom(unsigned char *, int);
 uint32_t arc4random(void);
+uint32_t arc4random_uniform(uint32_t);
 #endif
--- a/dhcp.c	Sat May 24 13:08:29 2014 +0000
+++ b/dhcp.c	Sat May 24 19:58:50 2014 +0000
@@ -1519,7 +1519,7 @@
 
 	ip->ip_v = IPVERSION;
 	ip->ip_hl = sizeof(*ip) >> 2;
-	ip->ip_id = arc4random() & UINT16_MAX;
+	ip->ip_id = (uint16_t)arc4random_uniform(UINT16_MAX);
 	ip->ip_ttl = IPDEFTTL;
 	ip->ip_len = htons(sizeof(*ip) + sizeof(*udp) + length);
 	ip->ip_sum = checksum(ip, sizeof(*ip));
@@ -1554,7 +1554,8 @@
 				state->interval = 64;
 		}
 		tv.tv_sec = state->interval + DHCP_RAND_MIN;
-		tv.tv_usec = arc4random() % (DHCP_RAND_MAX_U - DHCP_RAND_MIN_U);
+		tv.tv_usec = (suseconds_t)arc4random_uniform(
+		    (DHCP_RAND_MAX - DHCP_RAND_MIN) * 1000000);
 		timernorm(&tv);
 		syslog(LOG_DEBUG,
 		    "%s: sending %s (xid 0x%x), next in %0.1f seconds",
@@ -3015,8 +3016,8 @@
 		return;
 
 	tv.tv_sec = DHCP_MIN_DELAY;
-	tv.tv_usec = (suseconds_t)(arc4random() %
-	    ((DHCP_MAX_DELAY - DHCP_MIN_DELAY) * 1000000));
+	tv.tv_usec = (suseconds_t)arc4random_uniform(
+	    (DHCP_MAX_DELAY - DHCP_MIN_DELAY) * 1000000);
 	timernorm(&tv);
 	syslog(LOG_DEBUG,
 	    "%s: delaying DHCP for %0.1f seconds",
--- a/dhcp.h	Sat May 24 13:08:29 2014 +0000
+++ b/dhcp.h	Sat May 24 19:58:50 2014 +0000
@@ -68,15 +68,6 @@
 #define DHCP_RAND_MAX		1
 #define DHCP_ARP_FAIL		2
 
-/* number of usecs in a second. */
-#define USECS_SECOND		1000000
-/* As we use timevals, we should use the usec part for
- * greater randomisation. */
-#define DHCP_RAND_MIN_U		DHCP_RAND_MIN * USECS_SECOND
-#define DHCP_RAND_MAX_U		DHCP_RAND_MAX * USECS_SECOND
-#define PROBE_MIN_U		PROBE_MIN * USECS_SECOND
-#define PROBE_MAX_U		PROBE_MAX * USECS_SECOND
-
 #ifdef RFC2131_STRICT
 /* Be strictly conformant for section 4.1.1 */
 #  define DHCP_MIN_DELAY	1
--- a/dhcp6.c	Sat May 24 13:08:29 2014 +0000
+++ b/dhcp6.c	Sat May 24 19:58:50 2014 +0000
@@ -762,8 +762,8 @@
 				state->RT.tv_sec = 1;
 			else
 				state->RT.tv_sec = 0;
-			state->RT.tv_usec = (suseconds_t)(arc4random() %
-			    (state->IMD * 1000000));
+			state->RT.tv_usec = (suseconds_t)arc4random_uniform(
+			    state->IMD * 1000000);
 			timernorm(&state->RT);
 			broad_uni = "delaying";
 			goto logsend;
@@ -779,7 +779,8 @@
 		}
 
 		rnd = DHCP6_RAND_MIN;
-		rnd += arc4random() % (DHCP6_RAND_MAX - DHCP6_RAND_MIN);
+		rnd += (suseconds_t)arc4random_uniform(
+		    DHCP6_RAND_MAX - DHCP6_RAND_MIN);
 		rnd /= 1000;
 		neg = (rnd < 0.0);
 		if (neg)
--- a/ipv4ll.c	Sat May 24 13:08:29 2014 +0000
+++ b/ipv4ll.c	Sat May 24 19:58:50 2014 +0000
@@ -76,8 +76,7 @@
 
 	for (;;) {
 		addr = htonl(LINKLOCAL_ADDR |
-		    (((uint32_t)abs((int)arc4random())
-			% 0xFD00) + 0x0100));
+		    (uint32_t)abs((int)arc4random_uniform(0xFD00)) + 0x0100);
 		if (addr != old_addr &&
 		    IN_LINKLOCAL(ntohl(addr)))
 			break;
--- a/ipv6nd.c	Sat May 24 13:08:29 2014 +0000
+++ b/ipv6nd.c	Sat May 24 19:58:50 2014 +0000
@@ -1486,8 +1486,8 @@
 
 	eloop_timeout_delete(ifp->ctx->eloop, NULL, ifp);
 	tv.tv_sec = 0;
-	tv.tv_usec = (suseconds_t)(arc4random() %
-	    (MAX_RTR_SOLICITATION_DELAY * 1000000));
+	tv.tv_usec = (suseconds_t)arc4random_uniform(
+	    MAX_RTR_SOLICITATION_DELAY * 1000000);
 	timernorm(&tv);
 	syslog(LOG_DEBUG,
 	    "%s: delaying IPv6 router solictation for %0.1f seconds",