Re: Flaw in "random32: update the net random state on interrupt and activity"

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

[-- Attachment #1: letter --]
[-- Type: text/plain, Size: 9210 bytes --]

I'm quite annoyed at the way that this discussion has drifted away from
the main problem, which is that f227e3ec3b5c is broken and needs reverted.

The original bug report is accurate, and it's a critical issue.
My proposed fix is described (patch imminent) below.


THE PROBLEM:

The reseeding design in add_interrupt_randomness is fatally flawed.
Quite simply, drip-feeding entropy into a PRNG is pissing the entropy
straight down the drain.  It's a complete waste of time *and* it fatally
damages /dev/random.

This is an information-theoretic flaw which cannot be patched
by any amount of clever crypto.

People don't seem to be grasping this fundamental concept.  Ted,
I'm particularly disappointed in you; you *know* better.

First, why reseed at all?  We do it to reduce an attacker's ability
to predict the PRNG output, which in practice means to reduce their
knowledge of the PRNG's internal state.

So any discussion of reseeding begins by *assuming* an attacker has
captured the PRNG state.  If we weren't worried about this possibility,
we wouldn't need to reseed in the first place!

[Footnote: most crypto PRNGs also want rekeying before their cycle
length limit is reached, but these limits are more than 2^64 bits
nowadays and thus infinite in practice.]

If we add k bits of seed entropy to the (attacker-known!) state and let an
attacker see >= k bits of output, there is a trivial brute-force attack
on *any* deterministic PRNG algorithm: try all 2^k possible inputs and
choose the one that matches the observed output.

[Footnote: in real life, you don't have 2^k equally likely possibilities,
so you end up trying possibilities in decreasing order of likelihood,
giving the same average time to solve, but with a longer tail.
The implementation details are messier, but well known; RTFM of any
password-guessing software for details.]

If k is small, this is trivially easy.  Reseeding many times (large n)
doesn't help if you allow an attacker to observe PRNG output after each
small reseeding; the effort is n * 2^k.

The way to prevent this from becoming a problem is well-known: ensure
that k is large.  Save up the n seeds and reseed once, making the
brute-force effort 2^(n*k).  This is called "catastrophic reseeding"
and is described in more detail at e.g.
https://www.schneier.com/academic/paperfiles/paper-prngs.pdf

But the amount of entropy is any one interrupt timing sample is small.
/dev/random assumes it lies somewhere between 1/64 and 2 bits.  If
our attacker is less skilled, they may have more subjective uncertainty,
but guessing a TSC delta to within 20 bits (0.26 ms at 4 GHz) doesn't
seem at all difficult.  Testing 2^20 possibilities is trivial.

*This* is why Willy's patch is useless.  No amount of deckchair
rearrangement or bikeshed painting will fix this core structural flaw.
It *must* be redesigned to do catastrophic reseeding.


Additionally, the entropy revealed by this attack is *also* the primary
source for /dev/random, destroying its security guarantee.  This elevates
the problem from "useless" to "disastrous".  This patch *must* be reverted
for 5.8.1.


In response to various messages saying "this is all theoretical; I won't
believe you until I see a PoC", all I can say is "I feel that you should
be aware that some asshole is signing your name to stupid letters."

Just like a buffer overflow, a working attack is plausible using a
combination of well-understood techniques.  It's ridiculous to go to
the effort of developing a full exploit when it's less work to fix the
problem in the first place.

I also notice a lot of amateurish handwaving about the security of
various primitives.  This is particularly frustrating, but I will refrain
from giving vent/rant to my feelings, instead referring people to the
various references linked from

https://security.stackexchange.com/questions/18197/why-shouldnt-we-roll-our-own


A SOLUTION:

Now, how to fix it?

First, what is the problem?  "Non-cryptographic PRNGs are predictable"
fits in the cateogry of Not A Bug.  There are may applications for
a non-cryptographic PRNG in the kernel.  Self-tests, spreading wear
across flash memory, randomized backoff among cooperating processes,
and assigning IDs in protocols which aren't designed for DoS resistance
in the first place.

But apparently the network code is (ab)using lib/random32.c for choosing
TCP/UDP port numbers and someone has found a (not publicly disclosed)
attack which exploits the predictability to commit some mischief.

And apparently switching to the fastest secure PRNG currently
in the kernel (get_random_u32() using ChaCha + per-CPU buffers)
would cause too much performance penalty.

So the request is for a less predictable PRNG which is still extremely
fast.  It's specifically okay if the crypto is half-assed; this is
apparently some kind of nuisance (DoS?) attack rather than something
really valuable.

Gee, I seem to recall solving a very similar problem with the
dache hash function.  I think I can do this.

An important design constraint is that we want low-latency random number
generation, not just high bandwidth.  Amortizing over bulk operations
is *not* okay.


Well, the best crypto primitive I know of for such an application is
SipHash.  Its 4x 64-bit words of state is only twice the size of the
current struct rnd_state.  Converting it from a a pseudo-random function
to a CRNG is some half-assed amateur cryptography, but at least it's a
robust and well-studied primitive.

So here's my proposal, for comment:  (I'll post an RFC patch shortly.)
- Replace the prandom_u32() generator with something that does
  2 rounds of SipHash.  (Could drop to 1 round if we get complaints.)
- Keep the per-CPU structure, to minimize cacheline bouncing.
- On 32-bit processors, use HSipHash to keep performance up.  In the
  spirit of half-assedness, this is weaker, but hopefully good enough,
  and while there are lots of such processors in routers and IoT devices,
  they aren't handling thousands of connections per second and so expose
  much less PRNG output.
- Using random_ready_callback and periodically thereafter, do a full
  catastrophic reseed from the ChaCha generator.  There's no need for
  locking; tearing on updates doesn't do any harm.

Current plans I'm open to discussion about:
- Replace the current prandom_u32(), rather than adding yet another
  PRNG.  This keeps the patch smaller.
- Leave the 60-second reseed interval alone.  If someone can suggest a
  way to suppress reseeding when not needed, we could drop the interval
  without penalizing mobile devices.
- Leave the prandom_u32_state() code paths alone.  Those functions are
  used in self-test code and it's probably worth not changing the output.
  (The downside is misleading function names.)
- For robustness, seed each CPU's PRNG state independently.  We could
  use a global key and use SipHash itself to hash in the CPU number which
  would be faster than ChaCha, but let's KISS.


INDIVIDUAL REPLIES:

Jason A. Donenfeld: You're quite right about the accretion of
	superstitious incantations in random.c, but I do think it's a
	fundamentally sound design, just with an inelegant implementation.
	A comparison to SHACAL1 is not appropriate.  SHACAL is invertible
	because it leaves off the final Davies-Meyer add-back,	random.c
	uses SHA1 *with* the add-back, so the compression function
	is not invertible.  The most maliciously backdoored rdrand
	implementation imaginable can't analyze the entropy pool and
	choose its output so as to leak data to the Bavarian Illuminati.
	That's laughably impractical.

Willy Tarreau: Middle square + Weil sequence isn't even *close* to
	crypto-quality.  And you're badly misunderstanding what the
	fast_pool is doing.  Please stop trying to invent your own crypto
	primitives; see
	https://www.schneier.com/crypto-gram/archives/1998/1015.html#cipherdesign

Ted Ts'o: Actually, I'm (slowly) working through a complete audit of all
	RNG users in the kernel.  Current code offers four basic
	levels of security:
	- Trivial LCG (next_pseudo_random32, preserved for compatibility)
	- Trivially predictable (but statistically good) LFSR
	- Cryptographically strong ChaCha, batched
	- Cryptographically strong ChaCha, with anti-backtracking.
	(Because I'm working strong-to-weak, I've mostly downgraded
	call sites so far.  There's also the earlyrandom stuff, which
	is its own mess.)

	Do we want an additional "hopefully strong" level in the middle
	for TCP ports and other visible IDs only, or should we replace
	the LFSR and not have a conventional PRNG at all?

Andy Lutomirski: I also have some code for combining the 32- and 64-bit
	entropy batches, and I've generalized it to return bytes as well,
	because *most* users of get_random_bytes() in the kernel don't
	need anti-backtracking, but my understanding from Linus is that
	for this application, amortized time is *not* okay; we want a
	fast 99th percentile.


PERSONAL NOTE:

Events this year have left me without the bandwidth to keep up with kernel
development and so I've been AFK for some months.  My problems haven't
gone away, but this issue is important enough that I'll be making time
to see it through to resolution.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Andy Lutomirski]

> On Aug 8, 2020, at 8:29 AM, George Spelvin <lkml@sdf.org> wrote:
> 

> And apparently switching to the fastest secure PRNG currently
> in the kernel (get_random_u32() using ChaCha + per-CPU buffers)
> would cause too much performance penalty.

Can someone explain *why* the slow path latency is particularly relevant here?  What workload has the net code generating random numbers in a place where even a whole microsecond is a problem as long as the amortized cost is low?  (I’m not saying I won’t believe this matters, but it’s not obvious to me that it matters.)

>    - Cryptographically strong ChaCha, batched
>    - Cryptographically strong ChaCha, with anti-backtracking.

I think we should just anti-backtrack everything.  With the “fast key erasure” construction, already implemented in my patchset for the buffered bytes, this is extremely fast.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Willy Tarreau]

On Sat, Aug 08, 2020 at 03:26:28PM +0000, George Spelvin wrote:
> So any discussion of reseeding begins by *assuming* an attacker has
> captured the PRNG state.  If we weren't worried about this possibility,
> we wouldn't need to reseed in the first place!

Sure, but what matters is the time it takes to capture the state.
In the previous case it used to take Amit a few packets only. If it
takes longer than the reseeding period, then it's not captured anymore.
That was exactly the point there: break the certainty of the observations
so that the state cannot be reliably guessed anymore, hence cancelling
the concerns about the input bits being guessed. For sure if it is
assumed that the state is guessed nevertheless, this doesn't work
anymore, but that wasn't the assumption.

> Just like a buffer overflow, a working attack is plausible using a
> combination of well-understood techniques.  It's ridiculous to go to
> the effort of developing a full exploit when it's less work to fix the
> problem in the first place.

I totally agree with this principle. However, systematically starting
with assumptions like "the PRNG's state is known to the attacker" while
it's the purpose of the attack doesn't exactly match something which
does not warrant a bit more explanation. Otherwise I could as well say
in other contexts "let's assume I know the private key of this site's
certificate, after all it's only 2048 bits". And the reason why we're
looping here is that all explanations about the risk of losing entropy
are based on the assumption that the attacker has already won. The patch
was made to keep that assumption sufficiently away, otherwise it's
useless.

> A SOLUTION:
> 
> Now, how to fix it?
> 
> First, what is the problem?  "Non-cryptographic PRNGs are predictable"
> fits in the cateogry of Not A Bug.  There are may applications for
> a non-cryptographic PRNG in the kernel.  Self-tests, spreading wear
> across flash memory, randomized backoff among cooperating processes,
> and assigning IDs in protocols which aren't designed for DoS resistance
> in the first place.
> 
> But apparently the network code is (ab)using lib/random32.c for choosing
> TCP/UDP port numbers and someone has found a (not publicly disclosed)
> attack which exploits the predictability to commit some mischief.

Note, it's beyond predictability, it's reversibility at this point.

> And apparently switching to the fastest secure PRNG currently
> in the kernel (get_random_u32() using ChaCha + per-CPU buffers)
> would cause too much performance penalty.

Based on some quick userland tests, apparently yes.

> So the request is for a less predictable PRNG which is still extremely
> fast.

That was the goal around the MSWS PRNG, as it didn't leak its bits
and would require a certain amount of brute force.

> Well, the best crypto primitive I know of for such an application is
> SipHash.  Its 4x 64-bit words of state is only twice the size of the
> current struct rnd_state.  Converting it from a a pseudo-random function
> to a CRNG is some half-assed amateur cryptography, but at least it's a
> robust and well-studied primitive.

If it's considered as cryptographically secure, it's OK to feed it with
just a counter starting from a random value, since the only way to guess
the current counter state is to brute-force it, right ? I've done this in
the appended patch. Note that for now I've commented out all the reseeding
code because I just wanted to test the impact. 

In my perf measurements I've had some erratic behaviors, one test showing
almost no loss, and another one showing a lot, which didn't make sense, so
I'll need to measure again under better condition (i.e. not my laptop with
a variable frequency CPU).

> Willy Tarreau: Middle square + Weil sequence isn't even *close* to
> 	crypto-quality.

Absolutely, I've even said this myself.

>  And you're badly misunderstanding what the
> 	fast_pool is doing.  Please stop trying to invent your own crypto
> 	primitives; see
> 	https://www.schneier.com/crypto-gram/archives/1998/1015.html#cipherdesign

I know this pretty well and am NOT trying to invent crypto and am not
qualified for this. I'm not even trying to invent a PRNG myself because
there are some aspects I can't judge (such as measuring the sequence).
This is why I proposed to reuse some published work.

There seems to be some general thinking among many crypto-savvy people
that everything in the world needs strong crypto, including PRNGs, and
that doesn't always help. As you mentioned above, there are plenty of
valid use cases for weaker PRNGs, and my opinion (which may or may not
be shared) is that if guessing an internal state is expensive enough
for an attacker, either in terms of number of probes, or in brute-force
time, it may be sufficient for certain use cases. The main problem is
that every time someone says "oh it seems easy to guess a 16-bit port",
it's almost impossible not to receive proposals to implement expensive
super-strong crypto that will be suitable for everything. It would help
if security people would actually more often try to adapt to the context,
or explain why it still matters in a certain case. Actually that's what
Jason tried but as he already said, the covid outbreak arrived in the
middle of the work on this issue and stalled a lot of things.  

Regards,
Willy


commit dec36680a3f4888a7c026f8d40f978eec31ce1a1
Author: Willy Tarreau <w@1wt.eu>
Date:   Sun Apr 19 17:31:46 2020 +0200

    WIP: random32: use siphash with a counter for prandom_u32

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d20ba1b104ca..2a41b21623ae 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1277,7 +1277,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
 
 	fast_mix(fast_pool);
 	add_interrupt_bench(cycles);
-	this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
 
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
diff --git a/include/linux/random.h b/include/linux/random.h
index 9ab7443bd91b..9e22973b207c 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -12,6 +12,7 @@
 #include <linux/list.h>
 #include <linux/once.h>
 #include <asm/percpu.h>
+#include <linux/siphash.h>
 
 #include <uapi/linux/random.h>
 
@@ -117,7 +118,8 @@ void prandom_seed(u32 seed);
 void prandom_reseed_late(void);
 
 struct rnd_state {
-	__u32 s1, s2, s3, s4;
+	siphash_key_t key;
+	uint64_t counter;
 };
 
 DECLARE_PER_CPU(struct rnd_state, net_rand_state);
@@ -161,12 +163,14 @@ static inline u32 __seed(u32 x, u32 m)
  */
 static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
 {
+#if 0
 	u32 i = (seed >> 32) ^ (seed << 10) ^ seed;
 
 	state->s1 = __seed(i,   2U);
 	state->s2 = __seed(i,   8U);
 	state->s3 = __seed(i,  16U);
 	state->s4 = __seed(i, 128U);
+#endif
 }
 
 #ifdef CONFIG_ARCH_RANDOM
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 026ac01af9da..c9d839c2b179 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1743,13 +1743,6 @@ void update_process_times(int user_tick)
 	scheduler_tick();
 	if (IS_ENABLED(CONFIG_POSIX_TIMERS))
 		run_posix_cpu_timers();
-
-	/* The current CPU might make use of net randoms without receiving IRQs
-	 * to renew them often enough. Let's update the net_rand_state from a
-	 * non-constant value that's not affine to the number of calls to make
-	 * sure it's updated when there's some activity (we don't care in idle).
-	 */
-	this_cpu_add(net_rand_state.s1, rol32(jiffies, 24) + user_tick);
 }
 
 /**
diff --git a/lib/random32.c b/lib/random32.c
index 3d749abb9e80..aa83cade911a 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -59,13 +59,8 @@ DEFINE_PER_CPU(struct rnd_state, net_rand_state);
  */
 u32 prandom_u32_state(struct rnd_state *state)
 {
-#define TAUSWORTHE(s, a, b, c, d) ((s & c) << d) ^ (((s << a) ^ s) >> b)
-	state->s1 = TAUSWORTHE(state->s1,  6U, 13U, 4294967294U, 18U);
-	state->s2 = TAUSWORTHE(state->s2,  2U, 27U, 4294967288U,  2U);
-	state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U,  7U);
-	state->s4 = TAUSWORTHE(state->s4,  3U, 12U, 4294967168U, 13U);
-
-	return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4);
+	state->counter++;
+	return siphash(&state->counter, sizeof(state->counter), &state->key);
 }
 EXPORT_SYMBOL(prandom_u32_state);
 
@@ -161,12 +156,14 @@ static u32 __extract_hwseed(void)
 static void prandom_seed_early(struct rnd_state *state, u32 seed,
 			       bool mix_with_hwseed)
 {
+#if 0
 #define LCG(x)	 ((x) * 69069U)	/* super-duper LCG */
 #define HWSEED() (mix_with_hwseed ? __extract_hwseed() : 0)
 	state->s1 = __seed(HWSEED() ^ LCG(seed),        2U);
 	state->s2 = __seed(HWSEED() ^ LCG(state->s1),   8U);
 	state->s3 = __seed(HWSEED() ^ LCG(state->s2),  16U);
 	state->s4 = __seed(HWSEED() ^ LCG(state->s3), 128U);
+#endif
 }
 
 /**
@@ -184,8 +181,6 @@ void prandom_seed(u32 entropy)
 	 */
 	for_each_possible_cpu(i) {
 		struct rnd_state *state = &per_cpu(net_rand_state, i);
-
-		state->s1 = __seed(state->s1 ^ entropy, 2U);
 		prandom_warmup(state);
 	}
 }
@@ -244,14 +239,8 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
 
 	for_each_possible_cpu(i) {
 		struct rnd_state *state = per_cpu_ptr(pcpu_state, i);
-		u32 seeds[4];
-
-		get_random_bytes(&seeds, sizeof(seeds));
-		state->s1 = __seed(seeds[0],   2U);
-		state->s2 = __seed(seeds[1],   8U);
-		state->s3 = __seed(seeds[2],  16U);
-		state->s4 = __seed(seeds[3], 128U);
 
+		get_random_bytes(state, sizeof(*state));
 		prandom_warmup(state);
 	}
 }

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Willy Tarreau]

On Sat, Aug 08, 2020 at 10:07:51AM -0700, Andy Lutomirski wrote:
> 
> > On Aug 8, 2020, at 8:29 AM, George Spelvin <lkml@sdf.org> wrote:
> > 
> 
> > And apparently switching to the fastest secure PRNG currently
> > in the kernel (get_random_u32() using ChaCha + per-CPU buffers)
> > would cause too much performance penalty.
> 
> Can someone explain *why* the slow path latency is particularly relevant
> here?  What workload has the net code generating random numbers in a place
> where even a whole microsecond is a problem as long as the amortized cost is
> low?  (I'm not saying I won't believe this matters, but it's not obvious to
> me that it matters.)

It really depends on what is being done and how we want that code to
continue to be used. Often it will be a matter of queue sizes or
concurrency in certain contexts under a lock. For illustration let's
say you want to use randoms to choose a sequence number for a SYN
cookie (it's not what is done today), a 40G NIC can deliver 60Mpps
or one packet every 16 ns. If you periodically add 1us you end up
queuing 60 extra packets in a queue when this happens. This might
or might not be acceptable. Regarding concurrency, you could imagine
some code picking a random in a small function running under a
spinlock. Frequently adding 1us there can be expensive.

To be clear, I'm not *that* much worried about *some* extra latency,
however I'm extremely worried about the risks of increase once
some security researcher considers the PRNG not secure enough again
(especially once it starts to be used for security purposes after
having being claimed secure) and we replace it with another one
showing a higher cost and longer tail to amortize the cost. And given
that we're speaking about replacing a non-secure PRNG with *something*,
it doesn't seem really wise to start to introduce new constraints on
the data path when there are probably a large enough number of
possibilities which do not require these constraints.

Last point, we must not rule out the possibility than some clever
researcher will later come up with new time-based attacks consisting
in observing latencies of packet processing, explaining how they can
count the number of connections reaching a given host and reveal
certain useful information, and that we're then forced to slow down
all of them to proceed in constant time.

Just my two cents,
Willy

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Linus Torvalds]

On Sat, Aug 8, 2020 at 10:07 AM Andy Lutomirski <luto@amacapital.net> wrote:
>
>
> > On Aug 8, 2020, at 8:29 AM, George Spelvin <lkml@sdf.org> wrote:
> >
>
> > And apparently switching to the fastest secure PRNG currently
> > in the kernel (get_random_u32() using ChaCha + per-CPU buffers)
> > would cause too much performance penalty.
>
> Can someone explain *why* the slow path latency is particularly relevant here?

You guys know what's relevant?  Reality.

The thing is, I see Spelvin's rant, and I've generally enjoyed our
encounters in the past, but I look back at the kinds of security
problems we've had, and they are the exact _reverse_ of what
cryptographers and Spelvin is worried about.

The fact is, nobody ever EVER had any practical issues with our
"secure hash function" even back when it was MD5, which is today
considered trivially breakable.

Thinking back on it, I don't think it was even md5. I think it was
half-md5, wasn't it?

So what have people have had _real_ security problems with in our
random generators - pseudo or not?

EVERY SINGLE problem I can remember was because some theoretical
crypto person said "I can't guarantee that" and removed real security
- or kept it from being merged.

Seriously.

We've had absolutely horrendous performance issues due to the
so-called "secure" random number thing blocking. End result: people
didn't use it.

We've had absolutely garbage fast random numbers because the crypto
people don't think performance matters, so the people who _do_ think
it matters just roill their own.

We've had "random" numbers that weren't, because random.c wanted to
use only use inputs it can analyze and as a result didn't use any
input at all, and every single embedded device ended up having the
exact same state (this ends up being intertwined with the latency
thing).

We've had years of the drivers/char/random.c not getting fixed because
Ted listens too much to the "serious crypto" guys, with the end result
that I then have to step in and say "f*ck that, we're doing this
RIGHT".

And RIGHT means caring about reality, not theory.

So instead of asking "why is the slow path relevant", the question
should be "why is some theoretical BS relevant", when history says it
has never ever mattered.

Our random number generation needs to be _practical_.

When Spelvin and Marc complain about us now taking the fastpool data
and adding it to the prandom pool and "exposing" it, they are full of
shit. That fastpool data gets whitened so much by two layers of
further mixing, that there is no way you'll ever see any sign of us
taking one word of it for other things.

I want to hear _practical_ attacks against this whole "let's mix in
the instruction pointer and the cycle counter into both the 'serious'
random number generator and the prandom one".

Because I don't think they exist. And I think it's actively dangerous
to continue on the path of thinking that stable and "serious"
algorithms that can be analyzed are better than the one that end up
depending on random hardware details.

I really think kernel random people need to stop this whole "in
theory" garbage, and embrace the "let's try to mix in small
non-predictable things in various places to actively make it hard to
analyze this".

Because at some point, "security by obscurity" is actually better than
"analyze this".

And we have decades of history to back this up. Stop with the crazy
"let's only use very expensive stuff has been analyzed".

It's actively detrimental.

It's detrimental to performance, but it's also detrimental to real security.

And stop dismissing performance as "who cares". Because it's just
feeding into this bad loop.

               Linus

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Linus Torvalds]

On Sat, Aug 8, 2020 at 10:45 AM Willy Tarreau <w@1wt.eu> wrote:
>
>
>     WIP: random32: use siphash with a counter for prandom_u32

siphash is good.

But no:

> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1277,7 +1277,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
>
>         fast_mix(fast_pool);
>         add_interrupt_bench(cycles);
> -       this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
>
>         if (unlikely(crng_init == 0)) {
>                 if ((fast_pool->count >= 64) &&
> --- a/include/linux/random.h
> +++ b/include/linux/random.h
> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> index 026ac01af9da..c9d839c2b179 100644
> --- a/kernel/time/timer.c
> +++ b/kernel/time/timer.c
> @@ -1743,13 +1743,6 @@ void update_process_times(int user_tick)
>         scheduler_tick();
>         if (IS_ENABLED(CONFIG_POSIX_TIMERS))
>                 run_posix_cpu_timers();
> -
> -       /* The current CPU might make use of net randoms without receiving IRQs
> -        * to renew them often enough. Let's update the net_rand_state from a
> -        * non-constant value that's not affine to the number of calls to make
> -        * sure it's updated when there's some activity (we don't care in idle).
> -        */
> -       this_cpu_add(net_rand_state.s1, rol32(jiffies, 24) + user_tick);
>  }

We're not going back to "don't add noise, just make a stronger
analyzable function".

I simply won't take it. See my previous email. I'm 100% fed up with
security people screwing up real security by trying to make things
overly analyzable.

If siphash is a good enough hash to make the pseudo-random state hard
to guess, then it's also a good enough hash to hide the small part of
the fast-pool we mix in.

And while security researchers may hate it because it's hard to
analyze, that's the POINT, dammit.

This "it's analyzable" makes it repeatable. And since mixing in
serious things is too slow, and people thus delay reseeding for too
long, then we reseed with random crap that doesn't hurt and that isn't
realistically analyzable.

              Linus

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Willy Tarreau]

On Sat, Aug 08, 2020 at 11:19:01AM -0700, Linus Torvalds wrote:
> On Sat, Aug 8, 2020 at 10:45 AM Willy Tarreau <w@1wt.eu> wrote:
> >
> >
> >     WIP: random32: use siphash with a counter for prandom_u32
> 
> siphash is good.
> 
> But no:
> 
> > --- a/drivers/char/random.c
> > +++ b/drivers/char/random.c
> > @@ -1277,7 +1277,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
> >
> >         fast_mix(fast_pool);
> >         add_interrupt_bench(cycles);
> > -       this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
> >
> >         if (unlikely(crng_init == 0)) {
> >                 if ((fast_pool->count >= 64) &&
> > --- a/include/linux/random.h
> > +++ b/include/linux/random.h
> > diff --git a/kernel/time/timer.c b/kernel/time/timer.c
> > index 026ac01af9da..c9d839c2b179 100644
> > --- a/kernel/time/timer.c
> > +++ b/kernel/time/timer.c
> > @@ -1743,13 +1743,6 @@ void update_process_times(int user_tick)
> >         scheduler_tick();
> >         if (IS_ENABLED(CONFIG_POSIX_TIMERS))
> >                 run_posix_cpu_timers();
> > -
> > -       /* The current CPU might make use of net randoms without receiving IRQs
> > -        * to renew them often enough. Let's update the net_rand_state from a
> > -        * non-constant value that's not affine to the number of calls to make
> > -        * sure it's updated when there's some activity (we don't care in idle).
> > -        */
> > -       this_cpu_add(net_rand_state.s1, rol32(jiffies, 24) + user_tick);
> >  }
> 
> We're not going back to "don't add noise, just make a stronger
> analyzable function".
> 
> I simply won't take it. See my previous email. I'm 100% fed up with
> security people screwing up real security by trying to make things
> overly analyzable.
> 
> If siphash is a good enough hash to make the pseudo-random state hard
> to guess, then it's also a good enough hash to hide the small part of
> the fast-pool we mix in.

I'm totally fine with that. In fact, my secret goal there was to put
net_rand_state back to random32.c as a static and reinstall the
__latent_entropy that we had to remove :-)

I'll need to re-run more correct tests though. My measurements were
really erratic with some of them showing half an HTTP request rate in
a test, which makes absolutely no sense and thus disqualifies my
measurements.

But if the results are correct enough I'm fine with continuing on this
one and forgetting MSWS.

> And while security researchers may hate it because it's hard to
> analyze, that's the POINT, dammit.

Actually I think there are two approaches which explains the constant
disagreements in this area. Some people want something provably
difficult, and others want something that cannot be proven to be easy. 
Sadly by trying to please everyone we probably got something between
provably easy and not provably difficult :-/

Willy

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 10:07:51AM -0700, Andy Lutomirski wrote:
>>    - Cryptographically strong ChaCha, batched
>>    - Cryptographically strong ChaCha, with anti-backtracking.
> 
> I think we should just anti-backtrack everything.  With the "fast key 
> erasure" construction, already implemented in my patchset for the 
> buffered bytes, this is extremely fast.

The problem is that this is really *amorized* key erasure, and
requires large buffers to amortize the cost down to a reasonable
level.

E,g, if using 256-bit (32-byte) keys, 5% overhead would require generating
640 bytes at a time.

Are we okay with ~1K per core for this?  Which we might have to
throw away occasionally to incorporate fresh seed material?

You're right that the simplification in usage is a benefit.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Florian Westphal]

Willy Tarreau <w@1wt.eu> wrote:
> diff --git a/include/linux/random.h b/include/linux/random.h
> index 9ab7443bd91b..9e22973b207c 100644
> --- a/include/linux/random.h
> +++ b/include/linux/random.h
> @@ -12,6 +12,7 @@
>  #include <linux/list.h>
>  #include <linux/once.h>
>  #include <asm/percpu.h>
> +#include <linux/siphash.h>
>  
>  #include <uapi/linux/random.h>
>  
> @@ -117,7 +118,8 @@ void prandom_seed(u32 seed);
>  void prandom_reseed_late(void);
>  
>  struct rnd_state {
> -	__u32 s1, s2, s3, s4;
> +	siphash_key_t key;
> +	uint64_t counter;
>  };

Does the siphash_key really need to be percpu?
The counter is different of course.
Alternative would be to siphash a few prandom_u32 results
if the extra u64 is too much storage.

>  DECLARE_PER_CPU(struct rnd_state, net_rand_state);
> @@ -161,12 +163,14 @@ static inline u32 __seed(u32 x, u32 m)
>   */
>  static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
>  {
> +#if 0
>  	u32 i = (seed >> 32) ^ (seed << 10) ^ seed;
>  
>  	state->s1 = __seed(i,   2U);
>  	state->s2 = __seed(i,   8U);
>  	state->s3 = __seed(i,  16U);
>  	state->s4 = __seed(i, 128U);
> +#endif
>  }
[..]

Can't we keep prandom_u32 as-is...?  Most of the usage, esp. in the
packet schedulers, is fine.

I'd much rather have a prandom_u32_hashed() or whatever for
those cases where some bits might leak to the outside and then convert
those prandom_u32 users over to the siphashed version.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Andy Lutomirski]

> On Aug 8, 2020, at 12:03 PM, George Spelvin <lkml@sdf.org> wrote:
> 
> On Sat, Aug 08, 2020 at 10:07:51AM -0700, Andy Lutomirski wrote:
>>>   - Cryptographically strong ChaCha, batched
>>>   - Cryptographically strong ChaCha, with anti-backtracking.
>> 
>> I think we should just anti-backtrack everything.  With the "fast key 
>> erasure" construction, already implemented in my patchset for the 
>> buffered bytes, this is extremely fast.
> 
> The problem is that this is really *amorized* key erasure, and
> requires large buffers to amortize the cost down to a reasonable
> level.
> 
> E,g, if using 256-bit (32-byte) keys, 5% overhead would require generating
> 640 bytes at a time.
> 
> Are we okay with ~1K per core for this?  Which we might have to
> throw away occasionally to incorporate fresh seed material?

I don’t care about throwing this stuff away. My plan (not quite implemented yet) is to have a percpu RNG stream and to never to anything resembling mixing anything in. The stream is periodically discarded and reinitialized from the global “primary” pool instead.  The primary pool has a global lock. We do some vaguely clever trickery to arrange for all the percpu pools to reseed from the primary pool at different times.

Meanwhile the primary pool gets reseeded by the input pool on a schedule for catastrophic reseeding.

5% overhead to make a fresh ChaCha20 key each time sounds totally fine to me. The real issue is that the bigger we make this thing, the bigger the latency spike each time we run it.

Do we really need 256 bits of key erasure?  I suppose if we only replace half the key each time, we’re just asking for some cryptographer to run the numbers on a break-one-of-many attack and come up with something vaguely alarming.

I wonder if we get good performance by spreading out the work. We could, for example, have a 320 byte output buffer that get_random_bytes() uses and a 320+32 byte “next” buffer that is generated as the output buffer is used. When we finish the output buffer, the first 320 bytes of the next buffer becomes the current buffer and the extra 32 bytes becomes the new key (or nonce).  This will have lower worst case latency, but it will hit the cache lines more often, potentially hurting throughout.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 07:44:51PM +0200, Willy Tarreau wrote:
> On Sat, Aug 08, 2020 at 03:26:28PM +0000, George Spelvin wrote:
>> So any discussion of reseeding begins by *assuming* an attacker has
>> captured the PRNG state.  If we weren't worried about this possibility,
>> we wouldn't need to reseed in the first place!
> 
> Sure, but what matters is the time it takes to capture the state.
> In the previous case it used to take Amit a few packets only. If it
> takes longer than the reseeding period, then it's not captured anymore.
> That was exactly the point there: break the certainty of the observations
> so that the state cannot be reliably guessed anymore, hence cancelling
> the concerns about the input bits being guessed. For sure if it is
> assumed that the state is guessed nevertheless, this doesn't work
> anymore, but that wasn't the assumption.

Just checking that you're aware: modern high-end network hardware does 
aggressive interupt coalescing, and NAPI disables interrupts entirely.  So 
you can transfer 10K packets per interrupt in extreme cases.

*Especially* on the transmit side, where the only thing you need to do 
after transmission is recycle the buffer, so latency concerns are minimal.  
In the steady state, all buffer recycling is done by polling while 
queueing new packets. You only need an interrupt to reclaim the last few 
buffers when transmission pauses.

So assuming that once per interrupt equals "often" is completely false.

Not to mention that the generators are per-CPU, and the CPU gnerating the 
random numbers might not be the one getting what few interrupts there are.  
(It's quite common in networking applications to bind network interrupts 
and application logic to separate CPUs.)

This whole bit of logic just seems ridiculously fragile to me.

>> Just like a buffer overflow, a working attack is plausible using a
>> combination of well-understood techniques.  It's ridiculous to go to
>> the effort of developing a full exploit when it's less work to fix the
>> problem in the first place.

> I totally agree with this principle. However, systematically starting
> with assumptions like "the PRNG's state is known to the attacker" while
> it's the purpose of the attack doesn't exactly match something which
> does not warrant a bit more explanation.

I thought I explained it, though.  Reseeding only matters if you're
trying to disrupt an attacker's knowledge of the PRNG state.  Yes,
assuming complete knowledge is a simplified "spherical cow", but the
logic applies to more complex partial-knowledge attacks as well.

The point is that a solution which solves that limiting case automatically 
takes care of all the other attacks, too.

If we have to carefully quantify an attacker's knowledge, using careful 
and delicate analysis to show security, then it's both more work, and 
*brittle*: the analysis must be re-checked each time the code is modified.

It just seems like a really crappy slumlord-quality solution.

> Note, it's beyond predictability, it's reversibility at this point.

I'm not quite sure what the distinction you're making is, but
I don't disagree.  Conventional PRNGs are trivially extrapolatable
forward and backward.  The *real* problem is that the network code
is asking for a property the PRNG explicitly lacks.

Just remember that the property of *not* being extrapolatable is 
specifically and exactly what makes a CPRNG cryptographic.

>> So the request is for a less predictable PRNG which is still extremely
>> fast.
> 
> That was the goal around the MSWS PRNG, as it didn't leak its bits
> and would require a certain amount of brute force.

The techniques for MSWS cryptanalysis aren't as widely documented as
LFSRs and LCGs, but I'm *very* skeptical of this claim.  I'd like to use
the most robust primitive that's not prohibitively slow.

> If it's considered as cryptographically secure, it's OK to feed it with
> just a counter starting from a random value, since the only way to guess
> the current counter state is to brute-force it, right ? I've done this in
> the appended patch. Note that for now I've commented out all the reseeding
> code because I just wanted to test the impact. 
> 
> In my perf measurements I've had some erratic behaviors, one test showing
> almost no loss, and another one showing a lot, which didn't make sense, so
> I'll need to measure again under better condition (i.e. not my laptop with
> a variable frequency CPU).

Actually, I was going to use a somewhat weaker construction that
does 2 rounds per output number.  Standard SipHash does 2n+4
rounds to handle n words of input, so would do 6 rounds in this
standard construction.  The 3x performance gain seems worth it.

The standard construction *would* allow a great code simplification,
since the key could be global and shared, and the per-CPU data would
be limited to a counter.  But I don't think 6 rounds would be fast
enough.

> There seems to be some general thinking among many crypto-savvy people
> that everything in the world needs strong crypto, including PRNGs, and
> that doesn't always help.

No, it's not needed for everything, but it *greatly* simplifies the 
analysis.  I agree that the crypto world suffers from "everything looks 
like a nail" syndrome, but there's value in indestructible building 
blocks: it makes reasoning about the resultant structure ever so much 
easier.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 11:19:01AM -0700, Linus Torvalds wrote:
> If siphash is a good enough hash to make the pseudo-random state hard
> to guess, then it's also a good enough hash to hide the small part of
> the fast-pool we mix in.

No!

No, no, a thousand times no.

I *just* finished explaining, using dribs and drabs of entropy allows an 
*information theoretical attack* which *no* crypto can prevent.

The drip-feed design of the current patch is a catastrophic antifeature
which must be anethametized.

You could replace SipHash with a random function, the platonic ideal
to which all other cryptographic functions are compared, and you'd
still have a hole.

The fact that *nothing* can fix bad seeding is the entire reason
/dev/random exists in the first place.


*Second*, I have no intention of using full SipHash.  I'm spending
all of that security margin making it as fast as possible, leaving
just enough to discourage the original attack.

As you just pointed out, half-MD4 (still used in fs/ext4/hash.c) is quite 
enough to discourage attack if used appropriately.

If you go and *vastly* increase the value of a successful attack, 
letting an attacker at long-lived high-value keys, I have to put all
that margin back.

(Not to mention, even full SipHash only offers 128-bit security in the 
first place!  Shall I go and delete AES-256 and SHA2-512, since we've 
decided the Linux kernel is capped at 128-bit security?)

It's not even remotely difficult: use the *output* of random.c.  
Making that safe is what all that code is for.

(It costs some cycles, but SipHash's strength lets you go long 
enough between reseeds that it amorizes to insignificance.)

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Linus Torvalds]

On Sat, Aug 8, 2020 at 1:08 PM George Spelvin <lkml@sdf.org> wrote:
>
> So assuming that once per interrupt equals "often" is completely false.

That's not what people are assuming.

They are assuming it's "unpredictable".

Guys, look up the real and true meaning of "random" some day.

Guess what? It at no point says "secure hash".

> Not to mention that the generators are per-CPU, and the CPU gnerating the
> random numbers might not be the one getting what few interrupts there are.
> (It's quite common in networking applications to bind network interrupts
> and application logic to separate CPUs.)

.. which is exactly why the commit that introduced this _also_ does
things from timer interrupts.

And yes. We know.Timer interrupts are turned off when there's nothing going on.

But the sending side - if it's not responding to an interrupt -
explicitly does have something going on, so you actually end up having
timer interrupts.

And yes, both IP and the TSC are "predictable". In theory. Not in
reality, and particularly not remotely.

And again, we knew - and discussed - interrupts coalescing and not
happening under load.

And again - that's a completely specious and pointless argument.

If you can put a machine under such load that it goes into polling
mode _and_ you also control _all_ the network traffic to such an
extent that other actors don't matter, and you get all the data out
and can analyze it to the point of trying to figure out what the prng
internal buffers are, you are basically already on the same network
and are controlling the machine.

It's not an interesting attack, in other words.

I repeat: reality matters. Your theoretical arguments are irrelevant,
because they simply don't even apply.

Btw, don't get me wrong - I think we can improve on the actual hashing
on the prng too. But I'm not backing down on the whole "we need noise
too, and the noise is actually more important".

> This whole bit of logic just seems ridiculously fragile to me.

No, what is fragile is assuming that you can have a random number
generator that is an analyzable secure hash, and then expecting that
to be high-performance and unpredictable.

We can do both. I'm _hoping_ people can come up with a
high-performance hash that is better than what we have. But there was
absolutely nothing going on for months after the last report, and even
with a better high-performance hash, I will absolutely refuse to get
rid of the noise factor.

           Linus

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Linus Torvalds]

On Sat, Aug 8, 2020 at 1:47 PM George Spelvin <lkml@sdf.org> wrote:
>
> I *just* finished explaining, using dribs and drabs of entropy allows an
> *information theoretical attack* which *no* crypto can prevent.

The key word here being "theoretical".

The other key word is "reality".

We will have to agree to disagree. I don't _care_ about the
theoretical holes. I care about the real ones.

We plugged a real one. Deal with it.

              Linus

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 09:18:27PM +0200, Florian Westphal wrote:
> Can't we keep prandom_u32 as-is...?  Most of the usage, esp. in the
> packet schedulers, is fine.
> 
> I'd much rather have a prandom_u32_hashed() or whatever for
> those cases where some bits might leak to the outside and then convert
> those prandom_u32 users over to the siphashed version.

That's a question I've been asking.  Since this is apparently an
Important Security Bug that wants backported to -stable, I'm making
the minimally-invasive change, which is to change prandom_u32() for
all callers rather that decide which gets what.

But going forward, adding an additional security level between
the current prandom_u32() and get_random_u32() is possible.

I'm not sure it's a good idea, however.  This entire hullalbaloo stems
from someone choosing the wrong PRNG.  Adding another option doesn't
seem likely to prevent a repetition in future.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Willy Tarreau]

Hi Florian,

On Sat, Aug 08, 2020 at 09:18:27PM +0200, Florian Westphal wrote:
> >  struct rnd_state {
> > -	__u32 s1, s2, s3, s4;
> > +	siphash_key_t key;
> > +	uint64_t counter;
> >  };
> 
> Does the siphash_key really need to be percpu?

I don't think so, I was really exploring a quick and easy change, and
given that it was convenient to put that into rnd_state to ease
adaptation to existing code, I left it here.

> The counter is different of course.
> Alternative would be to siphash a few prandom_u32 results
> if the extra u64 is too much storage.

I don't think we need to make it complicated. If we can implement a
partial siphash that's fast enough and that makes everyone happy, it
will also not take too much space so that could become an overall
improvement (and I'd say that reconciling everyone would also be a
huge improvement).

> >  DECLARE_PER_CPU(struct rnd_state, net_rand_state);
> > @@ -161,12 +163,14 @@ static inline u32 __seed(u32 x, u32 m)
> >   */
> >  static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
> >  {
> > +#if 0
> >  	u32 i = (seed >> 32) ^ (seed << 10) ^ seed;
> >  
> >  	state->s1 = __seed(i,   2U);
> >  	state->s2 = __seed(i,   8U);
> >  	state->s3 = __seed(i,  16U);
> >  	state->s4 = __seed(i, 128U);
> > +#endif
> >  }
> [..]
> 
> Can't we keep prandom_u32 as-is...?  Most of the usage, esp. in the
> packet schedulers, is fine.
>
> I'd much rather have a prandom_u32_hashed() or whatever for
> those cases where some bits might leak to the outside and then convert
> those prandom_u32 users over to the siphashed version.

In fact I even thought about having a different name, such as "weak_u32"
or something like this for the parts where we need slightly more than a
purely predictable random, and keeping the existing function as-is. But
I discovered there's also another one which is sufficient for stats, it
just doesn't have the same interface. But I totally agree on the benefit
of keeping the fastest version available for packet schedulers. In fact
I've run some of my tests with iptables -m statistics --probability ...
However if it turns out we can end up on a very fast PRNG (Tausworthe
was not *that* fast), it would be 100% benefit to turn to it. That's why
I don't want to rule out the possibility of a simple drop-in replacement.

By the way, if we end up keeping a different function for simpler cases,
we should probably find a better name for them like "predictable random"
or "trivial random" that makes users think twice. Doing that in a packet
scheduler is fine. The problem with the "pseudo random" term is that it
evolved over time from "totally predictable" to "may be strongly secure"
depending on implementations and that various people understand it
differently and have different expectations on it :-/

Cheers,
Willy

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 12:49:30PM -0700, Andy Lutomirski wrote:

> I don't care about throwing this stuff away. My plan (not quite 
> implemented yet) is to have a percpu RNG stream and to never to anything 
> resembling mixing anything in. The stream is periodically discarded and 
> reinitialized from the global "primary" pool instead.  The primary pool 
> has a global lock. We do some vaguely clever trickery to arrange for all 
> the percpu pools to reseed from the primary pool at different times.
>
> Meanwhile the primary pool gets reseeded by the input pool on a schedule 
> for catastrophic reseeding.

Sounds good to me.

> Do we really need 256 bits of key erasure?  I suppose if we only replace 
> half the key each time, we're just asking for some cryptographer to run 
> the numbers on a break-one-of-many attack and come up with something 
> vaguely alarming.

It's possible to have different levels of overall and key-erasure 
security, but I'm not sure what the point is.  It doesn't change the 
numbers *that* much.

(But yes, if you do it, I like the idea of arranging the key 
overwrite so all of the key gets replaced after two passes.)

> I wonder if we get good performance by spreading out the work. We could, 
> for example, have a 320 byte output buffer that get_random_bytes() uses 
> and a 320+32 byte ?next? buffer that is generated as the output buffer 
> is used. When we finish the output buffer, the first 320 bytes of the next 
> buffer becomes the current buffer and the extra 32 bytes becomes the new 
> key (or nonce).  This will have lower worst case latency, but it will 
> hit the cache lines more often, potentially hurting throughout.

You definitely lose something in locality of reference when you spread out 
the work, but you don't need a double-sized buffer (and the resultant 
D-cache hit). Every time you use up a block of current output, fill it 
with a block of next output.

The last 32 bytes of the buffer are the next key. When you've used up all 
of the current buffer but that, overwrite the last block of the current 
buffer with the next^2 key and start over at the beginning, outputting the 
was-next-now-current data.

On other words, with a 320-byte buffer, 320-32 = 288 bytes are available 
for output.  When we pass 64, 128, 256 and 288 bytes, there is a small 
latency spike to run one iteration of ChaCha.

The main issue is the latency between seeding and it affecting the output.  
In particular, I think people expect writes to /dev/random (RNDADDENTROPY) 
to affect subsequent reads immediately, so we'd need to invalidate & 
regenerate the buffer in that case.  We could do something with generation 
numbers so in-kernel users aren't affected.

(And remember that we don't have to fill the whole buffer.  If it's
early boot and we're expecting crng_init to increment, we could
pregenerate less.)

Re: Flaw in "random32: update the net random state on interrupt and activity"

[George Spelvin]

On Sat, Aug 08, 2020 at 01:52:37PM -0700, Linus Torvalds wrote:
> On Sat, Aug 8, 2020 at 1:47 PM George Spelvin <lkml@sdf.org> wrote:
>> I *just* finished explaining, using dribs and drabs of entropy allows an
>> *information theoretical attack* which *no* crypto can prevent.
> 
> The key word here being "theoretical".
> 
> The other key word is "reality".
> 
> We will have to agree to disagree. I don't _care_ about the
> theoretical holes. I care about the real ones.

It's not a theoretical hole, it's a very real one.  Other than the cycles 
to do the brute-force part, it's not even all that complicated.  The 
theory part is that it's impossible to patch.

*If* you do the stupid thing.  WHICH YOU COULD JUST STOP DOING.

> We plugged a real one. Deal with it.

The explain it to me.  What is that actual *problem*?  Nobody's described 
one, so I've been guessing.  What is this *monumentally stupid* abuse of 
/dev/random allegedly fixing?

If you're not an idiot, explain.

Because right now you sound like one.  There's a simple and easy fix which 
I've described and will get back to implementing as soon as I've finished 
yelling at you.  What, FFS, is your objection to considering it?

I'm trying to implement a solution that satisfies everyone's requirements 
*including* the absence of catastrophic security holes.  If there's some 
requirement I'm not satisfying, please tell me.  Just please don't say "I 
prefer doing the stupid thing to changing my mind."  I hear enough of that 
on the news.

I can deal with it *personally* by patching it out of my private kernels, 
but I'd really rather it doesn't get deployed to a billion devices before 
someone exploits it.

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Linus Torvalds]

On Sat, Aug 8, 2020 at 3:28 PM George Spelvin <lkml@sdf.org> wrote:
>
> It's not a theoretical hole, it's a very real one.  Other than the cycles
> to do the brute-force part, it's not even all that complicated.  The
> theory part is that it's impossible to patch.

We'll just disagree.

I'm really fed up with security holes that are brought on by crypto
people not being willing to just do reasonable things.

> *If* you do the stupid thing.  WHICH YOU COULD JUST STOP DOING.

We're not feeding all the same bits to the /dev/random that we're
using to also update the pseudo-random state, so I think you're
overreacting. Think of it as "/dev/random gets a few bits, and prandom
gets a few other bits".

The fact that there is overlap between the bits is immaterial, when
other parts are disjoint. Fractonal bits of entropy and all that.

> The explain it to me.  What is that actual *problem*?  Nobody's described
> one, so I've been guessing.  What is this *monumentally stupid* abuse of
> /dev/random allegedly fixing?

The problem is that the networking people really want unguessable
random state. There was a remote DNS spoofing poisoning attack because
the UDP ports ended up being guessable.

And that was actually reported to us back in early March.

Almost five months later, nothing had been done, all the discussion
bogged down about "theoretical randomness" rather than to actual
real-life security.

> If you're not an idiot, explain.
>
> Because right now you sound like one.  There's a simple and easy fix which
> I've described and will get back to implementing as soon as I've finished
> yelling at you.  What, FFS, is your objection to considering it?

By now, I'm not in the least interested in theoretical arguments.

I claim that the simple "mix in (different parts of) the TSC bits and
IP bits into _both_ the pseudo random state and the /dev/random state"
is going to make it hell on earth for anybody to ever find weaknesses
in either. Or if they do, they need to find and then exploit them
really quickly, because practically speaking, a few hundred times a
second you end up with noise that you cannot attack algorithmically
perturbing the state of both.

And I realize that drives you crazy. You _want_ to be able to analyze
the state to prove something about it. And that's absolutely the
opposite of what I want. I want the internal state (both prandom and
/dev/random) to simply not be amenable to analysis - simple because we
intentionally screw it up on interrupts. You can analyze it all you
want, knowing that in a few milliseconds you'll have to start over (at
least partially).

So even if you're the NSA, and it turns out that you have a magical
quantum computer that can break the best hash function crypto people
know about by just seeing a fairly small part stream of random
numbers, you'd better figure that state out quickly, because next
interrupt comes along, and we'll perturb it.

Or, say that you find something like meltdown, and can actually use
some side channel to read out the full state of our internal
/dev/random mixing buffers. ALL of it. No magic NSA quantum computer
required, just a side channel. Your "theoretical" are all complete and
utter shit in that case, if all we do is have the best possible secure
algorithm. Because the state is right there, and our
super-duper-secure algorithm is all open source, and your claims of
"this is unbreakable in theory" is just complet and utter nonsense.

This is why I claim the noise that you can't analyze is so important.
You see it as a weakness, because you see it as a "now I can't prove
certain things". I see it as exactly the opposite.

So to me, your whole "theoretical safety" argument is actually a huge
honking weakness.

Btw, you'll really hate what I did to /dev/random for initializing the
pool last year. Another case of "Christ, crypto people have screwed us
for decades, now I'm going to just fix it" situation.

Go do

    git log --author=Torvalds --no-merges drivers/char/random.c

and you'll probably have a heart attack.

              Linus

[DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

[-- Attachment #1: 0001-random32-Make-prandom_u32-output-difficult-to-predic.patch --]
[-- Type: text/plain, Size: 15932 bytes --]

Non-cryptographic PRNGs may have great statistical proprties, but
are usually trivially predictable to someone who knows the algorithm,
given a small sample of their output.  An LFSR like prandom_u32() is
particularly simple, even if the sample is widely scattered bits.

It turns out the network stack uses prandom_u32() for some things like
random port numbers which it would prefer are *not* trivially predictable.
Predictability led to a practical DNS spoofing attack.  Oops.

This patch replaces the LFSR with a homebrew cryptographic PRNG based
on the SipHash round function, which is in turn seeded with 128 bits
of strong random key.  (The authors of SipHash have *not* been consulted
about this abuse of their algorithm.)  Speed is prioritized over security;
attacks are rare, while performance is always wanted.

Replacing all callers of prandom_u32() is the quick fix.
Whether to reinstate a weaker PRNG for uses which can tolerate it
is an open question.

TODO: The prandom_seed() function is currently a no-op stub.
It's not obvious how to use this additional data, so suggestions are
invited.

f227e3ec3b5c ("random32: update the net random state on interrupt and
activity") was an earlier attempt at a solution.  This patch
replaces it; revert it before applying this one.

Reported-by: Amit Klein <aksecurity@gmail.com>
Cc: Willy Tarreau <w@1wt.eu>
Cc: Eric Dumazet <edumazet@google.com>
Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc: Andy Lutomirski <luto@kernel.org>
Cc: Kees Cook <keescook@chromium.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: <stable@vger.kernel.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Fixes: f227e3ec3b5c ("random32: update the net random state on interrupt and activity")
Replaces: f227e3ec3b5c ("random32: update the net random state on interrupt and activity")
Signed-off-by: George Spelvin <lkml@sdf.org>
---
 lib/random32.c | 437 ++++++++++++++++++++++++++++++-------------------
 1 file changed, 267 insertions(+), 170 deletions(-)

I haven't yet rebooted, so this is only build-tested, but it should illustrate
the idea.

diff --git a/lib/random32.c b/lib/random32.c
index 763b920a6206c..2b048e2ea99f6 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -48,8 +48,6 @@ static inline void prandom_state_selftest(void)
 }
 #endif
 
-static DEFINE_PER_CPU(struct rnd_state, net_rand_state) __latent_entropy;
-
 /**
  *	prandom_u32_state - seeded pseudo-random number generator.
  *	@state: pointer to state structure holding seeded state.
@@ -69,25 +67,6 @@ u32 prandom_u32_state(struct rnd_state *state)
 }
 EXPORT_SYMBOL(prandom_u32_state);
 
-/**
- *	prandom_u32 - pseudo random number generator
- *
- *	A 32 bit pseudo-random number is generated using a fast
- *	algorithm suitable for simulation. This algorithm is NOT
- *	considered safe for cryptographic use.
- */
-u32 prandom_u32(void)
-{
-	struct rnd_state *state = &get_cpu_var(net_rand_state);
-	u32 res;
-
-	res = prandom_u32_state(state);
-	put_cpu_var(net_rand_state);
-
-	return res;
-}
-EXPORT_SYMBOL(prandom_u32);
-
 /**
  *	prandom_bytes_state - get the requested number of pseudo-random bytes
  *
@@ -119,20 +98,6 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, size_t bytes)
 }
 EXPORT_SYMBOL(prandom_bytes_state);
 
-/**
- *	prandom_bytes - get the requested number of pseudo-random bytes
- *	@buf: where to copy the pseudo-random bytes to
- *	@bytes: the requested number of bytes
- */
-void prandom_bytes(void *buf, size_t bytes)
-{
-	struct rnd_state *state = &get_cpu_var(net_rand_state);
-
-	prandom_bytes_state(state, buf, bytes);
-	put_cpu_var(net_rand_state);
-}
-EXPORT_SYMBOL(prandom_bytes);
-
 static void prandom_warmup(struct rnd_state *state)
 {
 	/* Calling RNG ten times to satisfy recurrence condition */
@@ -148,96 +113,6 @@ static void prandom_warmup(struct rnd_state *state)
 	prandom_u32_state(state);
 }
 
-static u32 __extract_hwseed(void)
-{
-	unsigned int val = 0;
-
-	(void)(arch_get_random_seed_int(&val) ||
-	       arch_get_random_int(&val));
-
-	return val;
-}
-
-static void prandom_seed_early(struct rnd_state *state, u32 seed,
-			       bool mix_with_hwseed)
-{
-#define LCG(x)	 ((x) * 69069U)	/* super-duper LCG */
-#define HWSEED() (mix_with_hwseed ? __extract_hwseed() : 0)
-	state->s1 = __seed(HWSEED() ^ LCG(seed),        2U);
-	state->s2 = __seed(HWSEED() ^ LCG(state->s1),   8U);
-	state->s3 = __seed(HWSEED() ^ LCG(state->s2),  16U);
-	state->s4 = __seed(HWSEED() ^ LCG(state->s3), 128U);
-}
-
-/**
- *	prandom_seed - add entropy to pseudo random number generator
- *	@entropy: entropy value
- *
- *	Add some additional entropy to the prandom pool.
- */
-void prandom_seed(u32 entropy)
-{
-	int i;
-	/*
-	 * No locking on the CPUs, but then somewhat random results are, well,
-	 * expected.
-	 */
-	for_each_possible_cpu(i) {
-		struct rnd_state *state = &per_cpu(net_rand_state, i);
-
-		state->s1 = __seed(state->s1 ^ entropy, 2U);
-		prandom_warmup(state);
-	}
-}
-EXPORT_SYMBOL(prandom_seed);
-
-/*
- *	Generate some initially weak seeding values to allow
- *	to start the prandom_u32() engine.
- */
-static int __init prandom_init(void)
-{
-	int i;
-
-	prandom_state_selftest();
-
-	for_each_possible_cpu(i) {
-		struct rnd_state *state = &per_cpu(net_rand_state, i);
-		u32 weak_seed = (i + jiffies) ^ random_get_entropy();
-
-		prandom_seed_early(state, weak_seed, true);
-		prandom_warmup(state);
-	}
-
-	return 0;
-}
-core_initcall(prandom_init);
-
-static void __prandom_timer(struct timer_list *unused);
-
-static DEFINE_TIMER(seed_timer, __prandom_timer);
-
-static void __prandom_timer(struct timer_list *unused)
-{
-	u32 entropy;
-	unsigned long expires;
-
-	get_random_bytes(&entropy, sizeof(entropy));
-	prandom_seed(entropy);
-
-	/* reseed every ~60 seconds, in [40 .. 80) interval with slack */
-	expires = 40 + prandom_u32_max(40);
-	seed_timer.expires = jiffies + msecs_to_jiffies(expires * MSEC_PER_SEC);
-
-	add_timer(&seed_timer);
-}
-
-static void __init __prandom_start_seed_timer(void)
-{
-	seed_timer.expires = jiffies + msecs_to_jiffies(40 * MSEC_PER_SEC);
-	add_timer(&seed_timer);
-}
-
 void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
 {
 	int i;
@@ -257,51 +132,6 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
 }
 EXPORT_SYMBOL(prandom_seed_full_state);
 
-/*
- *	Generate better values after random number generator
- *	is fully initialized.
- */
-static void __prandom_reseed(bool late)
-{
-	unsigned long flags;
-	static bool latch = false;
-	static DEFINE_SPINLOCK(lock);
-
-	/* Asking for random bytes might result in bytes getting
-	 * moved into the nonblocking pool and thus marking it
-	 * as initialized. In this case we would double back into
-	 * this function and attempt to do a late reseed.
-	 * Ignore the pointless attempt to reseed again if we're
-	 * already waiting for bytes when the nonblocking pool
-	 * got initialized.
-	 */
-
-	/* only allow initial seeding (late == false) once */
-	if (!spin_trylock_irqsave(&lock, flags))
-		return;
-
-	if (latch && !late)
-		goto out;
-
-	latch = true;
-	prandom_seed_full_state(&net_rand_state);
-out:
-	spin_unlock_irqrestore(&lock, flags);
-}
-
-void prandom_reseed_late(void)
-{
-	__prandom_reseed(true);
-}
-
-static int __init prandom_reseed(void)
-{
-	__prandom_reseed(false);
-	__prandom_start_seed_timer();
-	return 0;
-}
-late_initcall(prandom_reseed);
-
 #ifdef CONFIG_RANDOM32_SELFTEST
 static struct prandom_test1 {
 	u32 seed;
@@ -463,3 +293,270 @@ static void __init prandom_state_selftest(void)
 		pr_info("prandom: %d self tests passed\n", runs);
 }
 #endif
+
+
+
+/*
+ * The prandom_u32() implementation is now completely separate from the
+ * prandom_state() functions, which are retained (for now) for compatibility.
+ *
+ * Because of (ab)use in the networking code for choosing random TCP/UDP port
+ * numbers, which open DoS possibilities if guessable, we want something
+ * stronger than a standard PRNG.  But the performance requirements of
+ * the network code do not allow robust crypto for this application.
+ *
+ * So this is a homebrew Junior Spaceman implementation, based on the
+ * lowest-latency trustworthy crypto primitive available, SipHash.
+ * (The authors of SipHash have not been consulted about this abuse of
+ * their work.)
+ *
+ * Standard SipHash-2-4 uses 2n+4 rounds to hash n words of input to
+ * one word of output.  This abbreviated version uses 2 rounds per word
+ * of output.
+ */
+
+struct siprand_state {
+	unsigned long v[4];
+};
+
+static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
+
+#if BITS_PER_LONG == 64
+/*
+ * The core SipHash round function.  Each line can be executed in
+ * parallel given enough CPU resources.
+ */
+#define SIPROUND(v0,v1,v2,v3) ( \
+	v0 += v1, v1 = rol64(v1, 13),  v2 += v3, v3 = rol64(v3, 16), \
+	v1 ^= v0, v0 = rol64(v0, 32),  v3 ^= v2,                     \
+	v0 += v3, v3 = rol64(v3, 21),  v2 += v1, v1 = rol64(v1, 17), \
+	v3 ^= v0,                      v1 ^= v2, v2 = rol64(v2, 32)  )
+#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
+#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
+
+#elif BITS_PER_LONG == 23
+/*
+ * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
+ * This is weaker, but 32-bit machines are not used for high-traffic
+ * applications, so there is less output for an attacker to analyze.
+ */
+#define SIPROUND(v0,v1,v2,v3) ( \
+	v0 += v1, v1 = rol32(v1,  5),  v2 += v3, v3 = rol32(v3,  8), \
+	v1 ^= v0, v0 = rol32(v0, 16),  v3 ^= v2,                     \
+	v0 += v3, v3 = rol32(v3,  7),  v2 += v1, v1 = rol32(v1, 13), \
+	v3 ^= v0,                      v1 ^= v2, v2 = rol32(v2, 16)  )
+#define K0 0x6c796765
+#define K1 0x74656462
+
+#else
+#error Unsupported BITS_PER_LONG
+#endif
+
+/*
+ * This is the core CPRNG function.  As "pseudorandom", this is not used
+ * for truly valuable things, just intended to be a PITA to guess.
+ * For maximum speed, we do just two SipHash rounds per word.  This is
+ * the same rate as 4 rounds per 64 bits that SipHash normally uses,
+ * so hopefully it's reasonably secure.
+ *
+ * There are two changes from the official SipHash finalization:
+ * - We omit some constants XORed with v2 in the SipHash spec as irrelevant;
+ *   they are there only to make the output rounds distinct from the input
+ *   rounds, and this application has no input rounds.
+ * - Rather than returning v0^v1^v2^v3, return v1+v3.
+ *   If you look at the SipHash round, the last operation on v3 is
+ *   "v3 ^= v0", so "v0 ^ v3" just undoes that, a waste of time.
+ *   Likewise "v1 ^= v2".  (The rotate of v2 makes a difference, but
+ *   it still cancels out half of the bits in v2 for no benefit.)
+ *   Second, since the last combining operation was xor, continue the
+ *   pattern of alternating xor/add for a tiny bit of extra non-linearity.
+ */
+static u32 siprand_u32(struct siprand_state *s)
+{
+	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
+
+	SIPROUND(v0, v1, v2, v3);
+	SIPROUND(v0, v1, v2, v3);
+	s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;
+	return v1 + v3;
+}
+
+
+/**
+ *	prandom_u32 - pseudo random number generator
+ *
+ *	A 32 bit pseudo-random number is generated using a fast
+ *	algorithm suitable for simulation. This algorithm is NOT
+ *	considered safe for cryptographic use.
+ */
+u32 prandom_u32(void)
+{
+	struct siprand_state *state = get_cpu_ptr(&net_rand_state);
+	u32 res = siprand_u32(state);
+
+	put_cpu_ptr(&net_rand_state);
+	return res;
+}
+EXPORT_SYMBOL(prandom_u32);
+
+/**
+ *	prandom_bytes - get the requested number of pseudo-random bytes
+ *	@buf: where to copy the pseudo-random bytes to
+ *	@bytes: the requested number of bytes
+ */
+void prandom_bytes(void *buf, size_t bytes)
+{
+	struct siprand_state *state = get_cpu_ptr(&net_rand_state);
+	u8 *ptr = buf;
+
+	while (bytes >= sizeof(u32)) {
+		put_unaligned(siprand_u32(state), (u32 *)ptr);
+		ptr += sizeof(u32);
+		bytes -= sizeof(u32);
+	}
+
+	if (bytes > 0) {
+		u32 rem = siprand_u32(state);
+		do {
+			*ptr++ = (u8)rem;
+			rem >>= BITS_PER_BYTE;
+		} while (--bytes > 0);
+	}
+	put_cpu_ptr(&net_rand_state);
+}
+EXPORT_SYMBOL(prandom_bytes);
+
+/**
+ *	prandom_seed - add entropy to pseudo random number generator
+ *	@entropy: entropy value
+ *
+ *	Add some additional seed material to the prandom pool.
+ *	The "entropy" is actually our IP address (the only caller is
+ *	the network code), not for unpredictability, but to ensure that
+ *	different machines are initialized differently.
+ */
+void prandom_seed(u32 entropy)
+{
+	/* FIXME: Where to feed this in? */
+}
+EXPORT_SYMBOL(prandom_seed);
+
+/*
+ *	Generate some initially weak seeding values to allow
+ *	the prandom_u32() engine to be started.
+ */
+static int __init prandom_init_early(void)
+{
+	int i;
+	unsigned long v0, v1, v2, v3;
+
+	if (!arch_get_random_long(&v0))
+		v0 = jiffies;
+	if (!arch_get_random_long(&v1))
+		v0 = random_get_entropy();
+	v2 = v0 ^ K0;
+	v3 = v1 ^ K1;
+
+	for_each_possible_cpu(i) {
+		struct siprand_state *state;
+
+		v3 ^= i;
+		SIPROUND(v0, v1, v2, v3);
+		SIPROUND(v0, v1, v2, v3);
+		v0 ^= i;
+
+		state = per_cpu_ptr(&net_rand_state, i);
+		state->v[0] = v0;  state->v[1] = v1;
+		state->v[2] = v2;  state->v[3] = v3;
+	}
+
+	return 0;
+}
+core_initcall(prandom_init_early);
+
+
+/* Stronger reseeding when available, and periodically thereafter. */
+static void prandom_reseed(struct timer_list *unused);
+
+static DEFINE_TIMER(seed_timer, prandom_reseed);
+
+static void prandom_reseed(struct timer_list *unused)
+{
+	unsigned long expires;
+	int i;
+
+	/*
+	 * Reinitialize each CPU's PRNG with 128 bits of key.
+	 * No locking on the CPUs, but then somewhat random results are,
+	 * well, expected.
+	 */
+	for_each_possible_cpu(i) {
+		struct siprand_state *state;
+		unsigned long v0 = get_random_long(), v2 = v0 ^ K0;
+		unsigned long v1 = get_random_long(), v3 = v1 ^ K1;
+#if BITS_PER_LONG == 32
+		int j;
+
+		/*
+		 * On 32-bit machines, hash in two extra words to
+		 * approximate 128-bit key length.  Not that the hash
+		 * has that much security, but this prevents a trivial
+		 * 64-bit brute force.
+		 */
+		for (j = 0; j < 2; j++) {
+			unsigned long m = get_random_long();
+			v3 ^= m;
+			SIPROUND(v0, v1, v2, v3);
+			SIPROUND(v0, v1, v2, v3);
+			v0 ^= m;
+		}
+#endif
+		/*
+		 * Probably impossible in practice, but there is a
+		 * theoretical risk that a race between this reseeding
+		 * and the target CPU writing its state back could
+		 * create the all-zero SipHash fixed point.
+		 *
+		 * To ensure that never happens, ensure the state
+		 * we write contains no zero words.
+		 */
+		state = per_cpu_ptr(&net_rand_state, i);
+		WRITE_ONCE(state->v[0], v0 ? v0 : -1ul);
+		WRITE_ONCE(state->v[1], v1 ? v1 : -1ul);
+		WRITE_ONCE(state->v[2], v2 ? v2 : -1ul);
+		WRITE_ONCE(state->v[3], v3 ? v3 : -1ul);
+	}
+
+	/* reseed every ~60 seconds, in [40 .. 80) interval with slack */
+	expires = round_jiffies(jiffies + 40 * HZ + prandom_u32_max(40 * HZ));
+	mod_timer(&seed_timer, expires);
+}
+
+/*
+ * The random ready callback can be called from almost any interrupt.
+ * To avoid worrying about whether it's safe to delay that interrupt
+ * long enough to seed all CPUs, just schedule an immediate timer event.
+ */
+static void prandom_timer_start(struct random_ready_callback *unused)
+{
+	mod_timer(&seed_timer, jiffies);
+}
+
+/*
+ * Start periodic full reseeding as soon as strong
+ * random numbers are available.
+ */
+static int __init prandom_init_late(void)
+{
+	static struct random_ready_callback random_ready = {
+	        .func = prandom_timer_start
+	};
+	int ret = add_random_ready_callback(&random_ready);
+
+	if (ret == -EALREADY) {
+		prandom_timer_start(&random_ready);
+		ret = 0;
+	}
+	return ret;
+}
+late_initcall(prandom_init_late);
-- 
2.28.0

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

Hi George,

On Sun, Aug 09, 2020 at 06:57:44AM +0000, George Spelvin wrote:
> +/*
> + * This is the core CPRNG function.  As "pseudorandom", this is not used
> + * for truly valuable things, just intended to be a PITA to guess.
> + * For maximum speed, we do just two SipHash rounds per word.  This is
> + * the same rate as 4 rounds per 64 bits that SipHash normally uses,
> + * so hopefully it's reasonably secure.
> + *
> + * There are two changes from the official SipHash finalization:
> + * - We omit some constants XORed with v2 in the SipHash spec as irrelevant;
> + *   they are there only to make the output rounds distinct from the input
> + *   rounds, and this application has no input rounds.
> + * - Rather than returning v0^v1^v2^v3, return v1+v3.
> + *   If you look at the SipHash round, the last operation on v3 is
> + *   "v3 ^= v0", so "v0 ^ v3" just undoes that, a waste of time.
> + *   Likewise "v1 ^= v2".  (The rotate of v2 makes a difference, but
> + *   it still cancels out half of the bits in v2 for no benefit.)
> + *   Second, since the last combining operation was xor, continue the
> + *   pattern of alternating xor/add for a tiny bit of extra non-linearity.
> + */
> +static u32 siprand_u32(struct siprand_state *s)
> +{
> +	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
> +
> +	SIPROUND(v0, v1, v2, v3);
> +	SIPROUND(v0, v1, v2, v3);
> +	s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;
> +	return v1 + v3;
> +}
> +
> +
> +/**
> + *	prandom_u32 - pseudo random number generator
> + *
> + *	A 32 bit pseudo-random number is generated using a fast
> + *	algorithm suitable for simulation. This algorithm is NOT
> + *	considered safe for cryptographic use.
> + */
> +u32 prandom_u32(void)
> +{
> +	struct siprand_state *state = get_cpu_ptr(&net_rand_state);
> +	u32 res = siprand_u32(state);
> +
> +	put_cpu_ptr(&net_rand_state);
> +	return res;
> +}

So I gave it a quick test under Qemu and it didn't show any obvious
performance difference compared to Tausworthe, which is a good thing,
even though there's a significant amount of measurement noise in each
case.

However it keeps the problem that the whole sequence is entirely
determined at the moment of reseeding, so if one were to be able to
access the state, e.g. using l1tf/spectre/meltdown/whatever, then
this state could be used to predict the whole ongoing sequence for
the next minute. What some view as a security feature, others will
see as a backdoor :-/  That's why I really like the noise approach.
Even just the below would significantly harm that capability because
that state alone isn't sufficient anymore to pre-compute all future
values:

--- a/lib/random32.c
+++ b/lib/random32.c
@@ -375,6 +375,7 @@ static u32 siprand_u32(struct siprand_state *s)
 {
        unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
 
+       v0 += get_cycles();
        SIPROUND(v0, v1, v2, v3);
        SIPROUND(v0, v1, v2, v3);
        s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;

Regards,
Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Randy Dunlap]

On 8/8/20 11:57 PM, George Spelvin wrote:



+#elif BITS_PER_LONG == 23


s/23/32/ ???

-- 
~Randy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

On Sun, Aug 09, 2020 at 11:26:31AM +0300, Amit Klein wrote:
> BITS_PER_LONG==23 ???
> Should be ==32, I guess.

Of course.  I've been testing on a 64-bit system so hadn't
exercised that branch yet, and it's a case of "seeing what
I expect to see".

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

On Sun, Aug 09, 2020 at 11:38:05AM +0200, Willy Tarreau wrote:
> So I gave it a quick test under Qemu and it didn't show any obvious
> performance difference compared to Tausworthe, which is a good thing,
> even though there's a significant amount of measurement noise in each
> case.

Thank you very much!  I'm not quite sure how to benchmark this.
The whole idea is that it's *not* used in a tight cache-hot loop.
Hopefully someone already has a test setup so I don't have to invent
one.

> However it keeps the problem that the whole sequence is entirely
> determined at the moment of reseeding, so if one were to be able to
> access the state, e.g. using l1tf/spectre/meltdown/whatever, then
> this state could be used to predict the whole ongoing sequence for
> the next minute. What some view as a security feature, others will
> see as a backdoor :-/  That's why I really like the noise approach.
> Even just the below would significantly harm that capability because
> that state alone isn't sufficient anymore to pre-compute all future
> values:
> 
> --- a/lib/random32.c
> +++ b/lib/random32.c
> @@ -375,6 +375,7 @@ static u32 siprand_u32(struct siprand_state *s)
>  {
>         unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
>  
> +       v0 += get_cycles();
>         SIPROUND(v0, v1, v2, v3);
>         SIPROUND(v0, v1, v2, v3);
>         s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;

As long as:
1) The periodic catastrophic reseeding remains, and
2) You use fresh measurements, not the exact same bits
   that add_*_randomness feeds into /dev/random
then it doesn't do any real harm, so if it makes you feel better...

But I really want to stress how weak a design drip-reseeding is.

If an attacker has enough local machine access to do a meltdown-style attack,
then they can calibrate the TSC used in get_cycles very accurately, so the
remaining timing uncertainty is very low.  This makes a brute-force attack on
one or two reseedings quite easy.  I.e. if you can see every other output,
It's straightforward to figure out the ones in between.

I wonder if, on general principles, it would be better to use a more
SipHash style mixing in of the sample:
	m = get_cycles();
	v3 ^= m;
	SIPROUND(v0, v1, v2, v3);
	SIPROUND(v0, v1, v2, v3);
	v0 ^= m;

Not sure if it's worth the extra register (and associated spill/fill).

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Sun, Aug 09, 2020 at 05:06:39PM +0000, George Spelvin wrote:
> On Sun, Aug 09, 2020 at 11:38:05AM +0200, Willy Tarreau wrote:
> > So I gave it a quick test under Qemu and it didn't show any obvious
> > performance difference compared to Tausworthe, which is a good thing,
> > even though there's a significant amount of measurement noise in each
> > case.
> 
> Thank you very much!  I'm not quite sure how to benchmark this.
> The whole idea is that it's *not* used in a tight cache-hot loop.
> Hopefully someone already has a test setup so I don't have to invent
> one.

Due to limited access to representative hardware, the to main tests
I've been running were on my laptop in qemu, and consisted in :

   - a connect-accept-close test to stress the accept() code and
     verify we don't observe a significant drop. The thing is that
     connect() usually is much slower and running the two on the
     same machine tends to significantly soften the differences
     compared to what a real machine would see when handling a
     DDoS for example.

   - a packet rate test through this rule (which uses prandom_u32()
     for each packet and which matches what can be done in packet
     schedulers or just by users having to deal with random drop) :

     iptables -I INPUT -m statistic --probability 0.5 -j ACCEPT

While these ones are not very relevant, especially in a VM, not
seeing significant variations tends to indicate we should not see
a catastrophic loss.

> > However it keeps the problem that the whole sequence is entirely
> > determined at the moment of reseeding, so if one were to be able to
> > access the state, e.g. using l1tf/spectre/meltdown/whatever, then
> > this state could be used to predict the whole ongoing sequence for
> > the next minute. What some view as a security feature, others will
> > see as a backdoor :-/  That's why I really like the noise approach.
> > Even just the below would significantly harm that capability because
> > that state alone isn't sufficient anymore to pre-compute all future
> > values:
> > 
> > --- a/lib/random32.c
> > +++ b/lib/random32.c
> > @@ -375,6 +375,7 @@ static u32 siprand_u32(struct siprand_state *s)
> >  {
> >         unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
> >  
> > +       v0 += get_cycles();
> >         SIPROUND(v0, v1, v2, v3);
> >         SIPROUND(v0, v1, v2, v3);
> >         s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;
> 
> As long as:
> 1) The periodic catastrophic reseeding remains, and
> 2) You use fresh measurements, not the exact same bits
>    that add_*_randomness feeds into /dev/random
> then it doesn't do any real harm, so if it makes you feel better...
> 
> But I really want to stress how weak a design drip-reseeding is.
> 
> If an attacker has enough local machine access to do a meltdown-style attack,
> then they can calibrate the TSC used in get_cycles very accurately,

Absolutely.

> so the
> remaining timing uncertainty is very low.

Not that low in fact because they don't know precisely when the call is
made. I mean, let's say we're in the worst case, with two VMs running on
two siblings of the same core, with the same TSC, on a 3 GHz machine. The
attacker can stress the victim at 100k probes per second. That's still
15 bits of uncertainty on the TSC value estimation which is added to each
call. Even on the first call this is enough to make a source port
unguessable, and preventing the attacker from staying synchronized with
its victim. And I'm only speaking about an idle remote machine, not even
one taking unobservable traffic, which further adds to the difficulty.

> This makes a brute-force attack on
> one or two reseedings quite easy.  I.e. if you can see every other output,
> It's straightforward to figure out the ones in between.

But they already become useless because you're only observing stuff of
the past.

> I wonder if, on general principles, it would be better to use a more
> SipHash style mixing in of the sample:
> 	m = get_cycles();
> 	v3 ^= m;
> 	SIPROUND(v0, v1, v2, v3);
> 	SIPROUND(v0, v1, v2, v3);
> 	v0 ^= m;

Probably, if it's the recommended way to mix in other values, yes.

> Not sure if it's worth the extra register (and associated spill/fill).

If this makes the hash better, maybe. I can run some tests on this as
well. I'd really need to try on a cleaner setup, I have remote machines
at the office but I don't feel safe enough to remotely reboot them and
risk to lose them :-/

I'll also test on arm/arm64 to make sure we don't introduce a significant
cost there.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

On Sun, Aug 09, 2020 at 07:33:03PM +0200, Willy Tarreau wrote:
> Not that low in fact because they don't know precisely when the call is
> made. I mean, let's say we're in the worst case, with two VMs running on
> two siblings of the same core, with the same TSC, on a 3 GHz machine. The
> attacker can stress the victim at 100k probes per second. That's still
> 15 bits of uncertainty on the TSC value estimation which is added to each
> call. Even on the first call this is enough to make a source port
> unguessable, and preventing the attacker from staying synchronized with
> its victim. And I'm only speaking about an idle remote machine, not even
> one taking unobservable traffic, which further adds to the difficulty.

I'm trying to understand your attack scenario.  I'm assuming that an
attacker can call prandom_u32() locally.  (I don't have a specific code
path, but given the number of uses in the kernel, I assume *one* of
them will leak the output directly.)  And repeat the call fast
enough that there's at most *one* other user between our calls.

If an attacker knows the initial state, does an rdtsc, prandom_u32(),
and a second rdtsc, then they can guess the TSC value used in than
prandom_u32() quite accurately (4-6 bits fuzz, perhaps).  This is
trivial to brute force.

The fun comes if someone else does a prandom_u32() call in between.

All of a sudden, the 4-6 bit brute force of one get_cycles() value
fails to find a solution.  Someone else has called prandom_u32()!

Now we have 15 bits of uncertainty about that other call, and 5 bits
of uncertainty about our call.  2^20 possibilities only takes a few
milliseconds to test, and the 32-bit output of prandom_u32() can
verify a guess with minimal probability of error.

(Note that, to maintain tracking, we have to keep hammering
prandom_u32() *during* the search, but we can just buffer the results
and process them after the expensive search is complete.)

What you can see here is the incredible power of *multiple* unobserved
seedings.  As long as an attacker can limit things to one unobserved
prandom_u32(), it's a simple brute force.

If there are mroe than one, the additional bits of uncertainty
quickly make things impractical.

This is why I'm so keen on less frequent, more catastrophic,
reseeding.  Yes, the delay means an attacker who has captured
the state retains full knowledge for longer.  But they get
kicked off as soon as the catastophe happens.  Without it, they
can keep tracking the state indefinitely.

Even something simple like buffering 8 TSC samples, and adding them
at 32-bit offsets across the state every 8th call, would make a huge
difference.

Even if 7 of the timestamps are from attacker calls (4 bits
uncertainty), the time of the target call is 8x less known
(so it goes from 15 to 18 bits), and the total becomes
46 bits.  *So* much better.

> I can run some tests on this as
> well. I'd really need to try on a cleaner setup, I have remote machines
> at the office but I don't feel safe enough to remotely reboot them and
> risk to lose them :-/

Yeah, test kernels are nervous-making that way.

> I'll also test on arm/arm64 to make sure we don't introduce a significant
> cost there.

I don't expect a problem, but SipHash is optimized for 4-issue processors,
and on narrower machines fewer instructions are "free".

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Sun, Aug 09, 2020 at 06:30:17PM +0000, George Spelvin wrote:
> I'm trying to understand your attack scenario.  I'm assuming that an
> attacker can call prandom_u32() locally.

Well, first, I'm mostly focusing on remote attacks, because if the
attacker has a permanent local access, he can as well just bind()
a source port instead of having to guess the next one that will be
used. Second, I'm not aware of direct access from userland, so the
calls to prandom_u32() are expected to be done only via specific
code parts. The worst case (in my opinion) is when the attacker
runs on the same physical CPU and exploits some memory leakage to
find the internal state and uses the same TSC, but can only trigger
prandom_u32() via the network, hence with much less precision.

(...)
> Even something simple like buffering 8 TSC samples, and adding them
> at 32-bit offsets across the state every 8th call, would make a huge
> difference.
> 
> Even if 7 of the timestamps are from attacker calls (4 bits
> uncertainty), the time of the target call is 8x less known
> (so it goes from 15 to 18 bits), and the total becomes
> 46 bits.  *So* much better.

Maybe. I'm just suggesting to add *some* noise to keep things not
exploitable if the state is stolen once in a while (which would
already be a big problem, admittedly).

> > I can run some tests on this as
> > well. I'd really need to try on a cleaner setup, I have remote machines
> > at the office but I don't feel safe enough to remotely reboot them and
> > risk to lose them :-/
> 
> Yeah, test kernels are nervous-making that way.

In fact I never booted a 5.8 kernel on the machine I'm thinking about
yet and can't remote-control its power supply, so I'm worried about
a dirty hang at boot by missing a config entry. The risk is low but
that's annoying when it happens.

> > I'll also test on arm/arm64 to make sure we don't introduce a significant
> > cost there.
> 
> I don't expect a problem, but SipHash is optimized for 4-issue processors,
> and on narrower machines fewer instructions are "free".

OK.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Marc Plumb]

(Reseending since I accidentally sent it as HTML which the netdev 
mailing list doesn't like)

On 2020-08-09 2:05 p.m., Marc Plumb wrote:
>
> Willy,
>
>
> On 2020-08-07 3:19 p.m., Willy Tarreau wrote:
>>> If I can figure the state out once,
>> Yes but how do you take that as granted ? This state doesn't appear
>> without its noise counterpart, so taking as a prerequisite that you may
>> guess one separately obviously indicates that you then just have to
>> deduce the other, but the point of mixing precisely is that we do not
>> expose individual parts.
>
>
> On 2020-08-09 2:38 a.m., Willy Tarreau wrote:
>> However it keeps the problem that the whole sequence is entirely
>> determined at the moment of reseeding, so if one were to be able to
>> access the state, e.g. using l1tf/spectre/meltdown/whatever, then
>> this state could be used to predict the whole ongoing sequence for
>> the next minute. What some view as a security feature, others will
>> see as a backdoor :-/  That's why I really like the noise approach.
>> Even just the below would significantly harm that capability because
>> that state alone isn't sufficient anymore to pre-compute all future
>> values:
>
>
> So two days ago I was unreasonable for assuming an attacker to could 
> recover the entire state, now you're assuming the same thing? As I 
> said before, if an attacker can recover the complete state, then 
> slowly adding noise doesn't help significantly since an attacker can 
> brute force the noise added (even if a perfect CPRNG is used).
>
> However, I think I'm starting to see your underlying assumptions. 
> You're thinking that raw noise data are the only truly unpredictable 
> thing so you think that adding it is a defense against attacks like 
> foreshadow/spectre/meltdown. You aren't entirely wrong -- if there was 
> a fast noise source then it might be a good option. Just if the noise 
> source is slow, you're just causing far more damage to a far more 
> critical crytpto function to get very little benefit.
>
> If you want to add noise to the network PRNG, then you can't put the 
> same noise into the dev/random CPRNG at all, in any way. I've tried 
> explaining the crypto reasons for this, and George has added to that, 
> so let me try a different approach: It breaks FIPS 140-2 for all of 
> Linux. While FIPS certification isn't a key driver, it is a 
> consideration for the crypt modules. FIPS references NIST.SP.800-90B 
> (which is specifically about Recommendation for the Entropy Sources 
> Used for Random Bit Generation) which has a requirement that the noise 
> source not pass any data used for crypto operations to anything 
> outside of the defined security boundary. If you want to feed a noise 
> measurement into the network PRNG, then you can't feed it into the 
> /dev/random pool also. You have to decide where the different 
> measurements are going to go and keep them completely seperate.
>
> I'm not intimately familiar with the standards so I spoke with someone 
> who does FIPS 140-x certification and was told "I don't think the 
> standards even considered the idea that someone might pass data from a 
> conditioning pool to other functions. It completely violates the 
> security boundary concept so is just prohibited ... that type of 
> change would absolutely be a problem."
>
>
> Marc
>

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Linus Torvalds]

On Sun, Aug 9, 2020 at 2:10 PM Marc Plumb <lkml.mplumb@gmail.com> wrote:
>
> However, I think I'm starting to see your underlying assumptions.
> You're thinking that raw noise data are the only truly unpredictable
> thing so you think that adding it is a defense against attacks like
> foreshadow/spectre/meltdown. You aren't entirely wrong -- if there was
> a fast noise source then it might be a good option. Just if the noise
> source is slow, you're just causing far more damage to a far more
> critical crypto function to get very little benefit.

The only truly good noise source we have is any CPU native randomness.

Sadly, that is usually never really "fast". But we do use that for any
actual real /dev/random reading. We still whiten it through our
hashing, and we mix it in rather than use the raw CPU hw-provided
values (because not everybody trusts the CPU vendors either), but
/dev/random will most certainly take advantage of it as one source of
noise.

(Honesty in advertising: you can also use other interfaces that don't
bother with the remixing, and _will_ just return the raw CPU
randomness).

So if you make the (imho reasonable) assumption that you're running on
a modern enough CPU, and that the CPU hw randomness is of reasonable
quality, then you never need to worry about /dev/random. Every single
time you extract something from one of the pools, I think we mix in
that CPU randomness if it's available.

But the CPU randomness is too slow for the prandom code to use at
extraction time. It's on the order of a couple of hundred to a couple
of thousand cycles. That's peanuts for /dev/random, but quite a lot
for prandom.

In fact, at the slow end it is slow enough that you don't want to do
it at any fast granularity (ie not "every interrupt"), it's the "when
reseeding once a second" kind of slow.

arm64 has randomness too these days too, but that's only of the
"really slow, useful for seeding" variety. And I'm not sure which (if
any) CPU implementations out there actually do it yet.

Anyway, I suspect /dev/random has been over-engineered (I think we
have something like three layers of mixing bits _and_ the CPU
randomness _and_ all the interrupt randomness), and prandom may have
been left alone too much.

             Linus

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

Hi George,

On Sun, Aug 09, 2020 at 06:30:17PM +0000, George Spelvin wrote:
> Even something simple like buffering 8 TSC samples, and adding them
> at 32-bit offsets across the state every 8th call, would make a huge
> difference.

Doing testing on real hardware showed that retrieving the TSC on every
call had a non negligible cost, causing a loss of 2.5% on the accept()
rate and 4% on packet rate when using iptables -m statistics. However
I reused your idea of accumulating old TSCs to increase the uncertainty
about their exact value, except that I retrieve it only on 1/8 calls
and use the previous noise in this case. With this I observe the same
performance as plain 5.8. Below are the connection rates accepted on
a single core :

        5.8           5.8+patch     5.8+patch+tsc
   192900-197900   188800->192200   194500-197500  (conn/s)

This was on a core i7-8700K. I looked at the asm code for the function
and it remains reasonably light, in the same order of complexity as the
original one, so I think we could go with that.

My proposed change is below, in case you have any improvements to suggest.

Regards,
Willy


diff --git a/lib/random32.c b/lib/random32.c
index 2b048e2ea99f..a12d63028106 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -317,6 +317,8 @@ static void __init prandom_state_selftest(void)
 
 struct siprand_state {
 	unsigned long v[4];
+	unsigned long noise;
+	unsigned long count;
 };
 
 static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
@@ -334,7 +336,7 @@ static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
 #define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
 #define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
 
-#elif BITS_PER_LONG == 23
+#elif BITS_PER_LONG == 32
 /*
  * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
  * This is weaker, but 32-bit machines are not used for high-traffic
@@ -375,6 +377,12 @@ static u32 siprand_u32(struct siprand_state *s)
 {
 	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
 
+	if (++s->count >= 8) {
+		v3 ^= s->noise;
+		s->noise += random_get_entropy();
+		s->count = 0;
+	}
+
 	SIPROUND(v0, v1, v2, v3);
 	SIPROUND(v0, v1, v2, v3);
 	s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;

RE: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[David Laight]

From: Willy Tarreau
> Sent: 10 August 2020 12:47
> On Sun, Aug 09, 2020 at 06:30:17PM +0000, George Spelvin wrote:
> > Even something simple like buffering 8 TSC samples, and adding them
> > at 32-bit offsets across the state every 8th call, would make a huge
> > difference.
> 
> Doing testing on real hardware showed that retrieving the TSC on every
> call had a non negligible cost, causing a loss of 2.5% on the accept()
> rate and 4% on packet rate when using iptables -m statistics. However
> I reused your idea of accumulating old TSCs to increase the uncertainty
> about their exact value, except that I retrieve it only on 1/8 calls
> and use the previous noise in this case. With this I observe the same
> performance as plain 5.8. Below are the connection rates accepted on
> a single core :
> 
>         5.8           5.8+patch     5.8+patch+tsc
>    192900-197900   188800->192200   194500-197500  (conn/s)
> 
> This was on a core i7-8700K. I looked at the asm code for the function
> and it remains reasonably light, in the same order of complexity as the
> original one, so I think we could go with that.
> 
> My proposed change is below, in case you have any improvements to suggest.
> 
> Regards,
> Willy
> 
> 
> diff --git a/lib/random32.c b/lib/random32.c
> index 2b048e2ea99f..a12d63028106 100644
> --- a/lib/random32.c
> +++ b/lib/random32.c
> @@ -317,6 +317,8 @@ static void __init prandom_state_selftest(void)
> 
>  struct siprand_state {
>  	unsigned long v[4];
> +	unsigned long noise;
> +	unsigned long count;
>  };
> 
>  static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
> @@ -334,7 +336,7 @@ static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
>  #define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
>  #define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
> 
> -#elif BITS_PER_LONG == 23
> +#elif BITS_PER_LONG == 32
>  /*
>   * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
>   * This is weaker, but 32-bit machines are not used for high-traffic
> @@ -375,6 +377,12 @@ static u32 siprand_u32(struct siprand_state *s)
>  {
>  	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
> 
> +	if (++s->count >= 8) {
> +		v3 ^= s->noise;
> +		s->noise += random_get_entropy();
> +		s->count = 0;
> +	}
> +

Using:
	if (s->count-- <= 0) {
		...
		s->count = 8;
	}
probably generates better code.
Although you may want to use a 'signed int' instead of 'unsigned long'.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Florian Westphal]

Willy Tarreau <w@1wt.eu> wrote:
> On Sun, Aug 09, 2020 at 06:30:17PM +0000, George Spelvin wrote:
> > Even something simple like buffering 8 TSC samples, and adding them
> > at 32-bit offsets across the state every 8th call, would make a huge
> > difference.
> 
> Doing testing on real hardware showed that retrieving the TSC on every
> call had a non negligible cost, causing a loss of 2.5% on the accept()
> rate and 4% on packet rate when using iptables -m statistics. However
> I reused your idea of accumulating old TSCs to increase the uncertainty
> about their exact value, except that I retrieve it only on 1/8 calls
> and use the previous noise in this case. With this I observe the same
> performance as plain 5.8. Below are the connection rates accepted on
> a single core :
> 
>         5.8           5.8+patch     5.8+patch+tsc
>    192900-197900   188800->192200   194500-197500  (conn/s)
> 
> This was on a core i7-8700K. I looked at the asm code for the function
> and it remains reasonably light, in the same order of complexity as the
> original one, so I think we could go with that.
> 
> My proposed change is below, in case you have any improvements to suggest.

As this relates to networking, you could also hook perturbation into rx/tx
softirq processing.  E.g. once for each new napi poll round or only once
for each softnet invocation, depending on cost.

IIRC the proposed draft left a unused prandom_seed() stub around, you could
re-use that to place extra data to include in the hash in percpu data.

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Mon, Aug 10, 2020 at 12:01:11PM +0000, David Laight wrote:
> >  /*
> >   * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
> >   * This is weaker, but 32-bit machines are not used for high-traffic
> > @@ -375,6 +377,12 @@ static u32 siprand_u32(struct siprand_state *s)
> >  {
> >  	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
> > 
> > +	if (++s->count >= 8) {
> > +		v3 ^= s->noise;
> > +		s->noise += random_get_entropy();
> > +		s->count = 0;
> > +	}
> > +
> 
> Using:
> 	if (s->count-- <= 0) {
> 		...
> 		s->count = 8;
> 	}
> probably generates better code.
> Although you may want to use a 'signed int' instead of 'unsigned long'.

Yeah I know, it's just because I only slightly changed the previous code
there. I had an earlier version that kept the rand state fully padded
when storing intermediate values. That's among the final cleanups I'll
bring if we go down that route.

Thanks!

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Mon, Aug 10, 2020 at 02:03:02PM +0200, Florian Westphal wrote:
> As this relates to networking, you could also hook perturbation into rx/tx
> softirq processing.  E.g. once for each new napi poll round or only once
> for each softnet invocation, depending on cost.

I was wondering what/where to add some processing. I was thinking about
having a per_cpu "noise" variable that would get mixed with the randoms
when generated. This "noise" would need to be global so that we can easily
append to it. For example on the network path it would be nice to use
checksums but nowadays they're not calculated anymore.

> IIRC the proposed draft left a unused prandom_seed() stub around, you could
> re-use that to place extra data to include in the hash in percpu data.

Probably. What I saw was that prandom_seed() expected to perform a full
(hence slow) reseed. Instead I'd like to do something cheap. I like the
principle of "noise" in that it doesn't promise to bring any security,
only to perturb a little bit.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Linus Torvalds]

On Mon, Aug 10, 2020 at 4:47 AM Willy Tarreau <w@1wt.eu> wrote:
>
> Doing testing on real hardware showed that retrieving the TSC on every
> call had a non negligible cost, causing a loss of 2.5% on the accept()
> rate and 4% on packet rate when using iptables -m statistics.

And by "real hardware" I assume you mean x86, with a fairly fast and
high-performance TSC for get_random_entropy().

Reading the TSC takes on the order of 20-50 cycles, iirc.

But it can actually be *much* more expensive. On non-x86, it can be an
IO cycle to external chips.

And on older hardware VM's in x86, it can be a vm exit etc, so
thousands of cycles. I hope nobody uses those VM's any more, but it
would be a reasonable test-case for some non-x86 implementations, so..

IOW, no. You guys are - once again - ignoring reality.

            Linus

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Mon, Aug 10, 2020 at 09:31:48AM -0700, Linus Torvalds wrote:
> On Mon, Aug 10, 2020 at 4:47 AM Willy Tarreau <w@1wt.eu> wrote:
> >
> > Doing testing on real hardware showed that retrieving the TSC on every
> > call had a non negligible cost, causing a loss of 2.5% on the accept()
> > rate and 4% on packet rate when using iptables -m statistics.
> 
> And by "real hardware" I assume you mean x86, with a fairly fast and
> high-performance TSC for get_random_entropy().

Yep.

> Reading the TSC takes on the order of 20-50 cycles, iirc.
> 
> But it can actually be *much* more expensive. On non-x86, it can be an
> IO cycle to external chips.

I took what we were already using in add_interrupt_randomness() since
I considered that if it was acceptable there, it probably was elsewhere.

> And on older hardware VM's in x86, it can be a vm exit etc, so
> thousands of cycles. I hope nobody uses those VM's any more, but it
> would be a reasonable test-case for some non-x86 implementations, so..

Yes, I remember these ones, they were not fun at all.

> IOW, no. You guys are - once again - ignoring reality.

I'm not ignoring reality, quite the opposite, trying to take all knowledge
into account. If I'm missing some points, fine. But if we were already
calling that in the interrupt handler I expected that this would be OK.

The alternative Florian talked about is quite interesting as well,
which is to collect some cheap noise in the network rx/tx paths since
these are the areas we care about.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Linus Torvalds]

On Mon, Aug 10, 2020 at 9:59 AM Willy Tarreau <w@1wt.eu> wrote:
>
> I took what we were already using in add_interrupt_randomness() since
> I considered that if it was acceptable there, it probably was elsewhere.

Once you've taken an interrupt, you're doing IO anyway, and the
interrupt costs will dominate anything you do.

But the prandom_u32() interface is potentially done many times per
interrupt. For all I know it's done inside fairly critical locks etc
too.

So I don't think one usage translates to another very well.

              Linus

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Mon, Aug 10, 2020 at 10:45:26AM -0700, Linus Torvalds wrote:
> On Mon, Aug 10, 2020 at 9:59 AM Willy Tarreau <w@1wt.eu> wrote:
> >
> > I took what we were already using in add_interrupt_randomness() since
> > I considered that if it was acceptable there, it probably was elsewhere.
> 
> Once you've taken an interrupt, you're doing IO anyway, and the
> interrupt costs will dominate anything you do.
> 
> But the prandom_u32() interface is potentially done many times per
> interrupt. For all I know it's done inside fairly critical locks etc
> too.
> 
> So I don't think one usage translates to another very well.

Possible, hence the better solution to just feed noise in hot paths.
Using jiffies and skb pointer in xmit is better than nothing anyway.
I'm not seeking anything extremist, I just want to make sure we don't
get yet-another-report on this area next summer just because some
researcher using two VMs discovers that attacking a 100% idle VM from
another one running on the same CPU core is trivial after having stolen
some memory data.  If at least such an attack is boring and rarely
works, the rest of the job is provided by siphash and we should be fine.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

Linus, George, Florian,

would something in this vein be OK in your opinion ?

- update_process_times still updates the noise
- we don't touch the fast_pool anymore
- we don't read any TSC on hot paths
- we update the noise in xmit from jiffies and a few pointer values instead

I've applied it on top of George's patch rebased to mainline for simplicity.
I've used a separate per_cpu noise variable to keep the net_rand_state static
with its __latent_entropy.

With this I'm even getting very slightly better performance than with
the previous patch (195.7 - 197.8k cps).

What could be improved is the way the input values are mixed (just
added hence commutative for now). I didn't want to call a siphash
round on the hot paths, but just shifting the previous noise value
before adding would work, such as the following for example:

  void prandom_u32_add_noise(a, b, c, d)
  {
  	unsigned long *noise = get_cpu_ptr(&net_rand_noise);

  #if BITS_PER_LONG == 64
	*noise = rol64(*noise, 7) + a + b + c + d;
  #else
	*noise = rol32(*noise, 7) + a + b + c + d;
  #endif
  	put_cpu_ptr(&net_rand_noise);

  }

Thanks,
Willy

---


diff --git a/drivers/char/random.c b/drivers/char/random.c
index d20ba1b104ca..2a41b21623ae 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1277,7 +1277,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
 
 	fast_mix(fast_pool);
 	add_interrupt_bench(cycles);
-	this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
 
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index aa16e6468f91..e2b4990f2126 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -20,7 +20,7 @@ struct rnd_state {
 	__u32 s1, s2, s3, s4;
 };
 
-DECLARE_PER_CPU(struct rnd_state, net_rand_state);
+DECLARE_PER_CPU(unsigned long, net_rand_noise);
 
 u32 prandom_u32_state(struct rnd_state *state);
 void prandom_bytes_state(struct rnd_state *state, void *buf, size_t nbytes);
@@ -67,6 +67,7 @@ static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
 	state->s2 = __seed(i,   8U);
 	state->s3 = __seed(i,  16U);
 	state->s4 = __seed(i, 128U);
+	__this_cpu_add(net_rand_noise, i);
 }
 
 /* Pseudo random number generator from numerical recipes. */
diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index ae5029f984a8..2f07c569af77 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1721,7 +1721,7 @@ void update_process_times(int user_tick)
 	 * non-constant value that's not affine to the number of calls to make
 	 * sure it's updated when there's some activity (we don't care in idle).
 	 */
-	this_cpu_add(net_rand_state.s1, rol32(jiffies, 24) + user_tick);
+	__this_cpu_add(net_rand_noise, rol32(jiffies, 24) + user_tick);
 }
 
 /**
diff --git a/lib/random32.c b/lib/random32.c
index 2b048e2ea99f..d74cf1db8cc9 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -320,6 +320,8 @@ struct siprand_state {
 };
 
 static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
+DEFINE_PER_CPU(unsigned long, net_rand_noise);
+EXPORT_SYMBOL(net_rand_noise);
 
 #if BITS_PER_LONG == 64
 /*
@@ -334,7 +336,7 @@ static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
 #define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
 #define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
 
-#elif BITS_PER_LONG == 23
+#elif BITS_PER_LONG == 32
 /*
  * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
  * This is weaker, but 32-bit machines are not used for high-traffic
@@ -374,9 +376,12 @@ static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
 static u32 siprand_u32(struct siprand_state *s)
 {
 	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
+	unsigned long n = __this_cpu_read(net_rand_noise);
 
+	v3 ^= n;
 	SIPROUND(v0, v1, v2, v3);
 	SIPROUND(v0, v1, v2, v3);
+	v0 ^= n;
 	s->v[0] = v0;  s->v[1] = v1;  s->v[2] = v2;  s->v[3] = v3;
 	return v1 + v3;
 }
diff --git a/net/core/dev.c b/net/core/dev.c
index 7df6c9617321..55a2471cd75b 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -144,6 +144,7 @@
 #include <linux/indirect_call_wrapper.h>
 #include <net/devlink.h>
 #include <linux/pm_runtime.h>
+#include <linux/prandom.h>
 
 #include "net-sysfs.h"
 
@@ -3557,6 +3558,7 @@ static int xmit_one(struct sk_buff *skb, struct net_device *dev,
 		dev_queue_xmit_nit(skb, dev);
 
 	len = skb->len;
+	__this_cpu_add(net_rand_noise, (long)skb + (long)dev + (long)txq + len + jiffies);
 	trace_net_dev_start_xmit(skb, dev);
 	rc = netdev_start_xmit(skb, dev, txq, more);
 	trace_net_dev_xmit(skb, rc, dev, len);
@@ -4129,6 +4131,7 @@ static int __dev_queue_xmit(struct sk_buff *skb, struct net_device *sb_dev)
 			if (!skb)
 				goto out;
 
+			__this_cpu_add(net_rand_noise, (long)skb + (long)dev + (long)txq + jiffies);
 			HARD_TX_LOCK(dev, txq, cpu);
 
 			if (!netif_xmit_stopped(txq)) {
@@ -4194,6 +4197,7 @@ int dev_direct_xmit(struct sk_buff *skb, u16 queue_id)
 
 	skb_set_queue_mapping(skb, queue_id);
 	txq = skb_get_tx_queue(dev, skb);
+	__this_cpu_add(net_rand_noise, (long)skb + (long)dev + (long)txq + jiffies);
 
 	local_bh_disable();
 

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

On Mon, Aug 10, 2020 at 01:47:00PM +0200, Willy Tarreau wrote:
> except that I retrieve it only on 1/8 calls
> and use the previous noise in this case.

Er... that's quite different.  I was saying you measure them all, and do:

 struct siprand_state {
 	...
+	uint32_t noise[i];
+	unsigned counter;
 }
 	...
+	s->noise[--s->counter] = random_get_entropy();
+
+	if (!s->counter) {
+		for (i = 0; i < 4; i++)
+			s->v[i] += s->noise[2*i] +
+				((unsigned long)s->noise[2*i+1] << BITS_PER_LONG/2);
+		s->counter = 8;
+	}

What you're doing is just decreasing the amount of seeding by a factor
of 8.  (Roughly.  You do gain log2(8)/2 = 1.5 bits because the sum of
8 random values has a standard deviation sqrt(8) times as large as
the inputs.)

> diff --git a/lib/random32.c b/lib/random32.c
> index 2b048e2ea99f..a12d63028106 100644
> --- a/lib/random32.c
> +++ b/lib/random32.c
> @@ -317,6 +317,8 @@ static void __init prandom_state_selftest(void)
>  
>  struct siprand_state {
>  	unsigned long v[4];
> +	unsigned long noise;
> +	unsigned long count;
>  };
>  
>  static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
> @@ -334,7 +336,7 @@ static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
>  #define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
>  #define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
>  
> -#elif BITS_PER_LONG == 23
> +#elif BITS_PER_LONG == 32
>  /*
>   * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
>   * This is weaker, but 32-bit machines are not used for high-traffic
> @@ -375,6 +377,12 @@ static u32 siprand_u32(struct siprand_state *s)
>  {
>  	unsigned long v0 = s->v[0], v1 = s->v[1], v2 = s->v[2], v3 = s->v[3];
>  
> +	if (++s->count >= 8) {
> +		v3 ^= s->noise;
> +		s->noise += random_get_entropy();
> +		s->count = 0;
> +	}
> +

- Can you explain why you save the "noise" until next time?  Is this meant to
  make it harder for an attacker to observe the time?
- How about doing away with s->count and making it statistical:

+	if ((v3 & 7) == 0)
+		v3 ^= random_get_entropy();

That still does the seed 1/8 of the time, but in a much less regular pattern.
(Admittedly, it will totally break the branch predictor.  An unlikely()
might help.)

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Tue, Aug 11, 2020 at 03:47:24AM +0000, George Spelvin wrote:
> On Mon, Aug 10, 2020 at 01:47:00PM +0200, Willy Tarreau wrote:
> > except that I retrieve it only on 1/8 calls
> > and use the previous noise in this case.
> 
> Er... that's quite different.  I was saying you measure them all, and do:

That was my first approach and it resulted in a significant performance
loss, hence the change (and the resulting ugly construct with the counter).

> > +	if (++s->count >= 8) {
> > +		v3 ^= s->noise;
> > +		s->noise += random_get_entropy();
> > +		s->count = 0;
> > +	}
> > +
> 
> - Can you explain why you save the "noise" until next time?  Is this meant to
>   make it harder for an attacker to observe the time?

Just to make the observable call not depend on immediately measurable TSC
values. It's weak, but the point was that when mixing attack traffic with
regular one, if you can measure the time variations on TSC to know when
it was used and don't have its resulting effect at the same time, it's
harder to analyse than when you have both at once.

> - How about doing away with s->count and making it statistical:
> 
> +	if ((v3 & 7) == 0)
> +		v3 ^= random_get_entropy();

Absolutely. I just kept the counter from previous attempt. But Linus
prefers that we completely remove TSC calls from direct calls due to
old VMs that were slow at this. We could collect it anywhere else once
in a while instead.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[George Spelvin]

On Mon, Aug 10, 2020 at 11:04:55PM +0200, Willy Tarreau wrote:
> What could be improved is the way the input values are mixed (just
> added hence commutative for now). I didn't want to call a siphash
> round on the hot paths, but just shifting the previous noise value
> before adding would work, such as the following for example:
> 
>   void prandom_u32_add_noise(a, b, c, d)
>   {
>   	unsigned long *noise = get_cpu_ptr(&net_rand_noise);
> 
>   #if BITS_PER_LONG == 64
> 	*noise = rol64(*noise, 7) + a + b + c + d;
>   #else
> 	*noise = rol32(*noise, 7) + a + b + c + d;
>   #endif
>   	put_cpu_ptr(&net_rand_noise);
> 
>   }

If you think this is enough seed material, I'm fine with it.

I don't hugely like the fact that you sum all the inputs, since
entropy tends to be concentrated in the low-order words, and summing
risks cancellation.

You can't afford even one SIPROUND as a non-cryptographic hash?  E.g.

DEFINE_PER_CPU(unsigned long[4], net_rand_noise);
EXPORT_SYMBOL(net_rand_noise);

void prandom_u32_add_noise(a, b, c, d)
{
	unsigned long *noise = get_cpu_ptr(&net_rand_noise);

	a ^= noise[0];
	b ^= noise[1];
	c ^= noise[2];
	d ^= noise[3];
	/*
	 * This is not used cryptographically; it's just
	 * a convenient 4-word hash function.
	 */
	SIPROUND(a, b, c, d);
	noise[0] = a;
	noise[1] = b;
	noise[2] = c;
	put_cpu_ptr(&net_rand_noise);
}

(And then you mix in net_rand_noise[0].)

Other options are HASH_MIX() from fs/namei.c, but that's
more sequential.

There's also a simple Xorshift generator.

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Tue, Aug 11, 2020 at 05:26:49AM +0000, George Spelvin wrote:
> On Mon, Aug 10, 2020 at 11:04:55PM +0200, Willy Tarreau wrote:
> > What could be improved is the way the input values are mixed (just
> > added hence commutative for now). I didn't want to call a siphash
> > round on the hot paths, but just shifting the previous noise value
> > before adding would work, such as the following for example:
> > 
> >   void prandom_u32_add_noise(a, b, c, d)
> >   {
> >   	unsigned long *noise = get_cpu_ptr(&net_rand_noise);
> > 
> >   #if BITS_PER_LONG == 64
> > 	*noise = rol64(*noise, 7) + a + b + c + d;
> >   #else
> > 	*noise = rol32(*noise, 7) + a + b + c + d;
> >   #endif
> >   	put_cpu_ptr(&net_rand_noise);
> > 
> >   }
> 
> If you think this is enough seed material, I'm fine with it.
> 
> I don't hugely like the fact that you sum all the inputs, since
> entropy tends to be concentrated in the low-order words, and summing
> risks cancellation.

Yes I've figured this. But I thought it was still better than
a pure xor which would cancell the high bits from pointers.

> You can't afford even one SIPROUND as a non-cryptographic hash?  E.g.

That's what I mentioned above, I'm still hesitating. I need to test.

> 
> DEFINE_PER_CPU(unsigned long[4], net_rand_noise);
> EXPORT_SYMBOL(net_rand_noise);
> 
> void prandom_u32_add_noise(a, b, c, d)
> {
> 	unsigned long *noise = get_cpu_ptr(&net_rand_noise);
> 
> 	a ^= noise[0];
> 	b ^= noise[1];
> 	c ^= noise[2];
> 	d ^= noise[3];
> 	/*
> 	 * This is not used cryptographically; it's just
> 	 * a convenient 4-word hash function.
> 	 */
> 	SIPROUND(a, b, c, d);
> 	noise[0] = a;
> 	noise[1] = b;
> 	noise[2] = c;
> 	put_cpu_ptr(&net_rand_noise);
> }
> 
> (And then you mix in net_rand_noise[0].)
> 
> Other options are HASH_MIX() from fs/namei.c, but that's
> more sequential.
> 
> There's also a simple Xorshift generator.

I think a xorshift on each value will have roughly the same cost
as a single SIPROUND. But I've not yet completely eliminated these
options until I've tested. If we lose a few cycles per packet, that
might be OK.

Willy

Re: Flaw in "random32: update the net random state on interrupt and activity"

[Eric Dumazet]

On Sat, Aug 8, 2020 at 7:07 PM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> On Sat, Aug 8, 2020 at 3:28 PM George Spelvin <lkml@sdf.org> wrote:
> >
> > It's not a theoretical hole, it's a very real one.  Other than the cycles
> > to do the brute-force part, it's not even all that complicated.  The
> > theory part is that it's impossible to patch.
>
> We'll just disagree.
>
> I'm really fed up with security holes that are brought on by crypto
> people not being willing to just do reasonable things.
>
> > *If* you do the stupid thing.  WHICH YOU COULD JUST STOP DOING.
>
> We're not feeding all the same bits to the /dev/random that we're
> using to also update the pseudo-random state, so I think you're
> overreacting. Think of it as "/dev/random gets a few bits, and prandom
> gets a few other bits".
>
> The fact that there is overlap between the bits is immaterial, when
> other parts are disjoint. Fractonal bits of entropy and all that.
>
> > The explain it to me.  What is that actual *problem*?  Nobody's described
> > one, so I've been guessing.  What is this *monumentally stupid* abuse of
> > /dev/random allegedly fixing?
>
> The problem is that the networking people really want unguessable
> random state. There was a remote DNS spoofing poisoning attack because
> the UDP ports ended up being guessable.
>
> And that was actually reported to us back in early March.
>

Another typical use of prandom_u32() is the one in
tcp_conn_request(), when processing a SYN packet.

My fear was that adding much more cpu cycles to prandom_u32() would
reduce our ability to cope with a SYN flood attack,
but looking more closely to tcp_conn_request(), there might be a way
to remove the prandom_u32() call
when we generate a syncookie, reflecting incoming skb hash (if already
populated)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 184ea556f50e35141a4be5940c692db41e09f464..fc698a8ea13b1b6a6bd952308d11414eadfa4eaf
100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -6740,10 +6740,12 @@ int tcp_conn_request(struct request_sock_ops *rsk_ops,
                isn = cookie_init_sequence(af_ops, sk, skb, &req->mss);
                if (!tmp_opt.tstamp_ok)
                        inet_rsk(req)->ecn_ok = 0;
+               tcp_rsk(req)->txhash = skb->hash ?: 1;
+       } else {
+               tcp_rsk(req)->txhash = net_tx_rndhash();
        }

        tcp_rsk(req)->snt_isn = isn;
-       tcp_rsk(req)->txhash = net_tx_rndhash();
        tcp_openreq_init_rwin(req, sk, dst);
        sk_rx_queue_set(req_to_sk(req), skb);
        if (!want_cookie) {


BTW we could add a trace event so that the answer to 'who is using
prandom_u32' could be easily answered.

diff --git a/include/trace/events/random.h b/include/trace/events/random.h
index 32c10a515e2d5438e8d620a0c2313aab5f849b2b..9570a10cb949b5792c4290ba8e82a077ac655069
100644
--- a/include/trace/events/random.h
+++ b/include/trace/events/random.h
@@ -307,6 +307,23 @@ TRACE_EVENT(urandom_read,
                  __entry->pool_left, __entry->input_left)
 );

+TRACE_EVENT(prandom_u32,
+
+       TP_PROTO(unsigned int ret),
+
+       TP_ARGS(ret),
+
+       TP_STRUCT__entry(
+               __field(   unsigned int, ret)
+       ),
+
+       TP_fast_assign(
+               __entry->ret = ret;
+       ),
+
+       TP_printk("ret=%u" , __entry->ret)
+);
+
 #endif /* _TRACE_RANDOM_H */

 /* This part must be outside protection */
diff --git a/lib/random32.c b/lib/random32.c
index 3d749abb9e80d54d8e330e07fb8b773b7bec2b83..932345323af092a93fc2690b0ebbf4f7485ae4f3
100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -39,6 +39,7 @@
 #include <linux/random.h>
 #include <linux/sched.h>
 #include <asm/unaligned.h>
+#include <trace/events/random.h>

 #ifdef CONFIG_RANDOM32_SELFTEST
 static void __init prandom_state_selftest(void);
@@ -82,6 +83,7 @@ u32 prandom_u32(void)
        u32 res;

        res = prandom_u32_state(state);
+       trace_prandom_u32(res);
        put_cpu_var(net_rand_state);

        return res;

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Thu, Aug 27, 2020 at 3:09 AM Willy Tarreau <w@1wt.eu> wrote:
>
> Hi Amit,
>
> On Thu, Aug 27, 2020 at 02:06:39AM +0300, Amit Klein wrote:
> > Hi
> >
> > Is there an ETA for this patch then?
>
> No particular ETA on my side, I was waiting for potential criticisms
> before going further. I suspect that if nobody complains anymore, it's
> an implicit voucher and I'll have to clean up and post the series then.
>

Hi Willy,

again a feedback from me as a tester of the last patchset.

I have tested it in several build-environments:

#1: GCC v10.2 + GNU/ld (BFD)
#2: GCC v10.2 + LLVM/ld.lld (LLD)
#3: GCC v10.2 + LLD plus all available LLVM "bin"utils v11.0.0-rc2
(replacements for GNU's nm, objdump, objcopy, ar, strin, ranlib, etc.)
#4: LLVM toolchain v11.0.0-rc2 and Clang-IAS (Integrated ASsembler)
#5: LLVM toolchain v11.0.0-rc2 and Clang-LTO (LinkTime Optimization)
#6: LLVM toolchain v11.0.0-rc2 and Clang-CFI (Control Flow Integrity)

For what are you waiting for :-)?

Feel free to add my...

Tested-by: Sedat Dilek <sedat.dilek@gmail.com>

If you are interested in Clang-IAS/Clang-LTO/Clang-CFI... I want to
promote the LLVM MC (micro-conference) at Linux Plumbers Conference
2020 today (27-Aug-2020) - starting 16:00 UTC.
AFAICS it is freely available via YouTube (untested by me).

- Sedat -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

Hi Amit,

On Thu, Aug 27, 2020 at 02:06:39AM +0300, Amit Klein wrote:
> Hi
> 
> Is there an ETA for this patch then?

No particular ETA on my side, I was waiting for potential criticisms
before going further. I suspect that if nobody complains anymore, it's
an implicit voucher and I'll have to clean up and post the series then.

Thanks,
Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

[-- Attachment #1: Type: text/plain, Size: 2348 bytes --]

On Thu, Aug 20, 2020 at 10:05 AM Willy Tarreau <w@1wt.eu> wrote:
>
> On Thu, Aug 20, 2020 at 08:58:38AM +0200, Willy Tarreau wrote:
> > I've just pushed a new branch "20200820-siphash-noise" that I also
> > rebased onto latest master. It's currently running make allmodconfig
> > here, so that will take a while, but I think it's OK as random32.o is
> > already OK. I've also addressed a strange build issue caused by having
> > an array instead of 4 ints in siprand_state.
> >
> > Please just let me know if that's OK for you now.
>
> At least it worked for me now (built with no errors on x86_64):
>
> $ time make -j 8 bzImage modules
> (...)
> real    65m7.986s
> user    477m22.477s
> sys     38m0.545s
> $ find . -name '*.ko' |wc -l
> 7983
>

Runs fine here.

Thanks Willy for the "20200820-siphash-noise" [1] patchset and
including/fixing all my reported issues.

[1] Staging driver build failures fixed by...
WIP: random32: rename the K0/K1 SipHash constants to PRND_K*

[2] modpost undefined "net_rand_noise" errors fixed by...
WIP: random32: export net_rand_noise

[3] Consolidate/move/cleanup stuff in random32.c and prandom.h
WIP: random32: keep a single macro definition for sipround

This patchset looks very good to me :-).

[ TESTING WITH LTP ]

I run another perf-session by running
"LTP::net.features::tcp_fastopen" test only.
Unsure if there exist some more appropriate LTP tests.
For example there exists "net_stress.*" (see [2]).

[ PERF-SESSION ]

Link: https://github.com/ClangBuiltLinux/linux/issues/1086#issuecomment-675783804

/home/dileks/bin/perf list | grep prandom_u32 | column -t
random:prandom_u32  [Tracepoint  event]

cd /opt/ltp

echo 0 | tee /proc/sys/kernel/kptr_restrict /proc/sys/kernel/perf_event_paranoid

/home/dileks/bin/perf record -a -g -e random:prandom_u32 ./runltp -f
net.features -s tcp_fastopen
/home/dileks/bin/perf report --no-children --stdio > ./perf-report.txt
/home/dileks/bin/perf script > ./perf-script.txt

echo 1 | tee /proc/sys/kernel/kptr_restrict /proc/sys/kernel/perf_event_paranoid

[ /PERF-SESSION ]

For a "comparison" (?) I attached two perf-reports - the newer one
includes Willy's latest patchset.

- Sedat -

[1] https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/prandom.git/log/?h=20200820-siphash-noise
[2] https://github.com/linux-test-project/ltp/tree/master/runtest

[-- Attachment #2: perf-report-2020-08-19.txt --]
[-- Type: text/plain, Size: 21043 bytes --]

# To display the perf.data header info, please use --header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 120K of event 'random:prandom_u32'
# Event count (approx.): 120473
#
# Overhead  Command          Shared Object      Symbol         
# ........  ...............  .................  ...............
#
    59.67%  netstress        [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--33.21%--tcp_v4_connect
               |          __inet_stream_connect
               |          |          
               |          |--22.14%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          __noinstr_text_start
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --11.07%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     __noinstr_text_start
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--16.61%--tcp_v6_connect
               |          __inet_stream_connect
               |          |          
               |          |--11.07%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          __noinstr_text_start
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --5.54%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     __noinstr_text_start
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--6.64%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--3.35%--tcp_v4_do_rcv
               |          |          tcp_v4_rcv
               |          |          ip_protocol_deliver_rcu
               |          |          ip_local_deliver
               |          |          ip_rcv
               |          |          __netif_receive_skb
               |          |          process_backlog
               |          |          napi_poll
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          |          
               |          |          |--2.05%--__irq_exit_rcu
               |          |          |          |          
               |          |          |           --2.04%--sysvec_apic_timer_interrupt
               |          |          |                     asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |           --1.30%--do_softirq
               |          |                     __local_bh_enable_ip
               |          |                     |          
               |          |                      --1.27%--ip_finish_output2
               |          |                                ip_output
               |          |                                __ip_queue_xmit
               |          |                                __tcp_transmit_skb
               |          |                                |          
               |          |                                 --1.20%--tcp_write_xmit
               |          |                                           |          
               |          |                                            --1.02%--__tcp_push_pending_frames
               |          |                                                      tcp_sendmsg_locked
               |          |                                                      tcp_sendmsg
               |          |                                                      |          
               |          |                                                       --0.63%--__sys_sendto
               |          |                                                                 __x64_sys_sendto
               |          |                                                                 __noinstr_text_start
               |          |                                                                 entry_SYSCALL_64_after_hwframe
               |          |          
               |           --3.29%--tcp_v6_do_rcv
               |                     tcp_v6_rcv
               |                     ip6_protocol_deliver_rcu
               |                     ip6_input
               |                     ipv6_rcv
               |                     __netif_receive_skb
               |                     process_backlog
               |                     napi_poll
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     |          
               |                     |--2.02%--__irq_exit_rcu
               |                     |          sysvec_apic_timer_interrupt
               |                     |          asm_sysvec_apic_timer_interrupt
               |                     |          
               |                      --1.28%--do_softirq
               |                                __local_bh_enable_ip
               |                                |          
               |                                 --1.23%--ip6_finish_output2
               |                                           ip6_output
               |                                           ip6_xmit
               |                                           inet6_csk_xmit
               |                                           __tcp_transmit_skb
               |                                           |          
               |                                            --1.14%--tcp_write_xmit
               |                                                      |          
               |                                                       --0.98%--__tcp_push_pending_frames
               |                                                                 tcp_sendmsg_locked
               |                                                                 tcp_sendmsg
               |                                                                 |          
               |                                                                  --0.60%--__sys_sendto
               |                                                                            __x64_sys_sendto
               |                                                                            __noinstr_text_start
               |                                                                            entry_SYSCALL_64_after_hwframe
               |          
                --3.19%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                           --2.70%--tcp_try_fastopen
                                     tcp_conn_request
                                     tcp_rcv_state_process
                                     tcp_v4_do_rcv
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver
                                     ip_rcv
                                     __netif_receive_skb
                                     process_backlog
                                     napi_poll
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack
                                     |          
                                     |--1.71%--__irq_exit_rcu
                                     |          |          
                                     |           --1.70%--sysvec_apic_timer_interrupt
                                     |                     asm_sysvec_apic_timer_interrupt
                                     |          
                                      --0.99%--do_softirq
                                                __local_bh_enable_ip
                                                |          
                                                 --0.97%--ip_finish_output2
                                                           ip_output
                                                           __ip_queue_xmit
                                                           __tcp_transmit_skb
                                                           |          
                                                            --0.92%--tcp_write_xmit
                                                                      |          
                                                                       --0.78%--__tcp_push_pending_frames
                                                                                 tcp_sendmsg_locked
                                                                                 tcp_sendmsg

    36.09%  swapper          [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--23.84%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--11.94%--tcp_v6_do_rcv
               |          |          tcp_v6_rcv
               |          |          ip6_protocol_deliver_rcu
               |          |          ip6_input
               |          |          ipv6_rcv
               |          |          __netif_receive_skb
               |          |          process_backlog
               |          |          napi_poll
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          __irq_exit_rcu
               |          |          sysvec_apic_timer_interrupt
               |          |          asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |          |--10.49%--cpuidle_enter_state
               |          |          |          cpuidle_enter
               |          |          |          do_idle
               |          |          |          cpu_startup_entry
               |          |          |          |          
               |          |          |          |--7.92%--secondary_startup_64
               |          |          |          |          
               |          |          |           --2.57%--start_kernel
               |          |          |                     secondary_startup_64
               |          |          |          
               |          |           --0.92%--poll_idle
               |          |                     cpuidle_enter_state
               |          |                     cpuidle_enter
               |          |                     do_idle
               |          |                     cpu_startup_entry
               |          |                     |          
               |          |                      --0.68%--secondary_startup_64
               |          |          
               |           --11.90%--tcp_v4_do_rcv
               |                     tcp_v4_rcv
               |                     ip_protocol_deliver_rcu
               |                     ip_local_deliver
               |                     ip_rcv
               |                     __netif_receive_skb
               |                     process_backlog
               |                     napi_poll
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     __irq_exit_rcu
               |                     sysvec_apic_timer_interrupt
               |                     asm_sysvec_apic_timer_interrupt
               |                     |          
               |                     |--10.61%--cpuidle_enter_state
               |                     |          cpuidle_enter
               |                     |          do_idle
               |                     |          cpu_startup_entry
               |                     |          |          
               |                     |          |--7.92%--secondary_startup_64
               |                     |          |          
               |                     |           --2.69%--start_kernel
               |                     |                     secondary_startup_64
               |                     |          
               |                      --0.78%--poll_idle
               |                                cpuidle_enter_state
               |                                cpuidle_enter
               |                                do_idle
               |                                cpu_startup_entry
               |                                |          
               |                                 --0.60%--secondary_startup_64
               |          
                --12.23%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                          |--7.45%--tcp_try_fastopen
                          |          tcp_conn_request
                          |          tcp_rcv_state_process
                          |          tcp_v4_do_rcv
                          |          tcp_v4_rcv
                          |          ip_protocol_deliver_rcu
                          |          ip_local_deliver
                          |          ip_rcv
                          |          __netif_receive_skb
                          |          process_backlog
                          |          napi_poll
                          |          net_rx_action
                          |          __softirqentry_text_start
                          |          asm_call_on_stack
                          |          do_softirq_own_stack
                          |          __irq_exit_rcu
                          |          sysvec_apic_timer_interrupt
                          |          asm_sysvec_apic_timer_interrupt
                          |          |          
                          |           --6.62%--cpuidle_enter_state
                          |                     cpuidle_enter
                          |                     do_idle
                          |                     cpu_startup_entry
                          |                     |          
                          |                     |--4.85%--secondary_startup_64
                          |                     |          
                          |                      --1.77%--start_kernel
                          |                                secondary_startup_64
                          |          
                           --4.78%--tcp_check_req
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver
                                     ip_rcv
                                     __netif_receive_skb
                                     process_backlog
                                     napi_poll
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack
                                     __irq_exit_rcu
                                     sysvec_apic_timer_interrupt
                                     asm_sysvec_apic_timer_interrupt
                                     |          
                                      --4.53%--cpuidle_enter_state
                                                cpuidle_enter
                                                do_idle
                                                cpu_startup_entry
                                                |          
                                                |--3.48%--secondary_startup_64
                                                |          
                                                 --1.05%--start_kernel
                                                           secondary_startup_64

     0.92%  ksoftirqd/3      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.59%--tcp_conn_request
                          tcp_rcv_state_process

     0.90%  ksoftirqd/1      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.62%--tcp_conn_request
                          tcp_rcv_state_process

     0.84%  ksoftirqd/0      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.56%--tcp_conn_request
                          tcp_rcv_state_process

     0.77%  ksoftirqd/2      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.51%--tcp_conn_request
                          tcp_rcv_state_process

     0.17%  kworker/3:7-eve  [kernel.kallsyms]  [k] prandom_u32
     0.15%  kworker/1:2-eve  [kernel.kallsyms]  [k] prandom_u32
     0.14%  kworker/2:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.13%  kworker/0:5-eve  [kernel.kallsyms]  [k] prandom_u32
     0.07%  Xorg             [kernel.kallsyms]  [k] prandom_u32
     0.04%  avahi-daemon     [kernel.kallsyms]  [k] prandom_u32
     0.04%  ip               [kernel.kallsyms]  [k] prandom_u32
     0.02%  perf             [kernel.kallsyms]  [k] prandom_u32
     0.01%  rcu_sched        [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/u16:2-i  [kernel.kallsyms]  [k] prandom_u32
     0.00%  ltp-pan          [kernel.kallsyms]  [k] prandom_u32
     0.00%  awk              [kernel.kallsyms]  [k] prandom_u32
     0.00%  mktemp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  mysqld           [kernel.kallsyms]  [k] prandom_u32
     0.00%  systemd-journal  [kernel.kallsyms]  [k] prandom_u32
     0.00%  NetworkManager   [kernel.kallsyms]  [k] prandom_u32
     0.00%  QDBusConnection  [kernel.kallsyms]  [k] prandom_u32
     0.00%  gdbus            [kernel.kallsyms]  [k] prandom_u32
     0.00%  jbd2/sdc2-8      [kernel.kallsyms]  [k] prandom_u32
     0.00%  kded5            [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/2:2-eve  [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/3:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.00%  runltp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  tcp_fastopen_ru  [kernel.kallsyms]  [k] prandom_u32
     0.00%  gnome-software   [kernel.kallsyms]  [k] prandom_u32
     0.00%  irq/35-iwlwifi   [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/u16:1-p  [kernel.kallsyms]  [k] prandom_u32
     0.00%  org_kde_powerde  [kernel.kallsyms]  [k] prandom_u32
     0.00%  pool-org.gnome.  [kernel.kallsyms]  [k] prandom_u32
     0.00%  tst_net_iface_p  [kernel.kallsyms]  [k] prandom_u32
     0.00%  upowerd          [kernel.kallsyms]  [k] prandom_u32
     0.00%  xdg-desktop-por  [kernel.kallsyms]  [k] prandom_u32


# Samples: 0  of event 'dummy:HG'
# Event count (approx.): 0
#
# Overhead  Command  Shared Object  Symbol
# ........  .......  .............  ......
#


#
# (Tip: Customize output of perf script with: perf script -F event,ip,sym)
#

[-- Attachment #3: perf-report-2020-08-20.txt --]
[-- Type: text/plain, Size: 21103 bytes --]

# To display the perf.data header info, please use --header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 120K of event 'random:prandom_u32'
# Event count (approx.): 120542
#
# Overhead  Command          Shared Object      Symbol         
# ........  ...............  .................  ...............
#
    59.66%  netstress        [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--33.20%--tcp_v4_connect
               |          __inet_stream_connect
               |          |          
               |          |--22.13%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          __noinstr_text_start
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --11.07%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     __noinstr_text_start
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--16.60%--tcp_v6_connect
               |          __inet_stream_connect
               |          |          
               |          |--11.07%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          __noinstr_text_start
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --5.53%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     __noinstr_text_start
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--6.69%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--3.41%--tcp_v6_do_rcv
               |          |          tcp_v6_rcv
               |          |          ip6_protocol_deliver_rcu
               |          |          ip6_input
               |          |          ipv6_rcv
               |          |          __netif_receive_skb
               |          |          process_backlog
               |          |          napi_poll
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          |          
               |          |          |--2.15%--__irq_exit_rcu
               |          |          |          sysvec_apic_timer_interrupt
               |          |          |          asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |           --1.26%--do_softirq
               |          |                     __local_bh_enable_ip
               |          |                     |          
               |          |                      --1.22%--ip6_finish_output2
               |          |                                ip6_output
               |          |                                ip6_xmit
               |          |                                inet6_csk_xmit
               |          |                                __tcp_transmit_skb
               |          |                                |          
               |          |                                 --1.13%--tcp_write_xmit
               |          |                                           |          
               |          |                                            --0.99%--__tcp_push_pending_frames
               |          |                                                      tcp_sendmsg_locked
               |          |                                                      tcp_sendmsg
               |          |                                                      |          
               |          |                                                       --0.56%--__sys_sendto
               |          |                                                                 __x64_sys_sendto
               |          |                                                                 __noinstr_text_start
               |          |                                                                 entry_SYSCALL_64_after_hwframe
               |          |          
               |           --3.27%--tcp_v4_do_rcv
               |                     tcp_v4_rcv
               |                     ip_protocol_deliver_rcu
               |                     ip_local_deliver
               |                     ip_rcv
               |                     __netif_receive_skb
               |                     process_backlog
               |                     napi_poll
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     |          
               |                     |--1.94%--__irq_exit_rcu
               |                     |          sysvec_apic_timer_interrupt
               |                     |          asm_sysvec_apic_timer_interrupt
               |                     |          
               |                      --1.33%--do_softirq
               |                                __local_bh_enable_ip
               |                                |          
               |                                 --1.29%--ip_finish_output2
               |                                           ip_output
               |                                           __ip_queue_xmit
               |                                           __tcp_transmit_skb
               |                                           |          
               |                                            --1.21%--tcp_write_xmit
               |                                                      |          
               |                                                       --1.02%--__tcp_push_pending_frames
               |                                                                 tcp_sendmsg_locked
               |                                                                 tcp_sendmsg
               |                                                                 |          
               |                                                                  --0.67%--__sys_sendto
               |                                                                            __x64_sys_sendto
               |                                                                            __noinstr_text_start
               |                                                                            entry_SYSCALL_64_after_hwframe
               |          
                --3.16%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                           --2.68%--tcp_try_fastopen
                                     tcp_conn_request
                                     tcp_rcv_state_process
                                     tcp_v4_do_rcv
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver
                                     ip_rcv
                                     __netif_receive_skb
                                     process_backlog
                                     napi_poll
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack
                                     |          
                                     |--1.62%--__irq_exit_rcu
                                     |          sysvec_apic_timer_interrupt
                                     |          asm_sysvec_apic_timer_interrupt
                                     |          
                                      --1.07%--do_softirq
                                                __local_bh_enable_ip
                                                |          
                                                 --1.03%--ip_finish_output2
                                                           ip_output
                                                           __ip_queue_xmit
                                                           __tcp_transmit_skb
                                                           |          
                                                            --0.98%--tcp_write_xmit
                                                                      |          
                                                                       --0.82%--__tcp_push_pending_frames
                                                                                 tcp_sendmsg_locked
                                                                                 tcp_sendmsg
                                                                                 |          
                                                                                  --0.53%--__sys_sendto
                                                                                            __x64_sys_sendto
                                                                                            __noinstr_text_start
                                                                                            entry_SYSCALL_64_after_hwframe

    36.30%  swapper          [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--23.99%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--12.11%--tcp_v4_do_rcv
               |          |          tcp_v4_rcv
               |          |          ip_protocol_deliver_rcu
               |          |          ip_local_deliver
               |          |          ip_rcv
               |          |          __netif_receive_skb
               |          |          process_backlog
               |          |          napi_poll
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          __irq_exit_rcu
               |          |          sysvec_apic_timer_interrupt
               |          |          asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |          |--10.79%--cpuidle_enter_state
               |          |          |          cpuidle_enter
               |          |          |          do_idle
               |          |          |          cpu_startup_entry
               |          |          |          |          
               |          |          |          |--8.20%--secondary_startup_64
               |          |          |          |          
               |          |          |           --2.59%--start_kernel
               |          |          |                     secondary_startup_64
               |          |          |          
               |          |           --0.80%--poll_idle
               |          |                     cpuidle_enter_state
               |          |                     cpuidle_enter
               |          |                     do_idle
               |          |                     cpu_startup_entry
               |          |                     |          
               |          |                      --0.62%--secondary_startup_64
               |          |          
               |           --11.88%--tcp_v6_do_rcv
               |                     tcp_v6_rcv
               |                     ip6_protocol_deliver_rcu
               |                     ip6_input
               |                     ipv6_rcv
               |                     __netif_receive_skb
               |                     process_backlog
               |                     napi_poll
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     __irq_exit_rcu
               |                     sysvec_apic_timer_interrupt
               |                     asm_sysvec_apic_timer_interrupt
               |                     |          
               |                     |--10.46%--cpuidle_enter_state
               |                     |          cpuidle_enter
               |                     |          do_idle
               |                     |          cpu_startup_entry
               |                     |          |          
               |                     |          |--7.92%--secondary_startup_64
               |                     |          |          
               |                     |           --2.55%--start_kernel
               |                     |                     secondary_startup_64
               |                     |          
               |                      --0.89%--poll_idle
               |                                cpuidle_enter_state
               |                                cpuidle_enter
               |                                do_idle
               |                                cpu_startup_entry
               |                                |          
               |                                 --0.69%--secondary_startup_64
               |          
                --12.30%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                          |--7.52%--tcp_try_fastopen
                          |          tcp_conn_request
                          |          tcp_rcv_state_process
                          |          tcp_v4_do_rcv
                          |          tcp_v4_rcv
                          |          ip_protocol_deliver_rcu
                          |          ip_local_deliver
                          |          ip_rcv
                          |          __netif_receive_skb
                          |          process_backlog
                          |          napi_poll
                          |          net_rx_action
                          |          __softirqentry_text_start
                          |          asm_call_on_stack
                          |          do_softirq_own_stack
                          |          __irq_exit_rcu
                          |          sysvec_apic_timer_interrupt
                          |          asm_sysvec_apic_timer_interrupt
                          |          |          
                          |           --6.67%--cpuidle_enter_state
                          |                     cpuidle_enter
                          |                     do_idle
                          |                     cpu_startup_entry
                          |                     |          
                          |                     |--4.94%--secondary_startup_64
                          |                     |          
                          |                      --1.73%--start_kernel
                          |                                secondary_startup_64
                          |          
                           --4.79%--tcp_check_req
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver
                                     ip_rcv
                                     __netif_receive_skb
                                     process_backlog
                                     napi_poll
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack
                                     __irq_exit_rcu
                                     sysvec_apic_timer_interrupt
                                     asm_sysvec_apic_timer_interrupt
                                     |          
                                      --4.52%--cpuidle_enter_state
                                                cpuidle_enter
                                                do_idle
                                                cpu_startup_entry
                                                |          
                                                |--3.59%--secondary_startup_64
                                                |          
                                                 --0.93%--start_kernel
                                                           secondary_startup_64

     0.89%  ksoftirqd/3      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.58%--tcp_conn_request
                          tcp_rcv_state_process

     0.87%  ksoftirqd/1      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.58%--tcp_conn_request
                          tcp_rcv_state_process

     0.76%  ksoftirqd/0      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
                --0.52%--tcp_conn_request
                          tcp_rcv_state_process

     0.71%  ksoftirqd/2      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32

     0.16%  kworker/3:3-eve  [kernel.kallsyms]  [k] prandom_u32
     0.14%  kworker/1:2-eve  [kernel.kallsyms]  [k] prandom_u32
     0.12%  Xorg             [kernel.kallsyms]  [k] prandom_u32
     0.12%  kworker/0:5-eve  [kernel.kallsyms]  [k] prandom_u32
     0.11%  kworker/2:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.03%  avahi-daemon     [kernel.kallsyms]  [k] prandom_u32
     0.03%  ip               [kernel.kallsyms]  [k] prandom_u32
     0.03%  systemd-udevd    [kernel.kallsyms]  [k] prandom_u32
     0.02%  perf             [kernel.kallsyms]  [k] prandom_u32
     0.01%  rcu_sched        [kernel.kallsyms]  [k] prandom_u32
     0.00%  ltp-pan          [kernel.kallsyms]  [k] prandom_u32
     0.00%  NetworkManager   [kernel.kallsyms]  [k] prandom_u32
     0.00%  irq/35-iwlwifi   [kernel.kallsyms]  [k] prandom_u32
     0.00%  mktemp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  mysqld           [kernel.kallsyms]  [k] prandom_u32
     0.00%  tcp_fastopen_ru  [kernel.kallsyms]  [k] prandom_u32
     0.00%  DiscoverNotifie  [kernel.kallsyms]  [k] prandom_u32
     0.00%  QSGRenderThread  [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/1:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.00%  migration/3      [kernel.kallsyms]  [k] prandom_u32
     0.00%  ns_create        [kernel.kallsyms]  [k] prandom_u32
     0.00%  ns_ifmove        [kernel.kallsyms]  [k] prandom_u32
     0.00%  runltp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  QXcbEventQueue   [kernel.kallsyms]  [k] prandom_u32
     0.00%  Thread (pooled)  [kernel.kallsyms]  [k] prandom_u32
     0.00%  akonadi_followu  [kernel.kallsyms]  [k] prandom_u32
     0.00%  gnome-software   [kernel.kallsyms]  [k] prandom_u32
     0.00%  ln               [kernel.kallsyms]  [k] prandom_u32
     0.00%  mkdir            [kernel.kallsyms]  [k] prandom_u32


# Samples: 0  of event 'dummy:HG'
# Event count (approx.): 0
#
# Overhead  Command  Shared Object  Symbol
# ........  .......  .............  ......
#


#
# (Tip: Generate a script for your data: perf script -g <lang>)
#

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Thu, Aug 20, 2020 at 08:58:38AM +0200, Willy Tarreau wrote:
> I've just pushed a new branch "20200820-siphash-noise" that I also
> rebased onto latest master. It's currently running make allmodconfig
> here, so that will take a while, but I think it's OK as random32.o is
> already OK. I've also addressed a strange build issue caused by having
> an array instead of 4 ints in siprand_state.
> 
> Please just let me know if that's OK for you now.

At least it worked for me now (built with no errors on x86_64):

$ time make -j 8 bzImage modules
(...)
real    65m7.986s
user    477m22.477s
sys     38m0.545s
$ find . -name '*.ko' |wc -l
7983

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Thu, Aug 20, 2020 at 08:08:43AM +0200, Willy Tarreau wrote:
> On Thu, Aug 20, 2020 at 06:42:23AM +0200, Sedat Dilek wrote:
> > On Thu, Aug 20, 2020 at 6:33 AM Willy Tarreau <w@1wt.eu> wrote:
> > >
> > > On Thu, Aug 20, 2020 at 05:05:49AM +0200, Sedat Dilek wrote:
> > > > We have the same defines for K0 and K1 in include/linux/prandom.h and
> > > > lib/random32.c?
> > > > More room for simplifications?
> > >
> > > Definitely, I'm not surprized at all. As I said, the purpose was to
> > > discuss around the proposal, not much more. If we think it's the way
> > > to go, some major lifting is required. I just don't want to invest
> > > significant time on this if nobody cares.
> > >
> > 
> > OK.
> > 
> > Right now, I will try with the attached diff.
> 
> No, don't waste your time this way, it's not the right way to address it,
> you're still facing competition between defines. I'll do another one if
> you want to go further in the tests.

I've just pushed a new branch "20200820-siphash-noise" that I also
rebased onto latest master. It's currently running make allmodconfig
here, so that will take a while, but I think it's OK as random32.o is
already OK. I've also addressed a strange build issue caused by having
an array instead of 4 ints in siprand_state.

Please just let me know if that's OK for you now.

Thanks,
Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Thu, Aug 20, 2020 at 06:42:23AM +0200, Sedat Dilek wrote:
> On Thu, Aug 20, 2020 at 6:33 AM Willy Tarreau <w@1wt.eu> wrote:
> >
> > On Thu, Aug 20, 2020 at 05:05:49AM +0200, Sedat Dilek wrote:
> > > We have the same defines for K0 and K1 in include/linux/prandom.h and
> > > lib/random32.c?
> > > More room for simplifications?
> >
> > Definitely, I'm not surprized at all. As I said, the purpose was to
> > discuss around the proposal, not much more. If we think it's the way
> > to go, some major lifting is required. I just don't want to invest
> > significant time on this if nobody cares.
> >
> 
> OK.
> 
> Right now, I will try with the attached diff.

No, don't waste your time this way, it's not the right way to address it,
you're still facing competition between defines. I'll do another one if
you want to go further in the tests.

> Unclear to me where this modpost "net_rand_noise" undefined! comes from.
> Any hints?

Sure, the symbol is not exported. I'll address it as well for you.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Thu, Aug 20, 2020 at 6:33 AM Willy Tarreau <w@1wt.eu> wrote:
>
> On Thu, Aug 20, 2020 at 05:05:49AM +0200, Sedat Dilek wrote:
> > We have the same defines for K0 and K1 in include/linux/prandom.h and
> > lib/random32.c?
> > More room for simplifications?
>
> Definitely, I'm not surprized at all. As I said, the purpose was to
> discuss around the proposal, not much more. If we think it's the way
> to go, some major lifting is required. I just don't want to invest
> significant time on this if nobody cares.
>

OK.

Right now, I will try with the attached diff.

Unclear to me where this modpost "net_rand_noise" undefined! comes from.
Any hints?

- Sedat -

[ prandom-siphash-noise-wtarreau-20200816-dileks.diff ]

diff --git a/drivers/staging/rtl8188eu/include/rtw_security.h
b/drivers/staging/rtl8188eu/include/rtw_security.h
index 8ba02a7cea60..5cbb6fec71cd 100644
--- a/drivers/staging/rtl8188eu/include/rtw_security.h
+++ b/drivers/staging/rtl8188eu/include/rtw_security.h
@@ -221,6 +221,9 @@ do {
                         \
 #define ROL32(A, n)    (((A) << (n)) | (((A) >> (32 - (n)))  & ((1UL
<< (n)) - 1)))
 #define ROR32(A, n)    ROL32((A), 32 - (n))

+// XXX: Workaround: Undef defines from <include/linux/prandom.h>
+#undef K0
+#undef K1
 struct mic_data {
        u32  K0, K1;         /*  Key */
        u32  L, R;           /*  Current state */
diff --git a/drivers/staging/rtl8712/rtl871x_security.h
b/drivers/staging/rtl8712/rtl871x_security.h
index b2dda16cbd0a..d4ffb31d9d14 100644
--- a/drivers/staging/rtl8712/rtl871x_security.h
+++ b/drivers/staging/rtl8712/rtl871x_security.h
@@ -188,6 +188,9 @@ do {\
 #define ROL32(A, n) (((A) << (n)) | (((A)>>(32-(n)))  & ((1UL << (n)) - 1)))
 #define ROR32(A, n) ROL32((A), 32 - (n))

+// XXX: Workaround: Undef defines from <include/linux/prandom.h>
+#undef K0
+#undef K1
 struct mic_data {
        u32  K0, K1;         /* Key */
        u32  L, R;           /* Current state */
diff --git a/drivers/staging/rtl8723bs/include/rtw_security.h
b/drivers/staging/rtl8723bs/include/rtw_security.h
index 514c0799c34b..260ca9f29a35 100644
--- a/drivers/staging/rtl8723bs/include/rtw_security.h
+++ b/drivers/staging/rtl8723bs/include/rtw_security.h
@@ -271,6 +271,9 @@ do {\
 #define ROL32(A, n)    (((A) << (n)) | (((A)>>(32-(n)))  & ((1UL << (n)) - 1)))
 #define ROR32(A, n)    ROL32((A), 32-(n))

+// XXX: Workaround: Undef defines from <include/linux/prandom.h>
+#undef K0
+#undef K1
 struct mic_data {
        u32  K0, K1;         /*  Key */
        u32  L, R;           /*  Current state */
diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index 95d73b01d8c5..efebcff3c93d 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -32,6 +32,11 @@ DECLARE_PER_CPU(unsigned long, net_rand_noise);
        v1 ^= v0, v0 = rol64(v0, 32),  v3 ^= v2,                     \
        v0 += v3, v3 = rol64(v3, 21),  v2 += v1, v1 = rol64(v1, 17), \
        v3 ^= v0,                      v1 ^= v2, v2 = rol64(v2, 32)  )
+#define SIPROUND(v0,v1,v2,v3) ( \
+       v0 += v1, v1 = rol64(v1, 13),  v2 += v3, v3 = rol64(v3, 16), \
+       v1 ^= v0, v0 = rol64(v0, 32),  v3 ^= v2,                     \
+       v0 += v3, v3 = rol64(v3, 21),  v2 += v1, v1 = rol64(v1, 17), \
+       v3 ^= v0,                      v1 ^= v2, v2 = rol64(v2, 32)  )
 #define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
 #define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )

@@ -46,6 +51,11 @@ DECLARE_PER_CPU(unsigned long, net_rand_noise);
        v1 ^= v0, v0 = rol32(v0, 16),  v3 ^= v2,                     \
        v0 += v3, v3 = rol32(v3,  7),  v2 += v1, v1 = rol32(v1, 13), \
        v3 ^= v0,                      v1 ^= v2, v2 = rol32(v2, 16)  )
+#define SIPROUND(v0,v1,v2,v3) ( \
+       v0 += v1, v1 = rol32(v1,  5),  v2 += v3, v3 = rol32(v3,  8), \
+       v1 ^= v0, v0 = rol32(v0, 16),  v3 ^= v2,                     \
+       v0 += v3, v3 = rol32(v3,  7),  v2 += v1, v1 = rol32(v1, 13), \
+       v3 ^= v0,                      v1 ^= v2, v2 = rol32(v2, 16)  )
 #define K0 0x6c796765
 #define K1 0x74656462

diff --git a/lib/random32.c b/lib/random32.c
index 93f0cd3a67ee..f24c7a0febf0 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -323,37 +323,6 @@ struct siprand_state {
 static DEFINE_PER_CPU(struct siprand_state, net_rand_state) __latent_entropy;
 DEFINE_PER_CPU(unsigned long, net_rand_noise);

-#if BITS_PER_LONG == 64
-/*
- * The core SipHash round function.  Each line can be executed in
- * parallel given enough CPU resources.
- */
-#define SIPROUND(v0,v1,v2,v3) ( \
-       v0 += v1, v1 = rol64(v1, 13),  v2 += v3, v3 = rol64(v3, 16), \
-       v1 ^= v0, v0 = rol64(v0, 32),  v3 ^= v2,                     \
-       v0 += v3, v3 = rol64(v3, 21),  v2 += v1, v1 = rol64(v1, 17), \
-       v3 ^= v0,                      v1 ^= v2, v2 = rol64(v2, 32)  )
-#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
-#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
-
-#elif BITS_PER_LONG == 32
-/*
- * On 32-bit machines, we use HSipHash, a reduced-width version of SipHash.
- * This is weaker, but 32-bit machines are not used for high-traffic
- * applications, so there is less output for an attacker to analyze.
- */
-#define SIPROUND(v0,v1,v2,v3) ( \
-       v0 += v1, v1 = rol32(v1,  5),  v2 += v3, v3 = rol32(v3,  8), \
-       v1 ^= v0, v0 = rol32(v0, 16),  v3 ^= v2,                     \
-       v0 += v3, v3 = rol32(v3,  7),  v2 += v1, v1 = rol32(v1, 13), \
-       v3 ^= v0,                      v1 ^= v2, v2 = rol32(v2, 16)  )
-#define K0 0x6c796765
-#define K1 0x74656462
-
-#else
-#error Unsupported BITS_PER_LONG
-#endif
-
 /*
  * This is the core CPRNG function.  As "pseudorandom", this is not used
  * for truly valuable things, just intended to be a PITA to guess.

- EOF -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Thu, Aug 20, 2020 at 05:05:49AM +0200, Sedat Dilek wrote:
> We have the same defines for K0 and K1 in include/linux/prandom.h and
> lib/random32.c?
> More room for simplifications?

Definitely, I'm not surprized at all. As I said, the purpose was to
discuss around the proposal, not much more. If we think it's the way
to go, some major lifting is required. I just don't want to invest
significant time on this if nobody cares.

Thanks!
Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Sun, Aug 16, 2020 at 6:48 PM Sedat Dilek <sedat.dilek@gmail.com> wrote:
>
> On Sun, Aug 16, 2020 at 5:01 PM Willy Tarreau <w@1wt.eu> wrote:
> >
> > Hi,
> >
> > so as I mentioned, I could run several test on our lab with variations
> > around the various proposals and come to quite positive conclusions.
> >
> > Synthetic observations: the connection rate and the SYN cookie rate do not
> > seem to be affected the same way by the prandom changes. One explanation
> > is that the connection rates are less stable across reboots. Another
> > possible explanation is that the larger state update is more sensitive
> > to cache misses that increase when calling userland. I noticed that the
> > compiler didn't inline siprand_u32() for me, resulting in one extra
> > function call and noticeable register clobbering that mostly vanish
> > once siprand_u32() is inlined, getting back to the original performance.
> >
> > The noise generation was placed as discussed in the xmit calls, however
> > the extra function call and state update had a negative effect on
> > performance and the noise function alone appeared for up to 0.23% of the
> > CPU usage. Simplifying the mix of data by keeping only one long for
> > the noise and using one siphash round on 4 input words to keep only
> > the last word allowed to use very few instructions and to inline them,
> > making the noise collection imperceptible in microbenchmarks. The noise
> > is now collected this way (I verified that all inputs are used), this
> > performs 3 xor, 2 add and 2 rol, which is way sufficient and already
> > better than my initial attempt with a bare add :
> >
> >   static inline
> >   void prandom_u32_add_noise(unsigned long a, unsigned long b,
> >                              unsigned long c, unsigned long d)
> >   {
> >         /*
> >          * This is not used cryptographically; it's just
> >          * a convenient 4-word hash function. (3 xor, 2 add, 2 rol)
> >          */
> >         a ^= __this_cpu_read(net_rand_noise);
> >         PRND_SIPROUND(a, b, c, d);
> >         __this_cpu_write(net_rand_noise, d);
> >   }
> >
> > My tests were run on a 6-core 12-thread Core i7-8700k equipped with a 40G
> > NIC (i40e). I've mainly run two types of tests:
> >
> >   - connections per second: the machine runs a server which accepts and
> >     closes incoming connections. The load generators aim at it and the
> >     connection rate is measured once it's stabilized.
> >
> >   - SYN cookie rate: the load generators flood the machine with enough
> >     SYNs to saturate the CPU and the rate of response SYN-ACK is measured.
> >
> > Both correspond to real world use cases (DDoS protection against SYN flood
> > and connection flood).
> >
> > The base kernel was fc80c51f + Eric's patch to add a tracepoint in
> > prandom_u32(). Another test was made by adding George's changes to use
> > siphash. Then another test was made with the siprand_u32() function
> > inlined and with noise stored as a full siphash state. Then one test
> > was run with the noise reduced to a single long. And a final test was
> > run with the noise function inlined.
> >
> >           connections    SYN cookies   Notes
> >           per second     emitted/s
> >
> >   base:     556k          5.38M
> >
> >   siphash:  535k          5.33M
> >
> >   siphash inlined
> >   +noise:   548k          5.40M    add_noise=0.23%
> >
> >   siphash + single-word
> >    noise    555k          5.45M    add_noise=0.10%
> >
> >   siphash + single-word&inlined
> >    noise    559k          5.38M
> >
> > Actually the last one is better than the previous one because it also
> > swallows more packets. There were 10.9M pps in and 5.38M pps out versus
> > 10.77M in and 5.45M out for the previous one. I didn't report the incoming
> > traffic for the other ones as it was mostly irrelevant and always within
> > these bounds.
> >
> > Finally I've added Eric's patch to reuse the skb hash when known in
> > tcp_conn_request(), and was happy to see the SYN cookies reach 5.45 Mpps
> > again and the connection rate remain unaffected. A perf record during
> > the SYN flood showed almost no call to prandom_u32() anymore (just a few
> > in tcp_rtx_synack()) so this looks like a desirable optimization.
> >
> > At the moment the code is ugly, in experimental state (I've pushed all of
> > it at https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/prandom.git/).
> >
> > My impression on this is that given that it's possible to maintain the
> > same level of performance as we currently have while making the PRNG much
> > better, there's no more reason for not doing it.
> >
> > If there's enough interest at this point, I'm OK with restarting from
> > George's patches and doing the adjustments there. There's still this
> > prandom_seed() which looks very close to prandom_reseed() and that we
> > might possibly better remerge, but I'd vote for not changing everything
> > at once, it's ugly enough already. Also I suspect we can have an infinite
> > loop in prandom_seed() if entropy is 0 and the state is zero as well.
> > We'd be unlucky but I'd just make sure entropy is not all zeroes. And
> > running tests on 32-bit would be desirable as well.
> >
> > Finally one can wonder whether it makes sense to keep Tausworthe for
> > other cases (basic statistical sampling) or drop it. We could definitely
> > drop it and simplify everything given that we now have the same level of
> > performance. But if we do it, what should we do with the test patterns ?
> > I personally don't think that testing a PRNG against a known sequence
> > brings any value by definition, and that the more random we make it the
> > less relevant this is.
> >
>
> Hi Willy,
>
> Thanks for the new patchset and offering it via public available Git.
>
> Thanks for the numbers.
>
> As said I tested here against Linux v5.8.1 - with your previous patchset.
>
> I cannot promise I will test the new one.
>
> First, I have to see how things work with Linux v5.9-rc1 - which will
> hopefully be released within a few hours.
> My primary focus is to make it work with my GNU and LLVM toolchains.
>

I had some time to play with your new patchset.

I tried on top of Linux v5.9-rc1.

Unfortunately, some drivers from the staging area needed to be
disabled due to build failures.

I changed from kernel-modules to disabled:

scripts/config -d RTL8723BS
scripts/config -d R8712U
scripts/config -d R8188EU

See below for the error and [
drivers/staging/rtl8723bs/include/rtw_security.h ] and git grep for
#define K0 | #define K1.

Then I saw some modpost errors:

mkdir -p ./arch/x86_64/boot
ln -fsn ../../x86/boot/bzImage ./arch/x86_64/boot/bzImage
ERROR: modpost: "net_rand_noise" [drivers/scsi/fcoe/libfcoe.ko] undefined!
ERROR: modpost: "net_rand_noise" [lib/test_bpf.ko] undefined!
make[4]: *** [scripts/Makefile.modpost:111: Module.symvers] Error 1
make[4]: *** Deleting file 'Module.symvers'

Where I changed from kernel-modules to disabled:

scripts/config -d TEST_BPF
scripts/config -d LIBFCOE

- Sedat -

[ CONFIG_R8188EU=m and CONFIG_88EU_AP_MODE=y ]

$ grep "Error 1" build-log_5.9.0-rc1-5-amd64-llvm11-ias.txt
make[6]: *** [scripts/Makefile.build:283:
drivers/staging/rtl8188eu/core/rtw_ap.o] Error 1

[ CONFIG_RTL8723BS=m ]

In file included from drivers/staging/rtl8723bs/core/rtw_btcoex.c:7:
In file included from ./drivers/staging/rtl8723bs/include/drv_types.h:42:
./drivers/staging/rtl8723bs/include/rtw_security.h:275:7: error:
expected member name or ';' after declaration specifiers
        u32  K0, K1;         /*  Key */
        ~~~  ^
./include/linux/prandom.h:35:13: note: expanded from macro 'K0'
#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
            ^
In file included from drivers/staging/rtl8723bs/core/rtw_btcoex.c:7:
In file included from ./drivers/staging/rtl8723bs/include/drv_types.h:42:
./drivers/staging/rtl8723bs/include/rtw_security.h:275:7: error: expected ')'
./include/linux/prandom.h:35:13: note: expanded from macro 'K0'
#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
            ^
./drivers/staging/rtl8723bs/include/rtw_security.h:275:7: note: to
match this '('
./include/linux/prandom.h:35:12: note: expanded from macro 'K0'
#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
           ^
In file included from drivers/staging/rtl8723bs/core/rtw_btcoex.c:7:
In file included from ./drivers/staging/rtl8723bs/include/drv_types.h:42:
./drivers/staging/rtl8723bs/include/rtw_security.h:275:11: error:
expected member name or ';' after declaration specifiers
        u32  K0, K1;         /*  Key */
        ~~~      ^
./include/linux/prandom.h:36:13: note: expanded from macro 'K1'
#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
            ^
In file included from drivers/staging/rtl8723bs/core/rtw_btcoex.c:7:
In file included from ./drivers/staging/rtl8723bs/include/drv_types.h:42:
./drivers/staging/rtl8723bs/include/rtw_security.h:275:11: error: expected ')'
./include/linux/prandom.h:36:13: note: expanded from macro 'K1'
#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
            ^
./drivers/staging/rtl8723bs/include/rtw_security.h:275:11: note: to
match this '('
./include/linux/prandom.h:36:12: note: expanded from macro 'K1'
#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
           ^
4 errors generated.
make[6]: *** [scripts/Makefile.build:283:
drivers/staging/rtl8723bs/core/rtw_btcoex.o] Error 1

[ drivers/staging/rtl8723bs/include/rtw_security.h ]

struct mic_data {
    u32  K0, K1;         /*  Key */
    u32  L, R;           /*  Current state */
    u32  M;              /*  Message accumulator (single word) */
    u32     nBytesInM;      /*  # bytes in M */
}

$ git grep -E 'K0 |K1 ' drivers/staging/ | grep -i key
drivers/staging/rtl8188eu/core/rtw_security.c:  pmicdata->K0 =
secmicgetuint32(key);
drivers/staging/rtl8188eu/core/rtw_security.c:  pmicdata->K1 =
secmicgetuint32(key + 4);
drivers/staging/rtl8712/rtl871x_security.c:     pmicdata->K0 =
secmicgetuint32(key);
drivers/staging/rtl8712/rtl871x_security.c:     pmicdata->K1 =
secmicgetuint32(key + 4);
drivers/staging/rtl8723bs/core/rtw_security.c:  pmicdata->K0 =
secmicgetuint32(key);
drivers/staging/rtl8723bs/core/rtw_security.c:  pmicdata->K1 =
secmicgetuint32(key + 4);

$ git grep -E '\#define K0 |\#define K1 '
arch/arm/crypto/sha1-armv7-neon.S:#define K1  0x5A827999
arch/x86/crypto/sha1_avx2_x86_64_asm.S:#define K1 0x5a827999
crypto/rmd128.c:#define K1  RMD_K1
crypto/rmd160.c:#define K1  RMD_K1
crypto/rmd256.c:#define K1  RMD_K1
crypto/rmd320.c:#define K1  RMD_K1
fs/ext4/hash.c:#define K1 0
include/linux/prandom.h:#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
include/linux/prandom.h:#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
include/linux/prandom.h:#define K0 0x6c796765
include/linux/prandom.h:#define K1 0x74656462
lib/random32.c:#define K0 (0x736f6d6570736575 ^ 0x6c7967656e657261 )
lib/random32.c:#define K1 (0x646f72616e646f6d ^ 0x7465646279746573 )
lib/random32.c:#define K0 0x6c796765
lib/random32.c:#define K1 0x74656462

We have the same defines for K0 and K1 in include/linux/prandom.h and
lib/random32.c?
More room for simplifications?

- EOT -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Sun, Aug 16, 2020 at 5:01 PM Willy Tarreau <w@1wt.eu> wrote:
>
> Hi,
>
> so as I mentioned, I could run several test on our lab with variations
> around the various proposals and come to quite positive conclusions.
>
> Synthetic observations: the connection rate and the SYN cookie rate do not
> seem to be affected the same way by the prandom changes. One explanation
> is that the connection rates are less stable across reboots. Another
> possible explanation is that the larger state update is more sensitive
> to cache misses that increase when calling userland. I noticed that the
> compiler didn't inline siprand_u32() for me, resulting in one extra
> function call and noticeable register clobbering that mostly vanish
> once siprand_u32() is inlined, getting back to the original performance.
>
> The noise generation was placed as discussed in the xmit calls, however
> the extra function call and state update had a negative effect on
> performance and the noise function alone appeared for up to 0.23% of the
> CPU usage. Simplifying the mix of data by keeping only one long for
> the noise and using one siphash round on 4 input words to keep only
> the last word allowed to use very few instructions and to inline them,
> making the noise collection imperceptible in microbenchmarks. The noise
> is now collected this way (I verified that all inputs are used), this
> performs 3 xor, 2 add and 2 rol, which is way sufficient and already
> better than my initial attempt with a bare add :
>
>   static inline
>   void prandom_u32_add_noise(unsigned long a, unsigned long b,
>                              unsigned long c, unsigned long d)
>   {
>         /*
>          * This is not used cryptographically; it's just
>          * a convenient 4-word hash function. (3 xor, 2 add, 2 rol)
>          */
>         a ^= __this_cpu_read(net_rand_noise);
>         PRND_SIPROUND(a, b, c, d);
>         __this_cpu_write(net_rand_noise, d);
>   }
>
> My tests were run on a 6-core 12-thread Core i7-8700k equipped with a 40G
> NIC (i40e). I've mainly run two types of tests:
>
>   - connections per second: the machine runs a server which accepts and
>     closes incoming connections. The load generators aim at it and the
>     connection rate is measured once it's stabilized.
>
>   - SYN cookie rate: the load generators flood the machine with enough
>     SYNs to saturate the CPU and the rate of response SYN-ACK is measured.
>
> Both correspond to real world use cases (DDoS protection against SYN flood
> and connection flood).
>
> The base kernel was fc80c51f + Eric's patch to add a tracepoint in
> prandom_u32(). Another test was made by adding George's changes to use
> siphash. Then another test was made with the siprand_u32() function
> inlined and with noise stored as a full siphash state. Then one test
> was run with the noise reduced to a single long. And a final test was
> run with the noise function inlined.
>
>           connections    SYN cookies   Notes
>           per second     emitted/s
>
>   base:     556k          5.38M
>
>   siphash:  535k          5.33M
>
>   siphash inlined
>   +noise:   548k          5.40M    add_noise=0.23%
>
>   siphash + single-word
>    noise    555k          5.45M    add_noise=0.10%
>
>   siphash + single-word&inlined
>    noise    559k          5.38M
>
> Actually the last one is better than the previous one because it also
> swallows more packets. There were 10.9M pps in and 5.38M pps out versus
> 10.77M in and 5.45M out for the previous one. I didn't report the incoming
> traffic for the other ones as it was mostly irrelevant and always within
> these bounds.
>
> Finally I've added Eric's patch to reuse the skb hash when known in
> tcp_conn_request(), and was happy to see the SYN cookies reach 5.45 Mpps
> again and the connection rate remain unaffected. A perf record during
> the SYN flood showed almost no call to prandom_u32() anymore (just a few
> in tcp_rtx_synack()) so this looks like a desirable optimization.
>
> At the moment the code is ugly, in experimental state (I've pushed all of
> it at https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/prandom.git/).
>
> My impression on this is that given that it's possible to maintain the
> same level of performance as we currently have while making the PRNG much
> better, there's no more reason for not doing it.
>
> If there's enough interest at this point, I'm OK with restarting from
> George's patches and doing the adjustments there. There's still this
> prandom_seed() which looks very close to prandom_reseed() and that we
> might possibly better remerge, but I'd vote for not changing everything
> at once, it's ugly enough already. Also I suspect we can have an infinite
> loop in prandom_seed() if entropy is 0 and the state is zero as well.
> We'd be unlucky but I'd just make sure entropy is not all zeroes. And
> running tests on 32-bit would be desirable as well.
>
> Finally one can wonder whether it makes sense to keep Tausworthe for
> other cases (basic statistical sampling) or drop it. We could definitely
> drop it and simplify everything given that we now have the same level of
> performance. But if we do it, what should we do with the test patterns ?
> I personally don't think that testing a PRNG against a known sequence
> brings any value by definition, and that the more random we make it the
> less relevant this is.
>

Hi Willy,

Thanks for the new patchset and offering it via public available Git.

Thanks for the numbers.

As said I tested here against Linux v5.8.1 - with your previous patchset.

I cannot promise I will test the new one.

First, I have to see how things work with Linux v5.9-rc1 - which will
hopefully be released within a few hours.
My primary focus is to make it work with my GNU and LLVM toolchains.

Regards,
- Sedat -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

Hi,

so as I mentioned, I could run several test on our lab with variations
around the various proposals and come to quite positive conclusions.

Synthetic observations: the connection rate and the SYN cookie rate do not
seem to be affected the same way by the prandom changes. One explanation
is that the connection rates are less stable across reboots. Another
possible explanation is that the larger state update is more sensitive
to cache misses that increase when calling userland. I noticed that the
compiler didn't inline siprand_u32() for me, resulting in one extra
function call and noticeable register clobbering that mostly vanish
once siprand_u32() is inlined, getting back to the original performance.

The noise generation was placed as discussed in the xmit calls, however
the extra function call and state update had a negative effect on
performance and the noise function alone appeared for up to 0.23% of the
CPU usage. Simplifying the mix of data by keeping only one long for
the noise and using one siphash round on 4 input words to keep only
the last word allowed to use very few instructions and to inline them,
making the noise collection imperceptible in microbenchmarks. The noise
is now collected this way (I verified that all inputs are used), this
performs 3 xor, 2 add and 2 rol, which is way sufficient and already
better than my initial attempt with a bare add :

  static inline
  void prandom_u32_add_noise(unsigned long a, unsigned long b,
                             unsigned long c, unsigned long d)
  { 
	/*
	 * This is not used cryptographically; it's just
	 * a convenient 4-word hash function. (3 xor, 2 add, 2 rol)
	 */
	a ^= __this_cpu_read(net_rand_noise);
	PRND_SIPROUND(a, b, c, d);
	__this_cpu_write(net_rand_noise, d);
  }

My tests were run on a 6-core 12-thread Core i7-8700k equipped with a 40G
NIC (i40e). I've mainly run two types of tests:

  - connections per second: the machine runs a server which accepts and
    closes incoming connections. The load generators aim at it and the
    connection rate is measured once it's stabilized.

  - SYN cookie rate: the load generators flood the machine with enough
    SYNs to saturate the CPU and the rate of response SYN-ACK is measured.

Both correspond to real world use cases (DDoS protection against SYN flood
and connection flood).

The base kernel was fc80c51f + Eric's patch to add a tracepoint in
prandom_u32(). Another test was made by adding George's changes to use
siphash. Then another test was made with the siprand_u32() function
inlined and with noise stored as a full siphash state. Then one test
was run with the noise reduced to a single long. And a final test was
run with the noise function inlined.

          connections    SYN cookies   Notes
          per second     emitted/s
  
  base:     556k          5.38M
  
  siphash:  535k          5.33M
  
  siphash inlined
  +noise:   548k          5.40M    add_noise=0.23%
  
  siphash + single-word
   noise    555k          5.45M    add_noise=0.10%
  
  siphash + single-word&inlined
   noise    559k          5.38M

Actually the last one is better than the previous one because it also
swallows more packets. There were 10.9M pps in and 5.38M pps out versus
10.77M in and 5.45M out for the previous one. I didn't report the incoming
traffic for the other ones as it was mostly irrelevant and always within
these bounds.

Finally I've added Eric's patch to reuse the skb hash when known in
tcp_conn_request(), and was happy to see the SYN cookies reach 5.45 Mpps
again and the connection rate remain unaffected. A perf record during
the SYN flood showed almost no call to prandom_u32() anymore (just a few
in tcp_rtx_synack()) so this looks like a desirable optimization.

At the moment the code is ugly, in experimental state (I've pushed all of
it at https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/prandom.git/).

My impression on this is that given that it's possible to maintain the
same level of performance as we currently have while making the PRNG much
better, there's no more reason for not doing it.

If there's enough interest at this point, I'm OK with restarting from
George's patches and doing the adjustments there. There's still this
prandom_seed() which looks very close to prandom_reseed() and that we
might possibly better remerge, but I'd vote for not changing everything
at once, it's ugly enough already. Also I suspect we can have an infinite
loop in prandom_seed() if entropy is 0 and the state is zero as well.
We'd be unlucky but I'd just make sure entropy is not all zeroes. And
running tests on 32-bit would be desirable as well.

Finally one can wonder whether it makes sense to keep Tausworthe for
other cases (basic statistical sampling) or drop it. We could definitely
drop it and simplify everything given that we now have the same level of
performance. But if we do it, what should we do with the test patterns ?
I personally don't think that testing a PRNG against a known sequence
brings any value by definition, and that the more random we make it the
less relevant this is.

Thanks,
Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Fri, Aug 14, 2020 at 6:05 PM Willy Tarreau <w@1wt.eu> wrote:
>
> On Fri, Aug 14, 2020 at 05:32:32PM +0200, Sedat Dilek wrote:
> > commit 94c7eb54c4b8e81618ec79f414fe1ca5767f9720
> > "random32: add a tracepoint for prandom_u32()"
> >
> > ...I gave Willy's patches a try and used the Linux Test Project (LTP)
> > for testing.
>
> Just FWIW today I could run several relevant tests with a 40 Gbps NIC
> at high connection rates and under SYN flood to stress SYN cookies.
> I couldn't post earlier due to a net outage but will post the results
> here. In short, what I'm seeing is very good. The only thing is that
> the noise collection as-is with the 4 longs takes a bit too much CPU
> (0.2% measured) but if keeping only one word we're back to tausworthe
> performance, while using siphash all along.
>
> The noise generation function is so small that we're wasting cycles
> calling it and renaming registers. I'll run one more test by inlining
> it and exporting the noise.
>
> So provided quite some cleanup now, I really think we're about to
> reach a solution which will satisfy everyone. More on this after I
> extract the results.
>

Great news!

Will you publish your new version in [1]?

- Sedat -

[1] https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Fri, Aug 14, 2020 at 05:32:32PM +0200, Sedat Dilek wrote:
> commit 94c7eb54c4b8e81618ec79f414fe1ca5767f9720
> "random32: add a tracepoint for prandom_u32()"
> 
> ...I gave Willy's patches a try and used the Linux Test Project (LTP)
> for testing.

Just FWIW today I could run several relevant tests with a 40 Gbps NIC
at high connection rates and under SYN flood to stress SYN cookies.
I couldn't post earlier due to a net outage but will post the results
here. In short, what I'm seeing is very good. The only thing is that
the noise collection as-is with the 4 longs takes a bit too much CPU
(0.2% measured) but if keeping only one word we're back to tausworthe
performance, while using siphash all along.

The noise generation function is so small that we're wasting cycles
calling it and renaming registers. I'll run one more test by inlining
it and exporting the noise.

So provided quite some cleanup now, I really think we're about to
reach a solution which will satisfy everyone. More on this after I
extract the results.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

[-- Attachment #1: Type: text/plain, Size: 2163 bytes --]

On Thu, Aug 13, 2020 at 10:06 AM Willy Tarreau <w@1wt.eu> wrote:
>
> On Thu, Aug 13, 2020 at 09:53:11AM +0200, Sedat Dilek wrote:
> > On Wed, Aug 12, 2020 at 5:21 AM Willy Tarreau <w@1wt.eu> wrote:
> > >
> > > On Tue, Aug 11, 2020 at 12:51:43PM +0200, Sedat Dilek wrote:
> > > > Can you share this "rebased to mainline" version of George's patch?
> > >
> > > You can pick it from there if that helps, but keep in mind that
> > > it's just experimental code that we use to explain our ideas and
> > > that we really don't care a single second what kernel it's applied
> > > to:
> > >
> > >    https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/log/?h=20200811-prandom-1
> > >
> >
> > Thanks Willy.
> >
> > I disagree: the base for testing should be clear(ly communicated).
>
> It is. As you can see on the log above, this was applied on top of
> fc80c51fd4b2, there's nothing special here. In addition we're not even
> talking about testing nor calling for testers, just trying to find a
> reasonable solution. Maybe today I'll be able to re-run a few tests by
> the way.
>
> > There are two diffs from Eric to #1: add a trace event for
> > prandom_u32() and #2: a removal of prandom_u32() call in
> > tcp_conn_request().
> > In case you have not seen.
>
> I've seen, just not had the time to test yet.
>

Now with Eric' patch (see [1]) in mainline...

commit 94c7eb54c4b8e81618ec79f414fe1ca5767f9720
"random32: add a tracepoint for prandom_u32()"

...I gave Willy's patches a try and used the Linux Test Project (LTP)
for testing.

[ PERF SESSION #2 ]

Link: https://github.com/linux-test-project/ltp/blob/master/doc/mini-howto-building-ltp-from-git.txt

cd /opt/ltp

/home/dileks/bin/perf record -a -g -e random:prandom_u32 ./runltp -f
net.features -s tcp_fastopen

/home/dileks/bin/perf report --no-children --stdio > ./perf-report.txt
/home/dileks/bin/perf script > ./perf-script.txt

du -h perf*
34M     perf.data
20K     perf-report.txt
134M    perf-script.txt

Note: For a first test I used net.features::tcp_fastopen.

Attached is my perf-report.txt.

- Sedat -

[1] https://git.kernel.org/linus/94c7eb54c4b8e81618ec79f414fe1ca5767f9720

[-- Attachment #2: perf-report.txt --]
[-- Type: text/plain, Size: 20177 bytes --]

# To display the perf.data header info, please use --header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 120K of event 'random:prandom_u32'
# Event count (approx.): 120452
#
# Overhead  Command          Shared Object      Symbol         
# ........  ...............  .................  ...............
#
    58.22%  netstress        [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--33.22%--tcp_v4_connect
               |          __inet_stream_connect
               |          |          
               |          |--22.15%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          do_syscall_64
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --11.07%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     sock_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     do_syscall_64
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--16.61%--tcp_v6_connect
               |          __inet_stream_connect
               |          |          
               |          |--11.07%--inet_stream_connect
               |          |          __sys_connect
               |          |          __x64_sys_connect
               |          |          do_syscall_64
               |          |          entry_SYSCALL_64_after_hwframe
               |          |          __libc_connect
               |          |          0x65736e7500632e73
               |          |          
               |           --5.54%--tcp_sendmsg_locked
               |                     tcp_sendmsg
               |                     sock_sendmsg
               |                     __sys_sendto
               |                     __x64_sys_sendto
               |                     do_syscall_64
               |                     entry_SYSCALL_64_after_hwframe
               |                     __libc_sendto
               |          
               |--5.24%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--3.26%--tcp_v4_do_rcv
               |          |          tcp_v4_rcv
               |          |          ip_protocol_deliver_rcu
               |          |          ip_local_deliver_finish
               |          |          __netif_receive_skb_one_core
               |          |          process_backlog
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          |          
               |          |          |--2.03%--irq_exit_rcu
               |          |          |          sysvec_apic_timer_interrupt
               |          |          |          asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |           --1.23%--do_softirq
               |          |                     __local_bh_enable_ip
               |          |                     |          
               |          |                      --1.19%--ip_finish_output2
               |          |                                __ip_queue_xmit
               |          |                                __tcp_transmit_skb
               |          |                                |          
               |          |                                 --1.13%--tcp_write_xmit
               |          |                                           __tcp_push_pending_frames
               |          |                                           |          
               |          |                                            --0.95%--tcp_sendmsg_locked
               |          |                                                      tcp_sendmsg
               |          |                                                      sock_sendmsg
               |          |                                                      |          
               |          |                                                       --0.59%--__sys_sendto
               |          |                                                                 __x64_sys_sendto
               |          |                                                                 do_syscall_64
               |          |                                                                 entry_SYSCALL_64_after_hwframe
               |          |          
               |           --1.99%--tcp_v6_do_rcv
               |                     tcp_v6_rcv
               |                     ip6_protocol_deliver_rcu
               |                     ip6_input
               |                     __netif_receive_skb_one_core
               |                     process_backlog
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     |          
               |                     |--1.27%--irq_exit_rcu
               |                     |          sysvec_apic_timer_interrupt
               |                     |          asm_sysvec_apic_timer_interrupt
               |                     |          
               |                      --0.71%--do_softirq
               |                                __local_bh_enable_ip
               |                                |          
               |                                 --0.68%--ip6_finish_output2
               |                                           ip6_xmit
               |                                           inet6_csk_xmit
               |                                           __tcp_transmit_skb
               |                                           |          
               |                                            --0.62%--tcp_write_xmit
               |                                                      __tcp_push_pending_frames
               |                                                      |          
               |                                                       --0.53%--tcp_sendmsg_locked
               |                                                                 tcp_sendmsg
               |                                                                 sock_sendmsg
               |          
                --3.13%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                          |--2.61%--tcp_try_fastopen
                          |          tcp_conn_request
                          |          tcp_rcv_state_process
                          |          tcp_v4_do_rcv
                          |          tcp_v4_rcv
                          |          ip_protocol_deliver_rcu
                          |          ip_local_deliver_finish
                          |          __netif_receive_skb_one_core
                          |          process_backlog
                          |          net_rx_action
                          |          __softirqentry_text_start
                          |          asm_call_on_stack
                          |          do_softirq_own_stack
                          |          |          
                          |          |--1.66%--irq_exit_rcu
                          |          |          sysvec_apic_timer_interrupt
                          |          |          asm_sysvec_apic_timer_interrupt
                          |          |          
                          |           --0.95%--do_softirq
                          |                     __local_bh_enable_ip
                          |                     |          
                          |                      --0.92%--ip_finish_output2
                          |                                __ip_queue_xmit
                          |                                __tcp_transmit_skb
                          |                                |          
                          |                                 --0.87%--tcp_write_xmit
                          |                                           __tcp_push_pending_frames
                          |                                           |          
                          |                                            --0.72%--tcp_sendmsg_locked
                          |                                                      tcp_sendmsg
                          |                                                      sock_sendmsg
                          |          
                           --0.52%--tcp_check_req
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver_finish
                                     __netif_receive_skb_one_core
                                     process_backlog
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack

    37.93%  swapper          [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |          
               |--25.55%--tcp_conn_request
               |          tcp_rcv_state_process
               |          |          
               |          |--13.54%--tcp_v6_do_rcv
               |          |          tcp_v6_rcv
               |          |          ip6_protocol_deliver_rcu
               |          |          ip6_input
               |          |          __netif_receive_skb_one_core
               |          |          process_backlog
               |          |          net_rx_action
               |          |          __softirqentry_text_start
               |          |          asm_call_on_stack
               |          |          do_softirq_own_stack
               |          |          irq_exit_rcu
               |          |          sysvec_apic_timer_interrupt
               |          |          asm_sysvec_apic_timer_interrupt
               |          |          |          
               |          |          |--12.41%--cpuidle_enter_state
               |          |          |          cpuidle_enter
               |          |          |          do_idle
               |          |          |          cpu_startup_entry
               |          |          |          |          
               |          |          |          |--9.59%--start_secondary
               |          |          |          |          secondary_startup_64
               |          |          |          |          
               |          |          |           --2.82%--start_kernel
               |          |          |                     secondary_startup_64
               |          |          |          
               |          |           --0.68%--poll_idle
               |          |                     cpuidle_enter_state
               |          |                     cpuidle_enter
               |          |                     do_idle
               |          |                     cpu_startup_entry
               |          |                     |          
               |          |                      --0.52%--start_secondary
               |          |                                secondary_startup_64
               |          |          
               |           --12.02%--tcp_v4_do_rcv
               |                     tcp_v4_rcv
               |                     ip_protocol_deliver_rcu
               |                     ip_local_deliver_finish
               |                     __netif_receive_skb_one_core
               |                     process_backlog
               |                     net_rx_action
               |                     __softirqentry_text_start
               |                     asm_call_on_stack
               |                     do_softirq_own_stack
               |                     irq_exit_rcu
               |                     sysvec_apic_timer_interrupt
               |                     asm_sysvec_apic_timer_interrupt
               |                     |          
               |                     |--10.71%--cpuidle_enter_state
               |                     |          cpuidle_enter
               |                     |          do_idle
               |                     |          cpu_startup_entry
               |                     |          |          
               |                     |          |--8.21%--start_secondary
               |                     |          |          secondary_startup_64
               |                     |          |          
               |                     |           --2.50%--start_kernel
               |                     |                     secondary_startup_64
               |                     |          
               |                      --0.77%--poll_idle
               |                                cpuidle_enter_state
               |                                cpuidle_enter
               |                                do_idle
               |                                cpu_startup_entry
               |                                |          
               |                                 --0.60%--start_secondary
               |                                           secondary_startup_64
               |          
                --12.36%--tcp_v4_syn_recv_sock
                          tcp_v6_syn_recv_sock
                          |          
                          |--7.54%--tcp_try_fastopen
                          |          tcp_conn_request
                          |          tcp_rcv_state_process
                          |          tcp_v4_do_rcv
                          |          tcp_v4_rcv
                          |          ip_protocol_deliver_rcu
                          |          ip_local_deliver_finish
                          |          __netif_receive_skb_one_core
                          |          process_backlog
                          |          net_rx_action
                          |          __softirqentry_text_start
                          |          asm_call_on_stack
                          |          do_softirq_own_stack
                          |          irq_exit_rcu
                          |          sysvec_apic_timer_interrupt
                          |          asm_sysvec_apic_timer_interrupt
                          |          |          
                          |           --6.76%--cpuidle_enter_state
                          |                     cpuidle_enter
                          |                     do_idle
                          |                     cpu_startup_entry
                          |                     |          
                          |                     |--5.11%--start_secondary
                          |                     |          secondary_startup_64
                          |                     |          
                          |                      --1.65%--start_kernel
                          |                                secondary_startup_64
                          |          
                           --4.82%--tcp_check_req
                                     tcp_v4_rcv
                                     ip_protocol_deliver_rcu
                                     ip_local_deliver_finish
                                     __netif_receive_skb_one_core
                                     process_backlog
                                     net_rx_action
                                     __softirqentry_text_start
                                     asm_call_on_stack
                                     do_softirq_own_stack
                                     irq_exit_rcu
                                     sysvec_apic_timer_interrupt
                                     asm_sysvec_apic_timer_interrupt
                                     |          
                                      --4.59%--cpuidle_enter_state
                                                cpuidle_enter
                                                do_idle
                                                cpu_startup_entry
                                                |          
                                                |--3.63%--start_secondary
                                                |          secondary_startup_64
                                                |          
                                                 --0.95%--start_kernel
                                                           secondary_startup_64

     0.78%  ksoftirqd/1      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32

     0.76%  ksoftirqd/0      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32

     0.76%  ksoftirqd/3      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32

     0.71%  ksoftirqd/2      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32

     0.20%  kworker/3:3-eve  [kernel.kallsyms]  [k] prandom_u32
     0.17%  kworker/1:1-eve  [kernel.kallsyms]  [k] prandom_u32
     0.15%  kworker/2:2-eve  [kernel.kallsyms]  [k] prandom_u32
     0.12%  kworker/0:7-eve  [kernel.kallsyms]  [k] prandom_u32
     0.06%  Xorg             [kernel.kallsyms]  [k] prandom_u32
     0.04%  ip               [kernel.kallsyms]  [k] prandom_u32
     0.03%  avahi-daemon     [kernel.kallsyms]  [k] prandom_u32
     0.02%  perf             [kernel.kallsyms]  [k] prandom_u32
     0.01%  mysqld           [kernel.kallsyms]  [k] prandom_u32
     0.01%  tcp_fastopen_ru  [kernel.kallsyms]  [k] prandom_u32
     0.00%  irq/35-iwlwifi   [kernel.kallsyms]  [k] prandom_u32
     0.00%  rcu_sched        [kernel.kallsyms]  [k] prandom_u32
     0.00%  dbus-daemon      [kernel.kallsyms]  [k] prandom_u32
     0.00%  ltp-pan          [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/u16:3-i  [kernel.kallsyms]  [k] prandom_u32
     0.00%  mktemp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  QSGRenderThread  [kernel.kallsyms]  [k] prandom_u32
     0.00%  gdbus            [kernel.kallsyms]  [k] prandom_u32
     0.00%  jbd2/sdc2-8      [kernel.kallsyms]  [k] prandom_u32
     0.00%  kded5            [kernel.kallsyms]  [k] prandom_u32
     0.00%  konsole          [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/1:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.00%  kworker/2:0-eve  [kernel.kallsyms]  [k] prandom_u32
     0.00%  runltp           [kernel.kallsyms]  [k] prandom_u32
     0.00%  systemd-journal  [kernel.kallsyms]  [k] prandom_u32
     0.00%  xdg-desktop-por  [kernel.kallsyms]  [k] prandom_u32
     0.00%  sh               [kernel.kallsyms]  [k] prandom_u32


# Samples: 0  of event 'dummy:HG'
# Event count (approx.): 0
#
# Overhead  Command  Shared Object  Symbol
# ........  .......  .............  ......
#


#
# (Tip: To show assembler sample contexts use perf record -b / perf script -F +brstackinsn --xed)
#

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Thu, Aug 13, 2020 at 4:00 PM Eric Dumazet <edumazet@google.com> wrote:
>
> On Thu, Aug 13, 2020 at 1:27 AM Sedat Dilek <sedat.dilek@gmail.com> wrote:
> >
> > I run a perf session looks like this in my KDE/Plasma desktop-environment:
> >
> > [ PERF SESSION ]
> >
> >  1016  2020-08-13 09:57:24 echo 1 > /proc/sys/kernel/sched_schedstats
> >  1017  2020-08-13 09:57:24 echo prandom_u32 >>
> > /sys/kernel/debug/tracing/set_event
> >  1018  2020-08-13 09:57:24 echo traceon >
> > /sys/kernel/debug/tracing/events/random/prandom_u32/trigger
> >  1019  2020-08-13 09:57:25 echo 1 > /sys/kernel/debug/tracing/events/enable
> >
> >  1020  2020-08-13 09:57:32 sysctl -n kernel.sched_schedstats
> >  1021  2020-08-13 09:57:32 cat /sys/kernel/debug/tracing/events/enable
> >  1022  2020-08-13 09:57:32 grep prandom_u32 /sys/kernel/debug/tracing/set_event
> >  1023  2020-08-13 09:57:33 cat
> > /sys/kernel/debug/tracing/events/random/prandom_u32/trigger
> >
> > root# /home/dileks/bin/perf record -a -g -e random:prandom_u32 sleep 5
> >
>
> To be clear : This "perf record -a -g -e random:prandom_u32 sleep 5"
> is self sufficient.
>
> You have nothing to do before (as reported in your email), this is
> simply not needed.
>
> I am not sure why you added all this irrelevant stuff, this is distracting.

Initially I followed these Links:

Link: https://www.kernel.org/doc/html/v5.8/trace/events.html
Link: https://www.kernel.org/doc/html/v5.8/trace/events.html#boot-option
Link: http://www.brendangregg.com/perf.html
Link: http://www.brendangregg.com/perf.html#DynamicTracing

You are right, it's not needed to set and check all these variables as
perf says:

root# /home/dileks/bin/perf list | grep prandom_u32
  random:prandom_u32                                 [Tracepoint event]

So these two steps are indeed enough:

root# /home/dileks/bin/perf record -a -g -e random:prandom_u32 sleep 5
root# /home/dileks/bin/perf report --no-children --stdio

Lessons learned.

- Sedat -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Eric Dumazet]

On Thu, Aug 13, 2020 at 1:27 AM Sedat Dilek <sedat.dilek@gmail.com> wrote:
>
> I run a perf session looks like this in my KDE/Plasma desktop-environment:
>
> [ PERF SESSION ]
>
>  1016  2020-08-13 09:57:24 echo 1 > /proc/sys/kernel/sched_schedstats
>  1017  2020-08-13 09:57:24 echo prandom_u32 >>
> /sys/kernel/debug/tracing/set_event
>  1018  2020-08-13 09:57:24 echo traceon >
> /sys/kernel/debug/tracing/events/random/prandom_u32/trigger
>  1019  2020-08-13 09:57:25 echo 1 > /sys/kernel/debug/tracing/events/enable
>
>  1020  2020-08-13 09:57:32 sysctl -n kernel.sched_schedstats
>  1021  2020-08-13 09:57:32 cat /sys/kernel/debug/tracing/events/enable
>  1022  2020-08-13 09:57:32 grep prandom_u32 /sys/kernel/debug/tracing/set_event
>  1023  2020-08-13 09:57:33 cat
> /sys/kernel/debug/tracing/events/random/prandom_u32/trigger
>
> root# /home/dileks/bin/perf record -a -g -e random:prandom_u32 sleep 5
>

To be clear : This "perf record -a -g -e random:prandom_u32 sleep 5"
is self sufficient.

You have nothing to do before (as reported in your email), this is
simply not needed.

I am not sure why you added all this irrelevant stuff, this is distracting.

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

I run a perf session looks like this in my KDE/Plasma desktop-environment:

[ PERF SESSION ]

 1016  2020-08-13 09:57:24 echo 1 > /proc/sys/kernel/sched_schedstats
 1017  2020-08-13 09:57:24 echo prandom_u32 >>
/sys/kernel/debug/tracing/set_event
 1018  2020-08-13 09:57:24 echo traceon >
/sys/kernel/debug/tracing/events/random/prandom_u32/trigger
 1019  2020-08-13 09:57:25 echo 1 > /sys/kernel/debug/tracing/events/enable

 1020  2020-08-13 09:57:32 sysctl -n kernel.sched_schedstats
 1021  2020-08-13 09:57:32 cat /sys/kernel/debug/tracing/events/enable
 1022  2020-08-13 09:57:32 grep prandom_u32 /sys/kernel/debug/tracing/set_event
 1023  2020-08-13 09:57:33 cat
/sys/kernel/debug/tracing/events/random/prandom_u32/trigger

root# /home/dileks/bin/perf record -a -g -e random:prandom_u32 sleep 5

Simple-Test: Press F5 in Firefox in each opened tab (5 tabs in total)

root# /home/dileks/bin/perf report --no-children --stdio > /tmp/perf-report.txt

- Sedat -

[ perf-report.txt ]

# To display the perf.data header info, please use
--header/--header-only options.
#
#
# Total Lost Samples: 0
#
# Samples: 273  of event 'random:prandom_u32'
# Event count (approx.): 273
#
# Overhead  Command          Shared Object      Symbol
# ........  ...............  .................  ...............
#
    27.47%  firefox-esr      [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

    13.19%  DNS Resolver #9  [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               |
               |--5.86%--__ip4_datagram_connect
               |          ip4_datagram_connect
               |          __sys_connect
               |          __x64_sys_connect
               |          do_syscall_64
               |          entry_SYSCALL_64_after_hwframe
               |          |
               |          |--4.40%--__libc_connect
               |          |          0x2c1
               |          |
               |           --1.47%--connect
               |                     PR_GetAddrInfoByName
               |
               |--2.93%--udp_lib_get_port
               |          inet_dgram_connect
               |          __sys_connect
               |          __x64_sys_connect
               |          do_syscall_64
               |          entry_SYSCALL_64_after_hwframe
               |          |
               |          |--2.20%--__libc_connect
               |          |          0x2c1
               |          |
               |           --0.73%--connect
               |                     PR_GetAddrInfoByName
               |
               |--2.20%--__ip_select_ident
               |          __ip_make_skb
               |          ip_make_skb
               |          udp_sendmsg
               |          __sys_sendto
               |          __x64_sys_sendto
               |          do_syscall_64
               |          entry_SYSCALL_64_after_hwframe
               |          __libc_send
               |
                --2.20%--netlink_autobind
                          netlink_bind
                          __sys_bind
                          __x64_sys_bind
                          do_syscall_64
                          entry_SYSCALL_64_after_hwframe
                          bind
                          getaddrinfo
                          PR_GetAddrInfoByName

    12.45%  FS Broker 7060   [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

     8.79%  FS Broker 6334   [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

     8.06%  FS Broker 7161   [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

     8.06%  FS Broker 7195   [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

     7.33%  FS Broker 7126   [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               shmem_mknod
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7a6f6d2e67726f2f

     7.33%  Socket Thread    [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               tcp_v4_connect
               __inet_stream_connect
               inet_stream_connect
               __sys_connect
               __x64_sys_connect
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __libc_connect

     4.40%  Cache2 I/O       [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               __ext4_new_inode
               ext4_create
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x61632e2f736b656c

     1.10%  Xorg             [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               __shmem_file_setup
               create_shmem
               i915_gem_object_create_region
               i915_gem_create_ioctl
               drm_ioctl_kernel
               drm_ioctl
               __se_sys_ioctl
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               ioctl

     0.73%  QSGRenderThread  [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               shmem_get_inode
               __shmem_file_setup
               create_shmem
               i915_gem_object_create_region
               i915_gem_create_ioctl
               drm_ioctl_kernel
               drm_ioctl
               __se_sys_ioctl
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               ioctl

     0.37%  DOM Worker       [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               __ext4_new_inode
               ext4_create
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x6f6d2e2f736b656c

     0.37%  cupsd            [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               __ext4_new_inode
               ext4_create
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x7263736275732f73

     0.37%  mozStorage #8    [kernel.kallsyms]  [k] prandom_u32
            |
            ---prandom_u32
               prandom_u32
               __ext4_new_inode
               ext4_create
               path_openat
               do_filp_open
               do_sys_openat2
               __x64_sys_openat
               do_syscall_64
               entry_SYSCALL_64_after_hwframe
               __open64
               0x6f6d2e2f736b656c



# Samples: 0  of event 'dummy:HG'
# Event count (approx.): 0
#
# Overhead  Command  Shared Object  Symbol
# ........  .......  .............  ......
#


#
# (Tip: Print event counts in CSV format with: perf stat -x,)
#

- EOF -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Thu, Aug 13, 2020 at 10:06 AM Willy Tarreau <w@1wt.eu> wrote:
>
> On Thu, Aug 13, 2020 at 09:53:11AM +0200, Sedat Dilek wrote:
> > On Wed, Aug 12, 2020 at 5:21 AM Willy Tarreau <w@1wt.eu> wrote:
> > >
> > > On Tue, Aug 11, 2020 at 12:51:43PM +0200, Sedat Dilek wrote:
> > > > Can you share this "rebased to mainline" version of George's patch?
> > >
> > > You can pick it from there if that helps, but keep in mind that
> > > it's just experimental code that we use to explain our ideas and
> > > that we really don't care a single second what kernel it's applied
> > > to:
> > >
> > >    https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/log/?h=20200811-prandom-1
> > >
> >
> > Thanks Willy.
> >
> > I disagree: the base for testing should be clear(ly communicated).
>
> It is. As you can see on the log above, this was applied on top of
> fc80c51fd4b2, there's nothing special here. In addition we're not even
> talking about testing nor calling for testers, just trying to find a
> reasonable solution. Maybe today I'll be able to re-run a few tests by
> the way.
>

I agree with publishing in your Git tree it is clear.

> > There are two diffs from Eric to #1: add a trace event for
> > prandom_u32() and #2: a removal of prandom_u32() call in
> > tcp_conn_request().
> > In case you have not seen.
>
> I've seen, just not had the time to test yet.
>

Can you describe and share your test-environment/setup?

The Linux-kernel has kunit tests (I never played with that) - you
happen to know there is a suitable one available?

Maybe the Linux Test Project has some suitable tests?

- Sedat -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Thu, Aug 13, 2020 at 09:53:11AM +0200, Sedat Dilek wrote:
> On Wed, Aug 12, 2020 at 5:21 AM Willy Tarreau <w@1wt.eu> wrote:
> >
> > On Tue, Aug 11, 2020 at 12:51:43PM +0200, Sedat Dilek wrote:
> > > Can you share this "rebased to mainline" version of George's patch?
> >
> > You can pick it from there if that helps, but keep in mind that
> > it's just experimental code that we use to explain our ideas and
> > that we really don't care a single second what kernel it's applied
> > to:
> >
> >    https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/log/?h=20200811-prandom-1
> >
> 
> Thanks Willy.
> 
> I disagree: the base for testing should be clear(ly communicated).

It is. As you can see on the log above, this was applied on top of
fc80c51fd4b2, there's nothing special here. In addition we're not even
talking about testing nor calling for testers, just trying to find a
reasonable solution. Maybe today I'll be able to re-run a few tests by
the way.

> There are two diffs from Eric to #1: add a trace event for
> prandom_u32() and #2: a removal of prandom_u32() call in
> tcp_conn_request().
> In case you have not seen.

I've seen, just not had the time to test yet.

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

On Wed, Aug 12, 2020 at 5:21 AM Willy Tarreau <w@1wt.eu> wrote:
>
> On Tue, Aug 11, 2020 at 12:51:43PM +0200, Sedat Dilek wrote:
> > Can you share this "rebased to mainline" version of George's patch?
>
> You can pick it from there if that helps, but keep in mind that
> it's just experimental code that we use to explain our ideas and
> that we really don't care a single second what kernel it's applied
> to:
>
>    https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/log/?h=20200811-prandom-1
>

Thanks Willy.

I disagree: the base for testing should be clear(ly communicated).

There are two diffs from Eric to #1: add a trace event for
prandom_u32() and #2: a removal of prandom_u32() call in
tcp_conn_request().
In case you have not seen.
The first was helpful for playing with linux-perf.
I have tested both together with [2].

- Sedat -

[1] https://marc.info/?l=linux-netdev&m=159716173516111&w=2
[2] https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/log/?h=random/fast

Note2myself: Enable some useful random/random32 Kconfigs

RANDOM32_SELFTEST n -> y
WARN_ALL_UNSEEDED_RANDOM n -> y

- EOT -

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Willy Tarreau]

On Tue, Aug 11, 2020 at 12:51:43PM +0200, Sedat Dilek wrote:
> Can you share this "rebased to mainline" version of George's patch?

You can pick it from there if that helps, but keep in mind that
it's just experimental code that we use to explain our ideas and
that we really don't care a single second what kernel it's applied
to:

   https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau/cleanups.git/log/?h=20200811-prandom-1

Willy

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

In the previous discussion...

"Flaw in "random32: update the net random state on interrupt and activity"

...someone referred to <luto/linux.git#random/fast>.

Someone tested this?
Feedback?

- Sedat -

[0] https://marc.info/?t=159658903500002&r=1&w=2
[1] https://git.kernel.org/pub/scm/linux/kernel/git/luto/linux.git/log/?h=random/fast

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

[ CC netdev ML ]

Hi Willy,

in [1] you say:

> I've applied it on top of George's patch rebased to mainline for simplicity.
> I've used a separate per_cpu noise variable to keep the net_rand_state static
> with its __latent_entropy.

Can you share this "rebased to mainline" version of George's patch?
Maybe put your work "user-friendly-fetchable" in one of your
<kernel.org> Git tree (see [2])?

Yesterday random/random32/prandom mainline patches hit Linux
v5.8.1-rc1 (see [3]).

So, as I asked in my first email what is a suitable base?
Linux v5.9-rc1 (this Sunday) or if stable Linux v5.8.1 (next 1-2 days)

Thanks.

Regards,
- Sedat -


[1] https://marc.info/?l=linux-netdev&m=159709355528675&w=2
[2] https://git.kernel.org/pub/scm/linux/kernel/git/wtarreau
[3] https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable-rc.git/log/?h=linux-5.8.y

Re: [DRAFT PATCH] random32: make prandom_u32() output unpredictable

[Sedat Dilek]

+ CC:netdev

( Just FYI: Build and boot on bare metal. )

- Sedat -

On Sun, Aug 9, 2020 at 11:01 PM Sedat Dilek <sedat.dilek@gmail.com> wrote:
>
> Hi George,
>
> I have tried your patch on top of Linux v5.8 with...
>
> commit f227e3ec3b5c ("random32: update the net random state on
> interrupt and activity")
>
> ...reverted.
> This was a bit tricky - what was your base?
>
> Applied the typo fix from Randy - will a v2 follow?
>
> Why DRAFT and not RFC?
>
> Please drop the CC:stable - it's a DRAFT.
>
> Other Linux stable like linux-5.7.y include...
>
> commit c0842fbc1b18c7a044e6ff3e8fa78bfa822c7d1a
> random32: move the pseudo-random 32-bit definitions to prandom.h
>
> commit 585524081ecdcde1c719e63916c514866d898217
> random: random.h should include archrandom.h, not the other way around
>
> ...linux-5.8.y stable will follow.
>
> Isn't the move to prandom.h making your patch easier to apply?
>
> In a second build I applied the snippet from Willy.
>
> What do you mean by...?
>
> [ quote ]
> I wonder if, on general principles, it would be better to use a more
> SipHash style mixing in of the sample:
>     m = get_cycles();
>     v3 ^= m;
>     SIPROUND(v0, v1, v2, v3);
>     SIPROUND(v0, v1, v2, v3);
>     v0 ^= m;
>
> Not sure if it's worth the extra register (and associated spill/fill).
> [ /quote ]
>
> Have you a snippet for testing?
>
> Thanks.
>
> Regards,
> - Sedat -