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

[Anil Madhavapeddy <anil@xxxxxxxxxx>]

On 21 Nov 2014, at 18:45, david <unitedbiscuits@xxxxxxxxx> wrote:
> 
> 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].

It's only more dangerous in isolation.  This solution, *in combination*
with other sources such as the current time, should be how we do entropy.
A similar analogy is random.seed in the OpenBSD boot loader:  a per host
(or in this case, VM) source of entropy is still useful since it's 
unique per-host, despite being repeated across reboots.  The other sources
take care of the other dimension.

> 
>> 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.)

Excellent analysis.

> 
>> 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.
> 

Yes, but but let me reiterate that we *must* have a solution that
also works without a dom0 entropy proxy.  It may be that binding
RDRAND and scraping inter-event channel timings is the only answer, but
we must be able to get entropy at least as strong as existing VMs
do without dom0 assistance.

For that reason, I think we should still take a compile-time one-time
pad as one of the entropy sources, just like OpenBSD mixes in a
/etc/random.seed to help with start-of-day.

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