Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs - Kernel

This is a discussion on Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs - Kernel ; Hi, There appears to be an error in how random seeding is done in the random32.c RNG. I am looking at 2.6.25.7. For background, that file contains this comment: """ ... the k_j most significant bits of z_j must be ...

+ Reply to Thread
Results 1 to 6 of 6

Thread: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

  1. Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

    Hi,

    There appears to be an error in how random seeding is done in the
    random32.c RNG. I am looking at 2.6.25.7.

    For background, that file contains this comment:

    """
    ... the k_j most significant bits of z_j must be non-
    zero, for each j. (Note: this restriction also applies to the
    computer code given in [4], but was mistakenly not mentioned in
    that paper.)

    This affects the seeding procedure by imposing the requirement
    s1 > 1, s2 > 7, s3 > 15.
    """

    The function random32_reseed takes an unsigned long's worth of entropy
    from the entropy pool (get_random_bytes) and passes it to
    __set_random32. That function (seemingly attempts) to impose the
    requirement mentioned above by first checking if the seed is == 0, and
    if so setting it to one, then setting s2 to s*69069 and s3 to s2*69069

    However this will allow bad seeds. On 64-bit systems, if the low order
    32 bits of the seed are zero, then the check for s == 0 will pass, but
    s1, s2, and s3 will all be initialized to zero due to truncation. This
    will, since there are no additive factors in the RNG sequence, cause
    the RNG to output nothing but zero values. Assuming get_random_bytes
    returns uniform random numbers, this will occur with probability
    around 1/2^32.

    An easy and straightforward fix for this that doesn't require changing
    any interfaces is to add
    s &= 0xFFFFFFFF;
    before the check in __set_random32, which ensures this condition will
    be caught by the check. Alternately, you could replace the check for
    s == 0 with some logic like:
    if((s & 0xFFFFFFFF) == 0)
    s += 1;
    since just chopping the seed to 32 bits does throw away some of your
    seed input (with sizeof(long) == 8, at least; doesn't make any
    difference for sizeof(long) == 4)

    There are also many other seeds which will cause some (but not all) of
    the seeding requirements to be violated. Which seeds will cause this
    problem depend on the size of unsigned long, since the multiplications
    by 69069 are done in that size.

    For instance on 32-bit systems, a seed of 0x4BC54E0A will generate
    the state:
    s1 = 0x4BC54E0A
    s2 = (s1 * 69069) % 2^32 = 2
    s3 = 2*69069 = 138138

    In general, there seem to be large numbers of seeds that cause at
    least one of the restrictions on s1, s2, s3 to be false. The paper
    referenced in the source is not clear exactly how badly the generator
    fails when only one of the restrictions is violated. Certainly it
    seems much less serious than the 64-bit specific bug described above;
    which is fortunate since it seems to occur much more often. A trivial
    patch for both problems is attached.

    Please Cc: me on any replies as I am not subscribed to the list.

    Jack


  2. Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

    [who maintains random32.c ?]

    On Thu, Jun 19, 2008 at 5:30 PM, Jack Lloyd wrote:
    > Hi,
    >
    > There appears to be an error in how random seeding is done in the
    > random32.c RNG. I am looking at 2.6.25.7.
    >

    [snip]
    >
    > An easy and straightforward fix for this that doesn't require changing
    > any interfaces is to add
    > s &= 0xFFFFFFFF;
    > before the check in __set_random32, which ensures this condition will
    > be caught by the check. Alternately, you could replace the check for
    > s == 0 with some logic like:
    > if((s & 0xFFFFFFFF) == 0)
    > s += 1;
    > since just chopping the seed to 32 bits does throw away some of your
    > seed input (with sizeof(long) == 8, at least; doesn't make any
    > difference for sizeof(long) == 4)
    >


    I think it is cleaner to change the interface to account for long != u32

    The rest of your patch (ensuring values are big enough) looks valid to me.

    Signed-off-by: Benoit Boissinot

    diff -r ced66ca0044f lib/random32.c
    --- a/lib/random32.c Mon Jun 30 08:58:09 2008 -0700
    +++ b/lib/random32.c Wed Jul 02 01:13:12 2008 +0200
    @@ -56,7 +56,7 @@
    return (state->s1 ^ state->s2 ^ state->s3);
    }

    -static void __set_random32(struct rnd_state *state, unsigned long s)
    +static void __set_random32(struct rnd_state *state, u32 s)
    {
    if (s == 0)
    s = 1; /* default seed is 1 */
    @@ -84,7 +84,7 @@
    */
    u32 random32(void)
    {
    - unsigned long r;
    + u32 r;
    struct rnd_state *state = &get_cpu_var(net_rand_state);
    r = __random32(state);
    put_cpu_var(state);
    @@ -122,7 +122,7 @@

    for_each_possible_cpu(i) {
    struct rnd_state *state = &per_cpu(net_rand_state,i);
    - __set_random32(state, i + jiffies);
    + __set_random32(state, (u32) i + jiffies);
    }
    return 0;
    }
    @@ -135,7 +135,7 @@
    static int __init random32_reseed(void)
    {
    int i;
    - unsigned long seed;
    + u32 seed;

    for_each_possible_cpu(i) {
    struct rnd_state *state = &per_cpu(net_rand_state,i);
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  3. Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

    On Wed, 2 Jul 2008 01:19:27 +0200
    Benoit Boissinot wrote:

    > [who maintains random32.c ?]


    ah. I think it's ancient net code which was recently hoisted into lib/.
    So: not really anybody.

    I've been hopefully cc'ing Matt and Ted in the hope of fooling them
    into looking at it. But a netdev cc is appropriate also.

    > On Thu, Jun 19, 2008 at 5:30 PM, Jack Lloyd wrote:
    > > Hi,
    > >
    > > There appears to be an error in how random seeding is done in the
    > > random32.c RNG. I am looking at 2.6.25.7.
    > >

    > [snip]
    > >
    > > An easy and straightforward fix for this that doesn't require changing
    > > any interfaces is to add
    > > s &= 0xFFFFFFFF;
    > > before the check in __set_random32, which ensures this condition will
    > > be caught by the check. Alternately, you could replace the check for
    > > s == 0 with some logic like:
    > > if((s & 0xFFFFFFFF) == 0)
    > > s += 1;
    > > since just chopping the seed to 32 bits does throw away some of your
    > > seed input (with sizeof(long) == 8, at least; doesn't make any
    > > difference for sizeof(long) == 4)
    > >

    >
    > I think it is cleaner to change the interface to account for long != u32
    >
    > The rest of your patch (ensuring values are big enough) looks valid to me.
    >
    > Signed-off-by: Benoit Boissinot
    >
    > diff -r ced66ca0044f lib/random32.c
    > --- a/lib/random32.c Mon Jun 30 08:58:09 2008 -0700
    > +++ b/lib/random32.c Wed Jul 02 01:13:12 2008 +0200
    > @@ -56,7 +56,7 @@
    > return (state->s1 ^ state->s2 ^ state->s3);
    > }
    >
    > -static void __set_random32(struct rnd_state *state, unsigned long s)
    > +static void __set_random32(struct rnd_state *state, u32 s)
    > {
    > if (s == 0)
    > s = 1; /* default seed is 1 */
    > @@ -84,7 +84,7 @@
    > */
    > u32 random32(void)
    > {
    > - unsigned long r;
    > + u32 r;
    > struct rnd_state *state = &get_cpu_var(net_rand_state);
    > r = __random32(state);
    > put_cpu_var(state);
    > @@ -122,7 +122,7 @@
    >
    > for_each_possible_cpu(i) {
    > struct rnd_state *state = &per_cpu(net_rand_state,i);
    > - __set_random32(state, i + jiffies);
    > + __set_random32(state, (u32) i + jiffies);
    > }
    > return 0;
    > }
    > @@ -135,7 +135,7 @@
    > static int __init random32_reseed(void)
    > {
    > int i;
    > - unsigned long seed;
    > + u32 seed;
    >
    > for_each_possible_cpu(i) {
    > struct rnd_state *state = &per_cpu(net_rand_state,i);

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  4. Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs


    On Tue, 2008-07-01 at 17:34 -0700, Andrew Morton wrote:
    > On Wed, 2 Jul 2008 01:19:27 +0200
    > Benoit Boissinot wrote:
    >
    > > [who maintains random32.c ?]

    >
    > ah. I think it's ancient net code which was recently hoisted into lib/.
    > So: not really anybody.
    >
    > I've been hopefully cc'ing Matt and Ted in the hope of fooling them
    > into looking at it. But a netdev cc is appropriate also.


    I did look at it, and it looks reasonable. So:

    Acked-by: Matt Mackall

    Stephen Hemminger is responsible for the original code, I believe. I've
    been tempted to slurp this functionality into random.c but keep getting
    side-tracked into theoretical investigations of better functions, as I'm
    not a big fan of the current one from either a performance or strength
    perspective.

    --
    Mathematics is the supreme nostalgia of our time.

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  5. Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs


    On Wednesday 2008-07-02 01:19, Benoit Boissinot wrote:
    >@@ -122,7 +122,7 @@

    [ int i ]
    >
    > for_each_possible_cpu(i) {
    > struct rnd_state *state = &per_cpu(net_rand_state,i);
    >- __set_random32(state, i + jiffies);
    >+ __set_random32(state, (u32) i + jiffies);
    > }
    > return 0;
    > }


    This cast does not make sense since
    (int)i + jiffies ≡ i + jiffies ≡ (u32)i + jiffies mod 2^32
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  6. Re: Bug in random32.c: all-zero outputs with probability 1/2^32, other seeding bugs

    On Tue, 01 Jul 2008 22:22:31 -0500
    Matt Mackall wrote:

    >
    > On Tue, 2008-07-01 at 17:34 -0700, Andrew Morton wrote:
    > > On Wed, 2 Jul 2008 01:19:27 +0200
    > > Benoit Boissinot wrote:
    > >
    > > > [who maintains random32.c ?]

    > >
    > > ah. I think it's ancient net code which was recently hoisted into lib/.
    > > So: not really anybody.
    > >
    > > I've been hopefully cc'ing Matt and Ted in the hope of fooling them
    > > into looking at it. But a netdev cc is appropriate also.

    >
    > I did look at it, and it looks reasonable. So:
    >
    > Acked-by: Matt Mackall
    >
    > Stephen Hemminger is responsible for the original code, I believe. I've
    > been tempted to slurp this functionality into random.c but keep getting
    > side-tracked into theoretical investigations of better functions, as I'm
    > not a big fan of the current one from either a performance or strength
    > perspective.
    >


    Yes, I took it from gnu scientific lib it for use in netem. The seeding
    fixes make sense.

    Note: this should not be a security issue since this routine is explicitly
    not intended for cryptographic use.
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

+ Reply to Thread