########################################################################################## MISC-46: Dice rolls on random.bentasker.co.uk may not be consistently random ########################################################################################## Issue Type: Bug ----------------------------------------------------------------------------------------- Issue Information ==================== Priority: Major Status: Closed Resolution: Fixed (2021-06-05 11:37:06) Project: Miscellaneous (MISC) Reported By: btasker Assigned To: btasker Time Estimate: 0 minutes Time Logged: 0 minutes ----------------------------------------------------------------------------------------- Issue Description ================== We had a game of monopoly at the weekend and someone had lost the dice, so I used the dice at https://random.bentasker.co.uk However, I got doubles *a lot* (which was handy as I kept landing on "Go to jail"). The probability of rolling doubles when rolling two dice is 0.16 so it may be nothing, but it felt oddly frequent (it also only seemed to be me which lent a feeling that they might be coming in some kind of cycle). I thought it might be interesting to dig into as it's a while since I've touched that codebase. Random output is generated by a Hash-chains based RNG I created in LUA (originally, but no longer, reading in seeds from my ChaCha20 RNG - https://www.bentasker.co.uk/blog/software-development/689-writing-a-chacha20-based-csprng) ----------------------------------------------------------------------------------------- Activity ========== ----------------------------------------------------------------------------------------- 2021-06-03 18:22:02 btasker ----------------------------------------------------------------------------------------- So, to start off, lets place some requests to try and repro Rolling 2 dice twenty times -- BEGIN SNIPPET -- for i in {1..20}; do roll=$(curl -s https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice | tr '\n' ','); d1=$(echo $roll | cut -d, -f1) d2=$(echo $roll | cut -d, -f2) [[ "$d1" == "$d2" ]] && match="DOUBLES" || match="" echo $roll $match; done ben@optimus:~$ for i in {1..20}; > do > roll=$(curl -s https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice | tr '\n' ','); > d1=$(echo $roll | cut -d, -f1) > d2=$(echo $roll | cut -d, -f2) > [[ "$d1" == "$d2" ]] && match="DOUBLES" || match="" > echo $roll $match; > done 2,5, 4,6, 6,6, DOUBLES 6,6, DOUBLES 2,5, 3,3, DOUBLES 5,5, DOUBLES 3,1, 4,1, 5,2, 1,1, DOUBLES 5,6, 5,1, 1,6, 3,4, 1,5, 6,3, 1,6, 6,2, 1,1, DOUBLES -- END SNIPPET -- Does seem more common than might be expected. Can we get triples? -- BEGIN SNIPPET -- ben@optimus:~$ for i in {1..20}; do roll=$(curl -s https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice | tr '\n' ','); d1=$(echo $roll | cut -d, -f1); d2=$(echo $roll | cut -d, -f2); d3=$(echo $roll | cut -d, -f3); match=""; if [[ "$d1" == "$d2" ]]; then [[ "$d1" == "$d3" ]] && match="TRIPLES" || match=""; fi; echo $roll $match; done 2,1,5, 5,5,6, 1,3,5, 3,4,5, 2,4,6, 5,5,1, 1,6,1, 3,3,5, 4,4,6, 5,3,4, 1,6,4, 3,5,5, 2,6,1, 6,3,4, 5,5,4, 6,4,1, 1,5,1, 6,5,1, 6,1,1, 1,2,4, -- END SNIPPET -- No, but there is a sequence in there if we squash rolls together -- BEGIN SNIPPET -- 2,1,5,5,5,6, -- END SNIPPET -- Could be chance though. Another run yields two identical rolls one after the other -- BEGIN SNIPPET -- 5,3,2, 5,3,2, -- END SNIPPET -- Another run gets us triples -- BEGIN SNIPPET -- ben@optimus:~$ for i in {1..20}; do roll=$(curl -s https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice https://random.bentasker.co.uk/dice | tr '\n' ','); d1=$(echo $roll | cut -d, -f1); d2=$(echo $roll | cut -d, -f2); d3=$(echo $roll | cut -d, -f3); match=""; if [[ "$d1" == "$d2" ]]; then [[ "$d1" == "$d3" ]] && match="TRIPLES" || match=""; fi; echo $roll $match; done 1,4,5, 4,4,3, 6,5,1, 5,2,2, 2,5,3, 6,1,4, 6,6,4, 6,5,2, 5,3,4, 5,3,3, 5,5,4, 1,1,1, TRIPLES 3,6,3, 2,1,2, 5,4,1, 1,4,3, 4,3,5, 6,3,4, 5,5,2, 2,5,3, -- END SNIPPET -- Although unlikely, it is possible. It's gut feel, but I feel like something might be going on - because we're fetching over a network (and other stuff may also be fetching) there's a hell of a lot we can't control in order to test this. ----------------------------------------------------------------------------------------- 2021-06-03 18:46:37 btasker ----------------------------------------------------------------------------------------- There's potentially some scope for the re-seeding to go wrong at just the wrong moment, but as that's more complex, I'll KISS for now. That last output is written into last by pulling from SHM - it's possible that's racey so a subsequent request gets the same value before the value of the previous request has been written in - that _should_ be handled by what follows though. Variable digest is formed by taking the last output, and generating 3 HMACs: -- BEGIN SNIPPET -- for i = 3,0,-1 do -- Mix in some random bytes so that future numbers are hard to predict last = ngx.hmac_sha1(last, ngx.now()..random.bytes(16)) table.insert(dgst_tbl,last) end -- END SNIPPET -- Note: random is an FFI which under the hood calls -- BEGIN SNIPPET -- C.RAND_pseudo_bytes(buf,len) -- END SNIPPET -- I'll KISS for now and not delve too far into that. The table we populated in our iteration is concat'd to stretch 480 bytes creating the string digest. -- BEGIN SNIPPET -- local digest = table.concat(dgst_tbl,'') -- END SNIPPET -- In _theory_ the iteration and concat process should prevent repeats (because we're mixing in random data) - again, I'll KISS for now and move on. We call generate_limited_output(my_mode,digest) where my_mode is dice (defined in the Nginx config itself.) Type dice is a special one, it re-calls generate_limited_output to get a list of digits -- BEGIN SNIPPET -- if optype == "dice" then -- Call self to get a list of digits digis = generate_limited_output("digits",digest) -- END SNIPPET -- There's nothing immensely special about the digits mode -- BEGIN SNIPPET -- if optype == "digits" then for c in digest:gmatch("[%w%p]+") do table.insert(op,string.byte(c)) end return table.concat(op,"") end -- END SNIPPET -- It reads the digest, regexing out alphanumeric chars and punctuation, then converting that char to it's ascii char code and inserting. It's possible the fairly limited range of char codes (0-127) could lead to certain integers being more common - if that's the case then you'd expect to see a heavier weighting on those numbers: - 1 is probably an obvious example, because every ASCII character code > 100 has a 1 in it - 2 is also likely to be more common, because char codes get up to 127 - it has 8 more entries (120-127) than the numbers 3-0 That's something we should be able to check for reasonably easily - can come back to this. Getting back to the processing flow, the response from generate_limited_output("digits" will be a string of numbers: -- BEGIN SNIPPET -- ben@optimus:~$ curl -s https://random.bentasker.co.uk/randintegers 98446392427510789791146583501075951 -- END SNIPPET -- The response then processed within the dice section in order to extract integers and ensure they're ones you'd find on a dice -- BEGIN SNIPPET -- digis = string.reverse(digis) for c in digis:gmatch"." do if tonumber(c) > 0 and tonumber(c) < 7 then return c end end -- END SNIPPET -- For reasons I can't quite remember, the string is read backwards. As soon as we find a number that could be on a dice, we return it to give the value of a single dice. That's then sent to the user with ngx.say -- BEGIN SNIPPET -- ngx.say(generate_limited_output(my_mode,digest)) -- END SNIPPET -- Finally, the value is written to SHM for use by the next request (mixing with some random bytes to provide some back-tracking protectio) -- BEGIN SNIPPET -- apparea:set("last_rnd", ngx.sha1_bin(digest .. random.bytes(16))) -- END SNIPPET -- There's a potential race there then that another request could come in (potentially from the same user) between sending them the response and writing into SHM The page at random.bentasker.co.uk places two requests to https://random.bentasker.co.uk/dice giving us two values ----------------------------------------------------------------------------------------- 2021-06-03 18:51:20 btasker ----------------------------------------------------------------------------------------- So, to summarise, it _looks_ like the following should be true - Any possibility for a race fetching last roll from the SHM should be removed by the mixing/stretching done at the beginning - That mixing should also prevent erroneous doubles being served up if 2 workers simultaneously process requests - The mixing should also deal with the race where a result isn't written to SHM until after it's been returned (though that should be easy to fix) - Digits selection may introduce bias towards the numbers 1 and 2 (actually, is that why digis was reversed, to try and reduce the bias towards 1?) Will look at this more tomorrow ----------------------------------------------------------------------------------------- 2021-06-04 10:34:32 btasker ----------------------------------------------------------------------------------------- Let's start by testing this -- BEGIN QUOTE -- - Digits selection may introduce bias towards the numbers 1 and 2 (actually, is that why digis was reversed, to try and reduce the bias towards 1?) -- END QUOTE -- We'll roll 100 dice and then check distribution of the results - the expectation (if the above is true) being that 1 and 2 should appear more regularly -- BEGIN SNIPPET -- for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice done | sort | uniq -c ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 13 1 12 2 14 3 16 4 21 5 24 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 15 1 12 2 21 3 14 4 19 5 19 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 18 1 9 2 17 3 17 4 24 5 15 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 17 1 10 2 19 3 10 4 27 5 17 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 19 1 17 2 13 3 18 4 19 5 14 6 -- END SNIPPET -- The distribution of most digits fluctuates between tests (as might be expected of a random result set) - it feels like 6 is disproportionately common, but will examine that in a bit. Range of variation is - 1 : 6 - 2 : 6 - 3 : 7 - 4 : 8 - 5 : 8 - 6 : 10 Presumably, 1 and 2 having equal ranges is chance. If we run the test again, we should get a different range for each -- BEGIN SNIPPET -- ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 12 1 10 2 23 3 19 4 18 5 18 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 15 1 9 2 21 3 14 4 18 5 23 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 22 1 15 2 12 3 20 4 14 5 17 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 20 1 16 2 10 3 13 4 15 5 26 6 ben@optimus:~$ for i in {1..100}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c 23 1 10 2 13 3 19 4 12 5 23 6 -- END SNIPPET -- Which gives - 1 : 11 - 2 : 6 - 3 : 13 - 4 : 7 - 5 : 6 - 6 : 6 Good. OK, let's look at how often each number appeared - each set of 100 is already a percentage, so we'll work out: - the average for each result in a set of 500 rolls - the average of those averages (to roughly appropriate the chance of getting any given number) The expectation is that the first will vary between the two test sets, the latter should sit at roughly 1/6th (16.6667%) - if it doesn't then I've screwed the maths somewhere (because the sum of the first set should always be 100) so it's more a check than a test. Test run 1: - 1 : 16.4 - 2 : 12 - 3 : 16.8 - 4 : 15 - 5 : 22 - 6 : 17.8 - Aggregate: 16.6667 Test run 2: - 1 : 18.4 - 2 : 12 - 3 : 15.8 - 4 : 17 - 5 : 15.4 - 6 : 21.4 - Aggregate: 16.6667 Side note: -- BEGIN QUOTE -- it feels like 6 is disproportionately common, but will examine that in a bit. -- END QUOTE -- This doesn't appear to be the case 5 was more likely in the first round of 500. Can't really conclude from just 2 tests that it's truly random, but from the distribution of results the signs are there - The %age showing of any result differs between each test run - Groups of tests show different average showings per result - A bias towards 1/2 would be expected to lead to them appearing more frequently, that doesn't seem to be the case ----------------------------------------------------------------------------------------- 2021-06-04 12:01:12 btasker ----------------------------------------------------------------------------------------- Let's run this through an RNG tester -- BEGIN SNIPPET -- ben@optimus:~$ for i in {1..10000}; do curl -s https://random.bentasker.co.uk/dice | tr -d '\n' ; done > /tmp/rolls -- END SNIPPET -- Verifying we've a full set -- BEGIN SNIPPET -- ben@optimus:~$ wc -c /tmp/rolls 10000 /tmp/rolls -- END SNIPPET -- What does ent make of it -- BEGIN SNIPPET -- ben@optimus:~$ cat /tmp/rolls | ent -c Value Char Occurrences Fraction 49 1 2037 0.203700 50 2 1222 0.122200 51 3 1598 0.159800 52 4 1731 0.173100 53 5 1682 0.168200 54 6 1730 0.173000 Total: 10000 1.000000 Entropy = 2.569417 bits per byte. Optimum compression would reduce the size of this 10000 byte file by 67 percent. Chi square distribution for 10000 samples is 425574.84, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 51.4989 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is -0.014397 (totally uncorrelated = 0.0). -- END SNIPPET -- So - Entropy per char is low (not a good sign) - Chi Square is < 1%, suggesting numbers aren't random - Arithmetic mean value is quite a long way from 127.5, but then our range of available values is much smaller than in "normal" random data. Values available to us are 40-54, so 51.5 is smack in the middle, this is a good sign - Monte Carlo isn't great (we're aiming for Pi there really) - The serial correlation coefficient looks very good The negative signs there, though, are probably a result of using the wrong tool for the job - ent is really meant to assess a stream of random bytes, rather than concentration on a set of 6. The tests (Arithmetic mean and Serial Correlation) that take range of the dataset into account look much, much better. If we test with rngtest we see very good results - rngtest tests bits not bytes. Wrong tools for the job really. From the ent output, we can see the distribution of each of the results -- BEGIN SNIPPET -- 49 1 2037 0.203700 50 2 1222 0.122200 51 3 1598 0.159800 52 4 1731 0.173100 53 5 1682 0.168200 54 6 1730 0.173000 -- END SNIPPET -- So, in that set, 1 was most frequent, followed by 4 and then 6 - that earlier feeling that 6 was too frequent was obviously perception bias. Lets run another set of rolls and see how the distribution shifts there -- BEGIN SNIPPET -- ben@optimus:~$ cat /tmp/rolls2 | ent -c Value Char Occurrences Fraction 49 1 2003 0.200300 50 2 1275 0.127500 51 3 1605 0.160500 52 4 1654 0.165400 53 5 1744 0.174400 54 6 1719 0.171900 Total: 10000 1.000000 Entropy = 2.572590 bits per byte. Optimum compression would reduce the size of this 10000 byte file by 67 percent. Chi square distribution for 10000 samples is 423814.32, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 51.5018 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is -0.012181 (totally uncorrelated = 0.0). -- END SNIPPET -- Observations - 1 has the strongest showing again - Arithmetic mean falls in the middle of our range again (this is good) - Serial correlation looks very good Running a third set of rolls to look at the incidence of 1 in that. -- BEGIN SNIPPET -- ben@optimus:~$ cat /tmp/rolls3 | ent -c Value Char Occurrences Fraction 49 1 2051 0.205100 50 2 1226 0.122600 51 3 1641 0.164100 52 4 1689 0.168900 53 5 1717 0.171700 54 6 1676 0.167600 -- END SNIPPET -- ----------------------------------------------------------------------------------------- 2021-06-04 12:06:59 btasker ----------------------------------------------------------------------------------------- OK, I want to go back over the logic used to calculate the dice roll to make sure I'm not making assumptions about it (I keep doubting myself) - the fact we reverse the string of digits should stop 1 being uncommonly prevalent as a result of the character range we select from IOW, let's re-test this -- BEGIN SNIPPET -- It's possible the fairly limited range of char codes (0-127) could lead to certain integers being more common - if that's the case then you'd expect to see a heavier weighting on those numbers: 1 is probably an obvious example, because every ASCII character code > 100 has a 1 in it 2 is also likely to me more common, because char codes get up to 127 - it has 8 more entries (120-127) than the numbers 3-0 That's something we should be able to check for reasonably easily - can come back to this. -- END SNIPPET -- Wrote a quick LUA script to wrap the logic used by the dice roll generation -- BEGIN SNIPPET -- -- LUA script to double assumptions about processing being done -- See MISC-46 -- -- Assumptions: -- -- - I'm not going mad, we *do* test the first integer in the reversed string rather than testing from the other end -- function extract_dice_roll(digis) -- Print our input print("Orig: " .. digis) -- We reverse the string (presumably to remove the bias towards 1 being the first char - I can't remember) digis = string.reverse(digis) print("Rev : " .. digis) -- Run the check process for c in digis:gmatch"." do if tonumber(c) > 0 and tonumber(c) < 7 then print("Sel : " .. c) return end end end -- Test 2 strings of random integers -- ben@optimus:~$ curl -s https://random.bentasker.co.uk/randintegers https://random.bentasker.co.uk/randintegers -- 6912611083685936101731191241134012291105 -- 45715780626053396259123645310491805912010893 digis = '6912611083685936101731191241134012291105' extract_dice_roll(digis) print(" ") digis = '45715780626053396259123645310491805912010893' extract_dice_roll(digis) -- END SNIPPET -- Running -- BEGIN SNIPPET -- ben@optimus:~$ lua /tmp/test.lua Orig: 6912611083685936101731191241134012291105 Rev : 5011922104311421911371016395863801162196 Sel : 5 Orig: 45715780626053396259123645310491805912010893 Rev : 39801021950819401354632195269335062608751754 Sel : 3 -- END SNIPPET -- So I've _not_ gone nuts, there should be no bias towards 1 because it's ability to appear in the hundreds (or even the teens) is removed by the reversal of the string. To put it another way, if we have - 126 - 134 - 51 The number 1 has the same probability of being selected as 6 and 4, because after reversal we're actually selecting the first char from - 621 - 431 - 15 Yet, ent fairly consistent reports a higher showing for 1 than other numbers... Why is that? It's not a product of ent reading the data in an unexpected way (say bits instead of bytes) because we can repro the distribution with uniq -- BEGIN SNIPPET -- ben@optimus:~$ cat /tmp/rolls | sed -e "s/.\{1\}/&\n/g" | sort | uniq -c 2037 1 1222 2 1598 3 1731 4 1682 5 1730 6 -- END SNIPPET -- It's going to take quite a while to complete, but lets set a series of rolls going -- BEGIN SNIPPET -- ben@optimus:~$ for n in {1..10}; do for i in {1..10000}; do curl -s https://random.bentasker.co.uk/dice | tr -d '\n' ; done > /tmp/auto-rolls-$n; done -- END SNIPPET -- We can then see if that tendancy towards 1 continues ----------------------------------------------------------------------------------------- 2021-06-04 14:07:24 btasker ----------------------------------------------------------------------------------------- While I wait for that, I want to fix some of those races - even though they're ostensibly mitigated by the mixing, it'd still be good to try and minimise them. We can write the digest to SHM sooner (so that the next request doesn't re-use the one we've just used), but there are a couple of options here - Do we do it immediately? - Do we wait until we've performed our calculations, but before sending back to client Neither is perfect. If we write it out immediately, then there's potential for a different race: -- BEGIN SNIPPET -- Client a: get /DICE nginx: fetch last from SHM nginx: mix nginx: write to SHM (mix again) Client b: get /randombytes nginx -> Client a: response -- END SNIPPET -- In the flow above, the digest that Client b gets would be derived from the digest that Client a's response is derived from. It won't be directly the same, because of our earlier mixing, but as they're psuedo-random bytes there's still potential for a fuck-up. On the other hand, if we wait until we've performed our calculations, then the race we have is the same as now - it's just that the window is shortened by not having to wait until the response is sent to client. The difference between the two though, is that in the first, Client B could conceivably get random bytes before they've been served to Client A - he'd have preknowledge of what's going out (assuming he could overcome the mixing). I guess the truth of the matter is that we have to trust the mixing rounds - there's one when writing the value to SHM, and the 3 after loading it. So actually, the race's have different levels of mixing - Current: 3 rounds (load time) - Preknowledge: 1 round (when writing to SHM) + 3 rounds (load time) Although the storage mix wasn't added for that reason: -- BEGIN SNIPPET -- -- Store for use as a seed by the next request -- we don't store the value directly (otherwise there'd be a copy in RAM of what the last output was) apparea:set("last_rnd", ngx.sha1_bin(digest .. random.bytes(16))) -- END SNIPPET -- It would seem better to have the protection of the additional round. ----------------------------------------------------------------------------------------- 2021-06-04 14:11:53 git ----------------------------------------------------------------------------------------- -- BEGIN SNIPPET -- ------------------------- From: git@