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

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.

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.)

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.

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

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

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.

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.

Sounds good to me.

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.)

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.)

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.

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.

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

Based on some quick userland tests, apparently yes.

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

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).

Absolutely, I've even said this myself.

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 <[email protected]>
Date:   Sun Apr 19 17:31:46 2020 +0200

WIP: random32: use siphash with a counter for prandom_u32

index d20ba1b104ca..2a41b21623ae 100644
@@ -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) &&

index 9ab7443bd91b..9e22973b207c 100644
@@ -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

index 026ac01af9da..c9d839c2b179 100644
@@ -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);
 }
 
 /**

index 3d749abb9e80..aa83cade911a 100644
@@ -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);
 	}
 }

siphash is good.

But no:

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.

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

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.)

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

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.

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.

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.

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 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.

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

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)

index 184ea556f50e35141a4be5940c692db41e09f464..fc698a8ea13b1b6a6bd952308d11414eadfa4eaf

100644

@@ -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.

index 32c10a515e2d5438e8d620a0c2313aab5f849b2b..9570a10cb949b5792c4290ba8e82a077ac655069

100644

@@ -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 */

index 3d749abb9e80d54d8e330e07fb8b773b7bec2b83..932345323af092a93fc2690b0ebbf4f7485ae4f3

100644

@@ -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;

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.

Hi Florian,

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.

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).

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

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.

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.

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.

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.

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.

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.

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".

.. 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".

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

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.

Replaces: f227e3ec3b5c ("random32: update the net random state on interrupt and activity")

---
 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.

index 763b920a6206c..2b048e2ea99f6 100644
@@ -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

Hi George,

@@ -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;

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.

	m = get_cycles();
	v3 ^= m;
	SIPROUND(v0, v1, v2, v3);
	SIPROUND(v0, v1, v2, v3);
	v0 ^= m;

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.

Absolutely.

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.

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

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

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

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.

Yeah, test kernels are nervous-making that way.

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

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.

(...)

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).

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.

OK.

Willy

Hi George,

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

index 2b048e2ea99f..a12d63028106 100644
@@ -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;

From: Willy Tarreau

	if (s->count-- <= 0) {
		...
		s->count = 8;
	}

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

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.

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.

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

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

Yep.

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

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

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

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

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

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

---

index d20ba1b104ca..2a41b21623ae 100644
@@ -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) &&

index aa16e6468f91..e2b4990f2126 100644
@@ -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. */

index ae5029f984a8..2f07c569af77 100644
@@ -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);
 }
 
 /**

index 2b048e2ea99f..d74cf1db8cc9 100644
@@ -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;
 }

index 7df6c9617321..55a2471cd75b 100644
@@ -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();
 

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.

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

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

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

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.)

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

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.

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

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

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

+#elif BITS_PER_LONG == 23

s/23/32/ ???

~Randy

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".