Recently, I played around with the Random Number Generator (RNG) of the Mono Project 3.2.8. That version is a rather old one, but it’s the one shipped with Ubuntu 15.04. I needed some random numbers between 0 and 3:
Random rng = new Random();
var randomNumber = rng.Next(4); // you get 0,1,2 or 3
Actually, I was quite confused when I often I got the same sequence: 003311… sometimes it was also 110022… or 221133… or 332200… I double checked the way I initialized the RNG (you can barely do it wrong in .NET). Everything seemed okay. Self-doubts raised.
I created a new C# project to test this snippet it without other stuff around. Accidentally, I wrote this:
Random rng = new Random();
var randomNumber = rng.Next(3); // you get 0,1 or 2
And it worked. That was awkward. When I found the difference between the two snippets and changed the 3 to 4 again, it did not work again. That was even more awkward. I tested it with different upper limits, and most of them showed no strange effect. But some did: 2, 4, 8, 16, 32, 64, …
Okay that’s simple. Working hypothesis: use 2x as an upper limit and the RNG of Mono will rather be a Deterministic Number Generator than a Random Number Generator.
I wrote a small program which uses the RNG with different upper limits:
Random Numbers between 0 and (2-1) 001111111101100010010001010011 001111111101100010010001010011 001111111101100010010001010011 001111111101100010010001010011 110000000010011101101110101100 110000000010011101101110101100 110000000010011101101110101100 110000000010011101101110101100 110000000010011101101110101100 110000000010011101101110101100 There are 10 duplicates Random Numbers between 0 and (3-1) 000012221000222111100200111111 002110221011201010101002210101 002120112122221110121201221122 010212222001202202120112122100 011100201221022100222110120012 012022010120000001211111022021 020110010111100020000121002221 021002110100121111002201202222 021002222022002221212022201000 022222222012120022212222102201 There are 0 duplicates Random Numbers between 0 and (4-1) 003311313103322012030201010231 003311313103322012030201010231 110022020210033123101312121302 110022020210033123101312121302 221133131321100230212023232013 221133131321100230212023232013 221133131321100230212023232013 221133131321100230212023232013 332200202032211301323130303120 332200202032211301323130303120 There are 10 duplicates Random Numbers between 0 and (5-1) 003102433303224320344124413244 014002324010344001320033020132 043243041241110034214310311202 123102031104130223404020432042 144411314322324300000243000322 213020412123234203214144024130 303334443143224333420213212213 333430002031100042404304100321 413344002434130240034000230011 423243443040204021114414332404 There are 0 duplicates Random Numbers between 0 and (6-1) 001151135521522414212403214033 003131555343524210030205054051 005313511105104012254401410413 041555513105100450212045434253 045111335343302054454043034235 310404240454033101343114125340 334024002052235305305330525322 350000402230453125123550501500 352044220054411521101552305124 354424444410413323525554145142 There are 0 duplicates Random Numbers between 0 and (7-1) 033214526623606150556321512624 063341661552263666132455144332 140462111233332463413164456031 144456216033564651131621544310 205055051021666061606143460510 245621312432342225323012531145 352106204042035531250155442216 356163306202230353205312533565 450035402641045620130003124323 521500436411203455042330526446 There are 0 duplicates Random Numbers between 0 and (8-1) 043755717107726016030205054635 114462060614077523101712125342 265177131321140230252427276057 265177131321140230252427276057 407311353543362452474641410271 407311353543362452474641410271 550026424250433167545356561706 621533575765504674616063632413 621533575765504674616063632413 772240646472655301767570703120 There are 6 duplicates
As you can see, everything works fine except for 2x as an upper limit. (On 8, there are only 6 duplicates. But this is because I only generated 10 sequences. With 30 sequences, there should probably be 30 duplicates.)
I ran this again for only the 2x upper limits (I removed the output of the sequences because that would have been a little bit too verbose):
Random Numbers between 0 and (2-1) There are 2000 duplicates Random Numbers between 0 and (4-1) There are 2000 duplicates Random Numbers between 0 and (8-1) There are 2000 duplicates Random Numbers between 0 and (16-1) There are 2000 duplicates Random Numbers between 0 and (32-1) There are 2000 duplicates Random Numbers between 0 and (64-1) There are 2000 duplicates Random Numbers between 0 and (128-1) There are 2000 duplicates Random Numbers between 0 and (256-1) There are 2000 duplicates Random Numbers between 0 and (512-1) There are 1993 duplicates Random Numbers between 0 and (1024-1) There are 1822 duplicates
Obviously, something is wrong with the 2x upper limits.
Mono introduced this RNG (JKISS) in version 3.2.7 and it remained there till it was replaced by Microsoft’s .NET Core implementation in Mono 4.0. In 3.2.7, this RNG was introduced because „JKISS [..] is faster and has a longer period“. The change log references „Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications„.
Fun fact: Before version 3.2.7, Mono used the same RNG as Microsoft does. At least they seem quite similar. They are the RNG of Donald Knuth, described in Numerical Recipes in C, Second Edition (1992) p.283. Another fun fact: In Microsoft’s implementation, they use inextp=21 instead of inextp=31. Which in sequence created another bug. Unfortunately, they can’t simply fix it because some applications rely on this oddly initialized RNG. (As Mono is now also using this RNG, they’re buggy again – but at least compatible!)
Unfortunately, I’m no mathemagician and I have barely knowledge about crypto stuff. So I can’t really tell why there is this problem. As far as I figured out, JKISS generates random numbers, but if you apply a modulo operation, the resulting number sequence is always the same:
415579394 % 2 = 0 1247788766 % 2 = 0 1576907989 % 2 = 1 4120330265 % 2 = 1 373421407 % 2 = 1 2957693744 % 2 = 0 4000395092 % 2 = 0 565214835 % 2 = 1 3955692095 % 2 = 1 3013702125 % 2 = 1 586749482 % 2 = 0 2115627366 % 2 = 0 413595965 % 2 = 1 1496721121 % 2 = 1 2720998663 % 2 = 1 4215805220 % 2 = 0 230859640 % 2 = 0 261977095 % 2 = 1 3332717443 % 2 = 1 2428295201 % 2 = 1 235365793 % 2 = 1 3583443073 % 2 = 1 186167660 % 2 = 0 4250715604 % 2 = 0 2281943470 % 2 = 0 864421531 % 2 = 1 1698675347 % 2 = 1 34548790 % 2 = 0 1791744630 % 2 = 0 1989240008 % 2 = 0
So it is always 00111… (starting with even number) or 11000… (starting with odd number).
Further reading on why this may fail: http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx
Btw: Here’s the C# solution I used to test this: MonoBrokenRNG.tar