From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id C5CCC1382C5 for ; Wed, 27 Jan 2021 14:06:10 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id CDB0BE0ACD; Wed, 27 Jan 2021 14:06:09 +0000 (UTC) Received: from smtp.gentoo.org (mail.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id A1867E0ACD for ; Wed, 27 Jan 2021 14:06:09 +0000 (UTC) Received: from oystercatcher.gentoo.org (oystercatcher.gentoo.org [148.251.78.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.gentoo.org (Postfix) with ESMTPS id 354B034101F for ; Wed, 27 Jan 2021 14:06:08 +0000 (UTC) Received: from localhost.localdomain (localhost [IPv6:::1]) by oystercatcher.gentoo.org (Postfix) with ESMTP id 6F343476 for ; Wed, 27 Jan 2021 14:06:06 +0000 (UTC) From: "Lars Wendler" To: gentoo-commits@lists.gentoo.org Content-Transfer-Encoding: 8bit Content-type: text/plain; charset=UTF-8 Reply-To: gentoo-dev@lists.gentoo.org, "Lars Wendler" Message-ID: <1611756354.31a05f1b3fb90a3b4e9c0e587bdd5a39e8236f6b.polynomial-c@OpenRC> Subject: [gentoo-commits] proj/netifrc:master commit in: net/ X-VCS-Repository: proj/netifrc X-VCS-Files: net/apipa.sh X-VCS-Directories: net/ X-VCS-Committer: polynomial-c X-VCS-Committer-Name: Lars Wendler X-VCS-Revision: 31a05f1b3fb90a3b4e9c0e587bdd5a39e8236f6b X-VCS-Branch: master Date: Wed, 27 Jan 2021 14:06:06 +0000 (UTC) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-commits@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply X-Archives-Salt: cf0306b3-83d3-46c5-8663-3f29c05741e6 X-Archives-Hash: 294805d6add974a5a98892ce128d8f1d commit: 31a05f1b3fb90a3b4e9c0e587bdd5a39e8236f6b Author: Kerin Millar plushkava net> AuthorDate: Mon Jan 25 02:40:29 2021 +0000 Commit: Lars Wendler gentoo org> CommitDate: Wed Jan 27 14:05:54 2021 +0000 URL: https://gitweb.gentoo.org/proj/netifrc.git/commit/?id=31a05f1b 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 new _random_apipa_octets() function is responsible for generating all 65534 combinations of octet pairs in a random order. It mainly relies on awk(1) and sort(1). Where possible, a seed is obtained from /dev/urandom for the benefit of awk's RNG, but this is not required. I have isolated and tested the new 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 plushkava.net> Reported-by: Steve Arnold gentoo.org> Closes: https://bugs.gentoo.org/766890 Signed-off-by: Lars Wendler gentoo.org> net/apipa.sh | 94 +++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 67 insertions(+), 27 deletions(-) diff --git a/net/apipa.sh b/net/apipa.sh index 849728b..f3ec534 100644 --- a/net/apipa.sh +++ b/net/apipa.sh @@ -1,49 +1,89 @@ # Copyright (c) 2007-2008 Roy Marples # Released under the 2-clause BSD license. -# shellcheck shell=sh disable=SC1008 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}" - else - uuidgen | sed -n -e 's/[^[:digit:]]//g' -e 's/\(^.\{1,7\}\).*/\1/p' - fi + 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 highly random 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)) + }' } apipa_start() { - local iface="$1" i1= i2= addr= i=0 + local addr rc - _exists true || return 1 + _exists || 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 )) - - addr="169.254.${i1}.${i2}" - vebegin "${addr}/16" - if ! arping_address "${addr}"; then - eval config_${config_index}="\"${addr}/16 broadcast 169.254.255.255\"" - : $(( config_index -= 1 )) - veend 0 - eoutdent - return 0 - fi + exec 3>&1 + addr=$( + _random_apipa_octets | + { + while read -r i1 i2; do + addr="169.254.${i1}.${i2}" + vebegin "${addr}/16" >&3 + if ! arping_address "${addr}" >&3; then + printf '%s\n' "${addr}" + exit 0 + fi + done + exit 1 + } + ) + rc=$? + exec 3>&- - : $(( i += 1 )) - done + if [ "$rc" = 0 ]; then + eval "config_${config_index}=\"\${addr}/16 broadcast 169.254.255.255\"" + : $(( config_index -= 1 )) + veend 0 + else + eerror "No free address found!" + fi - eerror "No free address found!" eoutdent - return 1 + return "$rc" }