5 ms·

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

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.

mjw1007 5y ago
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".)
- zx2c4 5y ago
  > 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.
  - er4hn 5y ago
    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 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.
CyberRabbi 5y ago
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?
- whatshisface 5y ago
  Imagine running a Linux kernel on a fully deterministic CPU emulator. The jitter would be the same on every boot.
  - mohaine 5y ago
    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.
    - whatshisface 5y ago
      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.
  - tedunangst 5y ago
    Elaborate on the threat, please. Who is running the kernel and who is controlling the cycle perfect emulator?
    - 5y ago
metadat 5y ago
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&query=Jitter%20dance&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... Though this is the first time I recall hearing about it.

mjw1007 5y ago

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

zx2c4 5y ago
> 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.
- er4hn 5y ago
  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 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.

CyberRabbi 5y ago

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?

whatshisface 5y ago
Imagine running a Linux kernel on a fully deterministic CPU emulator. The jitter would be the same on every boot.
- mohaine 5y ago
  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.
  - whatshisface 5y ago
    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.
- tedunangst 5y ago
  Elaborate on the threat, please. Who is running the kernel and who is controlling the cycle perfect emulator?
  - 5y ago

metadat 5y ago

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&query=Jitter%20dance&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... Though this is the first time I recall hearing about it.