linux-kernel - [RFC PATCH v1 04/50] batman-adv: fix batadv_nc_random_weight

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-Id: <202003281707.02SH7EEB025951@sdf.org>
Date:   Sun, 8 Mar 2020 09:44:59 -0400
From:   George Spelvin <lkml@....org>
To:     linux-kernel@...r.kernel.org, lkml@....org
Cc:     Martin Hundeboll <martin@...deboll.net>,
        Marek Lindner <mareklindner@...mailbox.ch>,
        Simon Wunderlich <sw@...onwunderlich.de>,
        Antonio Quartulli <a@...table.cc>,
        Sven Eckelmann <sven@...fation.org>,
        b.a.t.m.a.n@...tynna.open-mesh.org
Subject: [RFC PATCH v1 04/50] batman-adv: fix batadv_nc_random_weight_tq

and change to pseudorandom numbers, as this is a traffic
dithering operation that doesn't need crypto-grade.

The previous code operated in 4 steps:
1) Generate a random byte 0 <= rand_tq <= 255
2) Multiply it by BATADV_TQ_MAX_VALUE - tq
3) Divide by 255 (= BATADV_TQ_MAX_VALUE)
4) Return BATADV_TQ_MAX_VALUE - rand_tq

This would apperar to scale (BATADV_TQ_MAX_VALUE - tq) by a random
value between 0/255 and 255/255.

But!  The intermediate value between steps 3 and 4 is stored in a u8
variable.  So it's truncated, and most of the time, is less than
255, after which the division produces 0.  Specifically, if tq is
odd, the product is always even, and can never be 255.  If tq is
even, there's exactly one random byte value that will produce
a product byte of 255.

Thus, the return value is 255 (511/512 of the time) or 254 (1/512
of the time).

If we assume that the truncation is a bug, and the code is meant to
scale the input, a simpler way of looking at it is that it's
returning a random value between tq and BATADV_TQ_MAX_VALUE,
inclusive.

Well, we have an optimized function for doing just that.

Signed-off-by: George Spelvin <lkml@....org>
Cc: Martin Hundebøll <martin@...deboll.net>
Cc: Marek Lindner <mareklindner@...mailbox.ch>
Cc: Simon Wunderlich <sw@...onwunderlich.de>
Cc: Antonio Quartulli <a@...table.cc>
Cc: Sven Eckelmann <sven@...fation.org>
Cc: b.a.t.m.a.n@...ts.open-mesh.org
---
 net/batman-adv/network-coding.c | 9 +--------
 1 file changed, 1 insertion(+), 8 deletions(-)

diff --git a/net/batman-adv/network-coding.c b/net/batman-adv/network-coding.c
index 580609389f0f7..70e3b161c6635 100644
--- a/net/batman-adv/network-coding.c
+++ b/net/batman-adv/network-coding.c
@@ -1009,15 +1009,8 @@ static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
  */
 static u8 batadv_nc_random_weight_tq(u8 tq)
 {
-	u8 rand_val, rand_tq;
-
-	get_random_bytes(&rand_val, sizeof(rand_val));
-
 	/* randomize the estimated packet loss (max TQ - estimated TQ) */
-	rand_tq = rand_val * (BATADV_TQ_MAX_VALUE - tq);
-
-	/* normalize the randomized packet loss */
-	rand_tq /= BATADV_TQ_MAX_VALUE;
+	u8 rand_tq = prandom_u32_max(BATADV_TQ_MAX_VALUE + 1 - tq);

 	/* convert to (randomized) estimated tq again */
 	return BATADV_TQ_MAX_VALUE - rand_tq;
-- 
2.26.0