Schneier on Security

Clive Robinson • April 26, 2013 6:28 AM

@ Nick P, Peter A., Mark J. Blair,

How about a 20- or 30-sided die of the sorts used by pencil-and-paper role-playing gamers, imprinted with a collection of letters and/or digits?

Whilst more sides at first sight suggests the less throws you need make, the problem is the more the number of sides you’ve got, the more bias and the more easily recognised it is in your resulting output [1].

Also a power of two (ie 2, 4, 8, 16, 32 etc) would at first sight appear to be better than other numbers of sides but in the words of the song “That ain’t necessarily so…” as it actually makes a bias more obvious.

To help remove bias it is easiest to use two or more random elements and then combine their results such the bias is spread across all of them. However this has to be done with care lest you change the probability distribution [2].

There is also the questions of “availability” and occasionaly “suspicion” in using anything other than two (coin) or six (regular die) sides. For instance a 20 sided dice is generaly only available through specialist educational suppliers or role playing games outlets which are not exactly thick on the ground. Further going through a check / customs point is likely to turn up a 20 sided die and one or two questions’ where as a couple of packs of cards and a couple of ordinary six sided dice are going to be less questioned and more easily explained. Whilst a pocket of lose change is so ordinary as to attract more suspicion if you did not have lose change…

So how to convert the throw of two dice to a number of bits. One simple way is by matrix. Draw up a six by six grid and fill in the squares with numbers from 0 to 35 in any order. Along the top of the grid write 1-6 and likewise down the left hand side of the grid. Have the dice marked in some way (different coloured bodies or dots etc) that does not add bias and use one to pick the left number the other the top and throw them from the cup at the same time as a pair. Read the result from the grid, if the number is outside your required range (0-31) discard the result and throw again. Keep going untill you have the required number of bits or more.

If however you want letters and numbers fill in the grid randomly with A-Z,0-9 or just letters fill in A-Z randomly and leave the other squares blank. If just numbers then use 0-9 three times and randomly and leave six squares blank.

It’s a process that has been used several times over the years to generate “One Time Pads” and I wrote a little program many years ago that fits nicely onto a floppy disk along with the MS OS that prints out two neatly formated pages for the pads to be easily used. It also keeps a running tab on the numbers looking for bias.
Importantly create the matrix anew for each random sequence you need and then destroy it afterwards as being in posetion of it is a dead give away as to what you are using the dice for.

[1] It’s been shown a number of times that it is actually quite dificult to make an unbiased mechanical object such as a coin or die. However for most uses the slight bias can be ignored or where important (cryptography etc) de-biased. The von newman de-biaser of taking two succesive and thus otherwise unbiased coin flips and using them to provide one unbiased bit is one of very many [2].

[2] As a simple example take six ordinary dice and throw them from a cup and count up all the spots you get numbers in the range 6-36 as you would expect but after a few throws or moments of thought you will realise that the probability distribution is not flat but a close approximation of the bell curve. However take the result mod 6 and you will get the equivalent of a single die being thrown but the bias of each of the six dice is reduced and spread across all the numbers making the probability nearer being flat.

Clive Robinson • April 26, 2013 5:49 PM

@ woody weaver,

My solution was just a penny,…

As I said,

Whilst a pocket of lose change is so ordinary as to attract more suspicion if you did not have lose change..

It is a working method but you have to watch you don’t fall into a predictable pattern such as using the penny for every fourth bit etc.

The reason for using dice, belive it or not is way to many don’t know how to flip a coin “fairly” where they show no such problems with dice (go figure, it’s puzzeled me for many years).

@ Peter A.,

By the way, I am completely puzzled by your comment about a non- standard die getting attention of customs/whatever. What’s wrong or unusual with it?

It’s the fact it’s “unusual” it makes people look at you differently and thus much much more likely to remember you or even think you “hinky” thus add you to their daily list.

As was once remarked by a famous physicist who liked to pick locks as a cure for being subject to excessive security,

The sound of a scientific discovery is not Eurica, but “that’s odd”.

Which is also often the sound of somebodies ‘legend’ (back / cover story) starting to unravel.