Re: randomise arc4random() rekey interval
On Sat, Jul 30, 2022 at 06:40:21PM +1000, Damien Miller wrote:
> On Fri, 29 Jul 2022, Theo de Raadt wrote:
>
> > The question is what _rs_random_u32() will do when it calls
> > _rs_stir_if_needed().
> >
> > There is one potential problem. lib/libcrypto/arc4random/*.h contains
> > portable wrappers for _rs_forkdetect(), which actually do things.
> > memset(rs, 0, sizeof(*rs)) will trash the rs state. Let's imagine a
> > "fork" has happened same time that bytes run out.
> >
> > _rs_stir()
> > ...
> > rs->rs_count = REKEY_BASE;
> > _rs_random_u32 -> _rs_stir_if_needed -> _rs_forkdetect
> > - all rs fields are zero'd with memset
> > - _rs_forkdetect returns
> >
> > back in _rs_stir_if_needed,
> > - if (!rs || rs->rs_count <= len)
> >_rs_stir();
> >
> >
> > So it will recurse once (only once, because a 2nd fork cannot happen).
> > But this is fragile.
> >
> > Alternatives are to get the value direct from getentropy -- with
> > KEYSZ + IVSZ + 4 maybe? Or fetch a value for this random bias early
> > and track it in rs, but don't damage it in the memset? Or split
> > _rs_random_u32() so that a sub-function of it may collect these 4
> > keystream bytes without the _rs_stir_if_needed/_rs_rekey checks?
>
> I don't see how a fork could trash these - do you mean one that
> happened in a thread or a signal handler? AFAIK arc4random() isn't
> safe in these contexts right now, even without fork().
>
> Anyway, this version invokes the chacha context directly so there's
> not possibility of _rs_stir() reentrance. It is still not safe against
> something clobbering rsx concurrently (but neither is the existing
> code).
>
> Index: crypt/arc4random.c
> ===
> RCS file: /cvs/src/lib/libc/crypt/arc4random.c,v
> retrieving revision 1.56
> diff -u -p -r1.56 arc4random.c
> --- crypt/arc4random.c28 Feb 2022 21:56:29 - 1.56
> +++ crypt/arc4random.c30 Jul 2022 08:38:44 -
> @@ -49,6 +49,8 @@
> #define BLOCKSZ 64
> #define RSBUFSZ (16*BLOCKSZ)
>
> +#define REKEY_BASE (1024*1024) /* NB. should be a power of 2 */
> +
> /* Marked MAP_INHERIT_ZERO, so zero'd out in fork children. */
> static struct _rs {
> size_t rs_have;/* valid bytes at end of rs_buf */
> @@ -86,6 +88,7 @@ static void
> _rs_stir(void)
> {
> u_char rnd[KEYSZ + IVSZ];
> + uint32_t rekey_fuzz = 0;
>
> if (getentropy(rnd, sizeof rnd) == -1)
> _getentropy_fail();
> @@ -100,7 +103,10 @@ _rs_stir(void)
> rs->rs_have = 0;
> memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
>
> - rs->rs_count = 160;
> + /* rekey interval should not be predictable */
> + chacha_encrypt_bytes(>rs_chacha, (uint8_t *)_fuzz,
> + (uint8_t *)_fuzz, sizeof(rekey_fuzz));
> + rs->rs_count += REKEY_BASE + (rekey_fuzz % REKEY_BASE);
Replace += with =. With that fixed, OK visa@
Re: randomise arc4random() rekey interval
On Fri, 29 Jul 2022, Theo de Raadt wrote:
> The question is what _rs_random_u32() will do when it calls
> _rs_stir_if_needed().
>
> There is one potential problem. lib/libcrypto/arc4random/*.h contains
> portable wrappers for _rs_forkdetect(), which actually do things.
> memset(rs, 0, sizeof(*rs)) will trash the rs state. Let's imagine a
> "fork" has happened same time that bytes run out.
>
> _rs_stir()
> ...
> rs->rs_count = REKEY_BASE;
> _rs_random_u32 -> _rs_stir_if_needed -> _rs_forkdetect
> - all rs fields are zero'd with memset
> - _rs_forkdetect returns
>
> back in _rs_stir_if_needed,
>- if (!rs || rs->rs_count <= len)
>_rs_stir();
>
>
> So it will recurse once (only once, because a 2nd fork cannot happen).
> But this is fragile.
>
> Alternatives are to get the value direct from getentropy -- with
> KEYSZ + IVSZ + 4 maybe? Or fetch a value for this random bias early
> and track it in rs, but don't damage it in the memset? Or split
> _rs_random_u32() so that a sub-function of it may collect these 4
> keystream bytes without the _rs_stir_if_needed/_rs_rekey checks?
I don't see how a fork could trash these - do you mean one that
happened in a thread or a signal handler? AFAIK arc4random() isn't
safe in these contexts right now, even without fork().
Anyway, this version invokes the chacha context directly so there's
not possibility of _rs_stir() reentrance. It is still not safe against
something clobbering rsx concurrently (but neither is the existing
code).
Index: crypt/arc4random.c
===
RCS file: /cvs/src/lib/libc/crypt/arc4random.c,v
retrieving revision 1.56
diff -u -p -r1.56 arc4random.c
--- crypt/arc4random.c 28 Feb 2022 21:56:29 - 1.56
+++ crypt/arc4random.c 30 Jul 2022 08:38:44 -
@@ -49,6 +49,8 @@
#define BLOCKSZ64
#define RSBUFSZ(16*BLOCKSZ)
+#define REKEY_BASE (1024*1024) /* NB. should be a power of 2 */
+
/* Marked MAP_INHERIT_ZERO, so zero'd out in fork children. */
static struct _rs {
size_t rs_have;/* valid bytes at end of rs_buf */
@@ -86,6 +88,7 @@ static void
_rs_stir(void)
{
u_char rnd[KEYSZ + IVSZ];
+ uint32_t rekey_fuzz = 0;
if (getentropy(rnd, sizeof rnd) == -1)
_getentropy_fail();
@@ -100,7 +103,10 @@ _rs_stir(void)
rs->rs_have = 0;
memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
- rs->rs_count = 160;
+ /* rekey interval should not be predictable */
+ chacha_encrypt_bytes(>rs_chacha, (uint8_t *)_fuzz,
+(uint8_t *)_fuzz, sizeof(rekey_fuzz));
+ rs->rs_count += REKEY_BASE + (rekey_fuzz % REKEY_BASE);
}
static inline void
Re: randomise arc4random() rekey interval
>Another option is to move the _rs_stir_if_needed() calls from >_rs_random_u32() and _rs_random_buf() to arc4random() and >arc4random_buf(). The latter two are the subsystem's entry points. That requires more careful review of the -portable versions in libcrypto. It seems they were forgotten. Maybe in a few years some of these will go away.. >Taking the fuzz value directly from getentropy() would be a clear >approach that does not add odd hoops, though some might feel it >uneconomic use of system entropy. ;) There is no such thing as 'system entropy' cost. The kernel buffer is mostly a long-duration chacha also, with the occasional refresh to pull from another sequence which does not measure entropy at all. This measuring entropy idea is garbage, and dead. The only concern for not doing this is system call overhead. arc4random one of the oldest ideas in computer science -- a local cache.
Re: randomise arc4random() rekey interval
On Fri, Jul 29, 2022 at 06:56:08AM -0600, Theo de Raadt wrote: > Visa Hankala wrote: > > > On Thu, Jul 28, 2022 at 11:00:12AM +1000, Damien Miller wrote: > > > + rs->rs_count = REKEY_BASE; > > > + /* rekey interval should not be predictable */ > > > + _rs_random_u32(_fuzz); > > > + rs->rs_count += rekey_fuzz % REKEY_BASE; > > > > The randomization looks good. > > > > However, might it cause a problem (in the future) that _rs_random_u32() > > calls _rs_stir_if_needed()? rs_count has a largish value so a recursive > > invocation of _rs_stir() should not happen, but anyway. > > The question is what _rs_random_u32() will do when it calls > _rs_stir_if_needed(). > > There is one potential problem. lib/libcrypto/arc4random/*.h contains > portable > wrappers for _rs_forkdetect(), which actually do things. memset(rs, 0, > sizeof(*rs)) > will trash the rs state. Let's imagine a "fork" has happened same time that > bytes > run out. > > _rs_stir() > ... > rs->rs_count = REKEY_BASE; > _rs_random_u32 -> _rs_stir_if_needed -> _rs_forkdetect > - all rs fields are zero'd with memset > - _rs_forkdetect returns > > back in _rs_stir_if_needed, >- if (!rs || rs->rs_count <= len) >_rs_stir(); > > > So it will recurse once (only once, because a 2nd fork cannot happen). > But this is fragile. > > Alternatives are to get the value direct from getentropy -- with KEYSZ + IVSZ > + 4 > maybe? Or fetch a value for this random bias early and track it in rs, but > don't > damage it in the memset? Or split _rs_random_u32() so that a sub-function of > it > may collect these 4 keystream bytes without the _rs_stir_if_needed/_rs_rekey > checks? _rs_stir() clears rs_buf, so a rekey is needed if the fuzz value is taken from the keystream. Another option is to move the _rs_stir_if_needed() calls from _rs_random_u32() and _rs_random_buf() to arc4random() and arc4random_buf(). The latter two are the subsystem's entry points. Taking the fuzz value directly from getentropy() would be a clear approach that does not add odd hoops, though some might feel it uneconomic use of system entropy. ;)
Re: randomise arc4random() rekey interval
Visa Hankala wrote: > On Thu, Jul 28, 2022 at 11:00:12AM +1000, Damien Miller wrote: > > + rs->rs_count = REKEY_BASE; > > + /* rekey interval should not be predictable */ > > + _rs_random_u32(_fuzz); > > + rs->rs_count += rekey_fuzz % REKEY_BASE; > > The randomization looks good. > > However, might it cause a problem (in the future) that _rs_random_u32() > calls _rs_stir_if_needed()? rs_count has a largish value so a recursive > invocation of _rs_stir() should not happen, but anyway. The question is what _rs_random_u32() will do when it calls _rs_stir_if_needed(). There is one potential problem. lib/libcrypto/arc4random/*.h contains portable wrappers for _rs_forkdetect(), which actually do things. memset(rs, 0, sizeof(*rs)) will trash the rs state. Let's imagine a "fork" has happened same time that bytes run out. _rs_stir() ... rs->rs_count = REKEY_BASE; _rs_random_u32 -> _rs_stir_if_needed -> _rs_forkdetect - all rs fields are zero'd with memset - _rs_forkdetect returns back in _rs_stir_if_needed, - if (!rs || rs->rs_count <= len) _rs_stir(); So it will recurse once (only once, because a 2nd fork cannot happen). But this is fragile. Alternatives are to get the value direct from getentropy -- with KEYSZ + IVSZ + 4 maybe? Or fetch a value for this random bias early and track it in rs, but don't damage it in the memset? Or split _rs_random_u32() so that a sub-function of it may collect these 4 keystream bytes without the _rs_stir_if_needed/_rs_rekey checks?
Re: randomise arc4random() rekey interval
On Thu, Jul 28, 2022 at 11:00:12AM +1000, Damien Miller wrote: > + rs->rs_count = REKEY_BASE; > + /* rekey interval should not be predictable */ > + _rs_random_u32(_fuzz); > + rs->rs_count += rekey_fuzz % REKEY_BASE; The randomization looks good. However, might it cause a problem (in the future) that _rs_random_u32() calls _rs_stir_if_needed()? rs_count has a largish value so a recursive invocation of _rs_stir() should not happen, but anyway.
Re: randomise arc4random() rekey interval
I've always loved these little feedback loops in the random subsystem,
where it relies upon it's own random state to subtly change the meaning
of future events.
Damien Miller wrote:
> On Thu, 28 Jul 2022, Damien Miller wrote:
>
> > On Wed, 27 Jul 2022, Theo de Raadt wrote:
> >
> > > + rs->rs_count += rekey_fuzz & (REKEY_BASE - 1);
> > >
> > > I mean, why not use % here
> >
> > Sure, that's reasonable.
>
> revised:
>
> Index: crypt/arc4random.c
> ===
> RCS file: /cvs/src/lib/libc/crypt/arc4random.c,v
> retrieving revision 1.56
> diff -u -p -r1.56 arc4random.c
> --- crypt/arc4random.c28 Feb 2022 21:56:29 - 1.56
> +++ crypt/arc4random.c28 Jul 2022 00:59:34 -
> @@ -49,6 +49,8 @@
> #define BLOCKSZ 64
> #define RSBUFSZ (16*BLOCKSZ)
>
> +#define REKEY_BASE (1024*1024) /* NB. should be a power of 2 */
> +
> /* Marked MAP_INHERIT_ZERO, so zero'd out in fork children. */
> static struct _rs {
> size_t rs_have;/* valid bytes at end of rs_buf */
> @@ -63,6 +65,8 @@ static struct _rsx {
>
> static inline int _rs_allocate(struct _rs **, struct _rsx **);
> static inline void _rs_forkdetect(void);
> +static inline void _rs_random_u32(uint32_t *);
> +
> #include "arc4random.h"
>
> static inline void _rs_rekey(u_char *dat, size_t datlen);
> @@ -86,6 +90,7 @@ static void
> _rs_stir(void)
> {
> u_char rnd[KEYSZ + IVSZ];
> + uint32_t rekey_fuzz;
>
> if (getentropy(rnd, sizeof rnd) == -1)
> _getentropy_fail();
> @@ -100,7 +105,10 @@ _rs_stir(void)
> rs->rs_have = 0;
> memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
>
> - rs->rs_count = 160;
> + rs->rs_count = REKEY_BASE;
> + /* rekey interval should not be predictable */
> + _rs_random_u32(_fuzz);
> + rs->rs_count += rekey_fuzz % REKEY_BASE;
> }
>
> static inline void
Re: randomise arc4random() rekey interval
On Thu, 28 Jul 2022, Damien Miller wrote:
> On Wed, 27 Jul 2022, Theo de Raadt wrote:
>
> > + rs->rs_count += rekey_fuzz & (REKEY_BASE - 1);
> >
> > I mean, why not use % here
>
> Sure, that's reasonable.
revised:
Index: crypt/arc4random.c
===
RCS file: /cvs/src/lib/libc/crypt/arc4random.c,v
retrieving revision 1.56
diff -u -p -r1.56 arc4random.c
--- crypt/arc4random.c 28 Feb 2022 21:56:29 - 1.56
+++ crypt/arc4random.c 28 Jul 2022 00:59:34 -
@@ -49,6 +49,8 @@
#define BLOCKSZ64
#define RSBUFSZ(16*BLOCKSZ)
+#define REKEY_BASE (1024*1024) /* NB. should be a power of 2 */
+
/* Marked MAP_INHERIT_ZERO, so zero'd out in fork children. */
static struct _rs {
size_t rs_have;/* valid bytes at end of rs_buf */
@@ -63,6 +65,8 @@ static struct _rsx {
static inline int _rs_allocate(struct _rs **, struct _rsx **);
static inline void _rs_forkdetect(void);
+static inline void _rs_random_u32(uint32_t *);
+
#include "arc4random.h"
static inline void _rs_rekey(u_char *dat, size_t datlen);
@@ -86,6 +90,7 @@ static void
_rs_stir(void)
{
u_char rnd[KEYSZ + IVSZ];
+ uint32_t rekey_fuzz;
if (getentropy(rnd, sizeof rnd) == -1)
_getentropy_fail();
@@ -100,7 +105,10 @@ _rs_stir(void)
rs->rs_have = 0;
memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
- rs->rs_count = 160;
+ rs->rs_count = REKEY_BASE;
+ /* rekey interval should not be predictable */
+ _rs_random_u32(_fuzz);
+ rs->rs_count += rekey_fuzz % REKEY_BASE;
}
static inline void
Re: randomise arc4random() rekey interval
> because we can't use arc4random_uniform() in this context. But who says it has to be uniform?? It is code which wasn't even there before. Or put it a different way, this additional you are adding used to be uniformly zero, or ununiformly zero...
Re: randomise arc4random() rekey interval
On Wed, 27 Jul 2022, Theo de Raadt wrote: > + rs->rs_count += rekey_fuzz & (REKEY_BASE - 1); > > I mean, why not use % here Sure, that's reasonable. > And then, set the default to a pow2. > > But if someone changes it to not pow2, it still works. > > The & is premature hand-optimization, let a compiler do it if it can.
Re: randomise arc4random() rekey interval
On Wed, 27 Jul 2022, Theo de Raadt wrote: > I love it. > > > +#define REKEY_BASE (1<<20) /* NB. *must* be a power of 2 */ > > Why insist on that? Because I need to do this later: + rs->rs_count += rekey_fuzz & (REKEY_BASE - 1); because we can't use arc4random_uniform() in this context. > Also, I would prefer (1024*1024), it is quicker to read. ack
Re: randomise arc4random() rekey interval
+ rs->rs_count += rekey_fuzz & (REKEY_BASE - 1); I mean, why not use % here And then, set the default to a pow2. But if someone changes it to not pow2, it still works. The & is premature hand-optimization, let a compiler do it if it can.
Re: randomise arc4random() rekey interval
I love it. > +#define REKEY_BASE (1<<20) /* NB. *must* be a power of 2 */ Why insist on that? Also, I would prefer (1024*1024), it is quicker to read.
