4 ms·

Using CPU jitter is a clever solution. I hope it stands up to scrutiny. > but mixing entropy from the hardware with other sources is considered to be safe by m

Using CPU jitter is a clever solution. I hope it stands up to scrutiny. > but mixing entropy from the hardware with other sources is considered to be safe by most, even if the hardware generator is somehow suspect. To be clear, it's a property of bitwise xor that it preserves entropy. If you xor a random bit with 1 you still have a random bit.

devit 7y ago
Assuming they are independent random variables, since e.g. X xor (not X) is constant.
dooglius 7y ago
Well, that's not entirely true, even if two random bits are independent, xor-ing them only gives you one random bit. What actually happens in Linux is that each new input of random bits gets pushed through a cryptographic hash, before being xor'd.
- ChrisSD 7y ago
  From replies it seems my two sentences weren't as clear as I thought. I'll try to refine it: A property of bitwise xoring random variable `x` with a constant (or otherwise non-random but independent) value is that the entropy of `x` is preserved in the result.
  - WAHa_06x36 7y ago
    However, xoring two arbitrary random variables is NOT guaranteed to preserve entropy. Preserving entropy only happens under certain specific conditions.
    - deleted 7y ago
      [deleted]
    - ChrisSD 7y ago
      Under what circumstances would xoring `x` and `y` not produce a result with entropy at least as great as `x`?
      - WAHa_06x36 7y ago
        In the very obvious cases where x == y, or x == not y, or x == y + 1, or many other correlations.
        ChrisSD 7y ago
        Only if y is known to be dependent on x. If y is random but just so happens to be `not x` or `== x` then that won't make the result any less random. 0 is as random a number as 529890873740477 is.
        WAHa_06x36 7y ago
        Single numbers don't really have entropy at all, so that is not something it even makes sense to talk about.
uasm 7y ago
> "Using CPU jitter is a clever solution. I hope it stands up to scrutiny." How safe is it to use CPU jitter in a virtual machine?
- jfindley 7y ago
  Safe as in safe from host interference? Not at all. But if your VM is running on a malicious host, you have bigger problems honestly.
  - stefan_ 7y ago
    This is kind of the ongoing joke here, yeah? Like HN users will gladly spend hours discussing the merits of various random number generation schemes, why that Intel HWRNG is probably backdoored and we should all be very afraid, all the while running their micro-services on the cloud where their entropy is literally spoon-fed from the hypervisor. SMC call into code-you-can't-see and back comes pure entropy (trust us)!
    - pjc50 7y ago
      Yes, although there's two kinds of VM safety people might care about. By using a VM you accept that the bare metal owner can look into it if they want to and you have to trust them not to. However, that doesn't mean accepting attacks from other customers - which was what all the Spectre/Meltdown risk was primarily about.
tptacek 7y ago
CPU jitter randomness is an old idea, and not especially well thought of.
- Diederich 7y ago
  If you have a moment, can you expand on that or provide a link? Especially for the last part. Thanks. This is well outside of my wheelhouse, so please pardon a naive inquiry.
  - toast0 7y ago
    These timing measurements by nature are going to have a small range of possible values --- the size of the range is going to likely be system specific, and for some systems, there may be only a few possible outcomes.
    - clarry 7y ago
      And that's enough. One bit is enough, less than one bit of randomness is enough if you can just repeat the process enough times.
      - toast0 7y ago
        How are we to know how much entropy the process provides our system? The patch in the article counts one bit per timer interrupt, but there may be much less than that. If the tsc clock and the timer clock are linked, and the system is totally blocked on entropy, it seems plausible that the tsc reads will be predictable/repeatable beyond maybe the first value.
        clarry 7y ago
        If you've ever tried to measure cycle-accurate timings for algorithms, you might've noticed that even relatively simple and short instruction streams have variance. Whether tsc clock and timer clock are linked or not is completely irrelevant, since the timer clock is only used to 1) credit entropy 2) possibly introduce additional jitter. The value of TSC when the timer interrupt runs is not used as entropy at all so even if that were 100% predictable, it doesn't matter. It only matters that you do have jitter (between calls to schedule() and random_get_entropy()), and I have a hard time imagining a modern system with a high-res TSC where calling schedule() with active timers in a loop (with branches) would not have any jitter at all. You probably have way more entropy than one bit per jiffy; I think the counter is very conservative. Notice that while entropy is credited only once per tick, actual TSC values are mixed into the entropy pool on every iteration of the loop that calls schedule().

devit 7y ago

Assuming they are independent random variables, since e.g. X xor (not X) is constant.

dooglius 7y ago

Well, that's not entirely true, even if two random bits are independent, xor-ing them only gives you one random bit. What actually happens in Linux is that each new input of random bits gets pushed through a cryptographic hash, before being xor'd.

ChrisSD 7y ago
From replies it seems my two sentences weren't as clear as I thought. I'll try to refine it: A property of bitwise xoring random variable `x` with a constant (or otherwise non-random but independent) value is that the entropy of `x` is preserved in the result.
- WAHa_06x36 7y ago
  However, xoring two arbitrary random variables is NOT guaranteed to preserve entropy. Preserving entropy only happens under certain specific conditions.
  - deleted 7y ago
    [deleted]
  - ChrisSD 7y ago
    Under what circumstances would xoring `x` and `y` not produce a result with entropy at least as great as `x`?
    - WAHa_06x36 7y ago
      In the very obvious cases where x == y, or x == not y, or x == y + 1, or many other correlations.
      - ChrisSD 7y ago
        Only if y is known to be dependent on x. If y is random but just so happens to be `not x` or `== x` then that won't make the result any less random. 0 is as random a number as 529890873740477 is.
        WAHa_06x36 7y ago
        Single numbers don't really have entropy at all, so that is not something it even makes sense to talk about.

uasm 7y ago

> "Using CPU jitter is a clever solution. I hope it stands up to scrutiny." How safe is it to use CPU jitter in a virtual machine?

jfindley 7y ago
Safe as in safe from host interference? Not at all. But if your VM is running on a malicious host, you have bigger problems honestly.
- stefan_ 7y ago
  This is kind of the ongoing joke here, yeah? Like HN users will gladly spend hours discussing the merits of various random number generation schemes, why that Intel HWRNG is probably backdoored and we should all be very afraid, all the while running their micro-services on the cloud where their entropy is literally spoon-fed from the hypervisor. SMC call into code-you-can't-see and back comes pure entropy (trust us)!
  - pjc50 7y ago
    Yes, although there's two kinds of VM safety people might care about. By using a VM you accept that the bare metal owner can look into it if they want to and you have to trust them not to. However, that doesn't mean accepting attacks from other customers - which was what all the Spectre/Meltdown risk was primarily about.

tptacek 7y ago

CPU jitter randomness is an old idea, and not especially well thought of.

Diederich 7y ago
If you have a moment, can you expand on that or provide a link? Especially for the last part. Thanks. This is well outside of my wheelhouse, so please pardon a naive inquiry.
- toast0 7y ago
  These timing measurements by nature are going to have a small range of possible values --- the size of the range is going to likely be system specific, and for some systems, there may be only a few possible outcomes.
  - clarry 7y ago
    And that's enough. One bit is enough, less than one bit of randomness is enough if you can just repeat the process enough times.
    - toast0 7y ago
      How are we to know how much entropy the process provides our system? The patch in the article counts one bit per timer interrupt, but there may be much less than that. If the tsc clock and the timer clock are linked, and the system is totally blocked on entropy, it seems plausible that the tsc reads will be predictable/repeatable beyond maybe the first value.
      - clarry 7y ago
        If you've ever tried to measure cycle-accurate timings for algorithms, you might've noticed that even relatively simple and short instruction streams have variance. Whether tsc clock and timer clock are linked or not is completely irrelevant, since the timer clock is only used to 1) credit entropy 2) possibly introduce additional jitter. The value of TSC when the timer interrupt runs is not used as entropy at all so even if that were 100% predictable, it doesn't matter. It only matters that you do have jitter (between calls to schedule() and random_get_entropy()), and I have a hard time imagining a modern system with a high-res TSC where calling schedule() with active timers in a loop (with branches) would not have any jitter at all. You probably have way more entropy than one bit per jiffy; I think the counter is very conservative. Notice that while entropy is credited only once per tick, actual TSC values are mixed into the entropy pool on every iteration of the loop that calls schedule().