Random Number Generator of Mono <= 3.12 is broken

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.0In 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

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *