On Sun, Jul 20, 2008 at 4:50 AM, Florian Weimer wrote: > I've got a function f : S -> X x S where S = (Z/2Z)**96 and > X = (Z/2Z)**32. Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}). > (f implements a PRNG. The s_i are subsequent internal states and the > x_i are results.) > > Now f happens to be linear. I know the values of x_i, x_{i+1}, ..., > x_{i+k} module N, for a fixed, known N. N is odd (but divisible by 9). > Is it possible to recover s_i with reasonable effort (better than brute > force, and k should be in the hundreds, not thousands)? And if yes, how? > Prediction of candidates for x_{i+k+1} with high probability would be > helpful, too. > > (Obviously, using f as an unpredictable PRNG is not a good idea. But if > there's a real attack I can present, convincing the authors to replace > it would be so much easier.) >
>From a little bit of off-line discussion, I think I've got a restatement of the problem that is more suitable to those with a stronger programming background than mathematical background: "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)?" Here is a C implementation of __random32: typedef unsigned long u32; struct rnd_state { u32 s1, s2, s3; }; static u32 __random32(struct rnd_state *state) { #define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b) state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); return (state->s1 ^ state->s2 ^ state->s3); } __random32: See http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=lib/random32.c;h=ca87d86992bdb7bfd6bb30d4dbe6dcefe2bab7b9;hb=bce7f793daec3e65ec5c5705d2457b81fe7b5725 Cheers, -Matt -- 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 [EMAIL PROTECTED]