Predict math.random(0) last bit

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Predict math.random(0) last bit

Albert Chan
 
On Mar 23, 2018, at 6:31 PM, Coda Highland <[hidden email]> wrote:

> 
> if you see the least significant bit of 128 consecutive calls to 
> math.random, then you can predict the least significant bit of every 
> call from there on out.
---
I think above statement is only half-right.
Above statement is true ONLY if we already solved
the 128 coefficient of LSFR.

To solve for the coefficients, we need 256 calls.
-> 128 equations with 128 unknown (coefficient)

http://practicalcryptography.com/cryptanalysis/modern-cryptanalysis/lfsrs-and-berlekampmassey-algorithm/
Reply | Threaded
Open this post in threaded view
|

Re: Predict math.random(0) last bit

Albert Chan
> To solve for the coefficients, we need 256 calls

Uh ..., no need for the 256 calls.
Just 1 email to Vigna, and ask for the LSFR coefficients.

Since he know last bit is LSFR of degree 128, he must had solved for it.

Reply | Threaded
Open this post in threaded view
|

Re: Predict math.random(0) last bit

Albert Chan
128 math.random(0) last bit can actually predict the sequence,
not just the last bit

let c = last bit LSFR coefficients = (c1, c2, ..., c128)
let x = last bit of 128 math.random(0) = (x1, x2, ... x128)

x129 = (c . x) & 1    -- predict last bit using vector dot product

Within the full period 2^128 - 1, all x's are unique
(otherwise, last bit period will be LESS than 2^128 - 1)

But, xorshift128+ only have 2^128 - 1 possible seeds
-> x and seed must map 1-to-1
-> x (after solving the seed) can predict the sequence.



Reply | Threaded
Open this post in threaded view
|

Re: Predict math.random(0) last bit

Dirk Laurie-2
2018-04-24 18:06 GMT+02:00 Albert Chan <[hidden email]>:

> 128 math.random(0) last bit can actually predict the sequence,
> not just the last bit
>
> let c = last bit LSFR coefficients = (c1, c2, ..., c128)
> let x = last bit of 128 math.random(0) = (x1, x2, ... x128)
>
> x129 = (c . x) & 1    -- predict last bit using vector dot product
>
> Within the full period 2^128 - 1, all x's are unique
> (otherwise, last bit period will be LESS than 2^128 - 1)
>
> But, xorshift128+ only have 2^128 - 1 possible seeds
> -> x and seed must map 1-to-1
> -> x (after solving the seed) can predict the sequence.

All this does not mean that math.random is bad. The purpose of a
pseudorandom number generator is to provide a reproducible sequence
that cannot be distinguished from true random numbers by statistical
properties alone. It's a totally different ball game to generate a
sequence that is hard to reverse-engineer.

Reply | Threaded
Open this post in threaded view
|

Re: Predict math.random(0) last bit

Albert Chan
> On Apr 24, 2018, at 3:43 PM, Dirk Laurie <[hidden email]> wrote:
>
> 2018-04-24 18:06 GMT+02:00 Albert Chan <[hidden email]>:
>>
>> let c = last bit LSFR coefficients = (c1, c2, ..., c128)
>> let x = last bit of 128 math.random(0) = (x1, x2, ... x128)
>>
>> x129 = (c . x) & 1    -- predict last bit using vector dot product
>>
>> But, xorshift128+ only have 2^128 - 1 possible seeds
>> -> x and seed must map 1-to-1
>> -> x (after solving the seed) can predict the sequence.
>
> All this does not mean that math.random is bad. The purpose of a
> pseudorandom number generator is to provide a reproducible sequence
> that cannot be distinguished from true random numbers by statistical
> properties alone. It's a totally different ball game to generate a
> sequence that is hard to reverse-engineer.
>

Above were just math trivia (nothing against xorshift128+)

Here is another.
math.random(0) can not produce double 0 sequence

However, if math.random uses xoroshiro128+, it can:
https://github.com/lemire/crackingxoroshiro128plus/issues/1