LinuxLists.cc - [PATCH] random: add blocking facility to urandom

[permalink] [raw]

Subject: [PATCH] random: add blocking facility to urandom

Certain security-related certifications and their respective review
bodies have said that they find use of /dev/urandom for certain
functions, such as setting up ssh connections, is acceptable, but if and
only if /dev/urandom can block after a certain threshold of bytes have
been read from it with the entropy pool exhausted. Initially, we were
investigating increasing entropy pool contributions, so that we could
simply use /dev/random, but since that hasn't (yet) panned out, and
upwards of five minutes to establsh an ssh connection using an
entropy-starved /dev/random is unacceptable, we started looking at the
blocking urandom approach.

At present, urandom never blocks, even after all entropy has been
exhausted from the entropy input pool. random immediately blocks when
the input pool is exhausted. Some use cases want behavior somewhere in
between these two, where blocking only occurs after some number have
bytes have been read following input pool entropy exhaustion. Its
possible to accomplish this and make it fully user-tunable, by adding a
sysctl to set a max-bytes-after-0-entropy read threshold for urandom. In
the out-of-the-box configuration, urandom behaves as it always has, but
with a threshold value set, we'll block when its been exceeded.

Tested by dd'ing from /dev/urandom in one window, and starting/stopping
a cat of /dev/random in the other, with some debug spew added to the
urandom read function to verify functionality.

CC: Matt Mackall <[email protected]>
CC: Neil Horman <[email protected]>
CC: Herbert Xu <[email protected]>
CC: Steve Grubb <[email protected]>
CC: Stephan Mueller <[email protected]>
CC: lkml <[email protected]>
Signed-off-by: Jarod Wilson <[email protected]>
---

Resending, neglected to cc lkml the first time, and this change could
have implications outside just the crypto layer...

drivers/char/random.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++-
1 files changed, 81 insertions(+), 1 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index c35a785..cf48b0f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -289,6 +289,13 @@ static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
static DEFINE_PER_CPU(int, trickle_count);

/*
+ * In normal operation, urandom never blocks, but optionally, you can
+ * set urandom to block after urandom_block_thresh bytes are read with
+ * the entropy pool exhausted.
+ */
+static int urandom_block_thresh = 0;
+
+/*
* A pool of size .poolwords is stirred with a primitive polynomial
* of degree .poolwords over GF(2). The taps for various sizes are
* defined below. They are chosen to be evenly spaced (minimum RMS
@@ -383,6 +390,7 @@ static struct poolinfo {
* Static global variables
*/
static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
+static DECLARE_WAIT_QUEUE_HEAD(urandom_read_wait);
static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
static struct fasync_struct *fasync;

@@ -554,6 +562,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
/* should we wake readers? */
if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {
wake_up_interruptible(&random_read_wait);
+ wake_up_interruptible(&urandom_read_wait);
kill_fasync(&fasync, SIGIO, POLL_IN);
}
spin_unlock_irqrestore(&r->lock, flags);
@@ -1060,7 +1069,55 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
static ssize_t
urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
{
- return extract_entropy_user(&nonblocking_pool, buf, nbytes);
+ ssize_t n;
+ static int excess_bytes_read;
+
+ /* this is the default case with no urandom blocking threshold set */
+ if (!urandom_block_thresh)
+ return extract_entropy_user(&nonblocking_pool, buf, nbytes);
+
+ if (nbytes == 0)
+ return 0;
+
+ DEBUG_ENT("reading %d bits\n", nbytes*8);
+
+ /* urandom blocking threshold set, but we have sufficient entropy */
+ if (input_pool.entropy_count >= random_read_wakeup_thresh) {
+ excess_bytes_read = 0;
+ return extract_entropy_user(&nonblocking_pool, buf, nbytes);
+ }
+
+ /* low on entropy, start counting bytes read */
+ if (excess_bytes_read + nbytes < urandom_block_thresh) {
+ n = extract_entropy_user(&nonblocking_pool, buf, nbytes);
+ excess_bytes_read += n;
+ return n;
+ }
+
+ /* low entropy read threshold exceeded, now we have to block */
+ n = nbytes;
+ if (n > SEC_XFER_SIZE)
+ n = SEC_XFER_SIZE;
+
+ n = extract_entropy_user(&nonblocking_pool, buf, n);
+ excess_bytes_read += n;
+
+ if (file->f_flags & O_NONBLOCK)
+ return -EAGAIN;
+
+ DEBUG_ENT("sleeping?\n");
+
+ wait_event_interruptible(urandom_read_wait,
+ input_pool.entropy_count >= random_read_wakeup_thresh);
+
+ DEBUG_ENT("awake\n");
+
+ if (signal_pending(current))
+ return -ERESTARTSYS;
+
+ excess_bytes_read = 0;
+
+ return n;
}

static unsigned int
@@ -1078,6 +1135,21 @@ random_poll(struct file *file, poll_table * wait)
return mask;
}

+static unsigned int
+urandom_poll(struct file *file, poll_table * wait)
+{
+ unsigned int mask;
+
+ poll_wait(file, &urandom_read_wait, wait);
+ poll_wait(file, &random_write_wait, wait);
+ mask = 0;
+ if (input_pool.entropy_count >= random_read_wakeup_thresh)
+ mask |= POLLIN | POLLRDNORM;
+ if (input_pool.entropy_count < random_write_wakeup_thresh)
+ mask |= POLLOUT | POLLWRNORM;
+ return mask;
+}
+
static int
write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
{
@@ -1178,6 +1250,7 @@ const struct file_operations random_fops = {
const struct file_operations urandom_fops = {
.read = urandom_read,
.write = random_write,
+ .poll = urandom_poll,
.unlocked_ioctl = random_ioctl,
.fasync = random_fasync,
.llseek = noop_llseek,
@@ -1266,6 +1339,13 @@ ctl_table random_table[] = {
.data = &input_pool.entropy_count,
},
{
+ .procname = "urandom_blocking_threshold",
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec,
+ .data = &urandom_block_thresh,
+ },
+ {
.procname = "read_wakeup_threshold",
.data = &random_read_wakeup_thresh,
.maxlen = sizeof(int),
--
1.7.1

2011-09-07 18:13:23

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 13:38 -0400, Jarod Wilson wrote:
> Certain security-related certifications and their respective review
> bodies have said that they find use of /dev/urandom for certain
> functions, such as setting up ssh connections, is acceptable, but if and
> only if /dev/urandom can block after a certain threshold of bytes have
> been read from it with the entropy pool exhausted. Initially, we were
> investigating increasing entropy pool contributions, so that we could
> simply use /dev/random, but since that hasn't (yet) panned out, and
> upwards of five minutes to establsh an ssh connection using an
> entropy-starved /dev/random is unacceptable, we started looking at the
> blocking urandom approach.

Can't you accomplish this in userspace by trying to read as much as you
can out of /dev/random without blocking, then reading out
of /dev/urandom the minimum between allowed threshold and remaining
bytes, and then blocking on /dev/random?

For example, lets say you need 100 bytes of randomness, and your
threshold is 30 bytes. You try reading out of /dev/random and get 50
bytes, at that point you'll read another 30 (=threshold) bytes
out /dev/urandom and then you'll need to block on /dev/random until you
get the remaining 20 bytes.

--

Sasha.

2011-09-07 18:26:40

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Sasha Levin wrote:
> On Wed, 2011-09-07 at 13:38 -0400, Jarod Wilson wrote:
>> Certain security-related certifications and their respective review
>> bodies have said that they find use of /dev/urandom for certain
>> functions, such as setting up ssh connections, is acceptable, but if and
>> only if /dev/urandom can block after a certain threshold of bytes have
>> been read from it with the entropy pool exhausted. Initially, we were
>> investigating increasing entropy pool contributions, so that we could
>> simply use /dev/random, but since that hasn't (yet) panned out, and
>> upwards of five minutes to establsh an ssh connection using an
>> entropy-starved /dev/random is unacceptable, we started looking at the
>> blocking urandom approach.
>
> Can't you accomplish this in userspace by trying to read as much as you
> can out of /dev/random without blocking, then reading out
> of /dev/urandom the minimum between allowed threshold and remaining
> bytes, and then blocking on /dev/random?
>
> For example, lets say you need 100 bytes of randomness, and your
> threshold is 30 bytes. You try reading out of /dev/random and get 50
> bytes, at that point you'll read another 30 (=threshold) bytes
> out /dev/urandom and then you'll need to block on /dev/random until you
> get the remaining 20 bytes.

We're looking for a generic solution here that doesn't require
re-educating every single piece of userspace. And anything done in
userspace is going to be full of possible holes -- there needs to be
something in place that actually *enforces* the policy, and centralized
accounting/tracking, lest you wind up with multiple processes racing to
grab the entropy.

--
Jarod Wilson
[email protected]

2011-09-07 19:05:30

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 14:26 -0400, Jarod Wilson wrote:
> Sasha Levin wrote:
> > On Wed, 2011-09-07 at 13:38 -0400, Jarod Wilson wrote:
> >> Certain security-related certifications and their respective review
> >> bodies have said that they find use of /dev/urandom for certain
> >> functions, such as setting up ssh connections, is acceptable, but if and
> >> only if /dev/urandom can block after a certain threshold of bytes have
> >> been read from it with the entropy pool exhausted. Initially, we were
> >> investigating increasing entropy pool contributions, so that we could
> >> simply use /dev/random, but since that hasn't (yet) panned out, and
> >> upwards of five minutes to establsh an ssh connection using an
> >> entropy-starved /dev/random is unacceptable, we started looking at the
> >> blocking urandom approach.
> >
> > Can't you accomplish this in userspace by trying to read as much as you
> > can out of /dev/random without blocking, then reading out
> > of /dev/urandom the minimum between allowed threshold and remaining
> > bytes, and then blocking on /dev/random?
> >
> > For example, lets say you need 100 bytes of randomness, and your
> > threshold is 30 bytes. You try reading out of /dev/random and get 50
> > bytes, at that point you'll read another 30 (=threshold) bytes
> > out /dev/urandom and then you'll need to block on /dev/random until you
> > get the remaining 20 bytes.
>
> We're looking for a generic solution here that doesn't require
> re-educating every single piece of userspace. [...]

A flip-side here is that you're going to break every piece of userspace
which assumed (correctly) that /dev/urandom never blocks. Since this is
a sysctl you can't fine tune which processes/threads/file-handles will
block on /dev/urandom and which ones won't.

> [..] And anything done in
> userspace is going to be full of possible holes [..]

Such as? Is there an example of a case which can't be handled in
userspace?

> [..] there needs to be
> something in place that actually *enforces* the policy, and centralized
> accounting/tracking, lest you wind up with multiple processes racing to
> grab the entropy.

Does the weak entropy you get out of /dev/urandom get weaker the more
you pull out of it? I assumed that this change is done because you want
to limit the amount of weak entropy mixed in with strong entropy.

btw, Is the threshold based on a research done on the linux RNG? Or is
it an arbitrary number that would be set by your local sysadmin?

--

Sasha.

2011-09-07 19:27:43

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> We're looking for a generic solution here that doesn't require
> re-educating every single piece of userspace. And anything done in
> userspace is going to be full of possible holes -- there needs to be
> something in place that actually *enforces* the policy, and
> centralized accounting/tracking, lest you wind up with multiple
> processes racing to grab the entropy.

Yeah, but there are userspace programs that depend on urandom not
blocking... so your proposed change would break them.

- Ted

2011-09-07 19:30:42

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Sasha Levin wrote:
> On Wed, 2011-09-07 at 14:26 -0400, Jarod Wilson wrote:
>> Sasha Levin wrote:
>>> On Wed, 2011-09-07 at 13:38 -0400, Jarod Wilson wrote:
>>>> Certain security-related certifications and their respective review
>>>> bodies have said that they find use of /dev/urandom for certain
>>>> functions, such as setting up ssh connections, is acceptable, but if and
>>>> only if /dev/urandom can block after a certain threshold of bytes have
>>>> been read from it with the entropy pool exhausted. Initially, we were
>>>> investigating increasing entropy pool contributions, so that we could
>>>> simply use /dev/random, but since that hasn't (yet) panned out, and
>>>> upwards of five minutes to establsh an ssh connection using an
>>>> entropy-starved /dev/random is unacceptable, we started looking at the
>>>> blocking urandom approach.
>>> Can't you accomplish this in userspace by trying to read as much as you
>>> can out of /dev/random without blocking, then reading out
>>> of /dev/urandom the minimum between allowed threshold and remaining
>>> bytes, and then blocking on /dev/random?
>>>
>>> For example, lets say you need 100 bytes of randomness, and your
>>> threshold is 30 bytes. You try reading out of /dev/random and get 50
>>> bytes, at that point you'll read another 30 (=threshold) bytes
>>> out /dev/urandom and then you'll need to block on /dev/random until you
>>> get the remaining 20 bytes.
>> We're looking for a generic solution here that doesn't require
>> re-educating every single piece of userspace. [...]
>
> A flip-side here is that you're going to break every piece of userspace
> which assumed (correctly) that /dev/urandom never blocks.

Out of the box, that continues to be the case. This just adds a knob so
that it *can* block at a desired threshold.

> Since this is
> a sysctl you can't fine tune which processes/threads/file-handles will
> block on /dev/urandom and which ones won't.

The security requirement is that everything blocks.

>> [..] And anything done in
>> userspace is going to be full of possible holes [..]
>
> Such as? Is there an example of a case which can't be handled in
> userspace?

How do you mandate preventing reads from urandom when there isn't
sufficient entropy? You likely wind up needing to restrict access to the
actual urandom via permissions and selinux policy or similar, and then
run a daemon or something that provides a pseudo-urandom that brokers
access to the real urandom. Get the permissions or policy wrong, and
havoc ensues. An issue with the initscript or udev rule to hide the real
urandom, and things can fall down. Its a whole lot more fragile than
this approach, and a lot more involved in setting it up.

>> [..] there needs to be
>> something in place that actually *enforces* the policy, and centralized
>> accounting/tracking, lest you wind up with multiple processes racing to
>> grab the entropy.
>
> Does the weak entropy you get out of /dev/urandom get weaker the more
> you pull out of it? I assumed that this change is done because you want
> to limit the amount of weak entropy mixed in with strong entropy.

The argument is that once there's no entropy left, an attacker only
needs X number of samples before they can start accurately determining
what the next random number will be.

> btw, Is the threshold based on a research done on the linux RNG? Or is
> it an arbitrary number that would be set by your local sysadmin?

Stephan (cc'd on the thread) is attempting to get some feedback from BSI
as to what they have in the way of an actual number. The implementation
has a goal of being flexible enough for whatever a given certification
or security requirement says that number is.

--
Jarod Wilson
[email protected]

2011-09-07 19:35:39

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 10:05:30PM +0300, Sasha Levin wrote:
> On Wed, 2011-09-07 at 14:26 -0400, Jarod Wilson wrote:
> > Sasha Levin wrote:
> > > On Wed, 2011-09-07 at 13:38 -0400, Jarod Wilson wrote:
> > >> Certain security-related certifications and their respective review
> > >> bodies have said that they find use of /dev/urandom for certain
> > >> functions, such as setting up ssh connections, is acceptable, but if and
> > >> only if /dev/urandom can block after a certain threshold of bytes have
> > >> been read from it with the entropy pool exhausted. Initially, we were
> > >> investigating increasing entropy pool contributions, so that we could
> > >> simply use /dev/random, but since that hasn't (yet) panned out, and
> > >> upwards of five minutes to establsh an ssh connection using an
> > >> entropy-starved /dev/random is unacceptable, we started looking at the
> > >> blocking urandom approach.
> > >
> > > Can't you accomplish this in userspace by trying to read as much as you
> > > can out of /dev/random without blocking, then reading out
> > > of /dev/urandom the minimum between allowed threshold and remaining
> > > bytes, and then blocking on /dev/random?
> > >
> > > For example, lets say you need 100 bytes of randomness, and your
> > > threshold is 30 bytes. You try reading out of /dev/random and get 50
> > > bytes, at that point you'll read another 30 (=threshold) bytes
> > > out /dev/urandom and then you'll need to block on /dev/random until you
> > > get the remaining 20 bytes.
> >
> > We're looking for a generic solution here that doesn't require
> > re-educating every single piece of userspace. [...]
>
> A flip-side here is that you're going to break every piece of userspace
> which assumed (correctly) that /dev/urandom never blocks. Since this is
> a sysctl you can't fine tune which processes/threads/file-handles will
> block on /dev/urandom and which ones won't.
>
I'm also squeamish about exactly this - theres no way to allow for applications
that expect a never-block /dev/urandom to co-exist with applications that want
an 'eventually' block /dev/urandom

That said, what about changing the model to make /dev/urandom configurable on a
per-file-descriptor basis, Add an ioctl to the urandom_fops ioctl handler to
specify on a per file struct basis the maximum number of bytes that can be read
past a zero entropy point for that file. The kernel could then track the number
of bytes read per fd after a zero entropy point (clearing it on a read when the
pool has non-zero entropy), and blocking/delaying any call until entropy had
been added back. That way apps the require a non-blocking urandom can co-exist
with apps that have this new requirement, and only the new apps have to be
taught about the additional urandom configuration.
Neil

2011-09-07 19:36:18

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Ted Ts'o wrote:
> On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
>> We're looking for a generic solution here that doesn't require
>> re-educating every single piece of userspace. And anything done in
>> userspace is going to be full of possible holes -- there needs to be
>> something in place that actually *enforces* the policy, and
>> centralized accounting/tracking, lest you wind up with multiple
>> processes racing to grab the entropy.
>
> Yeah, but there are userspace programs that depend on urandom not
> blocking... so your proposed change would break them.

But only if you've set the sysctl to a non-zero value, and even then,
only if someone is actively draining entropy from /dev/random.
Otherwise, in practice, it behaves the same as always. Granted, I
haven't tested with all possible userspace to see how it might fall
down, but suggestions for progs to try would be welcomed.

But again, I want to stress that out of the box, there's absolutely no
change to the way urandom behaves, no blocking, this *only* kicks in if
you twiddle the sysctl because you have some sort of security
requirement that mandates it.

--
Jarod Wilson
[email protected]

2011-09-07 19:49:37

by David Miller

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

From: "Ted Ts'o" <[email protected]>
Date: Wed, 7 Sep 2011 15:27:37 -0400

> On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
>> We're looking for a generic solution here that doesn't require
>> re-educating every single piece of userspace. And anything done in
>> userspace is going to be full of possible holes -- there needs to be
>> something in place that actually *enforces* the policy, and
>> centralized accounting/tracking, lest you wind up with multiple
>> processes racing to grab the entropy.
>
> Yeah, but there are userspace programs that depend on urandom not
> blocking... so your proposed change would break them.

Agreed, and this is a really poor approach to solving the problem.

If you change semantics, you have to create a new facility and then
convert the userland pieces over to it.

Yes, this is harder and requires more work, but it is necessary as
it is the only way to ensure that we won't break something.

2011-09-07 20:00:42

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 15:30 -0400, Jarod Wilson wrote:
> Sasha Levin wrote:
> > On Wed, 2011-09-07 at 14:26 -0400, Jarod Wilson wrote:
> >> Sasha Levin wrote:
> >> [..] And anything done in
> >> userspace is going to be full of possible holes [..]
> >
> > Such as? Is there an example of a case which can't be handled in
> > userspace?
>
> How do you mandate preventing reads from urandom when there isn't
> sufficient entropy? You likely wind up needing to restrict access to the
> actual urandom via permissions and selinux policy or similar, and then
> run a daemon or something that provides a pseudo-urandom that brokers
> access to the real urandom. Get the permissions or policy wrong, and
> havoc ensues. An issue with the initscript or udev rule to hide the real
> urandom, and things can fall down. Its a whole lot more fragile than
> this approach, and a lot more involved in setting it up.

Replace /dev/urandom with a simple CUSE driver, redirect reads to the
real urandom after applying your threshold.

--

Sasha.

2011-09-07 20:02:39

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > We're looking for a generic solution here that doesn't require
> > re-educating every single piece of userspace. And anything done in
> > userspace is going to be full of possible holes -- there needs to be
> > something in place that actually *enforces* the policy, and
> > centralized accounting/tracking, lest you wind up with multiple
> > processes racing to grab the entropy.
>
> Yeah, but there are userspace programs that depend on urandom not
> blocking... so your proposed change would break them.

The only time this kicks in is when a system is under attack. If you have set this and
the system is running as normal, you will never notice it even there. Almost all uses
of urandom grab 4 bytes and seed openssl or libgcrypt or nss. It then uses those
libraries. There are the odd cases where something uses urandom to generate a key or
otherwise grab a chunk of bytes, but these are still small reads in the scheme of
things. Can you think of any legitimate use of urandom that grabs 100K or 1M from
urandom? Even those numbers still won't hit the sysctl on a normally function system.

When a system is underattack, do you really want to be using a PRNG for anything like
seeding openssl? Because a PRNG is what urandom degrades into when its attacked. If
enough bytes are read that an attacker can guess the internal state of the RNG, do you
really want it seeding a openssh session? At that point you really need it to stop
momentarily until it gets fresh entropy so the internal state is unknown. That's what
this is really about.

-Steve

2011-09-07 20:23:36

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > We're looking for a generic solution here that doesn't require
> > > re-educating every single piece of userspace. And anything done in
> > > userspace is going to be full of possible holes -- there needs to be
> > > something in place that actually *enforces* the policy, and
> > > centralized accounting/tracking, lest you wind up with multiple
> > > processes racing to grab the entropy.
> >
> > Yeah, but there are userspace programs that depend on urandom not
> > blocking... so your proposed change would break them.
>
> The only time this kicks in is when a system is under attack. If you have set this and
> the system is running as normal, you will never notice it even there. Almost all uses
> of urandom grab 4 bytes and seed openssl or libgcrypt or nss. It then uses those
> libraries. There are the odd cases where something uses urandom to generate a key or
> otherwise grab a chunk of bytes, but these are still small reads in the scheme of
> things. Can you think of any legitimate use of urandom that grabs 100K or 1M from
> urandom? Even those numbers still won't hit the sysctl on a normally function system.
>

As far as I remember, several wipe utilities are using /dev/urandom to
overwrite disks (possibly several times).

Something similar probably happens for getting junk on disks before
creating an encrypted filesystem on top of them.

--

Sasha.

2011-09-07 20:30:30

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
> On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > We're looking for a generic solution here that doesn't require
> > > > re-educating every single piece of userspace. And anything done in
> > > > userspace is going to be full of possible holes -- there needs to be
> > > > something in place that actually *enforces* the policy, and
> > > > centralized accounting/tracking, lest you wind up with multiple
> > > > processes racing to grab the entropy.
> > >
> > > Yeah, but there are userspace programs that depend on urandom not
> > > blocking... so your proposed change would break them.
> >
> > The only time this kicks in is when a system is under attack. If you have
> > set this and the system is running as normal, you will never notice it
> > even there. Almost all uses of urandom grab 4 bytes and seed openssl or
> > libgcrypt or nss. It then uses those libraries. There are the odd cases
> > where something uses urandom to generate a key or otherwise grab a chunk
> > of bytes, but these are still small reads in the scheme of things. Can
> > you think of any legitimate use of urandom that grabs 100K or 1M from
> > urandom? Even those numbers still won't hit the sysctl on a normally
> > function system.
>
> As far as I remember, several wipe utilities are using /dev/urandom to
> overwrite disks (possibly several times).

Which should generate disk activity and feed entropy to urandom.

> Something similar probably happens for getting junk on disks before
> creating an encrypted filesystem on top of them.

During system install, this sysctl is not likely to be applied.

-Steve

2011-09-07 20:33:15

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 04:02:24PM -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > We're looking for a generic solution here that doesn't require
> > > re-educating every single piece of userspace. And anything done in
> > > userspace is going to be full of possible holes -- there needs to be
> > > something in place that actually *enforces* the policy, and
> > > centralized accounting/tracking, lest you wind up with multiple
> > > processes racing to grab the entropy.
> >
> > Yeah, but there are userspace programs that depend on urandom not
> > blocking... so your proposed change would break them.
>
> The only time this kicks in is when a system is under attack. If you have set this and
> the system is running as normal, you will never notice it even there. Almost all uses
> of urandom grab 4 bytes and seed openssl or libgcrypt or nss. It then uses those
> libraries. There are the odd cases where something uses urandom to generate a key or
> otherwise grab a chunk of bytes, but these are still small reads in the scheme of
Theres no way you can guarantee that. A quick lsof on my system here shows 27
unique pids that are holding /dev/urandom open, and while they may all be small reads,
taken in aggregate, I can imagine that they could pull a significant amount of
entropy out of /dev/urandom.

> things. Can you think of any legitimate use of urandom that grabs 100K or 1M from
> urandom? Even those numbers still won't hit the sysctl on a normally function system.
>
How can you be sure of that? This seems to make assumptions about both the rate
at which entropy is drained from /dev/urandom and the limit at which you will
start blocking, neither of which you can be sure of.

> When a system is underattack, do you really want to be using a PRNG for anything like
How can you be sure that this only happens when a system is under some sort of
attack. /dev/urandom is there for user space to use, and we can't make
assumptions as to how it will get drawn from. What if someone was running some
monte-carlo based test program? That could completely exhaust the entropy in
/dev/urandom and would be perfectly legitimate.

> seeding openssl? Because a PRNG is what urandom degrades into when its attacked. If
> enough bytes are read that an attacker can guess the internal state of the RNG, do you
> really want it seeding a openssh session? At that point you really need it to stop
> momentarily until it gets fresh entropy so the internal state is unknown. That's what
> this is really about.
I never really want my ssh session to be be seeded with non-random data. Of
course, in my mind thats an argument for making ssh use /dev/random rather than
/dev/urandom, but I'm willing to take the tradeoff in speed most of the time.

>
> -Steve

2011-09-07 20:38:20

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 16:30 -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
> > On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> > > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > > We're looking for a generic solution here that doesn't require
> > > > > re-educating every single piece of userspace. And anything done in
> > > > > userspace is going to be full of possible holes -- there needs to be
> > > > > something in place that actually *enforces* the policy, and
> > > > > centralized accounting/tracking, lest you wind up with multiple
> > > > > processes racing to grab the entropy.
> > > >
> > > > Yeah, but there are userspace programs that depend on urandom not
> > > > blocking... so your proposed change would break them.
> > >
> > > The only time this kicks in is when a system is under attack. If you have
> > > set this and the system is running as normal, you will never notice it
> > > even there. Almost all uses of urandom grab 4 bytes and seed openssl or
> > > libgcrypt or nss. It then uses those libraries. There are the odd cases
> > > where something uses urandom to generate a key or otherwise grab a chunk
> > > of bytes, but these are still small reads in the scheme of things. Can
> > > you think of any legitimate use of urandom that grabs 100K or 1M from
> > > urandom? Even those numbers still won't hit the sysctl on a normally
> > > function system.
> >
> > As far as I remember, several wipe utilities are using /dev/urandom to
> > overwrite disks (possibly several times).
>
> Which should generate disk activity and feed entropy to urandom.

I thought you need to feed random, not urandom.

Anyway, it won't happen fast enough to actually not block.

Writing 1TB of urandom into a disk won't generate 1TB (or anything close
to that) of randomness to cover for itself.

> > Something similar probably happens for getting junk on disks before
> > creating an encrypted filesystem on top of them.
>
> During system install, this sysctl is not likely to be applied.

It may happen at any time you need to create a new filesystem, which
won't necessarily happen during system install.

See for example the instructions on how to set up a LUKS filesystem:
https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Preparation_and_mapping

--

Sasha.

2011-09-07 20:49:12

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 04:33:05 PM Neil Horman wrote:
> On Wed, Sep 07, 2011 at 04:02:24PM -0400, Steve Grubb wrote:
> > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > We're looking for a generic solution here that doesn't require
> > > > re-educating every single piece of userspace. And anything done in
> > > > userspace is going to be full of possible holes -- there needs to be
> > > > something in place that actually *enforces* the policy, and
> > > > centralized accounting/tracking, lest you wind up with multiple
> > > > processes racing to grab the entropy.
> > >
> > > Yeah, but there are userspace programs that depend on urandom not
> > > blocking... so your proposed change would break them.
> >
> > The only time this kicks in is when a system is under attack. If you have
> > set this and the system is running as normal, you will never notice it
> > even there. Almost all uses of urandom grab 4 bytes and seed openssl or
> > libgcrypt or nss. It then uses those libraries. There are the odd cases
> > where something uses urandom to generate a key or otherwise grab a chunk
> > of bytes, but these are still small reads in the scheme of
>
> Theres no way you can guarantee that. A quick lsof on my system here shows
> 27 unique pids that are holding /dev/urandom open, and while they may all
> be small reads, taken in aggregate, I can imagine that they could pull a
> significant amount of entropy out of /dev/urandom.

These are likely for reseeding purposes. Even openssl/libgcrypt/nss need reseeding.

> > things. Can you think of any legitimate use of urandom that grabs 100K or
> > 1M from urandom? Even those numbers still won't hit the sysctl on a
> > normally function system.
>
> How can you be sure of that? This seems to make assumptions about both the
> rate at which entropy is drained from /dev/urandom and the limit at which
> you will start blocking, neither of which you can be sure of.

You can try Jarod's patch for a day or two and see if it affects your system.

> > When a system is underattack, do you really want to be using a PRNG for
> > anything like
>
> How can you be sure that this only happens when a system is under some sort
> of attack. /dev/urandom is there for user space to use, and we can't make
> assumptions as to how it will get drawn from. What if someone was running
> some monte-carlo based test program? That could completely exhaust the
> entropy in /dev/urandom and would be perfectly legitimate.

I doubt a Monte-Carlo simulation will be done in a high security setting where they
also depend entirely on a PRNG.

> > seeding openssl? Because a PRNG is what urandom degrades into when its
> > attacked. If enough bytes are read that an attacker can guess the
> > internal state of the RNG, do you really want it seeding a openssh
> > session? At that point you really need it to stop momentarily until it
> > gets fresh entropy so the internal state is unknown. That's what this is
> > really about.
>
> I never really want my ssh session to be be seeded with non-random data.
> Of course, in my mind thats an argument for making ssh use /dev/random
> rather than /dev/urandom, but I'm willing to take the tradeoff in speed
> most of the time.

Bingo! You hit the problem. In some of our tests, it was shown that it takes 4 minutes
to establish a connection when using random. So, if the system is under attack, the
seeding of openssh will be based on the output of a RNG where the attacker might be
able to guess the internal state. This is a problem we have right now. It not
theoretical. The best solution is Jarod's patch because any other solution will
require teaching all of user space about the new RNG and dressing it up for FIPS-140.
At that point, what's the difference?

-Steve

2011-09-07 20:57:05

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
> On Wed, 2011-09-07 at 16:30 -0400, Steve Grubb wrote:
> > On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
> > > On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> > > > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > > > We're looking for a generic solution here that doesn't require
> > > > > > re-educating every single piece of userspace. And anything done
> > > > > > in userspace is going to be full of possible holes -- there
> > > > > > needs to be something in place that actually *enforces* the
> > > > > > policy, and centralized accounting/tracking, lest you wind up
> > > > > > with multiple processes racing to grab the entropy.
> > > > >
> > > > > Yeah, but there are userspace programs that depend on urandom not
> > > > > blocking... so your proposed change would break them.
> > > >
> > > > The only time this kicks in is when a system is under attack. If you
> > > > have set this and the system is running as normal, you will never
> > > > notice it even there. Almost all uses of urandom grab 4 bytes and
> > > > seed openssl or libgcrypt or nss. It then uses those libraries.
> > > > There are the odd cases where something uses urandom to generate a
> > > > key or otherwise grab a chunk of bytes, but these are still small
> > > > reads in the scheme of things. Can you think of any legitimate use
> > > > of urandom that grabs 100K or 1M from urandom? Even those numbers
> > > > still won't hit the sysctl on a normally function system.
> > >
> > > As far as I remember, several wipe utilities are using /dev/urandom to
> > > overwrite disks (possibly several times).
> >
> > Which should generate disk activity and feed entropy to urandom.
>
> I thought you need to feed random, not urandom.

I think they draw from the same pool.

> Anyway, it won't happen fast enough to actually not block.
>
> Writing 1TB of urandom into a disk won't generate 1TB (or anything close
> to that) of randomness to cover for itself.

We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
8,000,000:1 or higher.

> > > Something similar probably happens for getting junk on disks before
> > > creating an encrypted filesystem on top of them.
> >
> > During system install, this sysctl is not likely to be applied.
>
> It may happen at any time you need to create a new filesystem, which
> won't necessarily happen during system install.
>
> See for example the instructions on how to set up a LUKS filesystem:
> https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Preparatio
> n_and_mapping

Those instructions might need to be changed. That is one way of many to get random
numbers on the disk. Anyone really needing the security to have the sysctl on will
also probably accept that its doing its job and keeping the numbers random. Again, no
effect unless you turn it on.

-Steve

2011-09-07 21:10:50

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 16:56 -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
> > On Wed, 2011-09-07 at 16:30 -0400, Steve Grubb wrote:
> > > On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
> > > > On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> > > > > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > > > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > > > > We're looking for a generic solution here that doesn't require
> > > > > > > re-educating every single piece of userspace. And anything done
> > > > > > > in userspace is going to be full of possible holes -- there
> > > > > > > needs to be something in place that actually *enforces* the
> > > > > > > policy, and centralized accounting/tracking, lest you wind up
> > > > > > > with multiple processes racing to grab the entropy.
> > > > > >
> > > > > > Yeah, but there are userspace programs that depend on urandom not
> > > > > > blocking... so your proposed change would break them.
> > > > >
> > > > > The only time this kicks in is when a system is under attack. If you
> > > > > have set this and the system is running as normal, you will never
> > > > > notice it even there. Almost all uses of urandom grab 4 bytes and
> > > > > seed openssl or libgcrypt or nss. It then uses those libraries.
> > > > > There are the odd cases where something uses urandom to generate a
> > > > > key or otherwise grab a chunk of bytes, but these are still small
> > > > > reads in the scheme of things. Can you think of any legitimate use
> > > > > of urandom that grabs 100K or 1M from urandom? Even those numbers
> > > > > still won't hit the sysctl on a normally function system.
> > > >
> > > > As far as I remember, several wipe utilities are using /dev/urandom to
> > > > overwrite disks (possibly several times).
> > >
> > > Which should generate disk activity and feed entropy to urandom.
> >
> > I thought you need to feed random, not urandom.
>
> I think they draw from the same pool.

There is a blocking and a non blocking pool.

>
> > Anyway, it won't happen fast enough to actually not block.
> >
> > Writing 1TB of urandom into a disk won't generate 1TB (or anything close
> > to that) of randomness to cover for itself.
>
> We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
> 8,000,000:1 or higher.

I'm just saying that writing 1TB into a disk using urandom will start to
block, it won't generate enough randomness by itself.

>
> > > > Something similar probably happens for getting junk on disks before
> > > > creating an encrypted filesystem on top of them.
> > >
> > > During system install, this sysctl is not likely to be applied.
> >
> > It may happen at any time you need to create a new filesystem, which
> > won't necessarily happen during system install.
> >
> > See for example the instructions on how to set up a LUKS filesystem:
> > https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Preparatio
> > n_and_mapping
>
> Those instructions might need to be changed. That is one way of many to get random
> numbers on the disk. Anyone really needing the security to have the sysctl on will
> also probably accept that its doing its job and keeping the numbers random. Again, no
> effect unless you turn it on.

There are bunch of other places that would need to be changed in that
case :)

Why not implement it as a user mode CUSE driver that would
wrap /dev/urandom and make it behave any way you want to? why push it
into the kernel?

--

Sasha.

2011-09-07 21:19:06

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 04:02:24PM -0400, Steve Grubb wrote:
>
> When a system is underattack, do you really want to be using a PRNG
> for anything like seeding openssl? Because a PRNG is what urandom
> degrades into when its attacked.

This is not technically true. urandom degrades into a CRNG
(cryptographic random number generator). In fact what most security
experts recommend is to take a small amount of security, and then use
that to seed a CRNG.

> If enough bytes are read that an
> attacker can guess the internal state of the RNG, do you really want
> it seeding a openssh session?

In a cryptographic random number generator, there is a either a
cryptographic hash or a encryption algorithm at the core. So you
would need a huge amounts of bytes, and then you would have to carry
out an attack on the cryptographic core.

If this is the basis for the patch, then we should definitely NACK it.
It sounds like snake oil fear mongering.

- Ted

2011-09-07 21:20:37

by Nikos Mavrogiannopoulos

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On 09/07/2011 10:02 PM, Steve Grubb wrote:

> When a system is underattack, do you really want to be using a PRNG
> for anything like seeding openssl? Because a PRNG is what urandom
> degrades into when its attacked.

Using a PRNG is not a problem. Making sure it is well seeded and no
input from the attacker can compromise its state are the difficult
parts. Making predictable estimates and blocking when your estimates are
off, makes it a good target for DoS. When your system is under attack,
you want to use your services. If they block then the attack might
have just been successful.

regards,
Nikos

2011-09-07 21:27:22

by Stephan Mueller

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On 07.09.2011 23:18:58, +0200, Ted Ts'o <[email protected]> wrote:

Hi Ted,

> On Wed, Sep 07, 2011 at 04:02:24PM -0400, Steve Grubb wrote:
>>
>> When a system is underattack, do you really want to be using a PRNG
>> for anything like seeding openssl? Because a PRNG is what urandom
>> degrades into when its attacked.
>
> This is not technically true. urandom degrades into a CRNG
> (cryptographic random number generator). In fact what most security
> experts recommend is to take a small amount of security, and then use
> that to seed a CRNG.

Correct.

However, a CRNG shall be reseeded once in a while - see standard crypto
libraries and their CRNGs (OpenSSL being a notable exception here). And
that is what this entire discussion is all about: to ensure that the
CRNG is reseeded with entropy, eventually.

>
>> If enough bytes are read that an
>> attacker can guess the internal state of the RNG, do you really want
>> it seeding a openssh session?
>
> In a cryptographic random number generator, there is a either a
> cryptographic hash or a encryption algorithm at the core. So you
> would need a huge amounts of bytes, and then you would have to carry
> out an attack on the cryptographic core.

Correct.

And exactly that is the concern from organizations like BSI. Their
cryptographer's concern is that due to the volume of data that you can
extract from /dev/urandom, you may find cycles or patterns that increase
the probability to guess the next random value compared to brute force
attack. Note, it is all about probabilities.
>
> If this is the basis for the patch, then we should definitely NACK it.
> It sounds like snake oil fear mongering.
>
> - Ted
>
>
>

--
Ciao
Stephan

2011-09-07 21:28:46

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 05:10:27 PM Sasha Levin wrote:
> > > > > Something similar probably happens for getting junk on disks before
> > > > > creating an encrypted filesystem on top of them.
> > > >
> > > > During system install, this sysctl is not likely to be applied.
> > >
> > > It may happen at any time you need to create a new filesystem, which
> > > won't necessarily happen during system install.
> > >
> > > See for example the instructions on how to set up a LUKS filesystem:
> > > https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Prepar
> > > atio n_and_mapping
> >
> > Those instructions might need to be changed. That is one way of many to
> > get random numbers on the disk. Anyone really needing the security to
> > have the sysctl on will also probably accept that its doing its job and
> > keeping the numbers random. Again, no effect unless you turn it on.
>
> There are bunch of other places that would need to be changed in that
> case :)
>
> Why not implement it as a user mode CUSE driver that would
> wrap /dev/urandom and make it behave any way you want to? why push it
> into the kernel?

For one, auditing does not work for FUSE or things like that. We have to be able to
audit who is using what. Then there are the FIPS-140 requirements and this will spread
it. There are problems sending crypto audit events from user space, too.

-Steve

2011-09-07 21:35:23

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Sasha Levin wrote:
> On Wed, 2011-09-07 at 16:56 -0400, Steve Grubb wrote:
>> On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
>>> On Wed, 2011-09-07 at 16:30 -0400, Steve Grubb wrote:
>>>> On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
>>>>> On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
>>>>>> On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
>>>>>>> On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
>>>>>>>> We're looking for a generic solution here that doesn't require
>>>>>>>> re-educating every single piece of userspace. And anything done
>>>>>>>> in userspace is going to be full of possible holes -- there
>>>>>>>> needs to be something in place that actually *enforces* the
>>>>>>>> policy, and centralized accounting/tracking, lest you wind up
>>>>>>>> with multiple processes racing to grab the entropy.
>>>>>>> Yeah, but there are userspace programs that depend on urandom not
>>>>>>> blocking... so your proposed change would break them.
>>>>>> The only time this kicks in is when a system is under attack. If you
>>>>>> have set this and the system is running as normal, you will never
>>>>>> notice it even there. Almost all uses of urandom grab 4 bytes and
>>>>>> seed openssl or libgcrypt or nss. It then uses those libraries.
>>>>>> There are the odd cases where something uses urandom to generate a
>>>>>> key or otherwise grab a chunk of bytes, but these are still small
>>>>>> reads in the scheme of things. Can you think of any legitimate use
>>>>>> of urandom that grabs 100K or 1M from urandom? Even those numbers
>>>>>> still won't hit the sysctl on a normally function system.
>>>>> As far as I remember, several wipe utilities are using /dev/urandom to
>>>>> overwrite disks (possibly several times).
>>>> Which should generate disk activity and feed entropy to urandom.
>>> I thought you need to feed random, not urandom.
>> I think they draw from the same pool.
>
> There is a blocking and a non blocking pool.

There's a single shared input pool that both the blocking and
non-blocking pools pull from. New entropy data is added to the input
pool, then transferred to the interface-specific pools as needed.

>>> Anyway, it won't happen fast enough to actually not block.
>>>
>>> Writing 1TB of urandom into a disk won't generate 1TB (or anything close
>>> to that) of randomness to cover for itself.
>> We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
>> 8,000,000:1 or higher.
>
> I'm just saying that writing 1TB into a disk using urandom will start to
> block, it won't generate enough randomness by itself.

Writing 1TB of data to a disk using urandom won't block at all if nobody
is using /dev/random. We seed /dev/urandom with entropy, then it just
behaves as a Cryptographic RNG, its not pulling out any further entropy
data until it needs to reseed, and thus the entropy count isn't dropping
to 0, so we're not blocking. Someone has to actually drain the entropy,
typically by pulling a fair bit of data from /dev/random, for the
blocking to actually come into play.

> Why not implement it as a user mode CUSE driver that would
> wrap /dev/urandom and make it behave any way you want to? why push it
> into the kernel?

Hadn't considered CUSE. But it does have the issues Steve mentioned in
his earlier reply.

Another proposal that has been kicked around: a 3rd random chardev,
which implements this functionality, leaving urandom unscathed. Some
udev magic or a driver param could move/disable/whatever urandom and put
this alternate device in its place. Ultimately, identical behavior, but
the true urandom doesn't get altered at all.

--
Jarod Wilson
[email protected]

2011-09-07 21:38:51

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 11:27:12PM +0200, Stephan Mueller wrote:
>
> And exactly that is the concern from organizations like BSI. Their
> cryptographer's concern is that due to the volume of data that you can
> extract from /dev/urandom, you may find cycles or patterns that increase
> the probability to guess the next random value compared to brute force
> attack. Note, it is all about probabilities.

The internal state of urandom is huge, and it does automatically
reseed. If you can find cycles that are significantly smaller than
what would be expected by the size of the internal state, (or any kind
of pattern at all) then there would be significant flaws in the crypto
algorithm used.

If the BSI folks think otherwise, then they're peddling snake oil FUD
(which is not unusual for security companies).

- Ted

2011-09-07 21:38:31

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 17:28 -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 05:10:27 PM Sasha Levin wrote:
> > > > > > Something similar probably happens for getting junk on disks before
> > > > > > creating an encrypted filesystem on top of them.
> > > > >
> > > > > During system install, this sysctl is not likely to be applied.
> > > >
> > > > It may happen at any time you need to create a new filesystem, which
> > > > won't necessarily happen during system install.
> > > >
> > > > See for example the instructions on how to set up a LUKS filesystem:
> > > > https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Prepar
> > > > atio n_and_mapping
> > >
> > > Those instructions might need to be changed. That is one way of many to
> > > get random numbers on the disk. Anyone really needing the security to
> > > have the sysctl on will also probably accept that its doing its job and
> > > keeping the numbers random. Again, no effect unless you turn it on.
> >
> > There are bunch of other places that would need to be changed in that
> > case :)
> >
> > Why not implement it as a user mode CUSE driver that would
> > wrap /dev/urandom and make it behave any way you want to? why push it
> > into the kernel?
>
> For one, auditing does not work for FUSE or things like that. We have to be able to
> audit who is using what. Then there are the FIPS-140 requirements and this will spread
> it. There are problems sending crypto audit events from user space, too.

auditd doesn't work with FUSE? afaik it should, FUSE is a filesystem
like any other.

--

Sasha.

2011-09-07 21:43:36

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wednesday, September 07, 2011 05:35:18 PM Jarod Wilson wrote:
> Another proposal that has been kicked around: a 3rd random chardev,
> which implements this functionality, leaving urandom unscathed. Some
> udev magic or a driver param could move/disable/whatever urandom and put
> this alternate device in its place. Ultimately, identical behavior, but
> the true urandom doesn't get altered at all.

Right, and that's what I was trying to say is that if we do all that and switch out
urandom with something new that does what we need, what's the difference in just
patching the behavior into urandom and calling it a day? Its simpler, less fragile,
admins won't make mistakes setting up the wrong one in a chroot, already has the
FIPS-140 dressing, and is auditable.

-Steve

2011-09-07 22:58:09

by Sven-Haegar Koch

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 7 Sep 2011, Steve Grubb wrote:

> On Wednesday, September 07, 2011 05:35:18 PM Jarod Wilson wrote:
> > Another proposal that has been kicked around: a 3rd random chardev,
> > which implements this functionality, leaving urandom unscathed. Some
> > udev magic or a driver param could move/disable/whatever urandom and put
> > this alternate device in its place. Ultimately, identical behavior, but
> > the true urandom doesn't get altered at all.
>
> Right, and that's what I was trying to say is that if we do all that and switch out
> urandom with something new that does what we need, what's the difference in just
> patching the behavior into urandom and calling it a day? Its simpler, less fragile,
> admins won't make mistakes setting up the wrong one in a chroot, already has the
> FIPS-140 dressing, and is auditable.

I as a 0815 admin would never want such a thing by default.

I already replace /dev/random with /dev/urandom to keep stupid sshd from
dying because there just is no entropy - I care more about all my
services staying alive than about perfect random.

c'ya
sven-haegar

--
Three may keep a secret, if two of them are dead.
- Ben F.

2011-09-07 23:57:50

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 04:56:49PM -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
> > On Wed, 2011-09-07 at 16:30 -0400, Steve Grubb wrote:
> > > On Wednesday, September 07, 2011 04:23:13 PM Sasha Levin wrote:
> > > > On Wed, 2011-09-07 at 16:02 -0400, Steve Grubb wrote:
> > > > > On Wednesday, September 07, 2011 03:27:37 PM Ted Ts'o wrote:
> > > > > > On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> > > > > > > We're looking for a generic solution here that doesn't require
> > > > > > > re-educating every single piece of userspace. And anything done
> > > > > > > in userspace is going to be full of possible holes -- there
> > > > > > > needs to be something in place that actually *enforces* the
> > > > > > > policy, and centralized accounting/tracking, lest you wind up
> > > > > > > with multiple processes racing to grab the entropy.
> > > > > >
> > > > > > Yeah, but there are userspace programs that depend on urandom not
> > > > > > blocking... so your proposed change would break them.
> > > > >
> > > > > The only time this kicks in is when a system is under attack. If you
> > > > > have set this and the system is running as normal, you will never
> > > > > notice it even there. Almost all uses of urandom grab 4 bytes and
> > > > > seed openssl or libgcrypt or nss. It then uses those libraries.
> > > > > There are the odd cases where something uses urandom to generate a
> > > > > key or otherwise grab a chunk of bytes, but these are still small
> > > > > reads in the scheme of things. Can you think of any legitimate use
> > > > > of urandom that grabs 100K or 1M from urandom? Even those numbers
> > > > > still won't hit the sysctl on a normally function system.
> > > >
> > > > As far as I remember, several wipe utilities are using /dev/urandom to
> > > > overwrite disks (possibly several times).
> > >
> > > Which should generate disk activity and feed entropy to urandom.
> >
> > I thought you need to feed random, not urandom.
>
> I think they draw from the same pool.
>
They share the primary pool, where timer/interrupt/etc randomness is fed in.
/dev/random and /dev/urandom each have their own secondary pools however.

>
> > Anyway, it won't happen fast enough to actually not block.
> >
> > Writing 1TB of urandom into a disk won't generate 1TB (or anything close
> > to that) of randomness to cover for itself.
>
> We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
> 8,000,000:1 or higher.
>
Where are you getting that number from?

You may not need it, but there are other people using this facility as well that
you're not considering. If you assume that in the example Sasha has given, if
conservatively, you have a modern disk with 4k sectors, and you fill each 4k
sector with the value obtained from a 4 byte read from /dev/urandom, You will:

1) Generate an interrupt for every page you write, which in turn will add at
most 12 bits to the entropy pool

2) Extract 32 bits from the entropy pool

Thats just a loosing proposition. Barring further entropy generation from
another source, this is bound to stall with this feature enabled.

>
> > > > Something similar probably happens for getting junk on disks before
> > > > creating an encrypted filesystem on top of them.
> > >
> > > During system install, this sysctl is not likely to be applied.
> >
> > It may happen at any time you need to create a new filesystem, which
> > won't necessarily happen during system install.
> >
> > See for example the instructions on how to set up a LUKS filesystem:
> > https://wiki.archlinux.org/index.php/System_Encryption_with_LUKS#Preparatio
> > n_and_mapping
>
> Those instructions might need to be changed. That is one way of many to get random
> numbers on the disk. Anyone really needing the security to have the sysctl on will
> also probably accept that its doing its job and keeping the numbers random. Again, no
> effect unless you turn it on.
>

And then its enforced on everyone, even those applications that don't want
it/can't work with it on. This has to be done in such a way that its opt-in on
a per-application basis. The CUSE idea put up previously sounds like a pretty
good way to do this. The ioctl for per-fd blocking thresholds is another way to
go.

Neil

> -Steve

2011-09-08 02:43:39

by Sandy Harris

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Jarod Wilson <[email protected]> wrote:

> Ted Ts'o wrote:

>> Yeah, but there are userspace programs that depend on urandom not
>> blocking... so your proposed change would break them.
>> ...

> But only if you've set the sysctl to a non-zero value, ...
>
> But again, I want to stress that out of the box, there's absolutely no
> change to the way urandom behaves, no blocking, this *only* kicks in if you
> twiddle the sysctl because you have some sort of security requirement that
> mandates it.

So it only breaks things on systems with high security requirements?

2011-09-08 06:42:09

by Tomas Mraz

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 19:57 -0400, Neil Horman wrote:
> On Wed, Sep 07, 2011 at 04:56:49PM -0400, Steve Grubb wrote:
> > On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
> > > Anyway, it won't happen fast enough to actually not block.
> > >
> > > Writing 1TB of urandom into a disk won't generate 1TB (or anything close
> > > to that) of randomness to cover for itself.
> >
> > We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
> > 8,000,000:1 or higher.
> >
> Where are you getting that number from?
>
> You may not need it, but there are other people using this facility as well that
> you're not considering. If you assume that in the example Sasha has given, if
> conservatively, you have a modern disk with 4k sectors, and you fill each 4k
> sector with the value obtained from a 4 byte read from /dev/urandom, You will:
>
> 1) Generate an interrupt for every page you write, which in turn will add at
> most 12 bits to the entropy pool
>
> 2) Extract 32 bits from the entropy pool
>
> Thats just a loosing proposition. Barring further entropy generation from
> another source, this is bound to stall with this feature enabled.
Why so? In the case the blocking limit is on 8MBits of data read
from /dev/urandom per every 1 bit added to the entropy pool (this is not
the exact way how the patch behaves but we can approximate that) I do
not see the /dev/urandom can block if the bytes read from it are written
to disk device - of course only if the device adds entropy into the
primary pool when there are writes on the device.

Of course you can still easily make the /dev/urandom to occasionally
block with this patch, just read the data and drop it.

But you have to understand that the value that will be set with the
sysctl added by this patch will be large in the order of millions of
bits.

--
Tomas Mraz
No matter how far down the wrong road you've gone, turn back.
Turkish proverb

2011-09-08 07:21:23

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, 2011-09-07 at 17:43 -0400, Steve Grubb wrote:
> On Wednesday, September 07, 2011 05:35:18 PM Jarod Wilson wrote:
> > Another proposal that has been kicked around: a 3rd random chardev,
> > which implements this functionality, leaving urandom unscathed. Some
> > udev magic or a driver param could move/disable/whatever urandom and put
> > this alternate device in its place. Ultimately, identical behavior, but
> > the true urandom doesn't get altered at all.
>
> Right, and that's what I was trying to say is that if we do all that and switch out
> urandom with something new that does what we need, what's the difference in just
> patching the behavior into urandom and calling it a day? Its simpler, less fragile,
> admins won't make mistakes setting up the wrong one in a chroot, already has the
> FIPS-140 dressing, and is auditable.

Whats the difference between changing the behavior of a well defined
interface (/dev/urandom) which may cause userspace applications to fail,
in opposed to a non-intrusive usermode CUSE driver which can do exactly
what you need (and more - if more is required in the future)? None, none
at all...

CUSE supports kernel auditing, admins making mistakes is hardly the
kernels' problem (unless it makes it easy for them to do mistakes) and
code moved into the kernel doesn't suddenly become more stable and
simpler.

--

Sasha.

2011-09-08 08:41:54

by Christoph Hellwig

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 04:02:24PM -0400, Steve Grubb wrote:
> The only time this kicks in is when a system is under attack. If you have set this and
> the system is running as normal, you will never notice it even there.

So your userspace will break exactly when you least need it and can't
debug it, awsome.

Could you security certification folks please get off your crack ASAP?

2011-09-08 08:43:01

by Christoph Hellwig

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 05:18:58PM -0400, Ted Ts'o wrote:
> If this is the basis for the patch, then we should definitely NACK it.
> It sounds like snake oil fear mongering.

You're around long enough to know that Steve and his gang do nothing but
selling snake oil.

2011-09-08 08:44:24

by Christoph Hellwig

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Wed, Sep 07, 2011 at 11:27:12PM +0200, Stephan Mueller wrote:
> And exactly that is the concern from organizations like BSI. Their
> cryptographer's concern is that due to the volume of data that you can
> extract from /dev/urandom, you may find cycles or patterns that increase
> the probability to guess the next random value compared to brute force
> attack. Note, it is all about probabilities.

So don't use /dev/urandom if you don't like the behaviour. Breaking all
existing application because of a certification is simply not an option.

2011-09-08 11:49:11

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thursday, September 08, 2011 04:44:20 AM Christoph Hellwig wrote:
> On Wed, Sep 07, 2011 at 11:27:12PM +0200, Stephan Mueller wrote:
> > And exactly that is the concern from organizations like BSI. Their
> > cryptographer's concern is that due to the volume of data that you can
> > extract from /dev/urandom, you may find cycles or patterns that increase
> > the probability to guess the next random value compared to brute force
> > attack. Note, it is all about probabilities.
>
> So don't use /dev/urandom if you don't like the behaviour. Breaking all
> existing application because of a certification is simply not an option.

This patch does not _break_ all existing applications. If a system were under attack,
they might pause momentarily, but they do not break. Please, try the patch and use a
nice large number like 2000000 and see for yourself. Right now, everyone arguing about
this breaking things have not tried it to see if in fact things do break and how they
break if they do.

-Steve

2011-09-08 12:52:46

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thu, Sep 08, 2011 at 08:41:57AM +0200, Tomas Mraz wrote:
> On Wed, 2011-09-07 at 19:57 -0400, Neil Horman wrote:
> > On Wed, Sep 07, 2011 at 04:56:49PM -0400, Steve Grubb wrote:
> > > On Wednesday, September 07, 2011 04:37:57 PM Sasha Levin wrote:
> > > > Anyway, it won't happen fast enough to actually not block.
> > > >
> > > > Writing 1TB of urandom into a disk won't generate 1TB (or anything close
> > > > to that) of randomness to cover for itself.
> > >
> > > We don't need a 1:1 mapping of RNG used to entropy acquired. Its more on the scale of
> > > 8,000,000:1 or higher.
> > >
> > Where are you getting that number from?
> >
> > You may not need it, but there are other people using this facility as well that
> > you're not considering. If you assume that in the example Sasha has given, if
> > conservatively, you have a modern disk with 4k sectors, and you fill each 4k
> > sector with the value obtained from a 4 byte read from /dev/urandom, You will:
> >
> > 1) Generate an interrupt for every page you write, which in turn will add at
> > most 12 bits to the entropy pool
> >
> > 2) Extract 32 bits from the entropy pool
> >
> > Thats just a loosing proposition. Barring further entropy generation from
> > another source, this is bound to stall with this feature enabled.
> Why so? In the case the blocking limit is on 8MBits of data read
> from /dev/urandom per every 1 bit added to the entropy pool (this is not
> the exact way how the patch behaves but we can approximate that) I do
> not see the /dev/urandom can block if the bytes read from it are written
Easy, all you have to do is read 8MB of data out of /dev/urandom (plus whatever
other conditions are needed to first drain the entropy pool), prior to that bit
of entropy getting added.

> to disk device - of course only if the device adds entropy into the
> primary pool when there are writes on the device.
Yes, and thats a problem. We're assuming in the above case that writes to disk
generate interrupts which in turn generate entropy in the pool. If that
happens, then yes, it can be difficult (though far from impossible) to block on
urandom with this patch and a sufficiently high blocking threshold. But
interrupt randomness is only added for interrupts flagged with
IRQF_SAMPLE_RANDOM, and if you look, almost no hard irqs add that flag. So its
possible (and even likely) that writing to disk will not generate additional
entropy.

>
> Of course you can still easily make the /dev/urandom to occasionally
> block with this patch, just read the data and drop it.
>
> But you have to understand that the value that will be set with the
> sysctl added by this patch will be large in the order of millions of
> bits.
>
You can guarantee that? This sysctl allows for a setting of 2 just as easily as
it allows for a setting of 8,000,000. And the former is sure to break or
otherwise adversely affect applications that expect urandom to never block.
Thats what Sasha was referring to, saying that patch makes it easy for admins to
make serious mistakes.

Neil

> --
> Tomas Mraz
> No matter how far down the wrong road you've gone, turn back.
> Turkish proverb
>

2011-09-08 13:11:29

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thursday, September 08, 2011 08:52:34 AM Neil Horman wrote:
> > to disk device - of course only if the device adds entropy into the
> > primary pool when there are writes on the device.
>
> Yes, and thats a problem. We're assuming in the above case that writes to
> disk generate interrupts which in turn generate entropy in the pool. If
> that happens, then yes, it can be difficult (though far from impossible)
> to block on urandom with this patch and a sufficiently high blocking
> threshold. But interrupt randomness is only added for interrupts flagged
> with
> IRQF_SAMPLE_RANDOM, and if you look, almost no hard irqs add that flag. So
> its possible (and even likely) that writing to disk will not generate
> additional entropy.

The system being low on entropy is another problem that should be addressed. For our
purposes, we cannot say take it from TPM or RDRND or any plugin board. We have to have
the mathematical analysis that goes with it, we need to know where the entropy comes
from, and a worst case entropy estimation. It has to be documented in detail. The only
way we can be certain is if its based on system events. Linux systems are constantly
low on entropy and this really needs addressing. But that is a separate issue. For
real world use, I'd recommend everyone use a TPM chip + rngd and you'll never be short
on random numbers. But in the case where we are certifying the OS, we need the
mathematical argument to prove that unaided, things are correct.

> > Of course you can still easily make the /dev/urandom to occasionally
> > block with this patch, just read the data and drop it.
> >
> > But you have to understand that the value that will be set with the
> > sysctl added by this patch will be large in the order of millions of
> > bits.
>
> You can guarantee that?

One proposal I made to Jarod was to add some minimum threshold that would prevent
people from setting a value of 2, for example. Maybe the threshold could be set at 64K
or higher depending on what number we get back from BSI.

> This sysctl allows for a setting of 2 just as easily as it allows for a setting of
> 8,000,000. And the former is sure to break or otherwise adversely affect
> applications that expect urandom to never block. Thats what Sasha was referring to,
> saying that patch makes it easy for admins to make serious mistakes.

Would a sufficiently high threshold make this easier to accept?

-Steve

2011-09-08 13:50:16

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thu, Sep 08, 2011 at 09:11:12AM -0400, Steve Grubb wrote:
> On Thursday, September 08, 2011 08:52:34 AM Neil Horman wrote:
> > > to disk device - of course only if the device adds entropy into the
> > > primary pool when there are writes on the device.
> >
> > Yes, and thats a problem. We're assuming in the above case that writes to
> > disk generate interrupts which in turn generate entropy in the pool. If
> > that happens, then yes, it can be difficult (though far from impossible)
> > to block on urandom with this patch and a sufficiently high blocking
> > threshold. But interrupt randomness is only added for interrupts flagged
> > with
> > IRQF_SAMPLE_RANDOM, and if you look, almost no hard irqs add that flag. So
> > its possible (and even likely) that writing to disk will not generate
> > additional entropy.
>
> The system being low on entropy is another problem that should be addressed. For our
> purposes, we cannot say take it from TPM or RDRND or any plugin board. We have to have
> the mathematical analysis that goes with it, we need to know where the entropy comes
> from, and a worst case entropy estimation. It has to be documented in detail. The only
> way we can be certain is if its based on system events. Linux systems are constantly
> low on entropy and this really needs addressing. But that is a separate issue. For
> real world use, I'd recommend everyone use a TPM chip + rngd and you'll never be short
> on random numbers. But in the case where we are certifying the OS, we need the
> mathematical argument to prove that unaided, things are correct.
>
I agree, it would be great if we had more entropy as a rule, but thats not
really what this patch is about. Its about how we behave in our various
interfaces when we don't have entropy.

>
> > > Of course you can still easily make the /dev/urandom to occasionally
> > > block with this patch, just read the data and drop it.
> > >
> > > But you have to understand that the value that will be set with the
> > > sysctl added by this patch will be large in the order of millions of
> > > bits.
> >
> > You can guarantee that?
>
> One proposal I made to Jarod was to add some minimum threshold that would prevent
> people from setting a value of 2, for example. Maybe the threshold could be set at 64K
> or higher depending on what number we get back from BSI.
>
> > This sysctl allows for a setting of 2 just as easily as it allows for a setting of
> > 8,000,000. And the former is sure to break or otherwise adversely affect
> > applications that expect urandom to never block. Thats what Sasha was referring to,
> > saying that patch makes it easy for admins to make serious mistakes.
>
> Would a sufficiently high threshold make this easier to accept?
>

I don't know, but IMO, no. The problems with this implementation go beyond just
picking the appropriate threshold. As several others have commented, theres
problems:

1) With having a threshold at all - I still don't think its clear what a 'good'
theshold is and why. I've seen 8,000,000 bytes beyond zero entropy tossed
about. I presume thats used because its been shown that after 8,000,000 bytes
read beyond zero entropy, the internal state of the urandom device can be
guessed? If so, how? If not, what the magic number?

2) With the implementation. There are still unaddressed concerns about
applications which expect urandom to never block living in conjunction with
applications that can tolerate it. As you noted above entropy is in short
supply in Linux systems. Regardless of what threshold you set, its possible
that it will not be high enough to prevent urandom blocking for indefinate
periods of time. Not addressing this I think is a complete show stopper. The
CUSE driver has been proposed as a solution here and I think its a good one. It
lets those that are worried about this sort of attack mitigate it and leaves the
rest of the world alone (and ostensibly is auditable)

Neil

> -Steve
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>

2011-09-08 16:13:47

by David Miller

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

From: Steve Grubb <[email protected]>
Date: Thu, 8 Sep 2011 07:48:27 -0400

> On Thursday, September 08, 2011 04:44:20 AM Christoph Hellwig wrote:
>> On Wed, Sep 07, 2011 at 11:27:12PM +0200, Stephan Mueller wrote:
>> > And exactly that is the concern from organizations like BSI. Their
>> > cryptographer's concern is that due to the volume of data that you can
>> > extract from /dev/urandom, you may find cycles or patterns that increase
>> > the probability to guess the next random value compared to brute force
>> > attack. Note, it is all about probabilities.
>>
>> So don't use /dev/urandom if you don't like the behaviour. Breaking all
>> existing application because of a certification is simply not an option.
>
> This patch does not _break_ all existing applications. If a system were under attack,
> they might pause momentarily, but they do not break. Please, try the patch and use a
> nice large number like 2000000 and see for yourself. Right now, everyone arguing about
> this breaking things have not tried it to see if in fact things do break and how they
> break if they do.

If the application holds a critical resource other threads want when it
blocks on /dev/urandom, then your change breaks things. I can come up
with more examples if you like.

Please get off this idea that you can just change the blocking behavior
for a file descriptor and nothing of consequence will happen.

When this happens in the networking due to a bug or similar, we know
it does break things.

2011-09-09 02:21:15

by Sandy Harris

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thu, Sep 8, 2011 at 9:11 PM, Steve Grubb <[email protected]> wrote:

> The system being low on entropy is another problem that should be addressed. For our
> purposes, we cannot say take it from TPM or RDRND or any plugin board. We have to have
> the mathematical analysis that goes with it, we need to know where the entropy comes
> from, and a worst case entropy estimation.

Much of that is in the driver code's comments or previous email
threads. For example,
this thread cover many of the issues:
http://yarchive.net/comp/linux/dev_random.html
There are plenty of others as well.

> It has to be documented in detail.

Yes. But apart from code comments, what documentation
are we talking about? Googling for /dev/random on tldp.org
turns up nothing that treats this in any detail.

> The only
> way we can be certain is if its based on system events. Linux systems are constantly
> low on entropy and this really needs addressing. But that is a separate issue. For
> real world use, I'd recommend everyone use a TPM chip + rngd and you'll never be short
> on random numbers.

Yes. Here's something I wrote on the Debian Freedombox list:

| No problem on a typical Linux desktop; it does not
| do much crypto and /dev/random gets input from
| keyboard & mouse movement, disk delays, etc.
| However, it might be a major problem for a plug
| server that does more crypto, runs headless, and
| use solid state storage.

| Some plug computers may have a hardware RNG,
| which is the best solution, but we cannot count on
| that in the general case.

| Where the plug has a sound card equivalent, and
| it isn't used for sound, there is a good solution
| using circuit noise in the card as the basis for
| a hardware RNG.
| http://www.av8n.com/turbid/paper/turbid.htm

| A good academic paper on the problem is:
| https://db.usenix.org/publications/library/proceedings/sec98/gutmann.html

| However, his software does not turn up in
| the Ubuntu repository. Is it in Debian?
| Could it be?

| Ubuntu, and I assume Debian, does have
| Havege, another researcher's solution
| to the same problem.
| http://www.irisa.fr/caps/projects/hipsor/

Some of that sort of discussion should be in the documentation.
I'm not sure how much currently is.

> But in the case where we are certifying the OS, we need the
> mathematical argument to prove that unaided, things are correct.

No, we cannot "prove that unaided, things are correct" if
by "correct" you mean urandom output is safe against all
conceivable attacks and by "unaided" you mean without
new entropy inputs. It is a PRNG, so without reseeding it
must be breakable in theory; that comes with the territory.

That need not be a problem, though. We cannot /prove/
that any of the ciphers or hashes in widespread use are
correct either. In fact, we can prove the opposite; they
are all provably breakable by an opponent with enough
resources, for extremely large values of enough.

Consider a block cipher like AES: there are three known
attacks that must break it in theory -- brute force search
for the key, or reduce the cipher to a set of equations
then feed in some known plaintext/ciphertext pairs and
solve for the key, or just collect enough known pairs to
build a codebook that breaks the cipher. We know the
brute force and codebook attacks are astronomically
expensive, and there are good arguments that algebra
is as well, but they all work in theory. Despite that, we
can use AES with reasonable confidence and with
certifications from various government bodies.

There are similar arguments for confidence in urandom.
The simplest are the size of the state relative to the
outputs and the XOR that reduces 160 bits of SHA-1
output to 80 of generator output. More detailed discussion is
in the first thread I cited above.

Barring a complete failure of SHA-1, an enemy who wants to
infer the state from outputs needs astronomically large amounts
of both data and effort.

2011-09-09 13:04:28

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thursday, September 08, 2011 10:21:13 PM Sandy Harris wrote:
> > The system being low on entropy is another problem that should be
> > addressed. For our purposes, we cannot say take it from TPM or RDRND or
> > any plugin board. We have to have the mathematical analysis that goes
> > with it, we need to know where the entropy comes from, and a worst case
> > entropy estimation.
>
> Much of that is in the driver code's comments or previous email
> threads. For example,
> this thread cover many of the issues:
> http://yarchive.net/comp/linux/dev_random.html
> There are plenty of others as well.
>
> > It has to be documented in detail.
>
> Yes. But apart from code comments, what documentation
> are we talking about? Googling for /dev/random on tldp.org
> turns up nothing that treats this in any detail.

Thanks for the reply. I see that you are trying to be helpful. But I think you
misunderstand what I was trying to say or maybe I was not entirely clear. We have the
correct analysis for the kernel and it does indeed pass FIPS-140, unaided. We know the
entropy comes from what the minimum entropy estimation is, and quality. (The only
issue is guaranteeing that any seed source must also include entropy.)

But what I was trying to say is that we can't depend on these supplemental hardware
devices like TPM because we don't have access to the proprietary technical details
that would be necessary to supplement the analysis. And when it comes to TPM chips, I
bet each chip has different details and entropy sources and entropy estimations and
rates. Those details we can't get at, so we can't solve the problem by including that
hardware. That is the point I was trying to make. :)

Thanks,
-Steve

2011-09-09 16:25:32

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Fri, Sep 09, 2011 at 09:04:17AM -0400, Steve Grubb wrote: But what
> I was trying to say is that we can't depend on these supplemental
> hardware devices like TPM because we don't have access to the
> proprietary technical details that would be necessary to supplement
> the analysis. And when it comes to TPM chips, I bet each chip has
> different details and entropy sources and entropy estimations and
> rates. Those details we can't get at, so we can't solve the problem
> by including that hardware. That is the point I was trying to
> make. :)

Let's be clear that _we_ which Steve is referring to is Red Hat's
attempt to get a BSI certification so they can make $$$. It has
nothing to do with security, except indirectly, and in my opinion,
breaking application by causing network daemons to suddenly lock up
randomly just so that Red Hat can make more $$$ is not a good reason
to push a incompatible behavioural change into /dev/random.

- Ted

2011-09-09 19:08:05

by Eric Paris

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Thu, Sep 8, 2011 at 12:13 PM, David Miller <[email protected]> wrote:
> From: Steve Grubb <[email protected]>

>> This patch does not _break_ all existing applications. If a system were under attack,
>> they might pause momentarily, but they do not break. Please, try the patch and use a
>> nice large number like 2000000 and see for yourself. Right now, everyone arguing about
>> this breaking things have not tried it to see if in fact things do break and how they
>> break if they do.
>
> If the application holds a critical resource other threads want when it
> blocks on /dev/urandom, then your change breaks things. ?I can come up
> with more examples if you like.
>
> Please get off this idea that you can just change the blocking behavior
> for a file descriptor and nothing of consequence will happen.

I know it's work porting userspace, but would anyone think that a new
char device to do this would be a good enough idea? You obviously
already worked out methods to port things which normally use urandom
to use random to discover the problem, so most of the work should be
done. I suggest /dev/jkrandom (since this is half way between
/dev/random and /dev/urandom and 'u' is the 21st letter it seemed
appropriate to use letters 10 and 11)

Thus userspace can decide what matters. Always with entropy and
blocks often (random). From good enough entropy and rarely blocks
(jkrandom). Possibly from some entropy and never block (urandom).

-Eric

2011-09-09 19:12:58

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Fri, Sep 09, 2011 at 03:08:03PM -0400, Eric Paris wrote:
> On Thu, Sep 8, 2011 at 12:13 PM, David Miller <[email protected]> wrote:
> > From: Steve Grubb <[email protected]>
>
> >> This patch does not _break_ all existing applications. If a system were under attack,
> >> they might pause momentarily, but they do not break. Please, try the patch and use a
> >> nice large number like 2000000 and see for yourself. Right now, everyone arguing about
> >> this breaking things have not tried it to see if in fact things do break and how they
> >> break if they do.
> >
> > If the application holds a critical resource other threads want when it
> > blocks on /dev/urandom, then your change breaks things. ?I can come up
> > with more examples if you like.
> >
> > Please get off this idea that you can just change the blocking behavior
> > for a file descriptor and nothing of consequence will happen.
>
> I know it's work porting userspace, but would anyone think that a new
> char device to do this would be a good enough idea? You obviously
> already worked out methods to port things which normally use urandom
> to use random to discover the problem, so most of the work should be
> done. I suggest /dev/jkrandom (since this is half way between
> /dev/random and /dev/urandom and 'u' is the 21st letter it seemed
> appropriate to use letters 10 and 11)
>
I was going to suggest /dev/sourandom (for sort-of-urandom) :)
Neil

> Thus userspace can decide what matters. Always with entropy and
> blocks often (random). From good enough entropy and rarely blocks
> (jkrandom). Possibly from some entropy and never block (urandom).
>
> -Eric

2011-09-09 21:27:32

by Thomas Gleixner

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Fri, 9 Sep 2011, Steve Grubb wrote:
> But what I was trying to say is that we can't depend on these supplemental hardware
> devices like TPM because we don't have access to the proprietary technical details
> that would be necessary to supplement the analysis. And when it comes to TPM chips, I
> bet each chip has different details and entropy sources and entropy estimations and
> rates. Those details we can't get at, so we can't solve the problem by including that
> hardware. That is the point I was trying to make. :)

Well, there is enough prove out there that the hardware you're using
is a perfect random number generator by itself.

So stop complaining about not having access to TPM chips if you can
create an entropy source just by (ab)using the inherent randomness of
modern CPU architectures to refill your entropy pool on the fly when
the need arises w/o imposing completely unintuitive thresholds and
user visible API changes.

Thanks,

tglx

2011-09-11 02:06:03

by Valdis Klētnieks

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Fri, 09 Sep 2011 10:21:13 +0800, Sandy Harris said:
> Barring a complete failure of SHA-1, an enemy who wants to
> infer the state from outputs needs astronomically large amounts
> of both data and effort.

So let me get this straight - the movie-plot attack we're defending against is
somebody readin literally gigabytes to terabytes (though I suspect realistic
attacks will require peta/exabytes) of data from /dev/urandom, then performing
all the data reduction needed to infer the state of enough of the entropy pool
to infer all 160 bits of SHA-1 when only 80 bits are output...

*and* doing it all without taking *any* action that adds any entropy to the
pool, and *also* ensuring that no other programs add any entropy via their
actions before the reading and data reduction completes. (Hint - if the
attacker can do this, you're already pwned and have bigger problems)

/me thinks RedHat needs to start insisting on random drug testing for
their security experts at BSI. EIther that, or force BSI to share the
really good stuff they've been smoking, or they need to learn how huge
a number 2^160 *really* is....

Attachments:

(No filename) (227.00 B)

2011-09-12 13:59:41

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

[email protected] wrote:
> On Fri, 09 Sep 2011 10:21:13 +0800, Sandy Harris said:
>> Barring a complete failure of SHA-1, an enemy who wants to
>> infer the state from outputs needs astronomically large amounts
>> of both data and effort.
>
> So let me get this straight - the movie-plot attack we're defending against is
> somebody readin literally gigabytes to terabytes (though I suspect realistic
> attacks will require peta/exabytes) of data from /dev/urandom, then performing
> all the data reduction needed to infer the state of enough of the entropy pool
> to infer all 160 bits of SHA-1 when only 80 bits are output...
>
> *and* doing it all without taking *any* action that adds any entropy to the
> pool, and *also* ensuring that no other programs add any entropy via their
> actions before the reading and data reduction completes. (Hint - if the
> attacker can do this, you're already pwned and have bigger problems)
>
> /me thinks RedHat needs to start insisting on random drug testing for
> their security experts at BSI. EIther that, or force BSI to share the
> really good stuff they've been smoking, or they need to learn how huge
> a number 2^160 *really* is....

Well, previously, we were looking at simply improving random entropy
contributions, but quoting Matt Mackall from here:

http://www.mail-archive.com/[email protected]/msg05799.html

'I recommend you do some Google searches for "ssl timing attack" and
"aes timing attack" to get a feel for the kind of seemingly impossible
things that can be done and thereby recalibrate your scale of the
impossible.'

:)

Note: I'm not a crypto person. At all. I'm just the "lucky" guy who got
tagged to work on trying to implement various suggestions to satisfy
various government agencies.

--
Jarod Wilson
[email protected]

2011-09-12 14:01:01

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Thomas Gleixner wrote:
> On Fri, 9 Sep 2011, Steve Grubb wrote:
>> But what I was trying to say is that we can't depend on these supplemental hardware
>> devices like TPM because we don't have access to the proprietary technical details
>> that would be necessary to supplement the analysis. And when it comes to TPM chips, I
>> bet each chip has different details and entropy sources and entropy estimations and
>> rates. Those details we can't get at, so we can't solve the problem by including that
>> hardware. That is the point I was trying to make. :)
>
> Well, there is enough prove out there that the hardware you're using
> is a perfect random number generator by itself.
>
> So stop complaining about not having access to TPM chips if you can
> create an entropy source just by (ab)using the inherent randomness of
> modern CPU architectures to refill your entropy pool on the fly when
> the need arises w/o imposing completely unintuitive thresholds and
> user visible API changes.

We started out going down that path:

http://www.mail-archive.com/[email protected]/msg05778.html

We hit a bit of a roadblock with it though.

--
Jarod Wilson
[email protected]

2011-09-12 14:02:43

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

Ted Ts'o wrote:
> On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
>> We're looking for a generic solution here that doesn't require
>> re-educating every single piece of userspace. And anything done in
>> userspace is going to be full of possible holes -- there needs to be
>> something in place that actually *enforces* the policy, and
>> centralized accounting/tracking, lest you wind up with multiple
>> processes racing to grab the entropy.
>
> Yeah, but there are userspace programs that depend on urandom not
> blocking... so your proposed change would break them.

I'm already consigned to the fact this isn't going to fly, but I'm still
curious to know examples of programs that are going to break here, for
my own education. Its already possible for urandom reads to fail as the
code is now (-ERESTARTSYS and -EFAULT are possible), so a sane program
ought to already be handling error cases, though not -EAGAIN, which this
would add.

--
Jarod Wilson
[email protected]

2011-09-12 14:58:28

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Mon, Sep 12, 2011 at 10:02:43AM -0400, Jarod Wilson wrote:
> Ted Ts'o wrote:
> >On Wed, Sep 07, 2011 at 02:26:35PM -0400, Jarod Wilson wrote:
> >>We're looking for a generic solution here that doesn't require
> >>re-educating every single piece of userspace. And anything done in
> >>userspace is going to be full of possible holes -- there needs to be
> >>something in place that actually *enforces* the policy, and
> >>centralized accounting/tracking, lest you wind up with multiple
> >>processes racing to grab the entropy.
> >
> >Yeah, but there are userspace programs that depend on urandom not
> >blocking... so your proposed change would break them.
>
> I'm already consigned to the fact this isn't going to fly, but I'm
> still curious to know examples of programs that are going to break
> here, for my own education. Its already possible for urandom reads
> to fail as the code is now (-ERESTARTSYS and -EFAULT are possible),
> so a sane program ought to already be handling error cases, though
> not -EAGAIN, which this would add.
>
Its not a failure return code here, its the possibility of no return code at all
(i.e. indefinte blocking). While I can't cite a specific application the
failure profile would be an application holding a critical system resource say a
manditory file lock that several applications require to do their work). If the
application that holds said lock blocks on urandom (having previously correctly
assumed that no blocking could occur), all applications requiring access to that
file lock then in turn block indefinately, violating any time critical deadlines
they may have.

Neil

>
> --
> Jarod Wilson
> [email protected]
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>

2011-09-12 16:58:19

by Valdis Klētnieks

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Mon, 12 Sep 2011 09:55:15 EDT, Jarod Wilson said:

> Well, previously, we were looking at simply improving random entropy
> contributions, but quoting Matt Mackall from here:
>
> http://www.mail-archive.com/[email protected]/msg05799.html
>
> 'I recommend you do some Google searches for "ssl timing attack" and
> "aes timing attack" to get a feel for the kind of seemingly impossible
> things that can be done and thereby recalibrate your scale of the
> impossible.'

If you're referring to Dan Bernstein's 2005 paper on AES timing attacks
(http://cr.yp.to/antiforgery/cachetiming-20050414.pdf), note that it took
him on the order of 2*25 packets per byte of AES key - targeting a
dummy server intentionally designed to minimize noise. Although he
correctly notes:

Of course, I wrote this server to minimize the amount of noise in the timings
available to the client. However, adding noise does not stop the attack: the client
simply averages over a larger number of samples, as in [7]. In particular, reducing
the precision of the server's timestamps, or eliminating them from the server's
responses, does not stop the attack: the client simply uses round-trip timings
based on its local clock, and compensates for the increased noise by averaging
over a larger number of samples.

one has to remember that he's measuring average differences in processing
time on the order of single-digits of cycles - if any *real* processing was happening
it would only take a few cache line misses or an 'if' statement branching the
other way to almost totally drown out the AES computation. (Personally,
I'm amazed that FreeBSD 4.8's kernel is predictable enough to do these
measurements - probably helps a *lot* that the server was otherwise idle -
if somebody else was getting a timeslice in between it would totally swamp
the numbers).

Dan's reference [7] mentions specifically that RSA blinding (first implemented
by default all the way back in OpenSSL 0.9.7b) defeats that paper's timing
attack.

If anything, those attacks are the best proof possible that the suggested
"fix" for /dev/urandom is a fool's errand - why would anybody bother trying to
figure out what the "next" data out of /dev/urandom is, when they can simply
wait for a few milliseconds and extract it out of whatever program read it? :)

Attachments:

(No filename) (227.00 B)

2011-09-12 17:07:07

by Mark Brown

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Mon, Sep 12, 2011 at 10:02:43AM -0400, Jarod Wilson wrote:
> Ted Ts'o wrote:

> >Yeah, but there are userspace programs that depend on urandom not
> >blocking... so your proposed change would break them.

> I'm already consigned to the fact this isn't going to fly, but I'm
> still curious to know examples of programs that are going to break
> here, for my own education. Its already possible for urandom reads
> to fail as the code is now (-ERESTARTSYS and -EFAULT are possible),
> so a sane program ought to already be handling error cases, though
> not -EAGAIN, which this would add.

It's not just a question of error handling existing, it's also about the
expectations the system has for the behaviour of the file - if urandom
is expected to always be able to return data an application is likely to
rely on the fact that it's effectively non-blocking anyway and not bother
setting non-blocking mode at all and so have no graceful handling for
this.

2011-09-12 18:30:32

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

[email protected] wrote:
> On Mon, 12 Sep 2011 09:55:15 EDT, Jarod Wilson said:
>
>> Well, previously, we were looking at simply improving random entropy
>> contributions, but quoting Matt Mackall from here:
>>
>> http://www.mail-archive.com/[email protected]/msg05799.html
>>
>> 'I recommend you do some Google searches for "ssl timing attack" and
>> "aes timing attack" to get a feel for the kind of seemingly impossible
>> things that can be done and thereby recalibrate your scale of the
>> impossible.'
>
> If you're referring to Dan Bernstein's 2005 paper on AES timing attacks
> (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf), note that it took
> him on the order of 2*25 packets per byte of AES key - targeting a
> dummy server intentionally designed to minimize noise. Although he
> correctly notes:
>
> Of course, I wrote this server to minimize the amount of noise in the timings
> available to the client. However, adding noise does not stop the attack: the client
> simply averages over a larger number of samples, as in [7]. In particular, reducing
> the precision of the server's timestamps, or eliminating them from the server's
> responses, does not stop the attack: the client simply uses round-trip timings
> based on its local clock, and compensates for the increased noise by averaging
> over a larger number of samples.
>
> one has to remember that he's measuring average differences in processing
> time on the order of single-digits of cycles - if any *real* processing was happening
> it would only take a few cache line misses or an 'if' statement branching the
> other way to almost totally drown out the AES computation. (Personally,
> I'm amazed that FreeBSD 4.8's kernel is predictable enough to do these
> measurements - probably helps a *lot* that the server was otherwise idle -
> if somebody else was getting a timeslice in between it would totally swamp
> the numbers).
>
> Dan's reference [7] mentions specifically that RSA blinding (first implemented
> by default all the way back in OpenSSL 0.9.7b) defeats that paper's timing
> attack.
>
> If anything, those attacks are the best proof possible that the suggested
> "fix" for /dev/urandom is a fool's errand - why would anybody bother trying to
> figure out what the "next" data out of /dev/urandom is, when they can simply
> wait for a few milliseconds and extract it out of whatever program read it? :)

I'm not referring to anything in particular, I'm mostly referring to the
irony that one approach that was shot down was because, while not
exactly practical, its theoretically not impossible to figure out clock
sample entropy contributions, which might weaken the strength of the
entropy pool. Your argument is more or less directly opposed to the
reasoning the clock entropy patches were deemed unacceptable. :)

Something to keep in mind: the whole impetus behind all this is
*government* crypto certification requirements. They're paranoid. And
something impractical at the individual level is less so at the
"determined, and willing to spend buckets of cash on resources, hostile
foreign government level. At least in the minds of some governments.

Note also: I don't necessarily share said governments' sentiments, I'm
just tasked with trying to satisfy the requirements, and this was looked
at as a potential minimally-invasive solution. I still think paranoid
government-types would be fine with applications falling down if urandom
blocked, because that should *only* happen if the system is being
abused, but I understand the objections, so that idea is off the table.

I'm likely going to look into Sasha's suggestion to do something via
CUSE next, followed by taking a long hard look at what's involved in
rewriting the entropy estimation logic such that clock-based entropy
would be acceptable.

--
Jarod Wilson
[email protected]

2011-09-13 10:58:29

by Peter Zijlstra

[permalink] [raw]

Subject: Re: [PATCH] random: add blocking facility to urandom

On Mon, 2011-09-12 at 09:56 -0400, Jarod Wilson wrote:
> Thomas Gleixner wrote:

> > Well, there is enough prove out there that the hardware you're using
> > is a perfect random number generator by itself.
> >
> > So stop complaining about not having access to TPM chips if you can
> > create an entropy source just by (ab)using the inherent randomness of
> > modern CPU architectures to refill your entropy pool on the fly when
> > the need arises w/o imposing completely unintuitive thresholds and
> > user visible API changes.
>
> We started out going down that path:
>
> http://www.mail-archive.com/[email protected]/msg05778.html
>
> We hit a bit of a roadblock with it though.

Have you guys seen this work:

http://lwn.net/images/conf/rtlws11/random-hardware.pdf

2011-09-13 12:19:01