[Cryptography] /dev/random is not robust

Eugen Leitl eugen at leitl.org
Thu Oct 17 14:23:17 PDT 2013


----- Forwarded message from Theodore Ts'o <tytso at mit.edu> -----

Date: Thu, 17 Oct 2013 09:08:00 -0400
From: Theodore Ts'o <tytso at mit.edu>
To: Adam Back <adam at cypherspace.org>
Cc: Jerry Leichter <leichter at lrw.com>, Sandy Harris <sandyinchina at gmail.com>, Cryptography <cryptography at metzdowd.com>
Subject: Re: [Cryptography] /dev/random is not robust
Message-ID: <20131017130800.GE11932 at thunk.org>
User-Agent: Mutt/1.5.21 (2010-09-15)

On Thu, Oct 17, 2013 at 02:32:57PM +0200, Adam Back wrote:
> 
> Yarrow, and the replacement Fortuna try to address this problem by
> accumulating entropy and adding it in bigger lumps..

... and Linux's /dev/random driver does this.

Post July 2012, most of the entropy is gathered via a per-CPU (to a
avoid cache line bouncing effects and so it can be lockless) entropy
pool, where we sample the high resolution cycle counter (or whatever
the highest granularity clock / memory refresh control register /
etc. we have access to on the archtecture) and the interrupted IP, and
mix that into the per-CPU fast mix pool on every interrupt.  We do
*not* use an entropy estimator for this interrupt fast mix pool.
Instead, we sample Every 64 interrupts, we transfer entropy from the
fast mix pool to the input pool, and we credit the input pool with a
single bit of entropy.  (There is very likely much more than a single
bit of entropy that has gotten accumulated during those 64 interrupts,
but out of an abundance of caution, we're using a very conservative
estimate for administrative concerns.)

In both the pre and post July 2012 designs, using a Yarrow-like
approach, we only transfer entropy from the input pool to the output
pool when there is sufficient entropy estimated to be in the input
pool so that we can do a "catastrophic ressed".  The "/dev/random is
not robust paper" assumed that the attacker could control the
interrupt timings such that estimate of entropy in the input pool was
incorrect, and thus the catastrophic reseed aspect of the design could
be bypassed.

I've already discussed why I don't believe that the assumption that
the attacker could control the interrupt timings to such an extent is
not realistic, and analysis of the entropy estimator (as used in the
pre-July 2012 design) showed that in fact, it was quite good.  But in
the post July 2012 design, we no longer use an interrupt estimator for
the interrupt fast mix pool.  We abandoned it for efficiency concerns,
since we wanted to make the cpu count on the global interrupt fast
path as low overhead as possible; instead, we traded this off by a
brute force quantity argument --- if we can collect the timing for
every single interrupt we're much better off than collecting it only
for some interrupts, especially when in the old design (which involved
CPU cache line bouncing and potential lock contention) device driver
authors were disabling the entropy collection more often than not.

So in the new design, we aren't using an dynamic entropy estimator ---
instead, we're assuming that after collecting the timings for 64
interrupts, we've collecting a single bit of entropy, which is really
a static entropy measure.  Could this be spoofed if the attacker has
control of the interrupt timings of the system?

Sure, but if the attacker has that level of control on the system,
then then pretty much all generators would be seriously compromised as
well.  The only way the paper could show that their proposed generator
was "robust" was based on the assumption that it would be possible for
the attacker to control the entropy inputs in such a way that entropy
estimator would be spoofed, but the attacker might still not know some
of the bits of the entropy inputs.

After all, if the attacker knows all of the bits, then by definition
all generators would be screwed.  However, what has not been
demonstrated in the paper is a real life scenario where the attacker
would have that level of control over the entropy inputs --- enough
that entrpoy estimators would be fooled, but not enough control that
their constuction could be considered robust.

Regards,

						- Ted
_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5



More information about the cypherpunks mailing list