Re: Lua 5.4 random number generator

[albertmcchan <albertmcchan@...>]

On Mar 23, 2018, at 6:31 PM, Coda Highland <chighland@gmail.com> wrote:

> On Fri, Mar 23, 2018 at 5:24 PM, Albert Chan <albertmcchan@yahoo.com> wrote:
>> You mean just two math.random(0) (128 bits) can predict the next one ?
> 
> No, 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 I can prove your statement is true (and more)

Even better than predicting the least significant bits. You can
calculate internal states, and predict ALL bits from there on out.

You can even get random bits backward in time !

https://blog.securityevaluators.com/xorshift128-backward-ff3365dc0c17?source=user_profile---------1----------------

state0 = {x, y}
state0 last bit 
= last_bit(x + y) = last_bit(x ^ y)      -- no carry for last bit
= x0 ^ y0

After 1 xorshift128+ :
state1 = {y, (x ^ x<<23) ^ y ^ ((x ^ x<<23)>>18) ^ (y>>5)}

state1 last bit 
= last_bit(y ^ (x ^ x<<23) ^ y ^ ((x ^ x<<23)>>18) ^ (y>>5))
= last_bit(x ^ (x>>18) ^ (y>>5))
= x0 ^ x18 ^ y5

...

--> 128 equations, 128 unknowns (bits of {x, y})
--> each equation cut down possible states by 50% (last bit is 0 or 1)
--> one unique {x, y} remain after solving all 128 equations

--> last bit of 0 128 times imply x = y = 0
--> with non-zero seed, it will never happens