CPU Jitter Based True Random Generator
chronox.de
chronox.de
[1] https://www.irisa.fr/caps/projects/hipsor/; see http://www.issihosts.com/haveged/
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.
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.
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.
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.
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.
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.
Here's a great blog post with more info: http://www.2uo.de/myths-about-urandom/
> /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
/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.
[1] http://www.mail-archive.com/cryptography@randombit.net/msg04...
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.
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.