Looking through a modulo operation

[Matt Ball]

On Mon, Jul 21, 2008 at 8:33 AM, Matt Ball <matt.ball at ieee.org> wrote:
>
>    "If someone uses the __random32 function as defined in the 2.6.26
> Linux kernel, and leaks to you the result of taking successive outputs
> modulo 28233 (= 9 * 3137), can you determine the probable 96-bit
> internal state with fewer than 1000 outputs and with modest processing
> power (e.g., a laptop computer running less than a day)?"
>

Another attacking avenue is the 32-bit initial seed.  If the
implementation re-seeds frequently, or leaks to you the first outputs
after initialization, then you only have to brute-force the 32-bit
seed space, times the number of samples since reseeding.

Here is the function that performs the initial seeding, based on a 32-bit seed:

static void __set_random32(struct rnd_state *state, unsigned long s)
{
        if (s == 0)
                s = 1;      /* default seed is 1 */
#define LCG(n) (69069 * n)
        state->s1 = LCG(s);
        state->s2 = LCG(state->s1);
        state->s3 = LCG(state->s2);
        /* "warm it up" */
        __random32(state);
        __random32(state);
        __random32(state);
        __random32(state);
        __random32(state);
        __random32(state);
}

For those who want to get cleaver, I suspect there is an optimization
for running __random32 six times.

--
Thanks!
Matt Ball, IEEE P1619.x SISWG Chair
M.V. Ball Technical Consulting, Inc.
Phone: 303-469-2469, Cell: 303-717-2717
http://www.mvballtech.com
http://www.linkedin.com/in/matthewvball

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com