Looking through a modulo operation

[Victor Duchovni]

On Mon, Jul 21, 2008 at 12:03:50PM -0400, Victor Duchovni wrote:

> On Sun, Jul 20, 2008 at 04:14:33PM -0600, Matt Ball wrote:
> 
> > >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)?"

I skipped over this part when reading the original message. Expecting per
Florian's original message the outputs to be a "linear" function of the
inputs, but they are not.

> After any consecutive 96 outputs, the 97th is a fixed linear function of
> those just observed. It is not necessary to determine the internal state.

This of course applies to the 32-bit output of the RNG. The operation
of reducing the 32-bit output modulo 28333, is not "linear" (over the
F_2 bit string vector-space). While:

	x_96 = c_95 * x_95 + ... c_0 * x_0

this is only true bitwise modulo 2. It is not obvious how one might
recover the full 32-bit outputs from the truncated outputs.

-- 

 /"\ ASCII RIBBON                  NOTICE: If received in error,
 \ / CAMPAIGN     Victor Duchovni  please destroy and notify
  X AGAINST       IT Security,     sender. Sender does not waive
 / \ HTML MAIL    Morgan Stanley   confidentiality or privilege,
                                   and use is prohibited.

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