[patch] netifrc-net-apipa.sh-fix-broken-implementation.patch

netifrc-net-apipa.sh-fix-broken-implementation.patch (text/plain), 7.34 KB, created by kfm on 2021-01-24 22:16:49 UTC

commit 0bd51ef815c08fe306b69bf7bdd4894aa8b1e713
Author: Kerin Millar <[e-mail]>
Date:   Sun Jan 24 22:10:22 2021 +0000

    net/apipa.sh: fix broken implementation by way of a rewrite
    
    Sadly, the present implementation has never functioned correctly. The
    original author employed incorrect syntax for what was intended to be a
    command substitution. As a result, the _random() function is never called.
    What actually happens is that arping is needlessly executed exactly 64516
    times, with no address ever being considered as a valid candidate.
    
    Furthermore, this module has other bugs and is poorly designed. Here are the
    reasons as to why:-
    
      • the 169.254.0.0/16 block offers 65534 addresses, not 64516
      • the main loop is horrendously slow at enumerating the address block
      • it counts to 64516 but doesn't ensure that each address is unique!
      • it prefers bash for generating entropy (fine, but non-standard)
      • it falls back to a non-standard utility for generating entropy
    
    Therefore, I decided to re-write most of it. The fundamental difference is
    that all 65534 octet pairs are generated up front before being processed by
    the main loop. At most, every possible address will now be tested exactly
    once.
    
    In fact, this approach turns out to be faster by an order of magnitude. The
    following synthetic tests - which calculate the time taken to enumerate the
    entire address space - demonstrate the tremendous difference between the
    existing code and mine. Of course, to ensure that the comparison was
    meaningful, I rectified the command substitution bug in the existing code.
    
      # time bash apipa-old-test.sh
      real    2m34.367s
      user    1m9.959s
      sys     1m37.502s
    
      # time bash apipa-new-test.sh
      real    0m1.119s
      user    0m0.965s
      sys     0m0.182s
    
    Note that the rewrite keeps portability in mind. The comments in the code
    clarify some of the details, but I shall provide an overview here.
    
    A _random_bytes_as_int() function has been defined. This uses the
    /dev/urandom interface as a source of entropy. As noted, it's not a
    POSIX-defined interface but is a de-facto standard and is virtually
    guaranteed to be available on any platform that we ever care about.
    
    A _random_apipa_octets() function has been defined. This is where the 65534
    combinations of octet pairs are generated and emitted in a random order. It
    relies on awk(1) and sort(1) to do the dirty work.
    
    A _mktemp() function has been defined because I rely on the generation of a
    temp file. It uses mktemp(1) if available, otherwise it mimics mktemp(1)
    with the aid of the /dev/urandom interface.
    
    I have isolated and tested these functions on GNU/Linux, macOS, FreeBSD,
    NetBSD, OpenBSD and MirBSD. I have individually tested gawk, mawk, nawk,
    busybox awk and the awk implementations provided by the previously mentioned
    operating systems in the case that they are distinct. The only
    incompatiblity that I was personally able to find was with the awk
    implementation of MirBSD, which affects the final invocation of awk in the
    _random_apipa_octets function.  However, MirBSD was forked from an old
    version of OpenBSD and seems sufficiently obscure so as not to be worth
    worrying about. If someone should try to integrate netifrc into MirBSD one
    day then the matter can be dealt with then.
    
    Finally, I want to thank Steve Arnold for bringing the original bug to my
    attention. Congratulations, Steve. You may be the only known user of
    net/apipa.sh on the planet.
    
    Signed-off-by: Kerin Millar <[e-mail]>
    Reported-by: Steve Arnold <[e-mail]>
    Closes: https://bugs.gentoo.org/766890

diff --git a/net/apipa.sh b/net/apipa.sh
index 849728b..5d48f33 100644
--- a/net/apipa.sh
+++ b/net/apipa.sh
@@ -1,49 +1,102 @@
 # Copyright (c) 2007-2008 Roy Marples <[e-mail]>
 # Released under the 2-clause BSD license.
-# shellcheck shell=sh disable=SC1008
+# shellcheck shell=sh disable=SC2094
 
 apipa_depend()
 {
 	program /sbin/arping /bin/arping
 }
 
-_random()
+_random_bytes_as_int()
 {
-	local r=${RANDOM} # checkbashisms: false positive, we handle it AFTERWARDS
-	if [ -n "${r}" ]; then
-		echo "${r}"
+	local hex num_bytes="$1"
+
+	# While POSIX does not require that /dev/urandom exist, it is a
+	# de-facto standard. Therefore, the following approach should be
+	# highly portable in practice. In the case of Linux, and unlike BSD
+	# this interface does not block in the event that the CSRNG has not
+	# yet been seeded. Still, this is acceptable because we do not
+	# require a guarantee that the entropy be cryptographically secure.
+	# It's also worth noting that Linux >=5.4 is faster at seeding in
+	# the absence of RDRAND/RDSEED than previous versions were.
+	test -e /dev/urandom &&
+	hex=$(
+		LC_ALL=C tr -dc '[:xdigit:]' < /dev/urandom |
+		dd bs="$(( num_bytes * 2 ))" count=1 2>/dev/null) &&
+	test "${#hex}" = "$(( num_bytes * 2 ))" &&
+	printf '%d\n' "0x${hex}"
+}
+
+_random_apipa_octets()
+{
+	local seed
+
+	# Obtain a high-entropy 16-bit seed for use by awk's RNG. In the
+	# unlikely event that the seed ends up being empty, awk will seed
+	# based on the time of day, with a granularity of one second.
+	seed=$(_random_bytes_as_int 2)
+
+	# For APIPA (RFC 3927), the 169.254.0.0/16 address block is
+	# reserved. This provides 65534 addresses, having accounted for the
+	# network and broadcast address. Note that we must count from 1.
+	awk "BEGIN {
+		srand($seed)
+		for (i=1; i<65535; i++) print rand() \" \" i
+	}" |
+	sort -k 1,1 -n |
+	POSIXLY_CORRECT=1 awk '{
+		hex = sprintf("%04x",$2)
+		printf("%d %d\n", "0x" substr(hex,1,2), "0x" substr(hex,3,2))
+	}'
+}
+
+_mktemp() {
+	local tmpfile randchars
+
+	# Try to use the non-standard mktemp(1) utility first.
+	if command -v mktemp >/dev/null; then
+		tmpfile=$(mktemp)
 	else
-		uuidgen | sed -n -e 's/[^[:digit:]]//g' -e 's/\(^.\{1,7\}\).*/\1/p'
-	fi
+		# See the definition of _random_bytes_as_int() for a
+		# justification of this method. It would have been nice to use
+		# the mkstemp function of m4(1) but, despite being defined by
+		# POSIX-1.2008, support is not yet sufficiently widespread.
+		randchars=$(
+			LC_ALL=C tr -dc '[:alnum:]' < /dev/urandom |
+			dd bs=10 count=1 2>/dev/null) &&
+		test "${#randchars}" = 10 &&
+		tmpfile="${TMPDIR:-/tmp}/tmp.${randchars}" &&
+		: >"${tmpfile}"
+	fi &&
+	printf '%s\n' "${tmpfile}"
 }
 
 apipa_start()
 {
-	local iface="$1" i1= i2= addr= i=0
+	local tmpfile i1 i2 addr
 
-	_exists true || return 1
+	_exists &&
+	tmpfile=$(_mktemp) &&
+	_random_apipa_octets > "${tmpfile}" || return
 
 	einfo "Searching for free addresses in 169.254.0.0/16"
 	eindent
 
-	while [ ${i} -lt 64516 ]; do
-		: $(( i1 = (_random % 255) + 1 ))
-		: $(( i2 = (_random % 255) + 1 ))
-
+	while read -r i1 i2; do
 		addr="169.254.${i1}.${i2}"
 		vebegin "${addr}/16"
 		if ! arping_address "${addr}"; then
-			eval config_${config_index}="\"${addr}/16 broadcast 169.254.255.255\""
+			eval "config_${config_index}=\"\${addr}/16 broadcast 169.254.255.255\""
 			: $(( config_index -= 1 ))
 			veend 0
 			eoutdent
+			rm -f -- "${tmpfile}"
 			return 0
 		fi
-
-		: $(( i += 1 ))
-	done
+	done < "${tmpfile}"
 
 	eerror "No free address found!"
 	eoutdent
+	rm -f -- "${tmpfile}"
 	return 1
 }