Discussion:
FYI/RFC: early-rng-init-tools
(too old to reply)
Thorsten Glaser
2019-02-24 20:00:01 UTC
Permalink
Hello fellow developers (and some users),

I would like to present a recent (this week) project of mine.
Background story:

In buster/sid, I noticed a massive delay booting up my laptop
and some virtual machines, which was reduced by hitting the
Shift and Ctrl keys multiple times randomly during boot; a
message =E2=80=9Crandom: crng init done=E2=80=9D would appear, and boot wou=
ld
continue.

This is a well-known problem, and there are several bugs about
this; new in buster/sid compared to stretch is that it also
blocks urandom reads (I was first hit in the tomcat init script
from this). This is especially noticeable if you use a sysvinit
non-parallel boot, but I=E2=80=99m sure it also affects all others.

There=E2=80=99s already code, in both sysv-rc/initscripts and systemd,
to store some random seed file and load it on reboot. The problem
with that is that it=E2=80=99s just written to /dev/urandom but the kernel
is not told =E2=80=9Chey I just gave you X bits worth of entropy=E2=80=9D, =
and it
happens much too late, especially during parallel boot.

I=E2=80=99ve written something, a linux-any package, that=E2=80=A6

=E2=80=A2 during postinst, creates a 128-byte random seed file in /
=E2=80=A2 updates that in a daily cronjob (using same tool as during
boot except with more bits taken from the kernel)
=E2=80=A2 updates (the second 64-byte half, from urandom) it on shutdown
=E2=80=A2 hooks into initramfs to=E2=80=A6
=E2=80=93 on x86, use =E2=80=9CJytter=E2=80=9D (CPU jitter) to try and ge=
t some more
random bytes (not accredited, just written to the pool)
=E2=80=93 makes it mount the root filesystem, after fsck, read-write
instead of deferring that to the init scripts (this should
be safe, though, as initramfs *does* fsck)
=E2=80=93 after the root filesystem is read-write,
=E2=80=A3 reads from the seed file (128 bytes)
=E2=80=A3 uses that and a number of other things (to make it differ)=E2=
=80=A6
=E2=86=90 md5sum of dmesg
=E2=86=90 3 random bytes written into initramfs during update-initram=
fs
=E2=86=90 the current time
=E2=86=90 a bit of kernel entropy (from AT_RANDOM auxvec, set anyway)
=E2=86=90 on x86, Jytter and the TSC
to initialise a stretching RNG (arc4random)
=E2=80=A3 writes between 32 and 256 bytes to /dev/urandom (but does not
accredit them yet, just remembers the amount written)
=E2=80=A3 updates the seed file with 128 bytes from the SRNG
=E2=80=A3 fsync(2)s and close(2)s the seed file to ensure the next run
will be different
=E2=80=A3 now tells the kernel X random bits were added, where X is=E2=
=80=A6
=E2=86=92 the number of bytes written earlier=E2=80=A6
=E2=86=92 times 6 (so we count at best six bits per byte)=E2=80=A6
=E2=86=92 capped at 128*7 bits, to both not overwhelm and because our
seed is only 128 bytes in size, estimated conservatively

tl;dr: it adds entropy during initramfs/as early as possible during
boot *and* tells the kernel it did so, to make its crng initialised,
and ensures a subsequent boot has a different seed, also updated
periodically and on shutdown for added entropy carry-over.

I=E2=80=99d like people to use it, experiment with it and criticise it.

Packages (.dsc / some .deb):
http://fish.mirbsd.org/~tg/Debs/dists/sid/wtf/Pkgs/early-rng-init-tools/

Repository:
https://evolvis.org/plugins/scmgit/cgi-bin/gitweb.cgi?p=3Dalioth/early-rng=
-init-tools.git;a=3Dtree
git clone https://evolvis.org/anonscm/git/alioth/early-rng-init-tools.git

Licence: MirOS, some parts ISC, some x86-only parts LGPL.

I am fully aware that it is not suitable for everyone:
=E2=80=A2 it=E2=80=99s Linux-only (the RNG on kFreeBSD is very different, a=
nd
I didn=E2=80=99t even look into Hurd=E2=80=99s urandom translator)
=E2=80=A2 it prevents you from booting with / mounted read-only
=E2=80=A3 although the checkroot init script remounts / read-only when ne=
eded
=E2=80=A3 perhaps we could remount / read-only ourselves afterwards,
but that can be tricky to get right too=E2=80=A6
=E2=80=A2 it means you trust a seed file and the arc4random algorithm (to m=
ake
a uniform enough stream from the various seeds)
=E2=80=A2 klibc lacks clock_gettime (#923098) so we cannot add the monotoni=
c
clock, which would be interesting in the cronjob/shutdown hook
=E2=80=A2 it links statically against klibc, because getting Depends on the
/lib/klibc-*.so file right is unchartered territory
=E2=80=A2 it does not use/add CPU RNG output where present
=E2=80=A3 though Linux can now do that itself, some command-line flag=E2=
=80=A6
=E2=80=A2 nor is there any jitter code on n=C5=8Dn-x86

On the plus side, I=E2=80=99ve tested it on i386, amd64, x32 (although klib=
c
for x32 is actually amd64 so I tested that with glibc) and as a n=C5=8Dn-x8=
6
architecture m68k. It also works on MirBSD, should do OpenBSD, too=E2=80=A6

Perhaps this helps someone. While too late for buster, unless there
is any justified concern, I=E2=80=99ll upload it to Debian (and provide it
via buster-backports) in a while.

Enjoy,
//mirabilos
PS: please keep me in Cc, I am not subscribed to d-devel
PPS: feel free to forward/distribute this elsewhere
--=20
18:47=E2=8E=9C<mirabilos:#!/bin/mksh> well channels=E2=80=A6 you see, I see=
everything in the
same window anyway 18:48=E2=8E=9C<xpt:#!/bin/mksh> i know, you have so=
me kind of
telnet with automatic pong 18:48=E2=8E=9C<mirabilos:#!/bin/mksh> ha=
ha, yes :D
18:49=E2=8E=9C<mirabilos:#!/bin/mksh> though that's more tinyirc =E2=80=93 =
sirc is more comfy
Philipp Kern
2019-02-24 20:10:01 UTC
Permalink
Post by Thorsten Glaser
In buster/sid, I noticed a massive delay booting up my laptop
and some virtual machines, which was reduced by hitting the
Shift and Ctrl keys multiple times randomly during boot; a
message “random: crng init done” would appear, and boot would
continue.
This is a well-known problem, and there are several bugs about
this; new in buster/sid compared to stretch is that it also
blocks urandom reads (I was first hit in the tomcat init script
from this). This is especially noticeable if you use a sysvinit
non-parallel boot, but I’m sure it also affects all others.
FTR this is supposedly fixed on the main architectures featuring an RNG
in the CPU by linux 4.19.20-1, which enabled RANDOM_TRUST_CPU. Which Ben
announced on this list[1] earlier this month.

Kind regards
Philipp Kern

[1] https://lists.debian.org/debian-devel/2019/02/msg00170.html
Thorsten Glaser
2019-02-24 20:20:02 UTC
Permalink
Hi Philipp,
Post by Philipp Kern
FTR this is supposedly fixed on the main architectures featuring an RNG
in the CPU by linux 4.19.20-1, which enabled RANDOM_TRUST_CPU. Which Ben
that=E2=80=99s what I referred to by=E2=80=A6
Post by Philipp Kern
Post by Thorsten Glaser
=E2=80=A2 it does not use/add CPU RNG output where present
=E2=80=A3 though Linux can now do that itself, some command-line flag=
=E2=80=A6

=E2=80=A6 but that only helps if the CPU has such instructions, and you
trust them sufficiently.

My package is useful for a lot of the other cases.

bye,
//mirabilos
--=20
<diogenese> Beware of ritual lest you forget the meaning behind it.
<igli> yeah but it means if you really care about something, don't
ritualise it, or you will lose it. don't fetishise it, don't
obsess. or you'll forget why you love it in the first place.
Ben Hutchings
2019-02-25 15:50:01 UTC
Permalink
Post by Thorsten Glaser
Hi Philipp,
Post by Philipp Kern
FTR this is supposedly fixed on the main architectures featuring an
RNG
Post by Philipp Kern
in the CPU by linux 4.19.20-1, which enabled RANDOM_TRUST_CPU. Which
Ben
that’s what I referred to by

Post by Philipp Kern
• it does not use/add CPU RNG output where present
‣ though Linux can now do that itself, some command-line flag


 but that only helps if the CPU has such instructions,
[...]

Indeed, on x86 this requires the RDRAND instruction which Intel
introduced in 2011 (Ivy Bridge core) and AMD only implemented in 2015
(Excavator core).

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Andy Simpkins
2019-02-25 08:50:01 UTC
Permalink
Post by Philipp Kern
Post by Thorsten Glaser
In buster/sid, I noticed a massive delay booting up my laptop
and some virtual machines, which was reduced by hitting the
Shift and Ctrl keys multiple times randomly during boot; a
message “random: crng init done” would appear, and boot would
continue.
This is a well-known problem, and there are several bugs about
this; new in buster/sid compared to stretch is that it also
blocks urandom reads (I was first hit in the tomcat init script
from this). This is especially noticeable if you use a sysvinit
non-parallel boot, but I’m sure it also affects all others.
FTR this is supposedly fixed on the main architectures featuring an RNG
in the CPU by linux 4.19.20-1, which enabled RANDOM_TRUST_CPU. Which Ben
announced on this list[1] earlier this month.
Be aware RANDOM_TRUST_CPU depends on: |CONFIG_X86
<https://cateee.net/lkddb/web-lkddb/X86.html> || CONFIG_S390
<https://cateee.net/lkddb/web-lkddb/S390.html> || CONFIG_PPC
<https://cateee.net/lkddb/web-lkddb/PPC.html>|

I should have thanked Ben for turning this on sooner, in the mean time I
am preparing email to list for other architectures (Mainly ARM at the
moment I admit)

/Andy
Thorsten Glaser
2019-02-24 22:10:01 UTC
Permalink
Daemon
There are no daemons running at that time. This is run in
initramfs, just after the root filesystem has been mounted,
with no background tasks save udev running, and network has
not been set up (unless NFS or dropbear are in use).

Adding bytes at both points sounds doable. I wanted to keep
it simple, no =E2=80=9Cmagic sprinkle=E2=80=9D, because people tend to fear
those. I might do that, but I don=E2=80=99t really see an attack
scenario here (see above)=E2=80=A6 we=E2=80=99re talking about a place in
boot where normally there=E2=80=99s 0 entropy available and / is
mounted read-only anyway.

bye,
//mirabilos
--=20
Solange man keine schmutzigen Tricks macht, und ich meine *wirklich*
schmutzige Tricks, wie bei einer doppelt verketteten Liste beide
Pointer XORen und in nur einem Word speichern, funktioniert Boehm ganz
hervorragend.=09=09-- Andreas Bogk =C3=BCber boehm-gc in d.a.s.r
Ben Hutchings
2019-02-25 16:00:02 UTC
Permalink
On Sun, 2019-02-24 at 19:52 +0000, Thorsten Glaser wrote:
[...]
I’ve written something, a linux-any package, that

• during postinst, creates a 128-byte random seed file in /
• updates that in a daily cronjob (using same tool as during
boot except with more bits taken from the kernel)
• updates (the second 64-byte half, from urandom) it on shutdown
• hooks into initramfs to

– on x86, use “Jytter” (CPU jitter) to try and get some more
random bytes (not accredited, just written to the pool)
– makes it mount the root filesystem, after fsck, read-write
instead of deferring that to the init scripts (this should
be safe, though, as initramfs *does* fsck)
– after the root filesystem is read-write,
‣ reads from the seed file (128 bytes)
‣ uses that and a number of other things (to make it differ)

← md5sum of dmesg
Much of which is the same from boot to boot. Yes, timestamps will
differ, but the same systems that currently have little entropy
available from interrupts will likely also have very consistent
timestamps during boot.
← 3 random bytes written into initramfs during update-initramfs
That doesn't change from boot to boot.
← the current time
This doesn't add much entropy since RTCs typically have 1 second
resolution and some systems don't even have an RTC.
← a bit of kernel entropy (from AT_RANDOM auxvec, set anyway)
Feeding the kernel RNG output back to itself doesn't add any entropy.
← on x86, Jytter and the TSC
to initialise a stretching RNG (arc4random)
‣ writes between 32 and 256 bytes to /dev/urandom (but does not
accredit them yet, just remembers the amount written)
How do you determine the number of bytes here?
‣ updates the seed file with 128 bytes from the SRNG
‣ fsync(2)s and close(2)s the seed file to ensure the next run
will be different
‣ now tells the kernel X random bits were added, where X is

→ the number of bytes written earlier

→ times 6 (so we count at best six bits per byte)

→ capped at 128*7 bits, to both not overwhelm and because our
seed is only 128 bytes in size, estimated conservatively
[...]

The major input into the new seed file contents is the old seed file
contents. You are adding very little entropy on x86, and possibly
almost none on other architectures.

Please reconsider this, as this description sounds dangerously
insecure.

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Michael Stone
2019-02-25 16:30:01 UTC
Permalink
Post by Ben Hutchings
The major input into the new seed file contents is the old seed file
contents.
Yes, I'd just drop the seed file once used, then have a scheduled job
write a new one at some point in the future if the random quality is
high enough. If you reboot twice in a row the second boot won't get
seeded, but that's better than a package that introduces potentially
insecure random seeding by default. Maybe add a non-default option to
allow seed reuse with a lot of warnings, but don't do it by default.
Thorsten Glaser
2019-02-25 16:50:01 UTC
Permalink
Post by Ben Hutchings
=E2=80=A3 writes between 32 and 256 bytes to /dev/urandom (but does =
not
Post by Ben Hutchings
accredit them yet, just remembers the amount written)
How do you determine the number of bytes here?
32 + arc4random_uniform(256 - 32 + 1)

[=E2=80=A6]
Post by Ben Hutchings
The major input into the new seed file contents is the old seed file
contents. You are adding very little entropy on x86, and possibly
almost none on other architectures.
This is during early boot, where there=E2=80=99s almost no entropy
available yet. This step, while having taken up a lot of
explanation, is mostly to ensure that the next seed differs
from the previous one.
Post by Ben Hutchings
=E2=80=A2 updates that in a daily cronjob (using same tool as during
boot except with more bits taken from the kernel)
=E2=80=A2 updates (the second 64-byte half, from urandom) it on shutdown
Let=E2=80=99s take the second bullet point first: I=E2=80=99m adding 64 byt=
es from
whatever the system has in its RNG during shutdown. This is the
step where entropy for the _next_ boot is _normally_ added.

The early-rng-init-tools initramfs part is *not* about gathering
more entropy during boot, it=E2=80=99s to make whatever entropy is there
available earlier. (The regular /var/lib/urandom/random-seed (or
whatever systemd does) thing is *also* *still* done, just later.)

Now, the daily cronjob. It uses the same mechanism as in early
boot, but without the -E parameter, so it reads a few bytes more
from the kernel. On Linux, the exact numbers (modulo things like
dmesg and time which are only used to diversify) are:

=E2=80=A2 with -E (early boot):
=E2=80=A3 with AT_RANDOM
=E2=80=93 16 bytes from AT_RANDOM (possibly shared with
other code in the same executable)
=E2=80=A3 without AT_RANDOM
=E2=80=93 4 bytes from /dev/urandom
(although all of them are probably not very random)

=E2=80=A2 without -E (daily cronjob):
=E2=80=A3 with AT_RANDOM
=E2=80=93 16 bytes from AT_RANDOM (possibly shared with
other code in the same executable)
=E2=80=93 8 bytes from /dev/urandom
=E2=80=A3 without AT_RANDOM
=E2=80=93 16 bytes from /dev/urandom
(and all of these are during normal system runtime,
so should be random enough, otherwise you have a
problem ANYWAY)

So, in the cronjob case, we get 128 to 192 bits from the
kernel. Tytso said that using 128 bits to initialise a
good RNG is probably enough for a lot=E2=80=A6 and we *do* also
add the 128 *bytes* (1024 bit) from the seedfile.

If the postinst (first time 1024 bits get written into
the seed file), cronjob (where the seed file is mixed
with another 128/192 bit from the kernel), shutdown
(where 512 bits in the seedfile are overwritten with
512 fresh bits from /dev/urandom) do not have entropy
enough, you have a different problem. Use something like
ekeyd with Simtec=E2=80=99s EntropyKey (which I do), or type more
on the keyboard, or, if you really must, use haveged or
something like that. My early-rng-init-tools does not
address that, you still have to ensure regular entropy
collection during normal system runtime happens and is
good enough. It=E2=80=99s really *just* about getting it usable
earlier in the boot process.

Perhaps you (or someone from l10n-en) could suggest
wording to that effect I could add to the package
description, or perhaps even a README? (Maybe I should
write a README anyway. I need to work on other stuff,
freeze/BSP-relevant but also real life-relevant, for
now, but I=E2=80=99ll revisit this anyway=E2=80=A6)

I=E2=80=99ll take all feedback into account by then.

bye,
//mirabilos
--=20
16:47=E2=8E=9C=C2=ABmika:#grml=C2=BB .oO(mira ist einfach gut....) 23:=
22=E2=8E=9C=C2=ABmikap:#grml=C2=BB
mirabilos: und dein bootloader ist geil :) 23:29=E2=8E=9C=C2=ABmikap:#gr=
ml=C2=BB und ich
finds saugeil dass ich ein bsd zum booten mit grml hab, das muss ich dann
gleich mal auf usb-stick installieren=09-- Michael Prokop =C3=BCber MirOS b=
sd4grml
Ben Hutchings
2019-02-25 17:20:01 UTC
Permalink
Post by Thorsten Glaser
Post by Ben Hutchings
‣ writes between 32 and 256 bytes to /dev/urandom (but does not
accredit them yet, just remembers the amount written)
How do you determine the number of bytes here?
32 + arc4random_uniform(256 - 32 + 1)
OMG. Don't randomise the length.

[...]
Post by Thorsten Glaser
If the postinst (first time 1024 bits get written into
the seed file), cronjob (where the seed file is mixed
with another 128/192 bit from the kernel), shutdown
(where 512 bits in the seedfile are overwritten with
512 fresh bits from /dev/urandom) do not have entropy
enough, you have a different problem.
[...]

Yes, but your implementation fails open in that case. In early boot
you should remove the seed file rather than creating it with
insufficient entropy.

To refresh the seed file, you should start a service at boot that does
a blocking read from /dev/random (not /dev/urandom). Possibly it
should sleep a few minutes or have dependencies that prevent it from
taking away entropy from other services.

I don't see the point of doing this repeatedly in a cron job. And you
can't do it properly at shutdown since you shouldn't block then.

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Ben Hutchings
2019-02-25 16:40:02 UTC
Permalink
Post by Ben Hutchings
The major input into the new seed file contents is the old seed file
contents. You are adding very little entropy on x86, and possibly
almost none on other architectures.
Please reconsider this, as this description sounds dangerously
insecure.
I don't think his goal was to add any significant entropy? I mean,
using old seed file should be enough by itself, as long as the random
state was ever initialized to an unpredictable state to create a secret
seed file, the contents stayed secret, and there is no reuse of the
same seed file without updating it on disk.
The output of the RNG may well become public, for example in document
UUIDs. So when estimating the entropy that the new seed file will
provide for the next boot, none of the entropy in the old seed file
should be credited.

Ben.
At least I didn't read the proposal as relying on that added entropy
for security.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Sam Hartman
2019-02-25 19:40:01 UTC
Permalink
Ben> The output of the RNG may well become public, for example in
Ben> document UUIDs. So when estimating the entropy that the new
Ben> seed file will provide for the next boot, none of the entropy
Ben> in the old seed file should be credited.

Are you saying that you believe that given output from the RNG it is
cryptographically feasible to determine the seed?

There's a trivial reduction from that claim to a proof that the PRNG is
not in fact a PRNG.

Unless there are cryptology results I'm unaware of--and it has been a
few years since I studied the construction of PRNGs--then I don't think
your argument is reasonable.
A PRNG should be secure so long as its seed stays secret.

Now, there are a lot of ways that a seed can become not secret. So I
don't think our default should be to assume that a seed is secret.
However, especially on platforms that don't have good hardware, I do
think having a quick package you can install that gives reasonable
operation under the assumption you keep your PRNG seed secret is very
valuable.
It shouldn't be the default out of the box, but it should be easy to
turn on because it's a common configuration for our users.

What am I missing here?
Ben Hutchings
2019-02-26 19:20:01 UTC
Permalink
Post by Sam Hartman
Ben> The output of the RNG may well become public, for example in
Ben> document UUIDs. So when estimating the entropy that the new
Ben> seed file will provide for the next boot, none of the entropy
Ben> in the old seed file should be credited.
Are you saying that you believe that given output from the RNG it is
cryptographically feasible to determine the seed?
There's a trivial reduction from that claim to a proof that the PRNG is
not in fact a PRNG.
Unless there are cryptology results I'm unaware of--and it has been a
few years since I studied the construction of PRNGs--then I don't think
your argument is reasonable.
A PRNG should be secure so long as its seed stays secret.
[...]

But if the input to the seed doesn't provide enough entropy, the seed
is not completely secret (that is, you can recover it with less work
than a brute force search). The extreme example of this is the OpenSSL
RNG debacle of some years back, where only the pid (15 bits) was used.

Thorsten's implementation should yield rather more than 15 bits of
entropy, but I think his entropy estimate is still over-optimistic. In
the worst case the Linux RNG is used to generate a private key
immediately on first boot, so the old seed file doesn't provide any
additional entropy. (Either it doesn't exist or it's part of an image
and not secret.) And in that case the space of possible keys may be
small enough that it's feasible to recover the private key.

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Ben Hutchings
2019-02-27 17:20:02 UTC
Permalink
Post by Ben Hutchings
But if the input to the seed doesn't provide enough entropy, the seed
is not completely secret (that is, you can recover it with less work
than a brute force search). The extreme example of this is the OpenSSL
RNG debacle of some years back, where only the pid (15 bits) was used.
Thorsten's implementation should yield rather more than 15 bits of
entropy, but I think his entropy estimate is still over-optimistic. In
the worst case the Linux RNG is used to generate a private key
immediately on first boot, so the old seed file doesn't provide any
additional entropy. (Either it doesn't exist or it's part of an image
and not secret.) And in that case the space of possible keys may be
small enough that it's feasible to recover the private key.
While what you're saying here is not strictly speaking false, I think
it's missing the point, and is not a valid objection to the approach as
a whole. The core point of a program like this is that if you had a
secret state for the PRNG before boot, then rebooting *should not lose
that state* as long as you trust a file to stay secure over the boot.
There should be zero time needed to gather any new genuine entropy.
The additional entropy gathered is for extra safety; it is not
*depended* on for basic security assumptions.
[...]

It is, because the the kernel is told to treat it as providing a
certain number of bits of entropy.

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Sam Hartman
2019-02-27 17:40:01 UTC
Permalink
The additional entropy gathered is for extra safety; it is not
*depended* on for basic security assumptions.
Ben> [...]

Ben> It is, because the the kernel is told to treat it as providing
Ben> a certain number of bits of entropy.

I see no problem crediting the secret stored across the reboot with the
entropy in the pool at the time of shutdown.
I agree that the credits for the entropy of the additional information
added may be too high.

I'm skeptical that the actual entropy credits matter much once you have
*enough*, but I agree that the /dev/random interface does depend on
that, and the proposal as described may be violating that assumption.
Ian Jackson
2019-02-28 12:00:01 UTC
Permalink
Post by Ben Hutchings
[Someone:]
The additional entropy gathered is for extra safety; it is not
*depended* on for basic security assumptions.
[...]
It is, because the the kernel is told to treat it as providing
a certain number of bits of entropy.
I see no problem crediting the secret stored across the reboot with the
entropy in the pool at the time of shutdown.
Indeed.

AIUI the reason given for not doing this by default is that nowadays
many installations are VMs of some kind which may be cloned between
shutdown and startup.

This makes some kind of sense, although I am not sure that it is right
to break a lot of embedded systems for the benefit of people who do
that without care for cryptographic seeds. Those are only one of
several things that need fixing up or working around when cloning a VM
image.
Post by Ben Hutchings
I agree that the credits for the entropy of the additional information
added may be too high.
I'm skeptical that the actual entropy credits matter much once you have
*enough*, but I agree that the /dev/random interface does depend on
that, and the proposal as described may be violating that assumption.
Linux /dev/random's notion that there is any difference between
`enough' entropy and `more' is wrong. In particular its idea that
taking PRNG output out of /dev/random could cause degradation of any
kind is wrong.

IMO this is a serious and longstanding design defect in Linux's
/dev/random (which incidentally is not present in FreeBSD's
/dev/random which has had contact with actual cryptographers; and it
is not present in at least one of the newer syscall APIs but for
reasons best known to Linux developers, there is no simple /dev device
with the correct semantics).

So, it is of no consequence if Thorsten's scheme violates this
/dev/random entropy-counting principle.


I have a PhD in computer security - in particular, in cryptographic
protocol design. But my knowledge is rather out of date since I left
academia and I have not reviewed Thorsten's design in detail.

Thanks,
Ian.
--
Ian Jackson <***@chiark.greenend.org.uk> These opinions are my own.

If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
a private address which bypasses my fierce spamfilter.
Sam Hartman
2019-02-28 13:00:02 UTC
Permalink
additional entropy gathered is for extra safety; it is not >>
*depended* on for basic security assumptions. > [...] It is,
because the the kernel is told to treat it as providing > a
certain number of bits of entropy.
I see no problem crediting the secret stored across the reboot
with the entropy in the pool at the time of shutdown.
Ian> Indeed.

Ian> AIUI the reason given for not doing this by default is that
Ian> nowadays many installations are VMs of some kind which may be
Ian> cloned between shutdown and startup.

Right, and I'm not talking about changing the default, simply saying
that having a simple way to change that default on a given system by
installing a package is important.
I agree that the credits for the entropy of the additional
information added may be too high.
I'm skeptical that the actual entropy credits matter much once
you have *enough*, but I agree that the /dev/random interface
does depend on that, and the proposal as described may be
violating that assumption.
Ian> Linux /dev/random's notion that there is any difference between
Ian> `enough' entropy and `more' is wrong. In particular its idea
Ian> that taking PRNG output out of /dev/random could cause
Ian> degradation of any kind is wrong.

I absolutely agree with you, and I think a lot of people in the Linux
community agree with you thus the getrandom syscall.

I'm not a designer of cryptographic primitives, but I am qualified to
evaluate their use in protocols. Having learned from my own mistakes
and others, I'm very nervous of violating the explicit security
assumptions or claims of an interface. If you asked me whether we
should make available an interface like /dev/random that cared about
entropy beyond "enough," I'd say "absolutely not." However, given that
we have such an interface, should we violate its assumptions?
I can't see the harm. I've been burned by the harm I didn't see too
many times before.
I'd do it on my system.
I might or might not flag it in a security review of someone else's
design depending on circumstances.
Once someone flags it--and Ben has flagged it--I'm reluctant to dismiss
it without careful consideration.

But since we think good enough is good enough, what's the big deal?
Credit the secret seed across boot but don't credit much for the low
entropy stuff we're mixing in additionally.
Ben Hutchings
2019-02-25 18:00:02 UTC
Permalink
On Mon, 2019-02-25 at 19:37 +0200, Uoti Urpala wrote:
[...]
Generally you don't ever
need to use /dev/random instead of /dev/urandom unless you make
assumptions about cryptography failing.
[...]

I think I agree with that, but there is no way to add entropy that
unblocks getrandom() without also unblocking /dev/random. If the seed
files used in two different boots are somewhat correlated, and the
entropy estimation doesn't account for that, the output of /dev/random
may also be somewhat correlated between the boots, which is not
supposed to happen.

Ben.
--
Ben Hutchings
The obvious mathematical breakthrough [to break modern encryption]
would be development of an easy way to factor large prime numbers.
- Bill Gates
Ian Jackson
2019-02-28 12:00:02 UTC
Permalink
Post by Ben Hutchings
Generally you don't ever
need to use /dev/random instead of /dev/urandom unless you make
assumptions about cryptography failing.
I think I agree with that, but there is no way to add entropy that
unblocks getrandom() without also unblocking /dev/random. If the seed
files used in two different boots are somewhat correlated, and the
entropy estimation doesn't account for that, the output of /dev/random
may also be somewhat correlated between the boots, which is not
supposed to happen.
I'm not sure what you mean by `somewhat correlated'.

Assuming that the random seed file is not copied, there is no weakness
in copying entropy out of the kernel random pool and reinserting it on
next boot, assuming that either (i) the entropy estimate provided on
next boot is no bigger than the kernel's entropy counter at shutdown
OR (ii) the kernel's PRNG was at any time properly seeded so that
/dev/random unblocked.

Ian.
--
Ian Jackson <***@chiark.greenend.org.uk> These opinions are my own.

If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
a private address which bypasses my fierce spamfilter.
Ben Hutchings
2019-02-28 17:00:02 UTC
Permalink
Post by Ian Jackson
Post by Ben Hutchings
Generally you don't ever
need to use /dev/random instead of /dev/urandom unless you make
assumptions about cryptography failing.
I think I agree with that, but there is no way to add entropy that
unblocks getrandom() without also unblocking /dev/random. If the seed
files used in two different boots are somewhat correlated, and the
entropy estimation doesn't account for that, the output of /dev/random
may also be somewhat correlated between the boots, which is not
supposed to happen.
I'm not sure what you mean by `somewhat correlated'.
I meant that they're not completely independent, so that knowing one
allows you to make some predictions about the other. But if I've
understood rightly, that doesn't matter as long as the entropy
estimation is right.
Post by Ian Jackson
Assuming that the random seed file is not copied, there is no weakness
in copying entropy out of the kernel random pool and reinserting it on
next boot, assuming that either (i) the entropy estimate provided on
next boot is no bigger than the kernel's entropy counter at shutdown
OR (ii) the kernel's PRNG was at any time properly seeded so that
/dev/random unblocked.
I think this is right.

Ben.
--
Ben Hutchings
This sentence contradicts itself - no actually it doesn't.
Sam Hartman
2019-02-28 18:20:01 UTC
Permalink
If the seed > files used in two different boots are somewhat
correlated, and the > entropy estimation doesn't account for
that, the output of /dev/random > may also be somewhat correlated
between the boots, which is not > supposed to happen.
I'm not sure what you mean by `somewhat correlated'.
Ben> I meant that they're not completely independent, so that
Ben> knowing one allows you to make some predictions about the
Ben> other. But if I've understood rightly, that doesn't matter as
Ben> long as the entropy estimation is right.

If the seed is secret and there is enough entropy, and some data (no
matter how low entropy) is added to distinguish the boots, then no you
should not be able to make such predictions. Doing so is sufficient to
prove the kernel PRNG is not a PRNG (at least assuming you can do so in
polynomial time).

I think that may be what you mean when you say that if you've understood
rightly, that doesn't matter. If so, then your understanding is
correct.
Sebastian Andrzej Siewior
2019-02-25 19:10:02 UTC
Permalink
Post by Thorsten Glaser
tl;dr: it adds entropy during initramfs/as early as possible during
boot *and* tells the kernel it did so, to make its crng initialised,
and ensures a subsequent boot has a different seed, also updated
periodically and on shutdown for added entropy carry-over.
so I have one older box that suffers from that. I installed haveged and
seemed to went away:

[ 1.600832] random: fast init done
[ 2.417621] systemd[1]: systemd 240 running in system mode. (+PAM +AUDIT +SELINUX +IMA +APPARMOR +SMACK +SYSVINIT +UTMP +LIBCRYPTSETUP +GCRYPT +GNUTLS +ACL +XZ +LZ4 +SECCOMP +BLKID +ELFUTILS +KMOD -IDN2 +IDN -PCRE2 default-hierarchy=hybrid)
[ 8.685406] random: crng init done

So what is the advantage over using haveged?
As far as I understand, it would reach the "init done" state before
systemd took over, right?

Sebastian
Thorsten Glaser
2019-02-28 20:50:01 UTC
Permalink
Post by Sebastian Andrzej Siewior
so I have one older box that suffers from that. I installed haveged and
I tried that, after the suggestion to use haveged went up, but=E2=80=A6
Post by Sebastian Andrzej Siewior
As far as I understand, it would reach the "init done" state before
systemd took over, right?
=E2=80=A6 this was not true for me. Not before init takes over, anyway (as
haveged does not have any initramfs integration), but we=E2=80=99re talking
about =E2=80=9Ccrng init done=E2=80=9D here, not =E2=80=9Cfast init done=E2=
=80=9D. In my scenario,
haveged was started much too late in the boot to be useful (after
tomcat, even). But then, I use a non-parallel sysvinit startup. It=E2=80=99=
s
fragile anyway; if you install more daemons, for example, it might
also block before reaching the stage where haveged starts on your
parallel systemd setup suddenly.
Post by Sebastian Andrzej Siewior
So what is the advantage over using haveged?
haveged tries to use CPU jitter, in a way similar to jytter but
on a much more massive scale, to gather entropy-ish and writes
that to the kernel RNG. It, however, does that all the time, and
not just a little bit. Basically, it=E2=80=99s an attempt to gather entropy=
,
while early-rng-init-tools just takes what=E2=80=99s there during normal
system runtime (which you have to provide yourself, at the very
least before installing it, but sensibly also normally) and makes
it available to the kernel earlier (this really ought to be done
in the bootloader, even, but this at least improves on what we
currently have).

So, different concept (even though early-rng-init-tools also has
a *small* gather function which, on x86, gathers a few bytes using
the same mechanism=E2=80=A6 but the majority of randomness comes from the
seed file).

From=20what I=E2=80=99ve read about haveged, statements from its author, an=
d
looking at the source code (which begs to be customised for the exact
CPU setup your machine has, as if it were a FORTRAN library), I=E2=80=99d
prefer to not use haveged on my systems even if it would help. I=E2=80=99m
the owner of several Simtec EntropyKey sticks and use them and a
entropy distributing scheme over the network (with SSL/SSH) instead
to add runtime entropy to machines lacking local (disk/keyboard/mouse).
But, as I said, that=E2=80=99s just at runtime; early-rng-init-tools isn=E2=
=80=99t
about that (except it updates the seedfile later durng runtime to
mix in at least some more runtime entropy that the next boot will
be able to use).

bye,
//mirabilos
--=20
=E2=80=9CIt is inappropriate to require that a time represented as
seconds since the Epoch precisely represent the number of
seconds between the referenced time and the Epoch.=E2=80=9D
=09-- IEEE Std 1003.1b-1993 (POSIX) Section B.2.2.2
Tollef Fog Heen
2019-03-02 09:10:02 UTC
Permalink
]] Thorsten Glaser
… this was not true for me. Not before init takes over, anyway (as
haveged does not have any initramfs integration), but we’re talking
about “crng init done” here, not “fast init done”. In my scenario,
haveged was started much too late in the boot to be useful (after
tomcat, even). But then, I use a non-parallel sysvinit startup. It’s
fragile anyway; if you install more daemons, for example, it might
also block before reaching the stage where haveged starts on your
parallel systemd setup suddenly.
It starts much earlier in a systemd setup; in sysvinit it's in rc2.d,
whereas with systemd it just waits for apparmor.service,
system-random-seed.service and systemd-tmpfiles-setup.service, so the
risk of it being blocked is much smaller.
--
Tollef Fog Heen
UNIX is user friendly, it's just picky about who its friends are
Ian Jackson
2019-02-28 15:00:02 UTC
Permalink
• during postinst, creates a 128-byte random seed file in /
Can you confirm that this is done with data from
getrandom(,,GRND_RANDOM) ? (Presumably with GRND_NONBLOCK too.)
– after the root filesystem is read-write,
‣ reads from the seed file (128 bytes)
‣ uses that and a number of other things (to make it differ)…
← md5sum of dmesg
← 3 random bytes written into initramfs during update-initramfs
← the current time
← a bit of kernel entropy (from AT_RANDOM auxvec, set anyway)
← on x86, Jytter and the TSC
This latter stuff is fine but not really critical IMO.
to initialise a stretching RNG (arc4random)
Why are you feeding this through a separate hashing function rather
than letting the kernel PRNG's hasher do it ? I am seriously
unconvinced that arc4random is a good idea here.
‣ writes between 32 and 256 bytes to /dev/urandom (but does not
accredit them yet, just remembers the amount written)
Why not write the whole lot ?
‣ updates the seed file with 128 bytes from the SRNG
‣ fsync(2)s and close(2)s the seed file to ensure the next run
will be different
Why not update the seed file with information from
getrandom(GRND_RANDOM), instead ? (You would have to do this after
the next step.)
‣ now tells the kernel X random bits were added, where X is…
→ the number of bytes written earlier…
→ times 6 (so we count at best six bits per byte)…
→ capped at 128*7 bits, to both not overwhelm and because our
seed is only 128 bytes in size, estimated conservatively
IMO you should promise to the kernel an amount of entropy exactly
equal to the size of the saved seed.
• it’s Linux-only (the RNG on kFreeBSD is very different, and
I didn’t even look into Hurd’s urandom translator)
I think the same principles will apply. If your utility on BSD uses
BSD's /dev/random instead of Linux's getrandom() syscall, then it will
DTRT.
• it prevents you from booting with / mounted read-only
I think this is an undesirable side effect. There is a tradeoff here:

If you defer updating the seed to later, after you have already set
off the kernel RNG, then any situation with multiple partial boots
will reuse the seed, which is bad. Whether that's a practical problem
depends on what exactly might be run in the meantime, with / still ro.

I missed the beginning part. Is it not possible to defer all of this
to make it run just after / is mounted rw ?
• it means you trust a seed file and the arc4random algorithm (to make
a uniform enough stream from the various seeds)
The question is nothing to do with its uniformity. The kernel PRNG
will hash its input. I think you can feed it whatever.

If the RC4 were critical to the security properties of your scheme,
then I would be making a much stronger complaint, because RC4 is (of
course) broken (when used as a supposedly cryptographically secure
pseudorandom bitstream generator).


I hope you have found this review helpful.


Regards,
Ian.
--
Ian Jackson <***@chiark.greenend.org.uk> These opinions are my own.

If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
a private address which bypasses my fierce spamfilter.
Ben Hutchings
2019-02-28 17:00:02 UTC
Permalink
On Thu, 2019-02-28 at 14:52 +0000, Ian Jackson wrote:
[...]
Post by Ian Jackson
Post by Thorsten Glaser
to initialise a stretching RNG (arc4random)
Why are you feeding this through a separate hashing function rather
than letting the kernel PRNG's hasher do it ? I am seriously
unconvinced that arc4random is a good idea here.
I agree.

[...]
Post by Ian Jackson
Post by Thorsten Glaser
• it means you trust a seed file and the arc4random algorithm (to make
a uniform enough stream from the various seeds)
The question is nothing to do with its uniformity. The kernel PRNG
will hash its input. I think you can feed it whatever.
Yes.
Post by Ian Jackson
If the RC4 were critical to the security properties of your scheme,
then I would be making a much stronger complaint, because RC4 is (of
course) broken (when used as a supposedly cryptographically secure
pseudorandom bitstream generator).
The "arc4random" functions really use ChaCha20 today, anyway.

Ben.
Post by Ian Jackson
I hope you have found this review helpful.
--
Ben Hutchings
This sentence contradicts itself - no actually it doesn't.
Thorsten Glaser
2019-02-28 21:00:01 UTC
Permalink
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
=E2=80=A2 during postinst, creates a 128-byte random seed file in /
Can you confirm that this is done with data from
getrandom(,,GRND_RANDOM) ? (Presumably with GRND_NONBLOCK too.)
No. The mechanism is to initialise a local arc4random instance,
which is then used to stretch the seed into the kernel and the
new content of the seed file.
Post by Ben Hutchings
Post by Ian Jackson
This latter stuff is fine but not really critical IMO.
It=E2=80=99s merely used to attempt to make the boots more dissimilar.
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
to initialise a stretching RNG (arc4random)
Why are you feeding this through a separate hashing function rather
than letting the kernel PRNG's hasher do it ? I am seriously
unconvinced that arc4random is a good idea here.
I agree.
This is the basic design decision (see above). I=E2=80=99m not reading from
the kernel to write to the seed file because

=E2=91=A0 the entropy given might not be enough to make it initialise,
depending on future kernel changes; this should not block boot,
just make it better if it can

=E2=91=A1 I only let the kernel attribute the random bytes AFTER the seed
file has been successfully written to disc with the new content,
in order to guarantee that either the next boot differs or that
the script does not make the system think it has more entropy
than it really has
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
=E2=80=A3 writes between 32 and 256 bytes to /dev/urandom (but does=
not
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
accredit them yet, just remembers the amount written)
Why not write the whole lot ?
The whole lot of what?

My only constraint here is that I need to write enough bits to
justifyably accredit at least 128 bits, and that the total number
of bits I accredit is at most the seed file size (128 bytes) times
a trust factor smaller than 1 (using =E2=85=9E here).
Post by Ben Hutchings
Post by Ian Jackson
IMO you should promise to the kernel an amount of entropy exactly
equal to the size of the saved seed.
Why is it a problem to use less? This is commonly called a security
margin.
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
=E2=80=A2 it=E2=80=99s Linux-only (the RNG on kFreeBSD is very differen=
t, and
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
I didn=E2=80=99t even look into Hurd=E2=80=99s urandom translator)
I think the same principles will apply. If your utility on BSD uses
BSD's /dev/random instead of Linux's getrandom() syscall, then it will
Some of the BSDs don=E2=80=99t even have /dev/random. It=E2=80=99s also not=
about
getrandom(), which is not used (read() from /dev/urandom is), but
about the RNDADDTOENTCNT ioctl, which is pretty much specific to
the Linux RNG and the ones deriving from it (OpenBSD/MirBSD).
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
=E2=80=A2 it means you trust a seed file and the arc4random algorithm =
(to make
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
a uniform enough stream from the various seeds)
The question is nothing to do with its uniformity. The kernel PRNG
will hash its input. I think you can feed it whatever.
It=E2=80=99s not about what we feed to the kernel, but about the property
of it distributing the input evenly across the output. The basic tenet
here is that, if I have 128 bytes of random input from the seed file,
then, if I write the output of an SRNG to both the kernel and back to
the seed file, each has about 128 bytes worth of entropy iff only one
is used (and somewhat less otherwise, but, again, according to tytso
and I believe even Ben in some Debbug against OpenSSL, 16 or 32 bytes
of input =E2=80=9Cshould be enough=E2=80=9D).
Post by Ben Hutchings
Post by Ian Jackson
Post by Thorsten Glaser
=E2=80=A2 it prevents you from booting with / mounted read-only
[=E2=80=A6]
Post by Ben Hutchings
Post by Ian Jackson
I missed the beginning part. Is it not possible to defer all of this
to make it run just after / is mounted rw ?
No, because we=E2=80=99re already in parallel boot by then, and this would
mean extremely invasively patching of all init scripts/systems.

Do you see any practical concern with mounting / read-write before
init, as opposed to rather quickly after init by one of the init
scripts?
Post by Ben Hutchings
Post by Ian Jackson
If the RC4 were critical to the security properties of your scheme,
then I would be making a much stronger complaint, because RC4 is (of
course) broken (when used as a supposedly cryptographically secure
pseudorandom bitstream generator).
=E2=80=9Cof course=E2=80=9D?

Not all applications of RC4 are broken. If you use it as a generator
of random bytes after seeding it with suitably large, suitably random
input (as opposed to an 8-byte IV that=E2=80=99s reused *cough*WEP*cough*) =
and
throw away some amount of initial keystream (which cannot be done in
things like TLS, because that would change the protocol), then, no, RC4
is not broken. (There=E2=80=99s additional throwing-away-stuff-randomly-dur=
ing-
execution in place. UTSL if interested.)
Post by Ben Hutchings
The "arc4random" functions really use ChaCha20 today, anyway.
Not all of them. This utility ships its own implementation, which
is derived from the original BSD one, so it=E2=80=99s still using aRC4,
although with all the changes from newer security research applied.
(I had hopes for Spritz, but it turns out it misbehaves worse.)
Post by Ben Hutchings
Post by Ian Jackson
I hope you have found this review helpful.
Somewhat. Thank you for taking the time, nevertheless.

I still believe that the concept has merit. Of course, it=E2=80=99s not for
people whose CPU has RNG instructions and who trust them (as I said
already), and people who mistrust the algorithms involved (such as
arc4random). But I believe that to be a minority, and that all of
them have a suitably large base of people who do trust them, so that
even those who distrust do so out of their own preferences, not due
to a general problem with it. (One of the reasons I=E2=80=99m asking for
feedback here is to improve it enough so that nobody finds it bad
when others use it even if they don=E2=80=99t use it themselves, and to see
that it will be welcomed into Debian at some point in time later.)

And that=E2=80=99s why this would be an optional package, anyway. You don=
=E2=80=99t
*have* to install it, but you *can* if you want.

It needs a README anyway, and I=E2=80=99m willing to write all kinds of
stuff into both it and the long package description to make sure
people know exactly what they trust when using it, and welcome
text suggestions.

(Plus, it=E2=80=99s a stopgap measure, until bootloaders do the entropy int=
o
the kernel early dance as is done in BSD land. (If early userland
then updates the seed file, it=E2=80=99s not even a problem if the bootload=
er
doesn=E2=80=99t and it gets repeated between boots since, if the boot did n=
ot
even reach early userland, it=E2=80=99s likely been used for almost nothing=
=2E)
But as I don=E2=80=99t expect that to become reality any time soon, this wi=
ll
likely live for quite some time.)

bye,
//mirabilos
--=20
Post by Ben Hutchings
Hi, does anyone sell openbsd stickers by themselves and not packaged
with other products?
No, the only way I've seen them sold is for $40 with a free OpenBSD CD.
=09-- Haroon Khalid and Steve Shockley in gmane.os.openbsd.misc
Sam Hartman
2019-02-28 22:40:02 UTC
Permalink
Thorsten> It’s not about what we feed to the kernel, but about the
Thorsten> property of it distributing the input evenly across the
Thorsten> output. The basic tenet here is that, if I have 128 bytes
Thorsten> of random input from the seed file, then, if I write the
Thorsten> output of an SRNG to both the kernel and back to the seed
Thorsten> file, each has about 128 bytes worth of entropy iff only
Thorsten> one is used (and somewhat less otherwise, but, again,
Thorsten> according to tytso and I believe even Ben in some Debbug
Thorsten> against OpenSSL, 16 or 32 bytes of input “should be
Thorsten> enough”).

Not exactly.
The entropy is also capped at the internal state of your SRNG whatever
it is.
I'd strongly recommend finding a design where you don't use your own
RNG and just use the kernel's RNG entirely.

I think it complicates the analysis and may introduce problems to have
multiple PRNGs involved: your security is the weakest link in this
instance.

Let me see if I understand the issue that makes this hard for you.

You want to avoid crediting the entropy before the new seed is written.
You cannot call getrandom before you credit the entropy.
So you cannot use getrandom to produce the new seed file.

That's ugly, and if I've got it right, I at least understand your
constraints.

I'd probably do something like:

1) read the seed file

2) remove the seed file; fsync the directory.

3) write to kernel; credit the entropy

4) mix in other stuff

5) call getrandom and generate a new seed file.

You're in a bad position if you crash between reading and writing the
seed file, but I think your other options are also bad.
Kurt Roeckx
2019-03-03 18:20:01 UTC
Permalink
I think the only sane things are:
- Use a hardware RNG (CPU, TPM, chaos key, ...)
- Credit a seed file stored during the previous boot
- Wait for new entropy from other sources

Note that is can be a combination of all 3.

We currently do not credit the seed file, for various good
reasons. We should provide an option to users that need it to
trust that file and credit that file. Note that it does not need
to be fully trusted, we could for instance say it only provides 64
bits of entropy.

Most people will actually have at least 2 hardware RNGs: One in
the CPU and one in the TPM. We can make the kernel trust those as
entropy source without using something in userspace to feed it.
I'm not sure in the kernel has the option to use the TPM directly
as source, but it makes it available as /dev/hwrng. (The TPM might
be disabled in the BIOS.) Some people don't trust them, I suggest
they buy something they do trust, and disable the ones they don't
trust. I think we should trust all hardware RNGs by default, and
then also actually extract data from all of them.

Note that the internal state of an RNG is only 256 bit / 32 byte.
If you make that output something, it can't have more than that 256
bit of entropy. It does not make sense to take more bytes of the RNG
than that to feed back in it. It can make sense to do this at
different times, after the RNG has reseeded, but both should be
limited to that 256 bit / 32 byte. It doesn't make sense to do
this at more than 2 different points in time.

There is no point in using an other RNG to stretch something. Just
use the kernel RNG to stretch it by just asking more data from it.

Do not feed the output of the kernel during boot back into the
kernel, even if you don't credit it. If there is something random
in it, the kernel will already have used that. If you do it, there
is no point in using something like md5, the kernel will take care
of that itself.

Other than the entropy you feed it, it can be useful to feed it
data that does not need to be secret but is very likely different
on each boot, including things like the current time, and an
incrementing counter. It would not be credited as having entropy.
The seed file currently acts as this. I have no idea if the kernel
does anything like that itself, like the mount count of a
filesystem. It might be useful that we feed it some boot counter.


Kurt
Ben Hutchings
2019-03-03 20:30:02 UTC
Permalink
On Sun, 2019-03-03 at 18:59 +0100, Kurt Roeckx wrote:
[...]
Post by Kurt Roeckx
Most people will actually have at least 2 hardware RNGs: One in
the CPU and one in the TPM. We can make the kernel trust those as
entropy source without using something in userspace to feed it.
I'm not sure in the kernel has the option to use the TPM directly
as source, but it makes it available as /dev/hwrng.
[...]

If there is at least one hardware RNG with a non-zero "quality" then
the kernel will start a thread (khwrngd) that reads from the hardware
RNG and adds those bits to the core RNG, crediting each bit with
quality/1024 bits of entropy.

Most hardware RNG drivers don't specify quality and it defaults to
zero, but this can be overridden by setting the module parameter
rng-core.default_quality. Perhaps we should set a low but non-zero
default value?

There are potential problems with doing this: some of these hardware
RNGs are probably quite weak, so we have to be very conservative, but
then the less entropy we credit the more CPU time will be spent in the
hardware RNG reader thread.

Ben.
--
Ben Hutchings
No political challenge can be met by shopping. - George Monbiot
Kurt Roeckx
2019-03-03 22:00:02 UTC
Permalink
Post by Ben Hutchings
[...]
Post by Kurt Roeckx
Most people will actually have at least 2 hardware RNGs: One in
the CPU and one in the TPM. We can make the kernel trust those as
entropy source without using something in userspace to feed it.
I'm not sure in the kernel has the option to use the TPM directly
as source, but it makes it available as /dev/hwrng.
[...]
If there is at least one hardware RNG with a non-zero "quality" then
the kernel will start a thread (khwrngd) that reads from the hardware
RNG and adds those bits to the core RNG, crediting each bit with
quality/1024 bits of entropy.
Most hardware RNG drivers don't specify quality and it defaults to
zero, but this can be overridden by setting the module parameter
rng-core.default_quality. Perhaps we should set a low but non-zero
default value?
I think choas key is the exception to this, the kernel uses it by
default. Changing that is going to surprise people.

I don't know if we can find actually find out what quality the
RNG should provide for most devices. I think for some we can set
reasonable defaults. But at least with TPMs it can be one of
various manufacturers, so the quality might be totally different.
Post by Ben Hutchings
There are potential problems with doing this: some of these hardware
RNGs are probably quite weak, so we have to be very conservative, but
then the less entropy we credit the more CPU time will be spent in the
hardware RNG reader thread.
I gues that what I would like is that at the start it just gets
the entropy it needs, and then keeps feeding it at a low rate, for
instance a few bytes every few seconds. I don't know if that's
something that can be set, or that it currently does.

I have a FST-01 / NeuG, which I guess is like the worst RNG you
can get. It generates less then 0.03 bit / bit of entropy, but can
do this at 80 or 280 kB/s depending on the setting. With 0.03 bit
/ bit, it takes 533 byte to get to the 128 bit entropy level. At
80 kB/s, that takes 6.6 ms. So even if we set the quality very
low, it can still be very useful.

(The kernel does not recoginize it as an RNG, you need rng-tools
for it.)


Kurt
Ben Hutchings
2019-03-03 23:20:01 UTC
Permalink
Post by Kurt Roeckx
Post by Ben Hutchings
[...]
Post by Kurt Roeckx
Most people will actually have at least 2 hardware RNGs: One in
the CPU and one in the TPM. We can make the kernel trust those as
entropy source without using something in userspace to feed it.
I'm not sure in the kernel has the option to use the TPM directly
as source, but it makes it available as /dev/hwrng.
[...]
If there is at least one hardware RNG with a non-zero "quality" then
the kernel will start a thread (khwrngd) that reads from the hardware
RNG and adds those bits to the core RNG, crediting each bit with
quality/1024 bits of entropy.
Most hardware RNG drivers don't specify quality and it defaults to
zero, but this can be overridden by setting the module parameter
rng-core.default_quality. Perhaps we should set a low but non-zero
default value?
I think choas key is the exception to this, the kernel uses it by
default. Changing that is going to surprise people.
The module parameter only affects devices where the driver doesn't
specify quality. The chaoskey driver should be unaffected.
Post by Kurt Roeckx
I don't know if we can find actually find out what quality the
RNG should provide for most devices. I think for some we can set
reasonable defaults. But at least with TPMs it can be one of
various manufacturers, so the quality might be totally different.
Post by Ben Hutchings
There are potential problems with doing this: some of these hardware
RNGs are probably quite weak, so we have to be very conservative, but
then the less entropy we credit the more CPU time will be spent in the
hardware RNG reader thread.
I gues that what I would like is that at the start it just gets
the entropy it needs, and then keeps feeding it at a low rate, for
instance a few bytes every few seconds. I don't know if that's
something that can be set, or that it currently does.
[...]

khwrngd will block (in add_hwgenerator_randomness()) when the estimated
entropy in the random pool is above a certain threshold, which appears
to be 7/8 of the pool size by default.

Ben.
--
Ben Hutchings
No political challenge can be met by shopping. - George Monbiot
Andy Simpkins
2019-03-07 12:40:01 UTC
Permalink
Post by Kurt Roeckx
- Use a hardware RNG (CPU, TPM, chaos key, ...)
- Credit a seed file stored during the previous boot
- Wait for new entropy from other sources
Note that is can be a combination of all 3.
We currently do not credit the seed file, for various good
reasons. We should provide an option to users that need it to
trust that file and credit that file. Note that it does not need
to be fully trusted, we could for instance say it only provides 64
bits of entropy.
Most people will actually have at least 2 hardware RNGs: One in
the CPU and one in the TPM.
No. This may be true for AMD64 but this is not the case for other platforms

We can make the kernel trust those as
Post by Kurt Roeckx
entropy source without using something in userspace to feed it.
I'm not sure in the kernel has the option to use the TPM directly
as source, but it makes it available as /dev/hwrng. (The TPM might
be disabled in the BIOS.) Some people don't trust them, I suggest
they buy something they do trust, and disable the ones they don't
trust. I think we should trust all hardware RNGs by default, and
then also actually extract data from all of them.
yes - if there is a HRNG we should use it by default. if the user DOES
not want to use this then they are free to disable it (we need to ensure
that this is not a complex procedure)
Post by Kurt Roeckx
Note that the internal state of an RNG is only 256 bit / 32 byte.
If you make that output something, it can't have more than that 256
bit of entropy. It does not make sense to take more bytes of the RNG
than that to feed back in it. It can make sense to do this at
different times, after the RNG has reseeded, but both should be
limited to that 256 bit / 32 byte. It doesn't make sense to do
this at more than 2 different points in time.
There is no point in using an other RNG to stretch something. Just
use the kernel RNG to stretch it by just asking more data from it.
Do not feed the output of the kernel during boot back into the
kernel, even if you don't credit it. If there is something random
in it, the kernel will already have used that. If you do it, there
is no point in using something like md5, the kernel will take care
of that itself.
Other than the entropy you feed it, it can be useful to feed it
data that does not need to be secret but is very likely different
on each boot, including things like the current time, and an
incrementing counter. It would not be credited as having entropy.
agreed - it provides a 'delta' that is especially useful for VMs
(Serial numbers and MACs may be useful sources of 'psudo uniqueness' here
Post by Kurt Roeckx
The seed file currently acts as this. I have no idea if the kernel
does anything like that itself, like the mount count of a
filesystem. It might be useful that we feed it some boot counter.
Kurt
/Andy

Loading...