RFC: Random numbers


Luiz Augusto von Dentz
 

Hi Marcus,

Lets move the discussion of
https://gerrit.zephyrproject.org/r/#/c/12341 here since it should be
quite important to get it right if we intend Zephyr to be somewhat
secure OS.

Hi,
> >
> > This PRNG implementation has more general utility in zephyr than
> as
> > a pseudo device driver, but I think adding it in this way as a
> > driver is taking us in the wrong direction.
> >
> > Even on systems which have access to HW entropy generators it can
> > be very expensive to harvest that entropy, which means entropy is
> > valuable. There are many places around zephyr where we need some
> > random number, but that number does need to be a high quality
> > random number. For example numerous parts of the network stack
> > need random numbers for transaction ids and timer offsets etc.
> On
> > such systems it would be useful to to distinguish between users
> > that require pure entropy and those that don't, thus reducing
> > pressure to collect quality entropy.
> >
> > I think this PRNG should be recast as subsystem/library rather
> than
> > as a driver for none existant hardware. The reseed interface
> > should be retained, its primary interface should be a new
> interface
> > to sit along side the existing sys_rand32_get(), perhaps
> > sys_prng_get(). We would then move users that don;t require high
> > quality entropy to the sys_prng_get() interface (Im thinking
> > maninly of all the network stack calls). This leaves us with two
> > interfaces, one to get (possibly expensive) high quality entropy,
> > and a second to give PRNG for all uses where that is 'good
> enough'
> >
>
> Maybe sys_urand32_get in addition to sys_rand32_get so we mimic
> /dev/urandom and /dev/random. sys_urand32_get might be PRNG based
> and should be considerably faster considering sys_rand32_get can
> block if it doesn't have enough entropy.
>
> > On systems with copious, low cost HW entropy we could simply wire
> > sys_prng_get() to the hw entropy source and bypass the prng
> > completely.
>
> Btw, isn't depending on one source of entropy alone bad/broken? I
> understand it is currently like this because the did not exist any
> way to collect entropy from other sources, but now we are talking
> about introducing one so we might as well switch from the driver
> given the random number to the driver working as a source of
> entropy which is then collected by random subsystem.
> >
> > On systems with limited/expensive HW entropy we use high quality
> > entropy to seed the prng.
> >
> > On systems with no dedicated source of HW entropy, rather than
> > building a driver like this we should perhaps instead look at
> > adding an entropy pool (as a subsystem or library, not a driver),
> > that has a mechanism to add entropy and can dole out entropy on
> > demand and then adjust various general hw drivers to feed what
> > meagre entropy then have to the pool. As with the previous
> > scenario, the PRNG would be seeded from the entropy pool.
> >
> > What do others think?
>
> I guess I agree, although currently the driver, there can be only
> one Im afraid, work as entropy pool instead of a source of entropy.
>
> Btw, regarding the implementation sys_urand32_get, if you agree
> with that, that might use sys_rand32_get to seed.
--
Luiz Augusto von Dentz


Marcus Shawcroft <marcus.shawcroft@...>
 

Hi Luiz

On 22 March 2017 at 11:26, Luiz Augusto von Dentz <luiz.dentz@gmail.com> wrote:
Hi Marcus,

Lets move the discussion of
https://gerrit.zephyrproject.org/r/#/c/12341 here since it should be
quite important to get it right if we intend Zephyr to be somewhat
secure OS.
My last set of comments in gerrit and this RFC crossed, I'll repost my
comments here in the thread:

> Maybe sys_urand32_get in addition to sys_rand32_get so we mimic
> /dev/urandom and /dev/random. sys_urand32_get might be PRNG based
> and should be considerably faster considering sys_rand32_get can
> block if it doesn't have enough entropy.
This seems reasonable. It would be good to choose names that more
clearly articulate the TRNG / PRNG aspect of their behaviour, its an
important distinction. In my mind the 'u' distinction is not
'obvious' enough. I would also advocate that any new interfaces we
add should drop the uint32_t chunks of entropy and instead adopt a
more flexible interface along the lines of:

int some_function_that_gets_entropy(uint8_t *buffer, uint16_t length);

> > On systems with copious, low cost HW entropy we could simply wire
> > sys_prng_get() to the hw entropy source and bypass the prng
> > completely.
>
> Btw, isn't depending on one source of entropy alone bad/broken? I
> understand it is currently like this because the did not exist any
> way to collect entropy from other sources, but now we are talking
> about introducing one so we might as well switch from the driver
> given the random number to the driver working as a source of
> entropy which is then collected by random subsystem.
Fair point, if there are multiple sources available then best practice
would be to mix all the sources. I think that this therefore implies
the legacy/existing sys_rand32_get() function should be rewired to
pull entropy from a pool and the pool should be fed by all available
sources. However, I am aware that finding other sources of entropy in
a system is a really hard problem since most if not all can be
externally biased. The interface between a pool and the sources of
entropy is likely to be slightly awkward. On the one hand we have the
"random" drivers that can just be called to produce entropy on demand
(although perhaps with limited bandwidth) in this case a pull
interface works, while on the other hand harvesting entropy from other
parts of the system will likely need to be structured as a push
interface.

> Btw, regarding the implementation sys_urand32_get, if you agree
> with that, that might use sys_rand32_get to seed.
This structure seems reasonable to me.

Cheers
/Marcus


Luiz Augusto von Dentz
 

Hi Marcus,

On Wed, Mar 22, 2017 at 2:34 PM, Marcus Shawcroft
<marcus.shawcroft@gmail.com> wrote:
Hi Luiz

On 22 March 2017 at 11:26, Luiz Augusto von Dentz <luiz.dentz@gmail.com> wrote:
Hi Marcus,

Lets move the discussion of
https://gerrit.zephyrproject.org/r/#/c/12341 here since it should be
quite important to get it right if we intend Zephyr to be somewhat
secure OS.
My last set of comments in gerrit and this RFC crossed, I'll repost my
comments here in the thread:

> Maybe sys_urand32_get in addition to sys_rand32_get so we mimic
> /dev/urandom and /dev/random. sys_urand32_get might be PRNG based
> and should be considerably faster considering sys_rand32_get can
> block if it doesn't have enough entropy.
This seems reasonable. It would be good to choose names that more
clearly articulate the TRNG / PRNG aspect of their behaviour, its an
important distinction. In my mind the 'u' distinction is not
'obvious' enough. I would also advocate that any new interfaces we
add should drop the uint32_t chunks of entropy and instead adopt a
more flexible interface along the lines of:
From a developer with no much expertise into what does TRNG/PRNG
really means, myself included, Im not sure how using this terms would
improve the situation, in fact I think it would confuse people. Also
after reading a bit more about TRNG there doesn't seem to have a
solution that wouldn't involve a dedicated hardware, perhaps because
of that the Linux /dev/random and /dev/urandom manpage only talks
about CPRNG.

To me it is much more important we define these in terms of behavior,
which should them translate into care or not care about entropy
quality. With that in mind we may decide to add a timeout parameter to
the random number generator and then use that to decide the quality of
the entropy to use, if the user cannot wait then perhaps using
HMAC_PRNG shall be sufficient, otherwise it shall read for the entropy
pool directly.

int some_function_that_gets_entropy(uint8_t *buffer, uint16_t length);
I'd suggest something like this:

int sys_random_get(uint8_t *buffer, uint16_t length, uint32_t timeout);
int sys_random_put(const uint8_t *buffer, uint16_t length, uint32_t timeout);

I was intending to use a k_msgq to implement the entropy pool, but if
we put and get byte a byte I think I might have to reconsider, or
perhaps handle the chunks internally by calling multiple times
k_msgq_put and k_msgq_get but Im not sure I will be able to honor the
timeout properly so perhaps it would be a better idea to define a
minimal entropy size, if the caller needs more than that then it
should call it multiple times.

> > On systems with copious, low cost HW entropy we could simply wire
> > sys_prng_get() to the hw entropy source and bypass the prng
> > completely.
>
> Btw, isn't depending on one source of entropy alone bad/broken? I
> understand it is currently like this because the did not exist any
> way to collect entropy from other sources, but now we are talking
> about introducing one so we might as well switch from the driver
> given the random number to the driver working as a source of
> entropy which is then collected by random subsystem.
Fair point, if there are multiple sources available then best practice
would be to mix all the sources. I think that this therefore implies
the legacy/existing sys_rand32_get() function should be rewired to
pull entropy from a pool and the pool should be fed by all available
sources. However, I am aware that finding other sources of entropy in
a system is a really hard problem since most if not all can be
externally biased. The interface between a pool and the sources of
entropy is likely to be slightly awkward. On the one hand we have the
"random" drivers that can just be called to produce entropy on demand
(although perhaps with limited bandwidth) in this case a pull
interface works, while on the other hand harvesting entropy from other
parts of the system will likely need to be structured as a push
interface.
I guess we can have both pull and push, for the most part it should be
a push interface feeding the entropy pool, but as soon the pool runs
out or we need a new seed we should attempt to pull, obviously the
pull method shall only be used in case the user have provide a
timeout, that way the driver can go ahead and take that time to
generate more entropy and when it is done wake up the thread waiting
it.

We may also add a k_work to request more entropy from the driver in
case we are sort of entropy in the pool, that should prevent errors
when users need a random number immediately that could otherwise be
provided e.g. HMAC_PRNG but that fails since it needs to be reseeded.


> Btw, regarding the implementation sys_urand32_get, if you agree
> with that, that might use sys_rand32_get to seed.
This structure seems reasonable to me.

Cheers
/Marcus


--
Luiz Augusto von Dentz


Luiz Augusto von Dentz
 

Hi,

On Wed, Mar 22, 2017 at 3:40 PM, Luiz Augusto von Dentz
<luiz.dentz@gmail.com> wrote:
Hi Marcus,

On Wed, Mar 22, 2017 at 2:34 PM, Marcus Shawcroft
<marcus.shawcroft@gmail.com> wrote:
Hi Luiz

On 22 March 2017 at 11:26, Luiz Augusto von Dentz <luiz.dentz@gmail.com> wrote:
Hi Marcus,

Lets move the discussion of
https://gerrit.zephyrproject.org/r/#/c/12341 here since it should be
quite important to get it right if we intend Zephyr to be somewhat
secure OS.
My last set of comments in gerrit and this RFC crossed, I'll repost my
comments here in the thread:

> Maybe sys_urand32_get in addition to sys_rand32_get so we mimic
> /dev/urandom and /dev/random. sys_urand32_get might be PRNG based
> and should be considerably faster considering sys_rand32_get can
> block if it doesn't have enough entropy.
This seems reasonable. It would be good to choose names that more
clearly articulate the TRNG / PRNG aspect of their behaviour, its an
important distinction. In my mind the 'u' distinction is not
'obvious' enough. I would also advocate that any new interfaces we
add should drop the uint32_t chunks of entropy and instead adopt a
more flexible interface along the lines of:
From a developer with no much expertise into what does TRNG/PRNG
really means, myself included, Im not sure how using this terms would
improve the situation, in fact I think it would confuse people. Also
after reading a bit more about TRNG there doesn't seem to have a
solution that wouldn't involve a dedicated hardware, perhaps because
of that the Linux /dev/random and /dev/urandom manpage only talks
about CPRNG.

To me it is much more important we define these in terms of behavior,
which should them translate into care or not care about entropy
quality. With that in mind we may decide to add a timeout parameter to
the random number generator and then use that to decide the quality of
the entropy to use, if the user cannot wait then perhaps using
HMAC_PRNG shall be sufficient, otherwise it shall read for the entropy
pool directly.

int some_function_that_gets_entropy(uint8_t *buffer, uint16_t length);
I'd suggest something like this:

int sys_random_get(uint8_t *buffer, uint16_t length, uint32_t timeout);
int sys_random_put(const uint8_t *buffer, uint16_t length, uint32_t timeout);

I was intending to use a k_msgq to implement the entropy pool, but if
we put and get byte a byte I think I might have to reconsider, or
perhaps handle the chunks internally by calling multiple times
k_msgq_put and k_msgq_get but Im not sure I will be able to honor the
timeout properly so perhaps it would be a better idea to define a
minimal entropy size, if the caller needs more than that then it
should call it multiple times.

> > On systems with copious, low cost HW entropy we could simply wire
> > sys_prng_get() to the hw entropy source and bypass the prng
> > completely.
>
> Btw, isn't depending on one source of entropy alone bad/broken? I
> understand it is currently like this because the did not exist any
> way to collect entropy from other sources, but now we are talking
> about introducing one so we might as well switch from the driver
> given the random number to the driver working as a source of
> entropy which is then collected by random subsystem.
Fair point, if there are multiple sources available then best practice
would be to mix all the sources. I think that this therefore implies
the legacy/existing sys_rand32_get() function should be rewired to
pull entropy from a pool and the pool should be fed by all available
sources. However, I am aware that finding other sources of entropy in
a system is a really hard problem since most if not all can be
externally biased. The interface between a pool and the sources of
entropy is likely to be slightly awkward. On the one hand we have the
"random" drivers that can just be called to produce entropy on demand
(although perhaps with limited bandwidth) in this case a pull
interface works, while on the other hand harvesting entropy from other
parts of the system will likely need to be structured as a push
interface.
I guess we can have both pull and push, for the most part it should be
a push interface feeding the entropy pool, but as soon the pool runs
out or we need a new seed we should attempt to pull, obviously the
pull method shall only be used in case the user have provide a
timeout, that way the driver can go ahead and take that time to
generate more entropy and when it is done wake up the thread waiting
it.

We may also add a k_work to request more entropy from the driver in
case we are sort of entropy in the pool, that should prevent errors
when users need a random number immediately that could otherwise be
provided e.g. HMAC_PRNG but that fails since it needs to be reseeded.
It turns out I was wrong in guessing how it works in Linux, in fact
both /dev/random and /dev/urandom uses PRNG, the only difference is
how they read as random does reads from a pool which collects entropy
_after_ PRNG gets reseed while urandom just reads directly for PRNG
generator:

http://www.2uo.de/myths-about-urandom/

We also probably need an entropy estimation, de-biasing and whitening
before reseeding, or we trust the sources do that properly but Im
afraid we might need some form of whitening anyway.


> Btw, regarding the implementation sys_urand32_get, if you agree
> with that, that might use sys_rand32_get to seed.
This structure seems reasonable to me.

Cheers
/Marcus


--
Luiz Augusto von Dentz


--
Luiz Augusto von Dentz