[128638] in cryptography@c2.net mail archive
Re: Looking through a modulo operation
daemon@ATHENA.MIT.EDU (Matt Ball)
Tue Jul 22 11:46:34 2008
Date: Tue, 22 Jul 2008 09:07:44 -0600
From: "Matt Ball" <matt.ball@ieee.org>
To: cryptography <cryptography@metzdowd.com>
In-Reply-To: <ed843b100807210733h1d363ea3m1c26f9e0c0863c6d@mail.gmail.com>
On Mon, Jul 21, 2008 at 8:33 AM, Matt Ball <matt.ball@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@metzdowd.com
