Hacker News Reader

Comment by mcpherrinm | Hacker News Reader

The jitter dance mentioned in here is pretty interesting. It doesn't seem obvious to me that a deterministic CPU running a deterministic scheduler is going to yield randomness.

But hopefully any modern system has some kind of hardware RNG and the "jitter dance" is just a last-resort type thing for strange systems.

View on HN

Right, I'm surprised to be reading justifications that amount to "it's been deployed for several years now, so we think it's OK", rather than "here's a report from a researcher who's tested how it behaves on a wide range of systems".

I don't know enough to count myself as a "skeptic", but if I try to apply the test "suppose in ten years time you're reading a news report describing how this feature failed to work as intended; is it easy to imagine the sort of things it could be saying?", the jitter dance doesn't do terribly well.

(I'm imagining something like the case where large numbers of consumer routers ended up generating the same secret on first boot, or perhaps large numbers of virtual machines. And there seem to be lots of ways to imagine a processor that had surprisingly little jitter: maybe an x86 emulator for Arm, or a "Big/Little/Tiny" processor, or "Spectre is really truly absolutely mitigated now we promise".)

> I'm surprised to be reading justifications that amount to "it's been deployed for several years now, so we think it's OK",

I'm not making any claims or justifications about it being good or not. Just a simple statement that Linus put it there, and there it is, and it's been that way for a while. I even referred to it as "voodoo". As I mentioned in the post, 5.18 didn't change anything about entropy sources and gathering. Certainly trying to see more rigorously whether or not the Linus Jitter Dance is defensible would make for a worthwhile research project.

Any comments about how related the Linus Jitter Dance (btw, glad to see that djb isn't the only one making new dance moves..) is to JitterRNG: https://www.chronox.de/jent.html ?

The PDF linked to on the page goes into more detail but that is measured across a number of CPUs and has good performance in both amount and entropy quality produced. You do need to measure it per CPU, but it does comply with SP 800-90B which is what the US Gov considers the standards for randomness.

I haven’t looked into it but from what I’ve read from various sources, not every platform can extract entropy from that process. I took that to mean that the CPUs on which the jitter dance is employed are not entirely “deterministic.” Well of course they are but they must be carrying black box state that affects execution that, so far, is impossible to extract without knowing the full execution trace up to that point.

Can anyone provide a specific explanation for why some of platforms can extract entropy from scheduling jitter and others can’t?

Imagine running a Linux kernel on a fully deterministic CPU emulator. The jitter would be the same on every boot.

Wouldn't disk, memory, network, cache and really anything that could trigger an interrupt also need to be fully deterministic? It seems to me this is really what the jitter dance is measuring to get randomness. It is only reading the cycle counter, all of the above would affect that slightly.

Memory, disk and cache could be deterministic in an emulator. Imagine an emulator for embedded software. Network doesn't come online until booting has reached a certain point and at that time some keys may have already been generated. It is not a showstopper (after all the jitter algorithm did make it in to the actual kernel) but there are cases in which problems would be conceivable.

Elaborate on the threat, please. Who is running the kernel and who is controlling the cycle perfect emulator?

I have an embedded product that generates keys very soon after boot. I run it on an emulator for some reason. Oops, now my keys are fully predictable.

My honest take is that these dumb "but what if I paint myself into a corner" scenarios are why it takes so fucking long for anything to get better.

How would you get a random number on a fully deterministic emulator?

You'd ask the emulator to give you a seed. (This was mentioned in the article, and a way for VMs to do this has been added in this kernel.) You could also refuse to produce any random numbers until you had entropy from some part of the emulator that wasn't deterministic. (Maybe the emulator gives real random numbers for the CPU random instruction, or maybe it lets you connect to a real network.) Since people don't think of cycle counts as something that needs to be nondeterministic for a computer to work, seeding on them makes it possible for people running the program to accidentally run it in a way that breaks the assumptions of the program authors. Note that this is true of many random sources - but the objection was not to including cycle counts, but to emitting random numbers while that was all the driver had collected.

How do you know you got real entropy instead of a replay of an already recorded stream of events?

That's not the threat model (and it can't be a threat model, it's impossible to defend against), the threat model is people accidentally replaying an exact boot (which is more likely than accidentally replaying everything and also failing to seed the VM.)

Probably expose a random device.

Interestingly, it seems the Jitter Dance has previously been discussed on HN quite a bit:

https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...

Though this is the first time I recall hearing about it.

Reply on news.ycombinator.com