Re: [MirageOS-devel] vchan hackers wanted for mirage-entropy

[david <unitedbiscuits@xxxxxxxxx>]

On Fri, Nov 21, 2014 at 11:39 AM, Anil Madhavapeddy <anil@xxxxxxxxxx> wrote:
> On 21 Nov 2014, at 10:30, Hannes Mehnert <hannes@xxxxxxxxxxx> wrote:
>>
>> While this is better than the current implementation (which uses
>> OCaml's Random, which on Xen is seeded very deterministic if I
>> understand that code correctly
>> https://github.com/ocaml/ocaml/blob/638a953bcf61678307fa5d0e1a969aaaf3f1ab20/byterun/sys.c#L364),
>> it is too easy to get it wrong (running the same unikernel image
>> several times with the same seed) that I don't feel comfortable to
>> ship mirage(-tls) with that.

This solution is easily much more dangerous; while `Random.self_init`
is as unpredictable as `gettimeofday`, and it is not hard to recover
the future of the random stream, fully *repeating* the stream will
completely compromise at least several algorithms I'm aware of. This
is because nonces require the guarantee of non-repetition (up to
astronomically small p), but not unpredictability. I tried to argue as
much in [1].

> http://www.ieee-security.org/TC/SP2014/papers/Not-So-RandomNumbersinVirtualizedLinuxandtheWhirlwindRNG.pdf

My main takeaway: rng based on strong crypto primitives, with
cascading pools, no entropy estimator, continuously fed by small
amounts of environmental entropy (timings), with some help from the
cpu (rdrand and cycle-counts of variable-length instructions), and
primed with the host rng via xenstore.

We have that. We have a rng based on strong crypto primitives. It uses
cascading pools, and there is research showing the pool system is
within a constant factor from optimally recovering from state
compromise [2], with shrinking that factor being a TODO. It avoids
entropy estimators and is designed for continuous reseeding. In fact,
their Whirlwind mentions Fortuna as their design inspiration, although
they don't explain why did they choose make their own algorithm.

So the core infrastructure is a well-mixing rng fed by a wide variety
of small entropy sources, and the gist of their findings is that such
an apparatus works in vm environments.

What they have but we don't is:
* instruction counting (doable)
* rdrand (doable)
* continuously injecting timings into the entropy pools (I swear, I
had a subclassed Lwt event loop that did this somewhere... i just
can't find it right now! :D )
* quick injection of entropy on boot/resume (they did it via xenstore)

(Have to go over that paper in more depth, but scanning their proposed
solution tells me as much.)

> Another alternative we could do in the short-term is just to pass
> the 16 bytes-every-10-minutes directly via Xenstore instead of a
> full-blown Vchan.  This would just require a daemon in dom0 to be
> run that does this.  The paper above also notes that the Xenstore
> hooks are useful to reinject fresh entropy upon suspend/resume,
> which couldn't be done easily in a pure vchan solution.

As Hannes pointed out, but maybe bears repeating: what mirage-entropy
is supposed to provide is not high-throughput. It serves to
periodically send small, relatively unpredictable packets. TLS itself
uses these to make the actual random stream.

Even if we had a high-throughput vchan sending GBs of entropy, we
would not read from it too eagerly. Entropy mixing and conversion into
the random stream is internal to TLS, and only small inputs are
required for everything to work nicely.

So for a quick fix, just sending a few bytes from dom0 rng every few
minutes is quite enough, in situations where we have control over
dom0. That entropy is high-quality, so it's ok to re-add it
infrequently. We could use any low-speed, high-latency channel for
this. We could write randomly named files on NFS and mix in the result
of `readdir`.

Plus, all the long term-solutions still contain the above as the
method of quickly bootstrapping the rng before its internal entropy
gathering has had a chance to take over.

So I believe the priority in the entropy saga should be *any* way to
dispatch a very small trickle of dom0 /dev/urandom to vms. With that,
we have our starting point.


~David

[1] - https://github.com/mirage/mirage-entropy/pull/6#issuecomment-64006065
[2] - http://eprint.iacr.org/2014/167.pdf

_______________________________________________
MirageOS-devel mailing list
MirageOS-devel@xxxxxxxxxxxxxxxxxxxx
http://lists.xenproject.org/cgi-bin/mailman/listinfo/mirageos-devel