[RFC] /dev/random for in-kernel use

[RFC] /dev/random for in-kernel use

[Stephan Mueller]

Hi,

before I start, please allow me to point out that this email is not a 
discussion about entropy. There was already too much such discussion without 
any conclusion. This email shall just explore the pros and cons as well as an 
implementation of making the logic behind /dev/random available for in-kernel 
use.

With the heavy update of random.c during the 3.13 development, the re-seeding 
of the nonblocking_pool from the input_pool is now prevented for a duration of 
random_min_urandom_seed seconds. Furthermore, the nonblocking_pool can be read 
from user space such that it acts as a deterministic RNG due to the non-
blocking behavior if more data is pulled than is delivered by the noise 
sources. As the nonblocking_pool is used when a in-kernel user invokes 
get_random_bytes, the described deterministic behavior also applies to this 
function.

Now, get_random_bytes is the only function inside the kernel that can deliver 
entropy. For most use cases, the described approach is just fine. However, 
when using well defined deterministic RNGs, like the already existing ANSI 
X9.31 or the suggested SP800-90A DRBG, seeding these DRNGs from the DRNG of 
the nonblocking_pool is typically not a suggested way. This is visible in user 
space where /dev/random is preferred when seeding deterministic RNGs (see 
libgcrypt as an example).

Therefore may I propose the implementation of the blocking concept of 
/dev/random as a provider of entropy to in-kernel callers like DRNGs? I would 
recommend a function of

void get_blocking_bytes_nowait(void *buf, int nbytes,
	void (*cb)(void *buf, int buflen))

which supplements get_random_bytes that implements the following:

- one work queue that collects data from blocking_pool (or directly from the 
input_pool?) with an identical concept as random_read from 
drivers/char/random.c

- the cb function is triggered when nbytes of data is gathered by the work 
queue. The cb function is implemented by the caller to obtain the requested 
data. The returned data is supplied with buf. The caller allocates that buffer 
and supplies the pointer to that buffer in the invocation of 
get_blocking_bytes_nowait.

- any invocation of get_blocking_bytes_nowait registers the request in a list. 
The work queue processes the list in a FIFO order and removes completed 
requests until the list is empty again. The list has a set length. If the list 
length is exceeded, the cb function is called right away with buflen set to 0.

Ciao
Stephan
-- 
| Cui bono? |

Re: [RFC] /dev/random for in-kernel use

[Theodore Ts'o]

On Sun, Apr 27, 2014 at 08:49:48PM +0200, Stephan Mueller wrote:
> With the heavy update of random.c during the 3.13 development, the re-seeding 
> of the nonblocking_pool from the input_pool is now prevented for a duration of 
> random_min_urandom_seed seconds. Furthermore, the nonblocking_pool can be read 
> from user space such that it acts as a deterministic RNG due to the non-
> blocking behavior if more data is pulled than is delivered by the noise 
> sources. As the nonblocking_pool is used when a in-kernel user invokes 
> get_random_bytes, the described deterministic behavior also applies to this 
> function.

This actually wasn't a major change.  If you are drawing sufficiently
heavily from /dev/urandom (and some crypto libraries draw _very_
heavily; the Chrome browser in particular draws from /dev/urandom
quite liberally), then you'll end up drawing from the input pool
faster than it can be filled from noise sources anyway.  So the rate
limiting wasn't making a material difference as far as the quality of
/dev/urandom and get_random_bytes() is concerned.  What it does do is
allow users of /dev/random (such as gpg key generaiton) to complete in
a reasonable time.

However, given that we're reseeding once a minute (or as needed), it's
actually not a deterministic RNG (per SP 800-90A, section 8.6.5, a
DRBG is forbidden to reseed itself automatically).

> Now, get_random_bytes is the only function inside the kernel that can deliver 
> entropy. For most use cases, the described approach is just fine. However, 
> when using well defined deterministic RNGs, like the already existing ANSI 
> X9.31 or the suggested SP800-90A DRBG, seeding these DRNGs from the DRNG of 
> the nonblocking_pool is typically not a suggested way. This is visible in user 
> space where /dev/random is preferred when seeding deterministic RNGs (see 
> libgcrypt as an example).

Well, as far as SP800-90A DRBG is concerned, using either the logical
equivalent of /dev/random or /dev/urandom is not allowed, since
neither is a "approved" entropy source.  (Then again, given that NIST
approved Dual-EC, I'm not sure how much I'm impressed by a NIST
approval, but whatever.  :-) But if your goal is to get the NIST
certification, which IMHO should only matter if you are selling to the
US government, it really can really only use RDRAND on Intel platforms
--- i.e., get_random_bytes_arch().

That being said, if some kernel module really wants to get its hands
on entropy extracted from the blocking pool, I don't see any reason
why we shouldn't deny them that functionality.


> Therefore may I propose the implementation of the blocking concept of 
> /dev/random as a provider of entropy to in-kernel callers like DRNGs? I would 
> recommend a function of
> 
> void get_blocking_bytes_nowait(void *buf, int nbytes,
> 	void (*cb)(void *buf, int buflen))

Let me make a counter proposal.  Let's instead provide a blocking
interface:

int get_blocking_random_bytes(void *buf, int nbytes);

and two helper functions:

void get_blocking_random_bytes_work(struct work_struct *work);
void get_blocking_random_bytes_cb(struct *workqueue_struct *wq,
     				  struct *random_work rw,
				  void *buf, int nbytes,
				  void (*cb)(void *buf, int buflen));

If a caller really needs to use the non-blocking variant, it can do
this:

static struct random_work my_random_work;

	...
	get_blocking_random_bytes_cb(NULL, &my_random_work, buf, nbytes, cb);
	...

There are two benefits of doing it this way.  First of all, we don't
have to have a fixed number of queued random bytes, since it's up to
the caller to allocate the struct random_work.

Secondly, if a module tries to use use this interface, if there is an
attempt to unload the module, it can do this to cancel the /dev/random
read request:

	cancel_work_sync(&my_random_work.rw_work);


With the original get_blocking_bytes_nowait() proposal, there is no
way to cancel the callback request, so the module would have to do
something much more complicated.  It would have to wire up a struct
completion mechanism, and then call completion_done() from the
callback function, and use wait_for_completion() in the module_exit()
function, which is more complicated.

Furthermore, for a DRBG, if it is going to be seeding itself from its
module_init() function, and then explicitly via an ioctl() request,
then it can use the simpler blocking interface directly.

Cheers,

						- Ted

P.S.  The sample implementation of the helper functions:

struct random_work {
       struct work	rw_work;
       void		*rw_buf;
       int		rw_len;
       void		(*rw_cb)(void *buf, int buflen);
}
       
void get_blocking_random_bytes_work(struct work_struct *work)
{
	struct random_work *rw = container_of(work, struct random_work,
	       		       	 	      rw_work);
	int ret;

	ret = get_blocking_random_bytes(rw->buf, rw->len);
	if (rw->cb)
		rw->cb(rw->rw_buf, ret);
}

void get_blocking_random_bytes_cb(struct *workqueue_struct *wq,
     				  struct *random_work rw,
				  void *buf, int nbytes,
				  void (*cb)(void *buf, int buflen))
{

	rw->rw_buf = buf;
	rw->rw_len = nbytes
	rw->rw_cb = cb;
	INIT_WORK(&work->work, get_blocking_random_bytes_work);
	if (wq)
		queue_work(wq, &work->work);
	else
		schedule_work(&work->work);
}

Re: [RFC] /dev/random for in-kernel use

[Stephan Mueller]

Am Sonntag, 27. April 2014, 20:19:41 schrieb Theodore Ts'o:

Hi Theodore,

> On Sun, Apr 27, 2014 at 08:49:48PM +0200, Stephan Mueller wrote:
> > With the heavy update of random.c during the 3.13 development, the
> > re-seeding of the nonblocking_pool from the input_pool is now prevented
> > for a duration of random_min_urandom_seed seconds. Furthermore, the
> > nonblocking_pool can be read from user space such that it acts as a
> > deterministic RNG due to the non- blocking behavior if more data is
> > pulled than is delivered by the noise sources. As the nonblocking_pool is
> > used when a in-kernel user invokes get_random_bytes, the described
> > deterministic behavior also applies to this function.
> 
> This actually wasn't a major change.  If you are drawing sufficiently
> heavily from /dev/urandom (and some crypto libraries draw _very_
> heavily; the Chrome browser in particular draws from /dev/urandom
> quite liberally), then you'll end up drawing from the input pool
> faster than it can be filled from noise sources anyway.  So the rate
> limiting wasn't making a material difference as far as the quality of
> /dev/urandom and get_random_bytes() is concerned.  What it does do is
> allow users of /dev/random (such as gpg key generaiton) to complete in
> a reasonable time.

Thanks for clarifying this. I agree that the change is immaterial considering 
a "random number hog" in user space with respect to the deterministic 
behavior.
> 
> However, given that we're reseeding once a minute (or as needed), it's
> actually not a deterministic RNG (per SP 800-90A, section 8.6.5, a
> DRBG is forbidden to reseed itself automatically).

To be honest, I do not read that in this section. Moreover, a DRBG must reseed 
itself -- the caller shall only have the ability to add additional data or 
trigger a reseeding earlier (the proposed DRBG implementation directly draws 
from get_random_bytes automatically). But this is a different topic and we 
should disregard it for the moment.
> 
> > Now, get_random_bytes is the only function inside the kernel that can
> > deliver entropy. For most use cases, the described approach is just fine.
> > However, when using well defined deterministic RNGs, like the already
> > existing ANSI X9.31 or the suggested SP800-90A DRBG, seeding these DRNGs
> > from the DRNG of the nonblocking_pool is typically not a suggested way.
> > This is visible in user space where /dev/random is preferred when seeding
> > deterministic RNGs (see libgcrypt as an example).
> 
> Well, as far as SP800-90A DRBG is concerned, using either the logical
> equivalent of /dev/random or /dev/urandom is not allowed, since
> neither is a "approved" entropy source.  (Then again, given that NIST
> approved Dual-EC, I'm not sure how much I'm impressed by a NIST
> approval, but whatever.  :-) But if your goal is to get the NIST

Well spoken words :-)

Considering that approved entropy sources have to comply with SP800-90B and C, 
I have prepared already some analyses of random.c whether the blocking or the 
nonblocking pool meets these requirements. Using several system tap scripts, 
the statistical behavior of the noise sources and the pool distributions look 
appropriate. In addition, some theoretical analyses showed that the blocking 
pool (considering the blocking behavior) would meet the requirements of 
SP800-90B/C whereas the nonblocking pool does not.

Anticipating that the compliance to SP800-90B/C would be required for a 
successful FIPS validation somewhen in the future, making the blocking 
behavior available to in-kernel users would be of interest.

> certification, which IMHO should only matter if you are selling to the
> US government, it really can really only use RDRAND on Intel platforms
> --- i.e., get_random_bytes_arch().

I am not too convinced of RDRAND due to the lack of usable source code (i.e. 
source code that I can build myself). But that is my personal taste :-)
> 
> That being said, if some kernel module really wants to get its hands
> on entropy extracted from the blocking pool, I don't see any reason
> why we shouldn't deny them that functionality.
> 
> > Therefore may I propose the implementation of the blocking concept of
> > /dev/random as a provider of entropy to in-kernel callers like DRNGs? I
> > would recommend a function of
> > 
> > void get_blocking_bytes_nowait(void *buf, int nbytes,
> > 
> > 	void (*cb)(void *buf, int buflen))
> 
> Let me make a counter proposal.  Let's instead provide a blocking
> interface:

[...]

Thanks for these suggestions. Shall I take these suggestions and turn them 
into a full patch?

Moreover, I read that even for in-kernel users we should use the blocking 
pool. Or shall we conceive of a third output pool, say, a kernel pool that is 
independent of the output pools to user space? Adding such a pool more or less 
only requires to define a new struct entropy_pool instance.

Ciao
Stephan
-- 
| Cui bono? |

Re: [RFC] /dev/random for in-kernel use

[Theodore Ts'o]

On Mon, Apr 28, 2014 at 08:00:19AM +0200, Stephan Mueller wrote:
> > However, given that we're reseeding once a minute (or as needed), it's
> > actually not a deterministic RNG (per SP 800-90A, section 8.6.5, a
> > DRBG is forbidden to reseed itself automatically).
> 
> To be honest, I do not read that in this section. Moreover, a DRBG must reseed 
> itself -- the caller shall only have the ability to add additional data or 
> trigger a reseeding earlier (the proposed DRBG implementation directly draws 
> from get_random_bytes automatically). 

It seems pretty clear to me: 

   The source of the entropy input (EI) SHALL be either:
       ...

   3.  An approved DRBG, thus forming a chain of at least two DRBGs;
       the initial DRBG in the chain SHALL be seeded by an approved
       NRBG or an approved entropy source. A DRBG instantiation may
       seed or reseed another DRBG instantiation, but SHALL NOT reseed
       itself.

The last "SHALL NOT" is what makes me think that the DRBG shouldn't be
doing this automatically.  So if it is only being done via explicit
user request (i.e., an ioctl) then the blocking interface should be
sufficient.

> Anticipating that the compliance to SP800-90B/C would be required for a 
> successful FIPS validation somewhen in the future, making the blocking 
> behavior available to in-kernel users would be of interest.
> ....
> 
> I am not too convinced of RDRAND due to the lack of usable source code (i.e. 
> source code that I can build myself). But that is my personal taste :-)

The problem is the FIPS validation would presumably require obeying
the SP-800A requirement for an approved entropy source, and while we
can't audit RDRAND to satisfy ourselves that the US government hasn't
introduced a back door, if the only purpose of the FIPS validation is
so that people can sell into the US government market, presuambly the
US government is OK with a potential NSA-introduced back door.  :-)

That being said, there is some FIPS compliance code in
drivers/char/random.c, which was introduced while Matt Mackall was
maintaining the driver, and it mystifies me, since I never thought
/dev/random could be an approved FIPS compliant generator --- not that
I care, since I'm not trying to sell into the US government market,
but the FIPS compliance code is largely harmless, so I've never
bothered to remove it.

> Thanks for these suggestions. Shall I take these suggestions and turn them 
> into a full patch?

Sure, go for it.

> Moreover, I read that even for in-kernel users we should use the blocking 
> pool. Or shall we conceive of a third output pool, say, a kernel pool that is 
> independent of the output pools to user space? Adding such a pool more or less 
> only requires to define a new struct entropy_pool instance.

I've audited most of the in-kernel users, and most of them aren't even
using them for a session key; they're using it for something less
critical (e.g. ASLR, stack magic, etc.).  CIFS is perhaps the only
place where it is generating a session key, and session key generation
is just fine with the /dev/urandom pool.

So making all of the in-kernel users deal with a blocking interface is
not worth it, IMHO.

Regards,

						- Ted

Re: [RFC] /dev/random for in-kernel use

[Gregory Baudet]

>    3.  An approved DRBG, thus forming a chain of at least two DRBGs;
>        the initial DRBG in the chain SHALL be seeded by an approved
>        NRBG or an approved entropy source. A DRBG instantiation may
>        seed or reseed another DRBG instantiation, but SHALL NOT reseed
>
>        itself.


According to me, this just means that the DRBG output cannot be used
as the seed input of that same DRBG.

On 28 April 2014 16:23, Theodore Ts'o <tytso@mit.edu> wrote:
> On Mon, Apr 28, 2014 at 08:00:19AM +0200, Stephan Mueller wrote:
>> > However, given that we're reseeding once a minute (or as needed), it's
>> > actually not a deterministic RNG (per SP 800-90A, section 8.6.5, a
>> > DRBG is forbidden to reseed itself automatically).
>>
>> To be honest, I do not read that in this section. Moreover, a DRBG must reseed
>> itself -- the caller shall only have the ability to add additional data or
>> trigger a reseeding earlier (the proposed DRBG implementation directly draws
>> from get_random_bytes automatically).
>
> It seems pretty clear to me:
>
>    The source of the entropy input (EI) SHALL be either:
>        ...
>
>    3.  An approved DRBG, thus forming a chain of at least two DRBGs;
>        the initial DRBG in the chain SHALL be seeded by an approved
>        NRBG or an approved entropy source. A DRBG instantiation may
>        seed or reseed another DRBG instantiation, but SHALL NOT reseed
>        itself.
>
> The last "SHALL NOT" is what makes me think that the DRBG shouldn't be
> doing this automatically.  So if it is only being done via explicit
> user request (i.e., an ioctl) then the blocking interface should be
> sufficient.
>
>> Anticipating that the compliance to SP800-90B/C would be required for a
>> successful FIPS validation somewhen in the future, making the blocking
>> behavior available to in-kernel users would be of interest.
>> ....
>>
>> I am not too convinced of RDRAND due to the lack of usable source code (i.e.
>> source code that I can build myself). But that is my personal taste :-)
>
> The problem is the FIPS validation would presumably require obeying
> the SP-800A requirement for an approved entropy source, and while we
> can't audit RDRAND to satisfy ourselves that the US government hasn't
> introduced a back door, if the only purpose of the FIPS validation is
> so that people can sell into the US government market, presuambly the
> US government is OK with a potential NSA-introduced back door.  :-)
>
> That being said, there is some FIPS compliance code in
> drivers/char/random.c, which was introduced while Matt Mackall was
> maintaining the driver, and it mystifies me, since I never thought
> /dev/random could be an approved FIPS compliant generator --- not that
> I care, since I'm not trying to sell into the US government market,
> but the FIPS compliance code is largely harmless, so I've never
> bothered to remove it.
>
>> Thanks for these suggestions. Shall I take these suggestions and turn them
>> into a full patch?
>
> Sure, go for it.
>
>> Moreover, I read that even for in-kernel users we should use the blocking
>> pool. Or shall we conceive of a third output pool, say, a kernel pool that is
>> independent of the output pools to user space? Adding such a pool more or less
>> only requires to define a new struct entropy_pool instance.
>
> I've audited most of the in-kernel users, and most of them aren't even
> using them for a session key; they're using it for something less
> critical (e.g. ASLR, stack magic, etc.).  CIFS is perhaps the only
> place where it is generating a session key, and session key generation
> is just fine with the /dev/urandom pool.
>
> So making all of the in-kernel users deal with a blocking interface is
> not worth it, IMHO.
>
> Regards,
>
>                                                 - Ted
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [RFC] /dev/random for in-kernel use

[Stephan Mueller]

Am Montag, 28. April 2014, 10:23:50 schrieb Theodore Ts'o:

Hi Theodore,

> > I am not too convinced of RDRAND due to the lack of usable source code
> > (i.e. source code that I can build myself). But that is my personal taste
> > :-)
> The problem is the FIPS validation would presumably require obeying
> the SP-800A requirement for an approved entropy source, and while we
> can't audit RDRAND to satisfy ourselves that the US government hasn't
> introduced a back door, if the only purpose of the FIPS validation is
> so that people can sell into the US government market, presuambly the
> US government is OK with a potential NSA-introduced back door.  :-)

>From a US centric view, you may be right. But there are some FIPS 140-2 
aspects which are helpful in general (albeit just a minority). And for those, 
auditible code is key. Not everybody is delighted to have NSA watching. :-)
> 
> That being said, there is some FIPS compliance code in
> drivers/char/random.c, which was introduced while Matt Mackall was
> maintaining the driver, and it mystifies me, since I never thought
> /dev/random could be an approved FIPS compliant generator --- not that
> I care, since I'm not trying to sell into the US government market,
> but the FIPS compliance code is largely harmless, so I've never
> bothered to remove it.

Ok, let me demystify it, because I was the initial trigger of the code 
changes. Albeit random.c is outside of any FIPS module, NIST requires that 
even seed sources that are outside the module boundary have a so-called 
"continuous selftest" as defined in FIPS specification section 4.9.2. If the 
self test fails, the seed source must become unavailable.
> 
> > Thanks for these suggestions. Shall I take these suggestions and turn them
> > into a full patch?
> 
> Sure, go for it.
> 
> > Moreover, I read that even for in-kernel users we should use the blocking
> > pool. Or shall we conceive of a third output pool, say, a kernel pool that
> > is independent of the output pools to user space? Adding such a pool more
> > or less only requires to define a new struct entropy_pool instance.
> 
> I've audited most of the in-kernel users, and most of them aren't even
> using them for a session key; they're using it for something less
> critical (e.g. ASLR, stack magic, etc.).  CIFS is perhaps the only
> place where it is generating a session key, and session key generation
> is just fine with the /dev/urandom pool.
> 
> So making all of the in-kernel users deal with a blocking interface is
> not worth it, IMHO.

Sorry, I did not make myself clear: for the purpose of the blocking behavior, 
shall we draw from blocking_pool or define a new pool used completely for this 
in-kernel blocking usage? Note, if we use the blocking_pool, any non-root user 
can stall the in-kernel operation indefinitely by simply reading /dev/random. 
As the in-kernel use for blocking random numbers would be limited, I was 
thinking about a new entropy pool that has no user space access.

I do not want to convert any existing in-kernel users of random data to use 
the new entropy pool.

Ciao
Stephan
-- 
| Cui bono? |