[1/6] eal: replace libc-based random number generation with LFSR
Checks
Commit Message
This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
combined Linear Feedback Shift Register (LFSR) (also known as
Tausworthe) pseudo-random number generator.
This generator is faster and produces better-quality random numbers
than the linear congruential generator (LCG) of lib's lrand48(). The
implementation, as opposed to lrand48(), is multi-thread safe in
regards to concurrent rte_rand() calls from different lcore threads.
A LCG is still used, but only to seed the five per-lcore LFSR
sequences.
In addition, this patch also addresses the issue of the legacy
implementation only producing 62 bits of pseudo randomness, while the
API requires all 64 bits to be random.
This pseudo-random number generator is not cryptographically secure -
just like lrand48().
Bugzilla ID: 114
Bugzilla ID: 276
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
lib/librte_eal/common/include/rte_random.h | 29 ++---
lib/librte_eal/common/meson.build | 1 +
lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++
lib/librte_eal/freebsd/eal/Makefile | 1 +
lib/librte_eal/freebsd/eal/eal.c | 2 -
lib/librte_eal/linux/eal/Makefile | 1 +
lib/librte_eal/linux/eal/eal.c | 2 -
lib/librte_eal/rte_eal_version.map | 8 ++
8 files changed, 161 insertions(+), 22 deletions(-)
create mode 100644 lib/librte_eal/common/rte_random.c
Comments
On 2019-05-14 11:20, Mattias Rönnblom wrote:
>
> Bugzilla ID: 114
> Bugzilla ID: 276
>
I don't know which, if any, of these bugs you want to address in any
stable releases.
If fixing bug 276 "rte_rand() bit 31 and 63 are always zero" is enough,
then one could either split this patch set in two (w/ only the new
rte_rand() going into stable), or develop a smaller fix based on lrand48().
Since the old implementation was an inline function, any fix will
require a recompilation.
On Tue, May 14, 2019 at 11:20:41AM +0200, Mattias Rönnblom wrote:
> This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
> combined Linear Feedback Shift Register (LFSR) (also known as
> Tausworthe) pseudo-random number generator.
>
> This generator is faster and produces better-quality random numbers
> than the linear congruential generator (LCG) of lib's lrand48(). The
> implementation, as opposed to lrand48(), is multi-thread safe in
> regards to concurrent rte_rand() calls from different lcore threads.
> A LCG is still used, but only to seed the five per-lcore LFSR
> sequences.
>
> In addition, this patch also addresses the issue of the legacy
> implementation only producing 62 bits of pseudo randomness, while the
> API requires all 64 bits to be random.
>
> This pseudo-random number generator is not cryptographically secure -
> just like lrand48().
>
> Bugzilla ID: 114
> Bugzilla ID: 276
>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> ---
> lib/librte_eal/common/include/rte_random.h | 29 ++---
> lib/librte_eal/common/meson.build | 1 +
> lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++
> lib/librte_eal/freebsd/eal/Makefile | 1 +
> lib/librte_eal/freebsd/eal/eal.c | 2 -
> lib/librte_eal/linux/eal/Makefile | 1 +
> lib/librte_eal/linux/eal/eal.c | 2 -
> lib/librte_eal/rte_eal_version.map | 8 ++
> 8 files changed, 161 insertions(+), 22 deletions(-)
> create mode 100644 lib/librte_eal/common/rte_random.c
>
> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> index b2ca1c209..66dfe8ae7 100644
> --- a/lib/librte_eal/common/include/rte_random.h
> +++ b/lib/librte_eal/common/include/rte_random.h
> @@ -16,7 +16,6 @@ extern "C" {
> #endif
>
> #include <stdint.h>
> -#include <stdlib.h>
>
> /**
> * Seed the pseudo-random generator.
> @@ -25,34 +24,28 @@ extern "C" {
> * value. It may need to be re-seeded by the user with a real random
> * value.
> *
> + * This function is not multi-thread safe in regards to other
> + * rte_srand() calls, nor is it in relation to concurrent rte_rand()
> + * calls.
> + *
> * @param seedval
> * The value of the seed.
> */
> -static inline void
> -rte_srand(uint64_t seedval)
> -{
> - srand48((long)seedval);
> -}
> +void
> +rte_srand(uint64_t seedval);
>
> /**
> * Get a pseudo-random value.
> *
> - * This function generates pseudo-random numbers using the linear
> - * congruential algorithm and 48-bit integer arithmetic, called twice
> - * to generate a 64-bit value.
> + * The generator is not cryptographically secure.
> + *
> + * If called from lcore threads, this function is thread-safe.
> *
> * @return
> * A pseudo-random value between 0 and (1<<64)-1.
> */
> -static inline uint64_t
> -rte_rand(void)
> -{
> - uint64_t val;
> - val = (uint64_t)lrand48();
> - val <<= 32;
> - val += (uint64_t)lrand48();
> - return val;
> -}
> +uint64_t
> +rte_rand(void);
>
> #ifdef __cplusplus
> }
> diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
> index 0670e4102..bafd23207 100644
> --- a/lib/librte_eal/common/meson.build
> +++ b/lib/librte_eal/common/meson.build
> @@ -35,6 +35,7 @@ common_sources = files(
> 'rte_keepalive.c',
> 'rte_malloc.c',
> 'rte_option.c',
> + 'rte_random.c',
> 'rte_reciprocal.c',
> 'rte_service.c'
> )
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> new file mode 100644
> index 000000000..4d3cf5226
> --- /dev/null
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -0,0 +1,139 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Ericsson AB
> + */
> +
> +#include <stdlib.h>
> +
> +#include <rte_branch_prediction.h>
> +#include <rte_cycles.h>
> +#include <rte_eal.h>
> +#include <rte_lcore.h>
> +#include <rte_memory.h>
> +#include <rte_random.h>
> +
> +struct rte_rand_state {
> + uint64_t z1;
> + uint64_t z2;
> + uint64_t z3;
> + uint64_t z4;
> + uint64_t z5;
> +} __rte_cache_aligned;
> +
> +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
> +
It just occured to me that this variable embodies all the state of the rng.
Whats to stop an attacker from digging through ram to get this info and
predicting what the output will be? I understand that this rng probably
shouldn't be considered secure for cryptographic use, but it is used in the
ipsec test example, so it could be mistaken for an rng that is.
Neil
>
On 2019-05-14 16:16, Neil Horman wrote:
> On Tue, May 14, 2019 at 11:20:41AM +0200, Mattias Rönnblom wrote:
>> This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
>> combined Linear Feedback Shift Register (LFSR) (also known as
>> Tausworthe) pseudo-random number generator.
>>
>> This generator is faster and produces better-quality random numbers
>> than the linear congruential generator (LCG) of lib's lrand48(). The
>> implementation, as opposed to lrand48(), is multi-thread safe in
>> regards to concurrent rte_rand() calls from different lcore threads.
>> A LCG is still used, but only to seed the five per-lcore LFSR
>> sequences.
>>
>> In addition, this patch also addresses the issue of the legacy
>> implementation only producing 62 bits of pseudo randomness, while the
>> API requires all 64 bits to be random.
>>
>> This pseudo-random number generator is not cryptographically secure -
>> just like lrand48().
>>
>> Bugzilla ID: 114
>> Bugzilla ID: 276
>>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> ---
>> lib/librte_eal/common/include/rte_random.h | 29 ++---
>> lib/librte_eal/common/meson.build | 1 +
>> lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++
>> lib/librte_eal/freebsd/eal/Makefile | 1 +
>> lib/librte_eal/freebsd/eal/eal.c | 2 -
>> lib/librte_eal/linux/eal/Makefile | 1 +
>> lib/librte_eal/linux/eal/eal.c | 2 -
>> lib/librte_eal/rte_eal_version.map | 8 ++
>> 8 files changed, 161 insertions(+), 22 deletions(-)
>> create mode 100644 lib/librte_eal/common/rte_random.c
>>
>> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
>> index b2ca1c209..66dfe8ae7 100644
>> --- a/lib/librte_eal/common/include/rte_random.h
>> +++ b/lib/librte_eal/common/include/rte_random.h
>> @@ -16,7 +16,6 @@ extern "C" {
>> #endif
>>
>> #include <stdint.h>
>> -#include <stdlib.h>
>>
>> /**
>> * Seed the pseudo-random generator.
>> @@ -25,34 +24,28 @@ extern "C" {
>> * value. It may need to be re-seeded by the user with a real random
>> * value.
>> *
>> + * This function is not multi-thread safe in regards to other
>> + * rte_srand() calls, nor is it in relation to concurrent rte_rand()
>> + * calls.
>> + *
>> * @param seedval
>> * The value of the seed.
>> */
>> -static inline void
>> -rte_srand(uint64_t seedval)
>> -{
>> - srand48((long)seedval);
>> -}
>> +void
>> +rte_srand(uint64_t seedval);
>>
>> /**
>> * Get a pseudo-random value.
>> *
>> - * This function generates pseudo-random numbers using the linear
>> - * congruential algorithm and 48-bit integer arithmetic, called twice
>> - * to generate a 64-bit value.
>> + * The generator is not cryptographically secure.
>> + *
>> + * If called from lcore threads, this function is thread-safe.
>> *
>> * @return
>> * A pseudo-random value between 0 and (1<<64)-1.
>> */
>> -static inline uint64_t
>> -rte_rand(void)
>> -{
>> - uint64_t val;
>> - val = (uint64_t)lrand48();
>> - val <<= 32;
>> - val += (uint64_t)lrand48();
>> - return val;
>> -}
>> +uint64_t
>> +rte_rand(void);
>>
>> #ifdef __cplusplus
>> }
>> diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
>> index 0670e4102..bafd23207 100644
>> --- a/lib/librte_eal/common/meson.build
>> +++ b/lib/librte_eal/common/meson.build
>> @@ -35,6 +35,7 @@ common_sources = files(
>> 'rte_keepalive.c',
>> 'rte_malloc.c',
>> 'rte_option.c',
>> + 'rte_random.c',
>> 'rte_reciprocal.c',
>> 'rte_service.c'
>> )
>> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
>> new file mode 100644
>> index 000000000..4d3cf5226
>> --- /dev/null
>> +++ b/lib/librte_eal/common/rte_random.c
>> @@ -0,0 +1,139 @@
>> +/* SPDX-License-Identifier: BSD-3-Clause
>> + * Copyright(c) 2019 Ericsson AB
>> + */
>> +
>> +#include <stdlib.h>
>> +
>> +#include <rte_branch_prediction.h>
>> +#include <rte_cycles.h>
>> +#include <rte_eal.h>
>> +#include <rte_lcore.h>
>> +#include <rte_memory.h>
>> +#include <rte_random.h>
>> +
>> +struct rte_rand_state {
>> + uint64_t z1;
>> + uint64_t z2;
>> + uint64_t z3;
>> + uint64_t z4;
>> + uint64_t z5;
>> +} __rte_cache_aligned;
>> +
>> +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
>> +
>
> It just occured to me that this variable embodies all the state of the rng.
> Whats to stop an attacker from digging through ram to get this info and
> predicting what the output will be? I understand that this rng probably
> shouldn't be considered secure for cryptographic use, but it is used in the
> ipsec test example, so it could be mistaken for an rng that is.
>
rte_rand() was never safe for use in cryptography, and now it's spelled
out in the API documentation.
If the IPsec example uses rte_rand() for anything security-related, it's
a bug or at least should be accompanied by a comment, in my opinion.
That said, if you have an attacker who's already broken into your DPDK
process' virtual memory, I'm not sure I understand why he would care
much about the state of the PRNG. Wouldn't he just read your private
keys, your messages in clear text or whatever other secrets you might
have in memory?
On Tue, 14 May 2019 11:20:41 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> +RTE_INIT(rte_rand_init)
> +{
> + rte_srand(rte_get_timer_cycles());
> +}
Please make initialization OS specific and use get_random() on Linux.
On Tue, May 14, 2019 at 04:53:08PM +0200, Mattias Rönnblom wrote:
> On 2019-05-14 16:16, Neil Horman wrote:
> > On Tue, May 14, 2019 at 11:20:41AM +0200, Mattias Rönnblom wrote:
> > > This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
> > > combined Linear Feedback Shift Register (LFSR) (also known as
> > > Tausworthe) pseudo-random number generator.
> > >
> > > This generator is faster and produces better-quality random numbers
> > > than the linear congruential generator (LCG) of lib's lrand48(). The
> > > implementation, as opposed to lrand48(), is multi-thread safe in
> > > regards to concurrent rte_rand() calls from different lcore threads.
> > > A LCG is still used, but only to seed the five per-lcore LFSR
> > > sequences.
> > >
> > > In addition, this patch also addresses the issue of the legacy
> > > implementation only producing 62 bits of pseudo randomness, while the
> > > API requires all 64 bits to be random.
> > >
> > > This pseudo-random number generator is not cryptographically secure -
> > > just like lrand48().
> > >
> > > Bugzilla ID: 114
> > > Bugzilla ID: 276
> > >
> > > Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> > > ---
> > > lib/librte_eal/common/include/rte_random.h | 29 ++---
> > > lib/librte_eal/common/meson.build | 1 +
> > > lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++
> > > lib/librte_eal/freebsd/eal/Makefile | 1 +
> > > lib/librte_eal/freebsd/eal/eal.c | 2 -
> > > lib/librte_eal/linux/eal/Makefile | 1 +
> > > lib/librte_eal/linux/eal/eal.c | 2 -
> > > lib/librte_eal/rte_eal_version.map | 8 ++
> > > 8 files changed, 161 insertions(+), 22 deletions(-)
> > > create mode 100644 lib/librte_eal/common/rte_random.c
> > >
> > > diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> > > index b2ca1c209..66dfe8ae7 100644
> > > --- a/lib/librte_eal/common/include/rte_random.h
> > > +++ b/lib/librte_eal/common/include/rte_random.h
> > > @@ -16,7 +16,6 @@ extern "C" {
> > > #endif
> > >
> > > #include <stdint.h>
> > > -#include <stdlib.h>
> > >
> > > /**
> > > * Seed the pseudo-random generator.
> > > @@ -25,34 +24,28 @@ extern "C" {
> > > * value. It may need to be re-seeded by the user with a real random
> > > * value.
> > > *
> > > + * This function is not multi-thread safe in regards to other
> > > + * rte_srand() calls, nor is it in relation to concurrent rte_rand()
> > > + * calls.
> > > + *
> > > * @param seedval
> > > * The value of the seed.
> > > */
> > > -static inline void
> > > -rte_srand(uint64_t seedval)
> > > -{
> > > - srand48((long)seedval);
> > > -}
> > > +void
> > > +rte_srand(uint64_t seedval);
> > >
> > > /**
> > > * Get a pseudo-random value.
> > > *
> > > - * This function generates pseudo-random numbers using the linear
> > > - * congruential algorithm and 48-bit integer arithmetic, called twice
> > > - * to generate a 64-bit value.
> > > + * The generator is not cryptographically secure.
> > > + *
> > > + * If called from lcore threads, this function is thread-safe.
> > > *
> > > * @return
> > > * A pseudo-random value between 0 and (1<<64)-1.
> > > */
> > > -static inline uint64_t
> > > -rte_rand(void)
> > > -{
> > > - uint64_t val;
> > > - val = (uint64_t)lrand48();
> > > - val <<= 32;
> > > - val += (uint64_t)lrand48();
> > > - return val;
> > > -}
> > > +uint64_t
> > > +rte_rand(void);
> > >
> > > #ifdef __cplusplus
> > > }
> > > diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
> > > index 0670e4102..bafd23207 100644
> > > --- a/lib/librte_eal/common/meson.build
> > > +++ b/lib/librte_eal/common/meson.build
> > > @@ -35,6 +35,7 @@ common_sources = files(
> > > 'rte_keepalive.c',
> > > 'rte_malloc.c',
> > > 'rte_option.c',
> > > + 'rte_random.c',
> > > 'rte_reciprocal.c',
> > > 'rte_service.c'
> > > )
> > > diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> > > new file mode 100644
> > > index 000000000..4d3cf5226
> > > --- /dev/null
> > > +++ b/lib/librte_eal/common/rte_random.c
> > > @@ -0,0 +1,139 @@
> > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > + * Copyright(c) 2019 Ericsson AB
> > > + */
> > > +
> > > +#include <stdlib.h>
> > > +
> > > +#include <rte_branch_prediction.h>
> > > +#include <rte_cycles.h>
> > > +#include <rte_eal.h>
> > > +#include <rte_lcore.h>
> > > +#include <rte_memory.h>
> > > +#include <rte_random.h>
> > > +
> > > +struct rte_rand_state {
> > > + uint64_t z1;
> > > + uint64_t z2;
> > > + uint64_t z3;
> > > + uint64_t z4;
> > > + uint64_t z5;
> > > +} __rte_cache_aligned;
> > > +
> > > +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
> > > +
> >
> > It just occured to me that this variable embodies all the state of the rng.
> > Whats to stop an attacker from digging through ram to get this info and
> > predicting what the output will be? I understand that this rng probably
> > shouldn't be considered secure for cryptographic use, but it is used in the
> > ipsec test example, so it could be mistaken for an rng that is.
> >
>
> rte_rand() was never safe for use in cryptography, and now it's spelled out
> in the API documentation.
>
> If the IPsec example uses rte_rand() for anything security-related, it's a
> bug or at least should be accompanied by a comment, in my opinion.
>
I would agree with that, but the fact remains that the examples use rte_rand in
a context that is explicitly in violation of what you are documenting, which
certainly seems confusing.
> That said, if you have an attacker who's already broken into your DPDK
> process' virtual memory, I'm not sure I understand why he would care much
> about the state of the PRNG. Wouldn't he just read your private keys, your
> messages in clear text or whatever other secrets you might have in memory?
>
Because the term "Breaking in" is a misnomer here. In unix system, IIRC, global
variables are shared accross processes. Breaking in to get this information is
as simple as writing a program that links against the dpdk shared library, or
just dlopens it and looks up the requisite symbol address. And while thats true
of any symbol, given the prior example which uses rte_rand for a cryptographic
purpose, it seems like this would be a particularly tempting target to exploit.
Either way, asserting that its fine to do this because any method that gives you
access to it gives you access to other information is really not a great
argument. We should protect application data wherever we can, and the integrity
of the randomness of data seems like a case in point.
Neil
On Fri, May 17, 2019 at 03:27:25PM -0400, Neil Horman wrote:
> On Tue, May 14, 2019 at 04:53:08PM +0200, Mattias Rönnblom wrote:
> > On 2019-05-14 16:16, Neil Horman wrote:
> > > On Tue, May 14, 2019 at 11:20:41AM +0200, Mattias Rönnblom wrote:
> > > > This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
> > > > combined Linear Feedback Shift Register (LFSR) (also known as
> > > > Tausworthe) pseudo-random number generator.
> > > >
> > > > This generator is faster and produces better-quality random numbers
> > > > than the linear congruential generator (LCG) of lib's lrand48(). The
> > > > implementation, as opposed to lrand48(), is multi-thread safe in
> > > > regards to concurrent rte_rand() calls from different lcore threads.
> > > > A LCG is still used, but only to seed the five per-lcore LFSR
> > > > sequences.
> > > >
> > > > In addition, this patch also addresses the issue of the legacy
> > > > implementation only producing 62 bits of pseudo randomness, while the
> > > > API requires all 64 bits to be random.
> > > >
> > > > This pseudo-random number generator is not cryptographically secure -
> > > > just like lrand48().
> > > >
> > > > Bugzilla ID: 114
> > > > Bugzilla ID: 276
> > > >
> > > > Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> > > > ---
> > > > lib/librte_eal/common/include/rte_random.h | 29 ++---
> > > > lib/librte_eal/common/meson.build | 1 +
> > > > lib/librte_eal/common/rte_random.c | 139 +++++++++++++++++++++
> > > > lib/librte_eal/freebsd/eal/Makefile | 1 +
> > > > lib/librte_eal/freebsd/eal/eal.c | 2 -
> > > > lib/librte_eal/linux/eal/Makefile | 1 +
> > > > lib/librte_eal/linux/eal/eal.c | 2 -
> > > > lib/librte_eal/rte_eal_version.map | 8 ++
> > > > 8 files changed, 161 insertions(+), 22 deletions(-)
> > > > create mode 100644 lib/librte_eal/common/rte_random.c
> > > >
> > > > diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> > > > index b2ca1c209..66dfe8ae7 100644
> > > > --- a/lib/librte_eal/common/include/rte_random.h
> > > > +++ b/lib/librte_eal/common/include/rte_random.h
> > > > @@ -16,7 +16,6 @@ extern "C" {
> > > > #endif
> > > >
> > > > #include <stdint.h>
> > > > -#include <stdlib.h>
> > > >
> > > > /**
> > > > * Seed the pseudo-random generator.
> > > > @@ -25,34 +24,28 @@ extern "C" {
> > > > * value. It may need to be re-seeded by the user with a real random
> > > > * value.
> > > > *
> > > > + * This function is not multi-thread safe in regards to other
> > > > + * rte_srand() calls, nor is it in relation to concurrent rte_rand()
> > > > + * calls.
> > > > + *
> > > > * @param seedval
> > > > * The value of the seed.
> > > > */
> > > > -static inline void
> > > > -rte_srand(uint64_t seedval)
> > > > -{
> > > > - srand48((long)seedval);
> > > > -}
> > > > +void
> > > > +rte_srand(uint64_t seedval);
> > > >
> > > > /**
> > > > * Get a pseudo-random value.
> > > > *
> > > > - * This function generates pseudo-random numbers using the linear
> > > > - * congruential algorithm and 48-bit integer arithmetic, called twice
> > > > - * to generate a 64-bit value.
> > > > + * The generator is not cryptographically secure.
> > > > + *
> > > > + * If called from lcore threads, this function is thread-safe.
> > > > *
> > > > * @return
> > > > * A pseudo-random value between 0 and (1<<64)-1.
> > > > */
> > > > -static inline uint64_t
> > > > -rte_rand(void)
> > > > -{
> > > > - uint64_t val;
> > > > - val = (uint64_t)lrand48();
> > > > - val <<= 32;
> > > > - val += (uint64_t)lrand48();
> > > > - return val;
> > > > -}
> > > > +uint64_t
> > > > +rte_rand(void);
> > > >
> > > > #ifdef __cplusplus
> > > > }
> > > > diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
> > > > index 0670e4102..bafd23207 100644
> > > > --- a/lib/librte_eal/common/meson.build
> > > > +++ b/lib/librte_eal/common/meson.build
> > > > @@ -35,6 +35,7 @@ common_sources = files(
> > > > 'rte_keepalive.c',
> > > > 'rte_malloc.c',
> > > > 'rte_option.c',
> > > > + 'rte_random.c',
> > > > 'rte_reciprocal.c',
> > > > 'rte_service.c'
> > > > )
> > > > diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> > > > new file mode 100644
> > > > index 000000000..4d3cf5226
> > > > --- /dev/null
> > > > +++ b/lib/librte_eal/common/rte_random.c
> > > > @@ -0,0 +1,139 @@
> > > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > > + * Copyright(c) 2019 Ericsson AB
> > > > + */
> > > > +
> > > > +#include <stdlib.h>
> > > > +
> > > > +#include <rte_branch_prediction.h>
> > > > +#include <rte_cycles.h>
> > > > +#include <rte_eal.h>
> > > > +#include <rte_lcore.h>
> > > > +#include <rte_memory.h>
> > > > +#include <rte_random.h>
> > > > +
> > > > +struct rte_rand_state {
> > > > + uint64_t z1;
> > > > + uint64_t z2;
> > > > + uint64_t z3;
> > > > + uint64_t z4;
> > > > + uint64_t z5;
> > > > +} __rte_cache_aligned;
> > > > +
> > > > +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
> > > > +
> > >
> > > It just occured to me that this variable embodies all the state of the rng.
> > > Whats to stop an attacker from digging through ram to get this info and
> > > predicting what the output will be? I understand that this rng probably
> > > shouldn't be considered secure for cryptographic use, but it is used in the
> > > ipsec test example, so it could be mistaken for an rng that is.
> > >
> >
> > rte_rand() was never safe for use in cryptography, and now it's spelled out
> > in the API documentation.
> >
> > If the IPsec example uses rte_rand() for anything security-related, it's a
> > bug or at least should be accompanied by a comment, in my opinion.
> >
> I would agree with that, but the fact remains that the examples use rte_rand in
> a context that is explicitly in violation of what you are documenting, which
> certainly seems confusing.
>
> > That said, if you have an attacker who's already broken into your DPDK
> > process' virtual memory, I'm not sure I understand why he would care much
> > about the state of the PRNG. Wouldn't he just read your private keys, your
> > messages in clear text or whatever other secrets you might have in memory?
> >
> Because the term "Breaking in" is a misnomer here. In unix system, IIRC, global
> variables are shared accross processes.
That doesn't seem right to me. Data variables, even globals, inside
processes are isolated from other processes unless the data is explicitly
placed in shared memory. Otherwise, what would be the point of having
shared memory areas?
Even for shared libraries, the text segment would be a single copy in
memory, but each process using the library should have it's own data area.
/Bruce
On 2019-05-17 21:27, Neil Horman wrote:
>>>> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
>>>> new file mode 100644
>>>> index 000000000..4d3cf5226
>>>> --- /dev/null
>>>> +++ b/lib/librte_eal/common/rte_random.c
>>>> @@ -0,0 +1,139 @@
>>>> +/* SPDX-License-Identifier: BSD-3-Clause
>>>> + * Copyright(c) 2019 Ericsson AB
>>>> + */
>>>> +
>>>> +#include <stdlib.h>
>>>> +
>>>> +#include <rte_branch_prediction.h>
>>>> +#include <rte_cycles.h>
>>>> +#include <rte_eal.h>
>>>> +#include <rte_lcore.h>
>>>> +#include <rte_memory.h>
>>>> +#include <rte_random.h>
>>>> +
>>>> +struct rte_rand_state {
>>>> + uint64_t z1;
>>>> + uint64_t z2;
>>>> + uint64_t z3;
>>>> + uint64_t z4;
>>>> + uint64_t z5;
>>>> +} __rte_cache_aligned;
>>>> +
>>>> +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
>>>> +
>>>
>>> It just occured to me that this variable embodies all the state of the rng.
>>> Whats to stop an attacker from digging through ram to get this info and
>>> predicting what the output will be? I understand that this rng probably
>>> shouldn't be considered secure for cryptographic use, but it is used in the
>>> ipsec test example, so it could be mistaken for an rng that is.
>>>
>>
>> rte_rand() was never safe for use in cryptography, and now it's spelled out
>> in the API documentation.
>>
>> If the IPsec example uses rte_rand() for anything security-related, it's a
>> bug or at least should be accompanied by a comment, in my opinion.
>>
> I would agree with that, but the fact remains that the examples use rte_rand in
> a context that is explicitly in violation of what you are documenting, which
> certainly seems confusing.
>
>> That said, if you have an attacker who's already broken into your DPDK
>> process' virtual memory, I'm not sure I understand why he would care much
>> about the state of the PRNG. Wouldn't he just read your private keys, your
>> messages in clear text or whatever other secrets you might have in memory?
>>
> Because the term "Breaking in" is a misnomer here. In unix system, IIRC, global
> variables are shared accross processes.
Mutable data, like the BSS section where the PRNG state goes, is not shared.
Does a srand48() call in one process reseed lrand48() PRNGs in all other
processes in the system? No.
> Breaking in to get this information is
> as simple as writing a program that links against the dpdk shared library, or
> just dlopens it and looks up the requisite symbol address.
Two programs using the same shared object do share memory, but the
portions shared are either read-only or copy-on-write (which means
modified pages will be private to the process).
It's even the case that with address space layout randomization (ASLR),
the address of the same symbol varies across different processes.
> And while thats true
> of any symbol, given the prior example which uses rte_rand for a cryptographic
> purpose, it seems like this would be a particularly tempting target to exploit.
> > Either way, asserting that its fine to do this because any method
that gives you
> access to it gives you access to other information is really not a great
> argument. We should protect application data wherever we can, and the integrity
> of the randomness of data seems like a case in point.
UNIX virtual memory and MMU memory protection is already protecting this
data, and has been doing so for the last 30-40 years or so.
On Fri, May 17, 2019 at 11:10:25PM +0200, Mattias Rönnblom wrote:
> On 2019-05-17 21:27, Neil Horman wrote:
>
> > > > > diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> > > > > new file mode 100644
> > > > > index 000000000..4d3cf5226
> > > > > --- /dev/null
> > > > > +++ b/lib/librte_eal/common/rte_random.c
> > > > > @@ -0,0 +1,139 @@
> > > > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > > > + * Copyright(c) 2019 Ericsson AB
> > > > > + */
> > > > > +
> > > > > +#include <stdlib.h>
> > > > > +
> > > > > +#include <rte_branch_prediction.h>
> > > > > +#include <rte_cycles.h>
> > > > > +#include <rte_eal.h>
> > > > > +#include <rte_lcore.h>
> > > > > +#include <rte_memory.h>
> > > > > +#include <rte_random.h>
> > > > > +
> > > > > +struct rte_rand_state {
> > > > > + uint64_t z1;
> > > > > + uint64_t z2;
> > > > > + uint64_t z3;
> > > > > + uint64_t z4;
> > > > > + uint64_t z5;
> > > > > +} __rte_cache_aligned;
> > > > > +
> > > > > +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
> > > > > +
> > > >
> > > > It just occured to me that this variable embodies all the state of the rng.
> > > > Whats to stop an attacker from digging through ram to get this info and
> > > > predicting what the output will be? I understand that this rng probably
> > > > shouldn't be considered secure for cryptographic use, but it is used in the
> > > > ipsec test example, so it could be mistaken for an rng that is.
> > > >
> > >
> > > rte_rand() was never safe for use in cryptography, and now it's spelled out
> > > in the API documentation.
> > >
> > > If the IPsec example uses rte_rand() for anything security-related, it's a
> > > bug or at least should be accompanied by a comment, in my opinion.
> > >
> > I would agree with that, but the fact remains that the examples use rte_rand in
> > a context that is explicitly in violation of what you are documenting, which
> > certainly seems confusing.
> >
> > > That said, if you have an attacker who's already broken into your DPDK
> > > process' virtual memory, I'm not sure I understand why he would care much
> > > about the state of the PRNG. Wouldn't he just read your private keys, your
> > > messages in clear text or whatever other secrets you might have in memory?
> > >
> > Because the term "Breaking in" is a misnomer here. In unix system, IIRC, global
> > variables are shared accross processes.
>
> Mutable data, like the BSS section where the PRNG state goes, is not shared.
>
Yes, you and bruce are right, It is shared, but marked copy on write, so
its safe from the common case of multiple programs loading the object.
Neil
>
@@ -16,7 +16,6 @@ extern "C" {
#endif
#include <stdint.h>
-#include <stdlib.h>
/**
* Seed the pseudo-random generator.
@@ -25,34 +24,28 @@ extern "C" {
* value. It may need to be re-seeded by the user with a real random
* value.
*
+ * This function is not multi-thread safe in regards to other
+ * rte_srand() calls, nor is it in relation to concurrent rte_rand()
+ * calls.
+ *
* @param seedval
* The value of the seed.
*/
-static inline void
-rte_srand(uint64_t seedval)
-{
- srand48((long)seedval);
-}
+void
+rte_srand(uint64_t seedval);
/**
* Get a pseudo-random value.
*
- * This function generates pseudo-random numbers using the linear
- * congruential algorithm and 48-bit integer arithmetic, called twice
- * to generate a 64-bit value.
+ * The generator is not cryptographically secure.
+ *
+ * If called from lcore threads, this function is thread-safe.
*
* @return
* A pseudo-random value between 0 and (1<<64)-1.
*/
-static inline uint64_t
-rte_rand(void)
-{
- uint64_t val;
- val = (uint64_t)lrand48();
- val <<= 32;
- val += (uint64_t)lrand48();
- return val;
-}
+uint64_t
+rte_rand(void);
#ifdef __cplusplus
}
@@ -35,6 +35,7 @@ common_sources = files(
'rte_keepalive.c',
'rte_malloc.c',
'rte_option.c',
+ 'rte_random.c',
'rte_reciprocal.c',
'rte_service.c'
)
new file mode 100644
@@ -0,0 +1,139 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_memory.h>
+#include <rte_random.h>
+
+struct rte_rand_state {
+ uint64_t z1;
+ uint64_t z2;
+ uint64_t z3;
+ uint64_t z4;
+ uint64_t z5;
+} __rte_cache_aligned;
+
+static struct rte_rand_state rand_states[RTE_MAX_LCORE];
+
+static uint32_t
+__rte_rand_lcg32(uint32_t *seed)
+{
+ *seed = 1103515245U * *seed + 12345U;
+
+ return *seed;
+}
+
+static uint64_t
+__rte_rand_lcg64(uint32_t *seed)
+{
+ uint64_t low;
+ uint64_t high;
+
+ /* A 64-bit LCG would have been much cleaner, but good
+ * multiplier/increments for such seem hard to come by.
+ */
+
+ low = __rte_rand_lcg32(seed);
+ high = __rte_rand_lcg32(seed);
+
+ return low | (high << 32);
+}
+
+static uint64_t
+__rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)
+{
+ uint64_t res;
+
+ res = __rte_rand_lcg64(seed);
+
+ if (res < min_value)
+ res += min_value;
+
+ return res;
+}
+
+static void
+__rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
+{
+ uint32_t lcg_seed;
+
+ lcg_seed = (uint32_t)(seed ^ (seed >> 32));
+
+ state->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL);
+ state->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL);
+ state->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL);
+ state->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL);
+ state->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL);
+}
+
+void
+rte_srand(uint64_t seed)
+{
+ unsigned int lcore_id;
+
+ /* add lcore_id to seed to avoid having the same sequence */
+ for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++)
+ __rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]);
+}
+
+static __rte_always_inline uint64_t
+__rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c,
+ uint64_t d)
+{
+ return ((z & c) << d) ^ (((z << a) ^ z) >> b);
+}
+
+/* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined
+ * LFSR generators.
+ */
+
+static __rte_always_inline uint64_t
+__rte_rand_lfsr258(struct rte_rand_state *state)
+{
+ state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL,
+ 18446744073709551614UL, 10UL);
+ state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL,
+ 18446744073709551104UL, 5UL);
+ state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL,
+ 18446744073709547520UL, 29UL);
+ state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL,
+ 18446744073709420544UL, 23UL);
+ state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL,
+ 18446744073701163008UL, 8UL);
+
+ return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5;
+}
+
+static __rte_always_inline
+struct rte_rand_state *__rte_rand_get_state(void)
+{
+ unsigned int lcore_id;
+
+ lcore_id = rte_lcore_id();
+
+ if (unlikely(lcore_id == LCORE_ID_ANY))
+ lcore_id = rte_get_master_lcore();
+
+ return &rand_states[lcore_id];
+}
+
+uint64_t
+rte_rand(void)
+{
+ struct rte_rand_state *state;
+
+ state = __rte_rand_get_state();
+
+ return __rte_rand_lfsr258(state);
+}
+
+RTE_INIT(rte_rand_init)
+{
+ rte_srand(rte_get_timer_cycles());
+}
@@ -69,6 +69,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += malloc_mp.c
SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_keepalive.c
SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_option.c
SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_service.c
+SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_random.c
SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_reciprocal.c
# from arch dir
@@ -727,8 +727,6 @@ rte_eal_init(int argc, char **argv)
#endif
}
- rte_srand(rte_rdtsc());
-
/* in secondary processes, memory init may allocate additional fbarrays
* not present in primary processes, so to avoid any potential issues,
* initialize memzones first.
@@ -77,6 +77,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += malloc_mp.c
SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_keepalive.c
SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_option.c
SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_service.c
+SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_random.c
SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_reciprocal.c
# from arch dir
@@ -1083,8 +1083,6 @@ rte_eal_init(int argc, char **argv)
#endif
}
- rte_srand(rte_rdtsc());
-
if (rte_eal_log_init(logid, internal_config.syslog_facility) < 0) {
rte_eal_init_alert("Cannot init logging.");
rte_errno = ENOMEM;
@@ -287,6 +287,14 @@ DPDK_19.05 {
} DPDK_18.11;
+DPDK_19.08 {
+ global:
+
+ rte_rand;
+ rte_srand;
+
+} DPDK_19.05;
+
EXPERIMENTAL {
global: