11
$\begingroup$

In some virtualized environments, the only source of entropy available is CPU timing jitter. Can one get enough entropy from this source for practical uses? Also, is this secure against local side-channel attacks against unprivileged local attackers?

"enough" in this context means "enough to seed a CSPRNG" (256 bits?). "unprivileged" means that the attacker cannot simply read the RNG state directly because of process or VM isolation.

$\endgroup$
  • $\begingroup$ You might want to consider rate of entropy production as opposed to absolute amount? If you only want to seed a CSPRNG once, and are willing to wait for enough entropy to be harvested, then all is good. But if your server is doing a lot of cryptographic functions and should routinely re-seed, that would be a different story. $\endgroup$ – Neil Slater Jan 3 '16 at 9:48
  • 2
    $\begingroup$ You may be interested in this descryption of a jitter RNG that went into Linux in some form (cf. crypto/jitterentropy.c): chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf $\endgroup$ – otus Jan 3 '16 at 10:04
  • 2
    $\begingroup$ I've been using CPU timing jitter as entropy source on a wide variety of CPU models since 2001. Perhaps the most important observation is that it has become more risky on modern multicore CPUs. If you are not careful, you might end up harvesting entropy from a core that is not used for anything else, meaning you will either end up with a poor entropy source, or be stuck in an endless loop. $\endgroup$ – Henrick Hellström Jan 3 '16 at 12:02
  • 1
    $\begingroup$ Note to people posting comments: remember to use comments to ask for more information or suggest improvements. Avoid answering questions in comments. Thanks $\endgroup$ – e-sushi Jan 4 '16 at 20:13
6
$\begingroup$

The problem with CPU jitter is that it is difficult to pin down an accurate physical model of it that would allow you to calculate the entropy involved. Therefore entropy estimates have to largely be grounded on statistical testing, as in the document I linked in the comments.

As you may know, statistical testing alone can only ever give you an upper bound for entropy. What you need for secure random number generation is a lower bound, and that requires making more assumptions.

However, since you only need enough entropy to seed a PRNG, the answer to your question is almost certainly that it does have enough entropy. You can always collect timings for a very long time and feed it all as seed material to the RNG, and unless the jitter contains no entropy at all you will eventually have 256 bits' worth. How long is the question, with no single answer.

If you use a recent Linux kernel, you should be able to get entropy with all that figured out (or guessed...) for you, just by accessing /dev/random or /dev/urandom. In practice it is also often possible to get a small seed into the VM from outside, so you do not necessarily have to rely on the VM being able to generate entropy.

$\endgroup$
1
$\begingroup$

Yes. The slight issue is in actually measuring how much entropy is available. I work with Java, so java.lang.System.nanoTime() does it for me. Before people get all uppity and say that nanoTime is not a possible source of entropy, consider...

The best random numbers come from true random number generators drawing upon physical sources of entropy. Quantum mechanics or chaotic physics means that there are no techniques of modelling the sources. That's in the physical world. There is also a similarly complex digital world inside a modern computer. This means that it can act as an ersatz physical entropy source.

In my experiments, I measured the rate of entropy from nanoTime() at 0.13%. That means that you'll need to take many measurements to fill 256 bits. Approximately 6000 samples in my case. The issue is that it's very difficult (impossible?) to measure accurately, so you have to err enormously on the side of caution. It's highly subject to the Observer Effect. But it can be done, especially for seeding a CSPRNG. After all, that's exactly what java.security.SecureRandom does to seed itself.

$\endgroup$
  • 1
    $\begingroup$ I mostly agree, but AFAIK java.security.SecureRandom only uses timing-based entropy as a last resort, in case the platform does not offer a secure entropy source. On Linux/Android it will read seeds from /dev/urandom and on Windows call something like CryptGenRandom (IIRC). $\endgroup$ – otus Aug 9 '16 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.