[Pkg-sysvinit-devel] init.d/urandom : random-seed [patches]

[Henrique de Moraes Holschuh]

I had a far more verbose reply half-typed, but decided to go to the main
points, instead.

Let me state that I do NOT agree with the use of the "seeding" term to talk
about writing to /dev/?random outside of this mailing-list, because the fact
that it actually shuffles (result depends on the previous state vector)
instead of overwriting the state vector is NOT going to be obvious to anyone
which is not well versed on the specifics.

That detail matters, as the security requirements and failure mode recovery
are much less strict for "shuffling" than they are for "seeding".

In this thread, it will not cause confusion.

On Sun, 12 Sep 2010, John Denker wrote:
> On 09/12/2010 08:45 AM, Henrique de Moraes Holschuh wrote:
> a) The underlying driver links these two in a peculiar limited way.  
> b) Opinions differ as to whether the details of this linkage are 
>  done in the optimal way.
> c) Neither (a) or (b) is in any way relevant to the patches for
>  init.d/urandom that we are considering here.

Actually, thinking about it, (a) is quite important.  It defines when the
kernel will (re)seed the /dev/urandom PRNG, and how.  This is important as
we will need to known WHEN any attempts to improve the safety net of a young
entropy pool will have an impact on /dev/urandom in PRNG mode.

After all, we want to make all of /dev/random, in-kernel, and /dev/urandom
uses more secure (or at least less troublesome).

> > Well, AFAIK, you have three situations you want to "fix":
> > 
> > S1. low variance (or no variance) across cold or warm boots on the same
> > equipment.
> 
> Yes, that is part of the problem that needs to be fixed.
> 
> > S2. low variance (or no variance) across cold or warm boots across
> > different units of the same equipment model, especially when booted at
> > the same time.
> 
> Agreed. To that I might add that various things you might
> think of as distinguishing features (such as MAC addresses 
> and mobo serial numbers) are all-too-easy for attackers to
> figure out, so they are of little value.
> 
> > S3. low variance across synchronized or unsynchronized cold or warm boots
> > of unrelated equipment.
> > 
> > With the constraints:
> > 
> > C1. All equipment are booting exactly the same software (live cd).
> 
> Yes and no.  This is an issue, but not necessarily an inflexible
> constraint.  Some specific constructive suggestions have been
> made for alleviating this problem.  They are tangentially
> related to the present discussion.
>  
> > C2. Entropy from previous runs is not available
> > 
> > C3. There is very little real entropy being gathered by the kernel from
> > the network and storage devices
> 
> We agree that C2 and C3 define the use-case where the patches
> in question are important.
> 
> > Now, the RTC date and time helps you when your RTC is not broken, but it
> > is not of much help when a number of devices are powered up/rebooted at
> > the same time should their RTCs be in sync.  It also has not that much
> > entropy.
> 
> That's true, and that's why we need to address issue C1.

Well, the only way to fix S1 and S2 in a *secure* manner (i.e.
attacker-resistant) while C2 exists, is to have an external source of
trusted entropy (hypervisor channel, HRNG usable at early boot, etc).  This
is outside of our scope.  It is to be dealt with by kernel drivers, or
userspace scripts that belong to HRNG support packages.

So, while we are constrained by C2, we will be trying to minimize the
visible effects of S1 and S2, because that's all we can do.  And there IS a
large improvement in behaviour if the sequence of random numbers generated
by a group of devices are at least *different*.  Many applications need the
variance, and could care less for the unpredictability to a potential
attacker.

When we are not constrained by C2, we want to shorten as much as possible
the window where the system is running with very little entropy and no
safety net.  This means we want a set of changes that allows us to write the
entropy file to /dev/random as soon as possible (in a secure manner).

> The following combination *is* useful:
>  Part 1: a goodly amount (e.g. 4k bits) of seed that is 
>   unknown to the attacker, and is unique to this machine, plus

The only thing that fits is the entropy file, when NO failure modes are in
effect...  or stuff outside of our scope (HRNGs, etc).

I don't care if we use the kernel log, or "ip link" output, or dmidecode
output or something else (suggestions welcome), but I would really like to
add something that will help with the "unique to this machine" part in
99.999% of the devices out there (which will at least have reasonably unique
MAC addresses or serial numbers), for when we are operating with constraint
C2, and also to reduce the damage of some of the failure modes which would
make us use the entropy file twice, or make it unavailable.

>  Part 2: something that is provably different each time the
>   machine is rebooted, i.e. each time there has been an
>   irreversible loss of state.

Here, timestamps will help.  I agree that we shall assume that the RTC is
not broken, and the system time has already been set from the RTC at early
boot.  This will be true for any of the arches we can reasonably care about,
AFAIK.  The line must be drawn somewhere, after all.

> Among the experts on the cryptography list, there was 100% consensus
> that this two-part solution made sense.

IMO Part 1 covers too much, in a way that it is unhelpful when it comes down
to implementing the solution (as the whole point of this is to deal with
situations where we cannot do part 1 properly because of C2).

A much better solution would be:

Part 1: enough stored entropy to use as "seed material" (4Kib for Linux)
that is unknown to the attacker.

Part 2: something that is unique to this specific device among all others.

Part 3: something that is provably different each time this specific device
is rebooted, i.e. each time there has been an irreversible loss of state.

The information used for part 2 and part 3 must be large enough to disturb
the entropy pool and change its output radically.  It takes very little
variance to do that, so this won't matter in practice.

Using the system time as part of the "seeding" process takes care of part 3,
(the typical RTC has at least 2s precision).  But we must make sure the
kernel has had the opportunity to read the RTC already when using the
standard distro kernel.  This requres the rtc modules to have been loaded
before we read the system time.

> Therefore it seems that these patches should be adopted.

They will, either if the changes are restricted to run only on systems with
a Linux kernel, or if we access that they won't cause trouble for
Debian/kFreeBSD (Debian in a FreeBSD kernel).

> >> The clock-time is guaranteed to be different on each
> >> reboot.  The log is not guaranteed to be different,
> > 
> > The clock-time is not different across a series of devices powered up at
> > the same time, 
> 
> That's why we need the unique, unshared random.seed file,
> i.e. part 2 of the two-part solution.

That file is part *1* of the two-part solution, I think.

Anyway, it is NOT available on live-cds or any other RO media unless special
care was taken to generate a device-unique "seed-file" (which, while useless
for security by itself, at least will cause the "seeded" state vectors to be
different across a group of boxes of the same model).

> > We _need_ to know the properties of operation 3.2 on the other kernels.
> > If it is a "seed" instead of "shuffle", you have to send all the data in
> > a single write.  If it is a shuffle that can weaken the pool, you cannot
> > use anything that is available later.
> 
> There is no known Linux /dev/random that has the weakness you 
> describe.  Furthermore, since the patch in question deposits the 

Debian supports three kernels, you know: Linux, FreeBSD, and The Hurd.
Debian GNU/kFreeBSD seems to be close enough to be supported in a stable
release to merit being taken into account on decisions like this.

> date/time before depositing the random.seed, it would be harmless 
> even in this fanciful scenario.

In Linux, yes.

> Again, this cannot be considered a valid criticism of the patch.

It is.  We can certainly just do it, and let the Debian/kFreeBSD people
scream if we cause trouble, but that is NOT a very good-neighbourly way of
doing things.  We should ask them.

-- 
  "One disk to rule them all, One disk to find them. One disk to bring
  them all and in the darkness grind them. In the Land of Redmond
  where the shadows lie." -- The Silicon Valley Tarot
  Henrique Holschuh