[cryptography] Kernel space vs userspace RNG

Russell Leidich pkejjy at gmail.com
Mon May 9 14:21:18 EDT 2016


"how do you plan to get notice of them? the very point of DMA is that it
goes on in the background, and then you get a notification."

Generically speaking, you can't get any such notice due to insufficient
privilege. The best a userspace TRNG can do is to filter out periodic and
polynomial patterns in the timedelta stream, then hope that the residue is
sufficiently mixed with actual physical entropy, to be secure. But it's
possible that all that purported entropy is really just the aperiodic
residue of other deterministic processes running on the machine. So its
security depends upon the difficulty of (1) isolating cases in which no
physical entropy affects the output (e.g. cold boot at deterministic core
frequency before bus intitialization, which no sane security engineer would
allow) or (2) inserting enough taps into the machine that despite the
presence of physical entropy, the output can still be predicted. No
userspace TRNG can have a rigorous proof of security, for these reasons.
They are an economic compromise, essentially.

"this is not the question at all. i don't doubt that userspace can see some
entropy. my point was that the kernel sees everything, while userspace sees
less. it is not refuted by showing examples of entropy userspace can
collect."

If you mean that the kernel can see randomness which it actually knows to
be entropy, whereas the userspace can only see randomness which may be
entropy or pseudorandomness, I agree. My point was just that collecting
most of the physical entropy requires a tight loop. To the extent that
kernels are willing to sit around for a while doing so, then they can
gather unlimited amounts of entropy, given a reasonable model of DMA clock
skew behavior. However, in practice, kernels hate latency, so userspace can
much better afford to sit around gathering randomness, at the cost of not
knowing how much of that is due to physical entropy.

"please note that i also pointed out a danger: all the entropy visible to
userspace might be easier to steal, because there is a chance that other
programs can gather the exact same entropy (hence my example of the sound
card noise)."

Your sound card noise example makes sense because a single server (the
audio driver) is broadcasting to multiple clients (parallel userspace
TRNGs). Fortunately, timedeltas don't work like that. For example, with
Intel Hyperthreading cores, both virtual cores compete for access to the
ALUs, so they will never show the same timedelta stream for anywhere near
the thousands of cycles required to produce a random number, especially
after periodicity subtraction. I would actually expect more raw timedelta
stream similarity between successive single-threaded runs, than from a pair
of simultaneous runs, on account of this competition. If we're talking
about physically separate CPUs, it only gets more complicated.

By the way, I would expect to be able to detect the arrival of an IRQ by
monitoring the timedelta stream in userspace, especially on more idle
machines. This is one way in which _kernel_ entropy could be stealable.
Intel provided a means to make RDTSC(P) illegal in userspace (via CR4?).
This should be implemented, and the timestamp counter virtualized to hide
kernel events, but I don't know of any OS which does that.

"to some extent, havege might alleviate this, because there is no direct
way to observe the parameters it collects. but this is highly speculative,
as the true source of havege random is not the CPU, but the same irqs and
other hw events. the CPU just acts as a hard to observe prng. so actually
i'm not a fan. without looking into it deeper, i believe this is also true
for enranda."

You are correct. The only guarantee that I can make about Enranda, in the
absence of physical entropy, is that it's a hard-to-observe PRNG with a
state space of O(1M) bits which ignores most periodic timedelta sequences.
Without a security violation of the OS, however, I think it's impossible to
steal enough timedeltas across a process boundary to predict its output to
any useful extent. Cache miss and timing attacks are useless, as is a
parallel instance of Enranda. If anyone can prove otherwise, it would make
a very interesting read.

The ideal physical random number generator, I think, would be an analog
computer of macroscopic size, like something soldered together inside a
clear case. That's the only way we could verify its functionality. I would
never buy something labelled "random number generator" that comes in a
black box containing 10 nanometer features or whatever. Who knows how that
would actually work under the hood.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20160509/95856760/attachment-0001.html>


More information about the cryptography mailing list