The RF/electrical/other emissions from general-purpose CPU cores and their supporting circuitry tend to have major features with good correlations to execution timing and pipeline stalls, which they are not designed to treat as secret.
This is one reason why crypto implementations should be written using techniques that avoid table lookups or branches based on secret data: another is of course that the resulting timing variations may be visible on another core, over a network, etc.
Systems which treat the TSC (etc) as such secret data that they effectively seed a PRNG with it should therefore be treated with a very considerable degree of caution considering just how (literally) squeaky some cores/boards can be about leaking it. Further research is needed.
There are several entropy sources like this -Havege, jytter and Dakarand all tries to use jitter and unpredictable behavior in CPUs.
The chief advantage is that they don't need another HW source beside the CPU itself. I've been sceptic to how well they work on simpler architectures like ARM. (Havege for example tries to force cache misses in multi level memory system, which implies a need for caches). But at least Jytter actually seems to work fairly well on embedded CPUs too.
What to remember is to use these as entropy sources, not source for random numbers. Seed a proper csprng and use that to generate numbers. Quite a few CPUs today can implement AES efficiently so AES-CTR is probably a good choice in many systems.
(Having read the beginning and skimmed the rest) my impression is that this is a useful but vulnerable technique. Useful in that it provides an entropy source not currently available. But vulnerable in that it could conceivably weakened considerably.
Perhaps what should be discussed in this context is not entropy but conditional entropy. Entropy really is relative to one's understanding of the underlying system being observed. For example, human height is nearly normally distributed and would provide some degree of entropy if it could be freely sampled from. But for a given person, knowledge of the parents' heights makes predicting the child's height a much easier task. The entropy of height given parents' heights is less than the entropy of height in general. H(Height|ParentsHeight) < H(Height)
In the case of this CPU jitter method, things it calls nondeterministic are, in fact, clearly deterministic---disparities between CPU and memory clockspeed come to mind. Effort at better modeling of the internals of a CPU may lead these "random" events to appear not-so-random-anymore. Suppose I build a statistical model of CPU jitter based on various properties observable from a non-privileged process in the OS. To the extent that my model predicts jitter better than random, an entropy source derived from CPU jitter is weaker. The conditional entropy _given_ the model could decrease substantially, to the point that it's no longer a good entropy source.
That said, none of that work seems to have been done yet. But I wouldn't consider this a bulletproof entropy source in the long run.
Wow, this is pretty thorough but I never saw it address the simple question, why not use rdrand?
Also:
> the CPU Jitter random number generator returns roughly 10 kBytes per second on an Intel Core i7
OpenBSD requires at least 8 bytes of random data per TCP connection. Limiting a system to 1000 conn/sec (to say nothing of any other processing those connections may require) probably isn't going to fly.
As a comparison, I can read from /dev/random (and write to /dev/null) at over 300 MB/s.
> OpenBSD requires at least 8 bytes of random data per TCP connection. Limiting a system to 1000 conn/sec (to say nothing of any other processing those connections may require) probably isn't going to fly.
They can use the generated random values to seed a CSPRNG. I guess for containers or other virtual environments this has distinct advantages (at least that's one of the reasons given in the introduction).
> As a comparison, I can read from /dev/random (and write to /dev/null) at over 300 MB/s.
You can read from /dev/random only if there is enough entropy in it, and it's rarely very much, I don't know how you got that 300MB/s figure.
Basically thread scheduling is an imperfect art. So when you tell a thread to sleep for 4ms, it may sleep for 1-16ms depending on other threads work load, resource contention, etc.
This is a huge problem if you work in very precise time sensitive data (I do ISO17025 flow calibration systems), and when you start needing >100 data points per second, of dynamic IO you will run into millisecond timing issue standard time shared OS's will introduce. The solution to this is Real-Time OS's (not Real-Time webdevelopment) that handle scheduling differently, and prioritize IO tasks even higher. But most of these suck.
:.:.:
This random noise (from the scheduler) is a pretty good source of entropy (and the only assumption is your Unix box has other processes, that are using resources). Because your process, generally has no clue that hundreds of other processes are inflight and also being executed at the same time.
So their interference, is effectively magic data from nowhere.
Dan Kaminsky did a talk at Defcon last year where he mentioned the need for this type of CSRNG [1]
I even tooled up a very basic (and flawed) implementation a few months ago to play with the notion [2]
Interprocess scheduling isn't currently a source of entropy for /dev/random or /dev/urandom.
Edit: I have random/urandom backwards. Still doesn't change my core point. Sorry for the confusion.
/dev/random is a PRNG, and predictable. You shouldn't use it for security applications but only for specific state/algorithm randomness.
/dev/urandom requires hardware noise/key events, etc. to generate its entropy. These become hard to find when your dealing with purely virtualized installations.
:.:.:
The key focus for this is webapps, or should be. Far to many use PRNG to give session cookies, and these are very very easy to hyjack especially if cookies can be issued whenever a user logs in/out. Its pretty trivial to generate 1,000 -> 5,000 session cookies (from login/logout) and attempt to find a PRNG pattern.
/dev/random is a PRNG, and predictable. You shouldn't use it for security applications but only for specific state/algorithm randomness.
/dev/urandom requires hardware noise/key events, etc. to generate its entropy. These become hard to find when your dealing with purely virtualized installations.
This is not true, at least on Linux. /dev/random is actually closer to what you describe as /dev/urandom. It is a cryptographically strong randomness source that blocks depending on the state of its internal "entropy pool". /dev/urandom is also a cryptographically strong randomness source (seeded from /dev/random), but it does not block.
> /dev/random is a PRNG, and predictable. You shouldn't use it for security applications but only for specific state/algorithm randomness.
> /dev/urandom requires hardware noise/key events, etc. to generate its entropy. These become hard to find when your dealing with purely virtualized installations.
Actually /dev/random is truly random and requires entropy inputs; once the current entropy pool is exhausted, reads from /dev/random block. /dev/urandom is similar but reuses the entropy pool to produce PR values until more entropy comes in, so it's good for games and such.
Note: this comment is being written after the correction above concerning the mixup of /dev/random and /dev/urandom.
/dev/urandom is not a mere PRNG. It is a CSPRNG. Once it has been seeded with a good amount of entropy, say, 256 bits, it is safe to use for essentially all cryptographic purposes. That includes making long term SSH, SSL, and OpenPGP keys, and of course also includes making session cookies.
Yes, I know the Linux man page for /dev/random says otherwise. As Dan Bernstein notes, this is "superstitious nonsense" [1]:
Cryptographers are certainly not responsible for
this superstitious nonsense. Think about this for a
moment: whoever wrote the /dev/random manual page
seems to simultaneously believe that
(1) we can't figure out how to deterministically
expand one 256-bit /dev/random output into an
endless stream of unpredictable keys (this is what
we need from urandom), but
(2) we _can_ figure out how to use a single key to
safely encrypt many messages (this is what we need
from SSL, PGP, etc.).
For a cryptographer this doesn't even pass the laugh
test.
There is almost never a good reason for anyone other then the people who wrote the init scripts for your distribution to read /dev/random on a Linux system. They should read it to get entropy to initialize /dev/urandom, and to periodically reseed /dev/urandom.
Yes it is. Just your looking at the system at a different level. Resource contention is the stalls caused by context switching, cache missing, system latencies, and branch prediction.
Ultimately these 4 sources of latency build on top of each other to generate all your stalls, and slow downs in the system. What you see as CPU frequency scaling, I just see as my state switching in my program happen slower. What you see as pipeline stalls are just cache/ram misses, hard disk IO latency, and lots of context switches compounding on each other.
TL;DR You say "a starchy, tuberous crop from the perennial nightshade Solanum tuberosum L.", I say potato.
Isn't this basically another take on HAVEGE[1]? I'm not sure I'd call that a true random source.
[1] https://www.irisa.fr/caps/projects/hipsor/; see http://www.issihosts.com/haveged/
As I've said before: look out for side-channels!
The RF/electrical/other emissions from general-purpose CPU cores and their supporting circuitry tend to have major features with good correlations to execution timing and pipeline stalls, which they are not designed to treat as secret.
This is one reason why crypto implementations should be written using techniques that avoid table lookups or branches based on secret data: another is of course that the resulting timing variations may be visible on another core, over a network, etc.
Systems which treat the TSC (etc) as such secret data that they effectively seed a PRNG with it should therefore be treated with a very considerable degree of caution considering just how (literally) squeaky some cores/boards can be about leaking it. Further research is needed.
There are several entropy sources like this -Havege, jytter and Dakarand all tries to use jitter and unpredictable behavior in CPUs.
The chief advantage is that they don't need another HW source beside the CPU itself. I've been sceptic to how well they work on simpler architectures like ARM. (Havege for example tries to force cache misses in multi level memory system, which implies a need for caches). But at least Jytter actually seems to work fairly well on embedded CPUs too.
What to remember is to use these as entropy sources, not source for random numbers. Seed a proper csprng and use that to generate numbers. Quite a few CPUs today can implement AES efficiently so AES-CTR is probably a good choice in many systems.
(Having read the beginning and skimmed the rest) my impression is that this is a useful but vulnerable technique. Useful in that it provides an entropy source not currently available. But vulnerable in that it could conceivably weakened considerably.
Perhaps what should be discussed in this context is not entropy but conditional entropy. Entropy really is relative to one's understanding of the underlying system being observed. For example, human height is nearly normally distributed and would provide some degree of entropy if it could be freely sampled from. But for a given person, knowledge of the parents' heights makes predicting the child's height a much easier task. The entropy of height given parents' heights is less than the entropy of height in general. H(Height|ParentsHeight) < H(Height)
In the case of this CPU jitter method, things it calls nondeterministic are, in fact, clearly deterministic---disparities between CPU and memory clockspeed come to mind. Effort at better modeling of the internals of a CPU may lead these "random" events to appear not-so-random-anymore. Suppose I build a statistical model of CPU jitter based on various properties observable from a non-privileged process in the OS. To the extent that my model predicts jitter better than random, an entropy source derived from CPU jitter is weaker. The conditional entropy _given_ the model could decrease substantially, to the point that it's no longer a good entropy source.
That said, none of that work seems to have been done yet. But I wouldn't consider this a bulletproof entropy source in the long run.
Great article on LWN about this: http://lwn.net/Articles/642166/
Wow, this is pretty thorough but I never saw it address the simple question, why not use rdrand?
Also:
> the CPU Jitter random number generator returns roughly 10 kBytes per second on an Intel Core i7
OpenBSD requires at least 8 bytes of random data per TCP connection. Limiting a system to 1000 conn/sec (to say nothing of any other processing those connections may require) probably isn't going to fly.
As a comparison, I can read from /dev/random (and write to /dev/null) at over 300 MB/s.
> OpenBSD requires at least 8 bytes of random data per TCP connection. Limiting a system to 1000 conn/sec (to say nothing of any other processing those connections may require) probably isn't going to fly.
They can use the generated random values to seed a CSPRNG. I guess for containers or other virtual environments this has distinct advantages (at least that's one of the reasons given in the introduction).
> As a comparison, I can read from /dev/random (and write to /dev/null) at over 300 MB/s.
You can read from /dev/random only if there is enough entropy in it, and it's rarely very much, I don't know how you got that 300MB/s figure.
He mentioned OpenBSD. On OpenBSD /dev/random is a CSPRNG.
I think I need to sleep.
Someone please ELI5 this?
Basically thread scheduling is an imperfect art. So when you tell a thread to sleep for 4ms, it may sleep for 1-16ms depending on other threads work load, resource contention, etc.
This is a huge problem if you work in very precise time sensitive data (I do ISO17025 flow calibration systems), and when you start needing >100 data points per second, of dynamic IO you will run into millisecond timing issue standard time shared OS's will introduce. The solution to this is Real-Time OS's (not Real-Time webdevelopment) that handle scheduling differently, and prioritize IO tasks even higher. But most of these suck.
:.:.:
This random noise (from the scheduler) is a pretty good source of entropy (and the only assumption is your Unix box has other processes, that are using resources). Because your process, generally has no clue that hundreds of other processes are inflight and also being executed at the same time.
So their interference, is effectively magic data from nowhere.
Dan Kaminsky did a talk at Defcon last year where he mentioned the need for this type of CSRNG [1]
I even tooled up a very basic (and flawed) implementation a few months ago to play with the notion [2]
[1] https://www.youtube.com/watch?v=xneBjc8z0DE
[2] https://github.com/valarauca/Simple-CSRNG
Is there a significant advantage? Either-way you just need to fill /dev/random enough for /urandom to be well seeded.
Yes.
Interprocess scheduling isn't currently a source of entropy for /dev/random or /dev/urandom.
Edit: I have random/urandom backwards. Still doesn't change my core point. Sorry for the confusion.
/dev/random is a PRNG, and predictable. You shouldn't use it for security applications but only for specific state/algorithm randomness.
/dev/urandom requires hardware noise/key events, etc. to generate its entropy. These become hard to find when your dealing with purely virtualized installations.
:.:.:
The key focus for this is webapps, or should be. Far to many use PRNG to give session cookies, and these are very very easy to hyjack especially if cookies can be issued whenever a user logs in/out. Its pretty trivial to generate 1,000 -> 5,000 session cookies (from login/logout) and attempt to find a PRNG pattern.
This is not true, at least on Linux. /dev/random is actually closer to what you describe as /dev/urandom. It is a cryptographically strong randomness source that blocks depending on the state of its internal "entropy pool". /dev/urandom is also a cryptographically strong randomness source (seeded from /dev/random), but it does not block.
Here's a great blog post with more info: http://www.2uo.de/myths-about-urandom/
On the BSDs, there's no real distinction between the two, and the names are just there for compat.
> /dev/random is a PRNG, and predictable. You shouldn't use it for security applications but only for specific state/algorithm randomness.
> /dev/urandom requires hardware noise/key events, etc. to generate its entropy. These become hard to find when your dealing with purely virtualized installations.
You have it backwards. http://en.wikipedia.org/?title=/dev/random
Actually /dev/random is truly random and requires entropy inputs; once the current entropy pool is exhausted, reads from /dev/random block. /dev/urandom is similar but reuses the entropy pool to produce PR values until more entropy comes in, so it's good for games and such.
As the comments above point out, this isn't correct.
Note: this comment is being written after the correction above concerning the mixup of /dev/random and /dev/urandom.
/dev/urandom is not a mere PRNG. It is a CSPRNG. Once it has been seeded with a good amount of entropy, say, 256 bits, it is safe to use for essentially all cryptographic purposes. That includes making long term SSH, SSL, and OpenPGP keys, and of course also includes making session cookies.
Yes, I know the Linux man page for /dev/random says otherwise. As Dan Bernstein notes, this is "superstitious nonsense" [1]:
There is almost never a good reason for anyone other then the people who wrote the init scripts for your distribution to read /dev/random on a Linux system. They should read it to get entropy to initialize /dev/urandom, and to periodically reseed /dev/urandom.
[1] http://www.mail-archive.com/cryptography@randombit.net/msg04...
That's not what the paper is doing.
It's exploiting randomness from pipeline stalls, memory access latencies, CPU frequency scaling, etc.
Even disabling interrupts and cache doesn't reduce the entropy enough to make it non-random.
Yes it is. Just your looking at the system at a different level. Resource contention is the stalls caused by context switching, cache missing, system latencies, and branch prediction.
Ultimately these 4 sources of latency build on top of each other to generate all your stalls, and slow downs in the system. What you see as CPU frequency scaling, I just see as my state switching in my program happen slower. What you see as pipeline stalls are just cache/ram misses, hard disk IO latency, and lots of context switches compounding on each other.
TL;DR You say "a starchy, tuberous crop from the perennial nightshade Solanum tuberosum L.", I say potato.