MISC-46: Dice rolls on random.bentasker.co.uk may not be consistently random

So, to start off, lets place some requests to try and repro

Rolling 2 dice twenty times

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

Does seem more common than might be expected.

Can we get triples?

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,

No, but there is a sequence in there if we squash rolls together

2,1,5,5,5,6,

Could be chance though.

Another run yields two identical rolls one after the other

5,3,2,
5,3,2,

Another run gets us triples

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,

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.

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:

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

Note: random is an FFI which under the hood calls

C.RAND_pseudo_bytes(buf,len)

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.

local digest = table.concat(dgst_tbl,'')

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

    if optype == "dice" then
        -- Call self to get a list of digits
        digis = generate_limited_output("digits",digest)

There's nothing immensely special about the digits mode

    if optype == "digits" then
        for c in digest:gmatch("[%w%p]+") do
            table.insert(op,string.byte(c))
        end
        return table.concat(op,"")
    end

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:

ben@optimus:~$ curl -s https://random.bentasker.co.uk/randintegers
98446392427510789791146583501075951

The response then processed within the dice section in order to extract integers and ensure they're ones you'd find on a dice

digis = string.reverse(digis)
for c in digis:gmatch"." do
	    if tonumber(c) > 0 and tonumber(c) < 7 then
		return c
	    end
        end

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

    ngx.say(generate_limited_output(my_mode,digest))

Finally, the value is written to SHM for use by the next request (mixing with some random bytes to provide some back-tracking protectio)

apparea:set("last_rnd", ngx.sha1_bin(digest .. random.bytes(16)))

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

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

Let's start by testing this

- 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?)

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

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

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

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

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:

it feels like 6 is disproportionately common, but will examine that in a bit.

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

Let's run this through an RNG tester

ben@optimus:~$ for i in {1..10000};  do      curl -s https://random.bentasker.co.uk/dice | tr -d '\n' ; done > /tmp/rolls

Verifying we've a full set

ben@optimus:~$ wc -c /tmp/rolls 
10000 /tmp/rolls

What does ent make of it

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).

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

 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

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

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).

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.

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

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

 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.

Wrote a quick LUA script to wrap the logic used by the dice roll generation

-- 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)

Running

ben@optimus:~$ lua /tmp/test.lua 
Orig: 6912611083685936101731191241134012291105
Rev : 5011922104311421911371016395863801162196
Sel : 5
 
Orig: 45715780626053396259123645310491805912010893
Rev : 39801021950819401354632195269335062608751754
Sel : 3

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

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

It's going to take quite a while to complete, but lets set a series of rolls going

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

We can then see if that tendancy towards 1 continues

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:

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

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:

-- 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)))

It would seem better to have the protection of the additional round.

My 100k rolls are still running, so lets move onto checking the remaining place that might lead to erroneous doubles - the browser cache.

The Dice at https://random.bentasker.co.uk are populated by placing 2 XHR requests to /dice - is the browser perhaps caching the first response, so using it to satisfy the second?

If we look at the response headers

> GET /dice HTTP/2
> Host: random.bentasker.co.uk
> user-agent: curl/7.68.0
> accept: */*
> 
{ [5 bytes data]
* Connection state changed (MAX_CONCURRENT_STREAMS == 128)!
} [5 bytes data]
< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 12:18:07 GMT
< content-type: text/plain
< vary: Accept-Encoding
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 

There is no cache-control so the browser might decide to cache.

Devtools says it's not cached though, and there are 2 requests showing in the nginx access log, so it's not that.

All the same, it'd probably be wise to stick a cache-control header in to make sure we're being explicit (other browsers might behave differently to Firefox).

OK, one hundred thousand rolls completed.

Lets start by looking at the distribution of the number 1 - in the earlier tests it was basically always 20% of rolls.

ben@optimus:~$ for n in {1..10}; do echo $n; cat /tmp/auto-rolls-$n | sed -e "s/.\{1\}/&\n/g" | sort | uniq -c; echo; done
1
   2020 1
   1267 2
   1564 3
   1732 4
   1669 5
   1748 6

2
   2076 1
   1247 2
   1582 3
   1687 4
   1634 5
   1774 6

3
   2106 1
   1195 2
   1631 3
   1708 4
   1655 5
   1705 6

4
   2080 1
   1208 2
   1608 3
   1707 4
   1751 5
   1646 6

5
   2081 1
   1183 2
   1655 3
   1752 4
   1679 5
   1650 6

6
   2061 1
   1183 2
   1630 3
   1715 4
   1699 5
   1712 6

7
   2094 1
   1228 2
   1588 3
   1703 4
   1693 5
   1694 6

8
   2048 1
   1215 2
   1549 3
   1712 4
   1719 5
   1757 6

9
   2041 1
   1206 2
   1618 3
   1710 4
   1682 5
   1743 6

10
   2073 1
   1233 2
   1550 3
   1771 4
   1705 5
   1668 6

That's... odd.

Putting them all together:

ben@optimus:~$ cat /tmp/auto-rolls-* | sed -e "s/.\{1\}/&\n/g" | sort | uniq -c
  20680 1
  12165 2
  15975 3
  17197 4
  16886 5
  17097 6

There does seem to be a consistent bias towards 1. In fact, the distribution of other results - whilst unequal - is also actually quite consistent between each of the batches (to the extent that batch 5 and 6 returned 2 exactly the same number of times).

So, I think we need to dig a bit deeper than the high level KISS skim we've done so far and look a little closer at our source (digest) and how we select bytes from it (i.e. is there an inherent bias in the HMAC towards these?)

OK, so going back to square one, the setup is based around the idea that we

- Generate a HMAC (from several rounds of mixing)
- Regex printable chars out of it
- Convert those chars into ASCII character codes (to get a string of integers)
- Select an integer from that string

We've ascertained (I think) that there's no race - the rounds of mixing are effective.

But, is there perhaps an introduced bias from the conversion process? For any given random string, there must be a fairly limited number of ascii printable chars

ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
cEs8otLS1
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
H!lXzvben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
h[WQF
2	s&~
Ga:0?
<9u\
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
 oT|
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
ben@optimus:~$ curl -s https://random.bentasker.co.uk/randombytes | base64 -d | strings
;)XV
QttG

There are a few there where we don't get any at all. Probably wise to start at looking how we handle that?

    if optype == "digits" then
        for c in digest:gmatch("[%w%p]+") do
            table.insert(op,string.byte(c))
        end
        return table.concat(op,"")
    end

....
    if optype == "dice" then
        -- Call self to get a list of digits
        digis = generate_limited_output("digits",digest)
        -- Reverse the string, it'll regularly start with 1
	digis = string.reverse(digis)
        for c in digis:gmatch"." do
	    if tonumber(c) > 0 and tonumber(c) < 7 then
		return c
	    end
        end
	ngx.header['X-generated'] = digis
	return ''
    end

We should get an empty value back. But, despite quite easily failing to find matches with strings in over 10,000 rolls I've not seen an empty roll come back.

Ah, that's my fault - strings only prints sequences of 4 chars by default, retesting with strings -n1 doesn't yield empty responses

Have added some debug headers so that we can look at what digits are being fed into the dice selection, ignoring output unless I got a 1 back:

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:08:01 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 33521025988756110095454169589110841117
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 71114801198596145459001165788952012533
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:11:20 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 118103863671937910844861181147096110
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 011690741181168448019739176368301811
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:11:50 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 121551003553122110446963396256948689983974487971
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 179784479389986849652693369644011221355300155121
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:12:06 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 6685357796515263120476454345933781234371
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 1734321873395434546740213625156977535866
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:12:30 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 66598610870869457876963126571177310945897341
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 14379854901377117562136967875496807801689566
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

< HTTP/2 200 
< server: openresty/1.13.6.2
< date: Fri, 04 Jun 2021 13:12:59 GMT
< content-type: text/plain
< vary: Accept-Encoding
< cache-control: no-cache,no-store
< pragma: no-cache
< x-generated: 7594111104734451878178355277851208311684117
< x-generated-triggered: Y
< x-selected: 1
< x-selection: 7114861138021587725538718781544374011114957
< x-clacks-overhead: GNU Terry Pratchett
< access-control-allow-origin: *
< access-control-allow-methods: GET, POST, OPTIONS
< access-control-allow-headers: DNT,User-Agent,X-Requested-With,If-Modified-Since,Cache-Control,Content-Type,Range
< access-control-expose-headers: Content-Length,Content-Range
< onion-location: http://ws6hhe4yscma2mtg26lnhc77relfrk3qs5lpgjqzuu6bu5nldbcet2ad.onion/dice
< 
1

There is actually a slight potential for bias towards 1 here, though it's not the hundreds column, it's the 10s.

There are three ways a result can get selected

- They're in the units column (i.e. the last number in the digit string prior to reversing)
- They're in the tens column (i.e. the penultimate number before reversing) and the number in units is >= 7 or is 0
- They're in the hundreds column, and the numbers in both tens and units are >= 7 or 0

Which gives a couple of observations

- results >= 3 lose the advantage of the second selection mechanism after we've reached 100 (because the pool of integers is 1 - 127)
- Only result 1 has the advantage of the third selection mechanism, giving it a boost with 100,107,108,109 as entries (in addition to it's 101)

Taking 4 as an example, it has 17 "entries" (4, 14, 24, 34, 40, 44, 47, 48, 49, 54, 64, 74, 84, 94, 104, 114, 124)

Whereas 1 has 24 entries (1, 10, 11, 17, 18, 19, 21, 31, 41, 51, 61, 71, 81, 91, 101, 107, 108, 109, 110, 111, 117, 118, 119, 121). It literally has 41% more chance of being selected than each of 3 - 6.

Number 2 also has an advantage with 19 entries (2, 12, 20, 22, 27, 28, 29, 32, 42, 52, 62, 72, 82, 92, 102, 112, 120, 122, 127) - 11% more chance.

In total, there should be 111 entries - there are < 127 because there are certain numbers that can't be used at all (0, 7, 8, 9, 70, 77, 78, 79, 80, 87, 88, 89, 90, 97, 98, 99)

Those entries (seperated by result) are

1,10,11,17,18,19,21,31,41,51,61,71,81,91,101,107,108,109,110,111,117,118,119,121
2,12,20,22,27,28,29,32,42,52,62,72,82,92,102,112,120,122,127
3,13,23,30,33,37,38,39,43,53,63,73,83,93,103,113,123
4,14,24,34,40,44,47,48,49,54,64,74,84,94,104,114,124
5,15,25,35,45,50,55,57,58,59,65,75,85,95,105,115,125
6,16,26,36,46,56,60,66,67,68,69,76,86,96,106,116,126

So we can now work out the percentage chance of a number being selected vs any other result

- 1 : 21.62%
- 2 : 17.11%
- 3 : 15.31
- 4 : 15.31
- 5 : 15.31
- 6 : 15.31

Bias doesn't apply linearly, so the results we were getting earlier now make a lot more sense (although 2 doesn't seem to have sufficiently high an advantage to capitalise on it, and made quite a poor showing in the earlier rise).

We now know why I got snake-eyes so frequently in our monopoly game.

Next thing is working out how to fix it.

OK, fixing this without introducing (or worsening) bias may be interesting.

There are two obvious options

- Shuffle/randomise the digit string rather than simply reversing it (effectively picking a random position in the digit string)
- When selecting digits, constrain to char codes 1-96 (which should give an equal number of entries to each)

The problem with shuffling is we probably actually worsen the bias towards 1 in some cases.

Currently there are mitigations (reversing the string) in place to deal with it's advantage of appearing in the 100s column, doing shuffle/random select would undermine that, giving 1 additional entries.

So, in addition to it's current entries 1 would start to gain an entry for the numbers 102, 103, 104, 105, 106, 112, 113, 114, 115, 116, 122, 123, 124, 125 and 126 (because the 1 from the hundreds column could be moved anywhere in the digits string).

It's a (slightly) bigger code change, but constraining the digit string to values between 1 and 96 should be a better fit. It'd constrain the entries to

1,10,11,17,18,19,21,31,41,51,61,71,81,91
2,12,20,22,27,28,29,32,42,52,62,72,82,92
3,13,23,30,33,37,38,39,43,53,63,73,83,93
4,14,24,34,40,44,47,48,49,54,64,74,84,94
5,15,25,35,45,50,55,57,58,59,65,75,85,95
6,16,26,36,46,56,60,66,67,68,69,76,86,96

It would however increase the chance of getting an empty digit string back (so I need to look closer at how we handle that too)

Preliminary tests show that's shifted the bias the other way

ben@optimus:~$ cat /tmp/auto-rolls-1 | sort | uniq -c
    565 1
    537 2
   1808 3
   2371 4
   2388 5
   2331 6
ben@optimus:~$ cat /tmp/auto-rolls-2 | sort | uniq -c
    289 1
    275 2
   1062 3
   1363 4
   1326 5
   1313 6

That'll be courtesy of the pattern match

digest:gmatch("[%w%p]+")

Matches alphanumerics and punctuation. But, the lower end of the ASCII table (0-32) is comprised of chars that won't match.

Turns out we needed the hundreds to give 1 and 2 (and to a limited extent, 3) a showing. I should've thought of that earlier.

So, we need to redefine the rules a bit:

- Char code should be between 32 (the first punctuation char) and 126 (the last)
- Unusable codes should be omitted (to avoid bias toward 1 and 2)

So, we'd need to omit 107,108,109 - that'd still leave us imbalanceed though (3 doesn't get the benefit of 30), so we also need to omit multiples of 10)

Giving

- 1 : 41,51,61,71,81,91,101,110,110,121 (10 entries)
- 2 : 32,42,52,62,72,82,92,102,112,122 (10 entries)
- 3 : 33,43,53,63,73,83,93,103,113,123 (10 entries)
- 4 : 34,44,54,64,74,85,94,104,114,124 (10 entries)
- 5 : 35,45,55,65,75,85,95,105,115,125 (10 entries)
- 6 : 36,46,56,66,76,86,96,106,116,126 (10 entries)

Exclusion list is therefore 40,50,60,107,108,109.

Rather than a bunch of if statements, we need a function to check if the value is in a table of exclusions

ben@optimus:$ cat /tmp/test.lua
function table_contains(tbl, x)
    found = false
        for _, v in pairs(tbl) do
                if v == x then 
            found = true 
        end
        end
        return found
end



tbl = {1,2,3}
print(table_contains(tbl,1))
print(table_contains(tbl,99))
ben@optimus:~$ lua /tmp/test.lua
true
false

Ah, but, if we're reintroducing hundereds, we also need to reintroduce reversing the string otherwise 1 will get a massive weighting

-------------------------
From: git@<Domain Hidden>
To: jira@<Domain Hidden>
Date: None
Subject: MISC-26 Adjust character selection again
-------------------------

Repo: domains.d
Host:astria

commit 04f42fe2bfa4e8e133caeca974d834f52c88a1dd
Author: B Tasker <github@<Domain Hidden>>
Date: Fri Jun 4 18:00:42 2021 +0100

Commit Message: MISC-46 Adjust character selection again

The previous approach weighted correctly in terms of char code distribution, but many of the char codes in that set wouldn't be selected by the regex used.

Switch to using a higher set (starting at 36/!) and exclude codes that give 1 a bias. Because codes > 100 are back in use, reintroduce the string reversal

LUA/rnd_number_gen.lua | 31 +++++++++++++++++++++++++++++--
1 file changed, 29 insertions(+), 2 deletions(-)

View Commit | View Changes

The latest run of 10,000 rolls looks much better

ben@optimus:~$ cat /tmp/rolls | sort | uniq -c
   1952 1
   1354 2
   1648 3
   1663 4
   1642 5
   1741 6

So, lets check the 10K rolls from overnight

ben@optimus:~$ for n in {1..10}; do echo $n; cat /tmp/auto-rolls-$n | sort | uniq -c; echo; done
1
   1985 1
   1364 2
   1623 3
   1589 4
   1604 5
   1835 6

2
   1968 1
   1361 2
   1673 3
   1600 4
   1655 5
   1743 6

3
   1915 1
   1356 2
   1623 3
   1650 4
   1660 5
   1796 6

4
   1868 1
   1355 2
   1689 3
   1589 4
   1706 5
   1793 6

5
   1890 1
   1407 2
   1621 3
   1684 4
   1648 5
   1750 6

6
   1967 1
   1365 2
   1668 3
   1590 4
   1645 5
   1765 6

7
   1901 1
   1354 2
   1650 3
   1658 4
   1621 5
   1816 6

8
   1922 1
   1413 2
   1649 3
   1581 4
   1652 5
   1783 6

9
   1969 1
   1394 2
   1637 3
   1634 4
   1621 5
   1745 6

10
   1869 1
   1403 2
   1607 3
   1628 4
   1657 5
   1836 6

That's much better, but it still feels like there might be a bias there, was 1 really the most common every time?

ben@optimus:~$ cat /tmp/auto-rolls-* | sort | uniq -c
  19254 1
  13772 2
  16440 3
  16203 4
  16469 5
  17862 6

Ah, maybe it's that our exclusion list isn't quite comprehensive enough - 1 still gets the benefit of 117,118,119 which may well be enough to tilt in it's favour slightly. In fact, actually, is it slightly worse than that? We've not done anything really about numbers ending in 7,8,9 so some may still have an advantage, lets fill those in


- 1 : 41,51,61,71,81,91,101,110,110,117,118,119,121 (13 entries)
- 2 : 32,42,52,62,72,82,92,102,112,122 (10 entries)
- 3 : 33,37,38,39,43,53,63,73,83,93,103,113,123 (13 entries)
- 4 : 34,44,47,48,49,54,64,74,85,94,104,114,124 (13 entries)
- 5 : 35,45,55,57,58,59,65,75,85,95,105,115,125 (13 entries)
- 6 : 36,46,56,66,67,68,69,76,86,96,106,116,126 (13 entries)

2 is at a definite disadvantage

Lets adjust so that numbers ending in 7,8,9 are excluded - that brings us back to 10 entries per result.

Distribution between 5 sets of rolls looks much better

ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c
    214 1
    185 2
    134 3
    151 4
    161 5
    155 6
ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c
    187 1
    165 2
    143 3
    162 4
    171 5
    172 6
ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c
    174 1
    164 2
    157 3
    180 4
    157 5
    168 6
ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c
    192 1
    176 2
    142 3
    168 4
    144 5
    178 6
ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/dice; done | sort | uniq -c
    179 1
    194 2
    148 3
    157 4
    147 5
    175 6

Setting 10k rolls going for verification, but I think we've probably got it this time.

So, as this ticket's now quite long, I'll attempt to summarise

- There are possible race conditions stemming from the way hashes in the chain are passed between requests
- all appear to be well mitigated by the mixing rounds
- There was a bias towards result 1 (caused by the advantage gained from numbers in the hundreds and hundred-and-tens)
- Result 1 had 6% more chance of being returned than 3-6 combined (it had a 41% headstart on each though)
- This was sufficient to gain an advantage, but not enough that it's immediately obvious in a small number of rolls
- Low levels of bias require large datasets to spot, so testing for them is hard and time consuming
- There was no bias towards doubles in general, but the bias towards 1 increased the probability of getting snake eyes.
- Human memory sucks: I was aware I'd got a lot of doubles, but statistically it's likely that a lot of them were snake eyes - something I hadn't consciously registered (too excited at escaping jail I guess)
- Human perception of randomness really sucks - we often see randomness where there's bias, and bias in properly random sets

On that last point, I've written in the past about the difficulties involved in assessing randomness (https://www.bentasker.co.uk/documentation/security/287-understanding-the-difficulty-of-assessing-entropy), so it's not solely a human problem - machines suck at it too.

There is a certain irony in the dice having been biased. The codebase was originally created to consume seeds from a ChaCha20 generator I wrote and backdoored (https://www.bentasker.co.uk/blog/software-development/689-writing-a-chacha20-based-csprng), so there was an early intention to make inputs predictable.

It, along with some of my hamfisted fixes above, show just how easy it is to accidentally introduce a new bias - if it's a subtle enough advantage you may not register it until you're looking at large datasets. Even then, there's a lot of cross-checking and doubt involved because the brain will tend to see patterns where none exist, and miss patterns that do exist.


Abusing this

It'd be remiss of me not to look at how we weaponise this

That we can so easily tilt rolls in favour of 1 is interesting, but probably not that useful for cheating (getting out Monopoly jail not withstanding), but because the bias is at the start of the result range, we can quite trivially make it more useful.

If we invert the range (so 1 becomes 6, 2 becomes 5 etc) then we've given ourselves dice that have a habit of rolling 6, with a corresponding increase in the number of double 6s - in LUA that'd be as simple as

ben@optimus:~$ cat /tmp/test.lua
function invert_roll(r)
	return 7 - r
end

print(invert_roll(1))
print(invert_roll(2))
print(invert_roll(6))
ben@optimus:~$ lua /tmp/test.lua
6
5
1

I've added a new "Rigged Dice" option to https://random.bentasker.co.uk/ - it should show a subtle bias towards 6:

ben@optimus:~$ for i in {1..1000}; do curl -s https://random.bentasker.co.uk/riggeddice; done | sort -n | uniq -c
    175 1
    172 2
    179 3
    164 4
    101 5
    209 6