[erlang-bugs] All possible internal states of Erlang/OTP random module are practically computable

[Kenji Rikitake]

This is a preliminary result of a brute-force check of the AS183 algorithm
looping period, using a C program running in the exactly same algorithm as in
the Erlang/OTP random module. 

The code is shown at the following GitHub repository:

https://github.com/jj1bdx/as183-c/

The preliminary result tested on Mac mini 2012 (2.6GHz Core i7) using single
core (the code is purely sequential) for *less than nine hours* shows that

Internal state loop detected
count = 6953607871644, y1 = 3172, y2=9814, y3 = 20125

(The {3172, 9814, 20125} is the internal initial seed value of
erlang:seed/0, and given as the initial value of the simulation code.)

So the period length is: 6953607871644 ~= 2 ^ (42.661). This period is
an expected value in the original AS183 algorithm paper.
<http://wwwf.imperial.ac.uk/~ayoung/m3s9/wichmannhill.pdf>

The fact I observed this time is: A C code can practically exploit all
the possible sequence of AS183 in less than NINE HOURS on a Mac mini,
far shorter than 880 years shown in the original paper.  This suggests
you can guess the seed value (three 15-bit integers) from a partial
random number sequence, and this can be used for an algorithmic attack.
(The calculation is practically easily parallelized, since the internal
state values can be obtained for a certain large interval value (of 10^8
in my code, for example).)

I am now testing this on an Intel NUC at home running FreeBSD as
well. The code is portable and will run on other platforms as well.

Conclusion: I have to say that Erlang/OTP "random" module should be
revised ASAP.

Kenji Rikitake