Generate entropy with dice.

Entropy == some information without predictable structure.

Convert the result to 8-bit bytes.







- Goal
- Contents
- Brief Summary
- Summary
- Recipe For Generating Entropy Bytes Using Dice
- Downloadable Assets
- Notes
- Further Work
- Project Log







During this project, I developed a process that converts dice roll results into hex bytes with ~66% entropy preservation. I estimate that using dice and this process to generate sufficient entropy for a Bitcoin address should take at most 10 minutes.

Please read the Recipe For Generating Entropy Bytes Using Dice section if you would like to know how to use this process.

Please read the Summary section for a more thorough description of this project.







Using 5 dice, it took me 310 seconds (6 minutes, 10 seconds) to perform 200 dice rolls and record the results in a text file. I rolled the dice in a tray with raised edges.

I developed a process that converted the dice roll results into hex bytes with ~66% entropy preservation. This process consists of an algorithm, a script that implements this algorithm, and a recipe for using the script. I was able to extract 34 bytes of entropy from the 200 dice rolls. For comparison, a Bitcoin address and a Bitcoin transaction signature each require 32 bytes of entropy. I think that a reasonable high-end time estimate for using dice to generate sufficient entropy for a Bitcoin address is about 10 minutes.

The Recipe For Generating Entropy Bytes Using Dice section describes the conversion process.


Notes section:

The Notes section contains the following parts:

- Entropy and cryptography
- Entropy in RSA and ECDSA
- Generating entropy
- Generating entropy with dice
- Algorithm for converting dice rolls to entropy bytes


Further Work section:

The Further Work section contains the following parts:

- Greater entropy preservation
- Debiasing dice







Note: This recipe relies, at its base, on the algorithm described in the Notes section, in the "Algorithm for converting dice rolls to entropy bytes" part.

0. Obtain the script convert_dice_rolls_to_hex_bytes.py. This file is stored as an asset of this article. See the Downloadable Assets section.

1. Obtain one or more dice.

2. Choose a desired number of bytes of entropy. Multiply this number by 8 to convert to bits. Divide the result by the expected-bit-rate-per-dice-roll value (1.3333) to find the expected number of dice rolls that should generate this number of entropy bits. Multiply this result by 1.1 to add a 10% margin, then round up to the nearest integer.

Note: Some dice roll result values will be discarded so that the value domain becomes base4, which can be then be converted to base16 (i.e. hex bytes).

3. Perform this number of dice rolls and record the results in a text file. An individual dice roll must be recorded as one individual character from the list "123456". Whitespace (newline, tab, space) can be used to separate groups of dice roll values. Recommendation: Roll the dice on a flat tray with raised edges, so that they don't scatter too far.

4. In the script convert_dice_rolls_to_hex_bytes.py, scroll to the section of text that lies between

and

- Set the variable to be the desired number of bytes of entropy.
- Set the variable to be the path to the text file containing the dice roll results.

5. Open a terminal. Change directory to the directory containing this script. Run the script using the following command:


6. The output of the script should contain the generated entropy as hex bytes.

7. (optional) If more dice rolls are needed in order to reach the desired number of bytes of entropy, the script will calculate a suggested number of new dice rolls. Perform the dice rolls, add the results to the dice roll results text file, and run the script again.







Description: A script that converts dice roll results into bytes.
convert_dice_rolls_to_hex_bytes.py


Description: A set of 200 dice roll results produced during this project.
dice_rolls.txt













Parts:

- Entropy and cryptography
- Entropy in RSA and ECDSA
- Generating entropy
- Generating entropy with dice
- Algorithm for converting dice rolls to entropy bytes




Entropy and cryptography


Secure cryptography requires secret values that are very difficult to guess.

An adversary could try to use all conceivable secret values in a cryptosystem to perform a particular operation, store the results, and see if any result matches a public cryptographic item. If a match is found, the adversary now knows the corresponding secret value. This is known as a "brute force attack". In any cryptosystem, this option is always available to an adversary.

For this reason, good cryptosystems have large possibility spaces for these secret values. The number of possible secret values should be so vast that to try all possible guesses would take many human lifetimes, even if an adversary can use enormous amounts of computational power.

In computing, "entropy" is used to mean "some information without predictable structure". It is generated using some physical process whose output is unpredictable and converted by a transducer into digital data.

Entropy is hard for an adversary to guess. An amount of entropy can therefore be used as a secret value for cryptographic operations. Entropy is also useful in other contexts e.g. for choosing values for testing a function.

In high-quality entropy, any piece of the information should be as unrelated as possible to any other piece of the information. It should be as close to "noise" as possible, with no "signal" i.e. no pattern. If there is a systematic pattern caused by the entropy source process, i.e. the process does not produce perfectly random values, this will reduce the possibility space of secret values. If an adversary is able to somehow learn this pattern, and the possibility space is small enough, the adversary may be able to use a brute force attack.

Individual sections of entropy may look like they fit a pattern, due to random variation. Conversely, digits 1000-1057 of the transcendental number π may look randomly generated, but are not. It is not possible to prove, from the data alone, that a given amount of entropy was generated by a random process. Entropy can only be tested for "noisiness". For this reason, it is important to focus on and examine the physical process of the entropy source in order to be satisfied that it produces high-quality entropy. As a confirmation, a large amount of entropy data should be generated and tested for noisiness.




Entropy in RSA and ECDSA


In the RSA cryptosystem, entropy is needed for private keys.

In the ECDSA cryptosystem, entropy is needed for private keys and for making signatures.

ECDSA digital signatures require a random K value, which must be used only once for one signature by a private key. For another signature, a second random K value must be used.

I don't know if it is dangerous to use the same random K value for two separate signatures made by two different private keys, but I regard doing so as risky until proven otherwise. A new K value should be generated for each ECDSA signature.




Generating entropy


It is difficult and time-consuming to generate good entropy. If a tool is used to automate entropy generation, auditing such a tool is difficult and time-consuming.

Let's define a Random Number Generator (RNG) to be "a process whose output is unpredictable". The output of an RNG must be convertible to a digital bit sequence.

The human brain is bad at generating entropy. Given that a large part of its operation involves detecting patterns, this is unsurprising. Detecting patterns is the opposite of generating random values. If a human is asked to think of a random string of words, his/her mind will flow along existing grooves of thought in ways that could be predicted with some success by an adversary.

Example RNGs:
- A human flipping through a dictionary, pointing at words at random, and writing them in a text file. This probably produces higher-quality entropy than trying to think of a random sequence of words. When he/she has recorded 100 words, he/she can use a hash function (e.g. SHA256) to calculate the hash digest of the text file. The digest will be a bit sequence (entropy).
- A circuit board containing a) a heated element that generates thermal noise and b) a transducer that converts this thermal noise into digital output i.e. a bit sequence (entropy).

Note: A Pseudorandom Number Generator (PRNG) is a type of algorithm that generates a sequence of values that appears to be random. It requires a seed value from which to begin generation. This seed value should be random. Thus, it still requires some entropy. It is really an "entropy-stretcher", making a little entropy appear to be a much larger amount of entropy. A PRNG can be useful for testing but should not be used for important cryptographic operations. An adversary could attempt to guess the seed value.




Generating entropy with dice


I used dice to generate entropy during this project.

An individual dice roll has 6 possible outcomes: 1, 2, 3, 4, 5, 6. A dice roll result will thus be in base6. The values should start at 0, so 1 should be subtracted from each result. The possibility space of the result is therefore [0,1,2,3,4,5]. If multiple dice are rolled, their results can be concatenated to form a numeric string in base6. Example: "4032151".

I needed to convert the dice roll results to digital data, without skewing the value space during the conversion process (i.e. introducing a systematic pattern or bias). Also, I wanted to avoid the need to perform BigNumber calculations. I chose to use a lookup table to map the dice roll value space to a digital data value space.

Numbers stored as bit sequences are in base2, but in computing, bits are usually stored and manipulated in groups of 8 ("bytes"), so numbers stored as bytes are in base(2^8) == base256. Bytes can be written in hex characters (2 hex characters per byte). I originally planned to convert dice roll results directly to bytes. However, I found it easier to work with half-bytes, which have 16 possible values (rather than 256) and can be written with 1 hex character.

I decided to discard one third (2/6 = 1/3) of the entropy by discarding the top two dice roll values, reducing the value space of a dice roll result to [1,2,3,4]. All remaining dice roll results could now be described in base4. 4^2 = 16, so a sequence of two base4 digits maps directly onto one base16 digit. The base4 dice roll results could now be converted to base16, with no skew / pattern / shift introduced into the conversion process.

Using 5 dice, it took me 310 seconds (6 minutes, 10 seconds) to perform 200 dice rolls and record the results in a text file. I rolled the dice in a tray with raised edges. 310/200 ~= 1.5 seconds per dice roll. 1.33 bits of entropy per 1.5 seconds = 1.33 / 1.5 ~= 0.89 bits of entropy per second.

After running a script, which discarded a portion of the entropy, I was left with 34 bytes of entropy. For comparison, a Bitcoin address and a Bitcoin transaction signature each require 32 bytes of entropy. I think that a reasonable high-end time estimate for using dice to generate sufficient entropy for a Bitcoin address is about 10 minutes.




Algorithm for converting dice rolls to entropy bytes


An 8-bit byte (base256) can be written as two hex characters.

Hex characters:
0123456789abcdef

A single hex character is a half-byte (base16).


Lookup table for converting two base4 digits to one base16 digit:




1. Roll dice and record the results as values in the list [1,2,3,4,5,6].

2. Discard all values in the list [5,6]. This means that the value domain now consists of 4 digits, and a string of these values will be in base4.

3. Subtract 1 from all remaining values. This means that the value domain now starts at 0.

4. If the number of remaining dice rolls is uneven, remove one.

5. Proceed through the dice roll values by groups of two. Using the lookup table above, convert each group of two to a base16 digit. Store the resulting base16 digits.

6. If the number of base16 digits is uneven, remove one. This means that the result is now comprised of entire 8-bit bytes.













Parts:
- Greater entropy preservation
- Debiasing dice




Greater entropy preservation

In this project, I derived an algorithm, an implementation, and a recipe for converting dice rolls into entropy bytes. A large proportion (one third) of the original entropy is lost.

Note: Some values may be removed during a run so that the results are entire bytes, but at most this subtracts 3/4 of a byte (6 bits).

How might the discarded entropy be preserved and used?

I have read some material that proposed assigning a bit value of 1 to dice value "5" and a bit value of 0 to dice value "6". This would preserve some, but not all, of the entropy that is currently discarded.

Some more material suggested approaches that aggregate the unused entropy over several dice rolls, allowing a higher proportion of this entropy to be preserved. Note: These algorithms are necessarily more complex than the one used in this project, and would therefore require a higher degree of study and thought before they could be used in the field.




Debiasing dice


Dice cannot be perfectly fair i.e. perfectly random. Therefore, dice rolls as an entropy source will have a systematic pattern (e.g. more "5" values than "1" values). An adversary might be able to discover this pattern by examining other dice manufactured by the same company.

Initial improvements:
- Purchase casino-grade dice.
- Purchase dice from several different manufacturers.

I have read that Von Neumann thought of an algorithm for using a biased coin to produce perfectly fair outcomes.

Von Neumann's Algorithm For Debiasing A Coin:
1. Flip the coin twice and record the results.
2. If the results are the same, record a 0 value. If they are different, record a 1 value.

This algorithm puts the biased results into two groups in such a way that the groups have equal probabilities of occurrence, producing an unbiased entropy source. Notably, the actual degree of bias in the physical entropy source is unknown.

Does there exist a similar algorithm for dice rolls?














Secure cryptography requires secret values that are very difficult to guess.

An adversary could try to use all conceivable secret values in a cryptosystem to perform a particular operation, store the results, and see if any result matches a public cryptographic item. If a match is found, the adversary now knows the corresponding secret value. This is known as a "brute force attack". No matter what cryptosystem is used, this option is always available to an adversary.

For this reason, good cryptosystems have large possibility spaces for these secret values. The number of possible secret values should be so vast that to try all possible guesses would take many human lifetimes, even if an adversary can use enormous amounts of computational power.

In computing, "entropy" is used to mean "some information without predictable structure". It should be generated by a Random Number Generator (RNG), which is a process whose output is unpredictable. It must be in digital form (bit sequences) so that it can be used in digital operations.

An amount of entropy can be used as a secret value for cryptographic operations. Entropy is also useful in other contexts e.g. for choosing values for testing a function.

The human brain is bad at generating entropy. Given that a large part of its operation involves detecting patterns, this is unsurprising. Detecting patterns is the opposite of generating random values.

It is difficult and time-consuming to generate good entropy. If a tool is used to automate entropy generation, auditing such a tool is still difficult and time-consuming.

Example RNGs:
- A human flipping through a dictionary, choosing words at random (as randomly as he/she can), and writing them in a text file. When he/she has recorded 100 words, use a hash function (e.g. SHA256) to calculate the hash digest of the text file. The digest will be a bit sequence (entropy).
- A circuit board containing a) a heated element that generates thermal noise and b) a transducer that converts this thermal noise into digital output i.e. a bit sequence (entropy).

A Pseudorandom Number Generator (PRNG) is a type of algorithm that generates a sequence of values that appears to be random. It requires a seed value from which to begin generation. This seed value should be random. Thus, it still requires some entropy. It is really an "entropy-stretcher", making a little entropy appear to be a much larger amount of entropy. A PRNG can be useful for testing but should not be used for important cryptographic operations. An adversary could attempt to guess the seed value.

In the RSA cryptosystem, entropy is needed for private keys.

In the ECDSA cryptosystem, entropy is needed for private keys and for making signatures.

ECDSA digital signatures require a random K value, which must be used only once for one signature by a private key. For another signature, a second random K value must be used.

I don't know if it is dangerous to use the same random K value for two separate signatures made by two different private keys, but I regard doing so as risky until proven otherwise. A new K value should be generated for each ECDSA signature and securely erased afterwards.

I am going to use dice to generate some entropy.

An individual dice roll has 6 possible outcomes: 1, 2, 3, 4, 5, 6. A dice roll result will thus be in base6. The values should start at 0, so 1 should be subtracted from each result. The possibility space of the result is therefore [0,1,2,3,4,5]. If multiple dice are rolled, their results can be concatenated to form a numeric string in base6. Example: "4032151".

Numbers stored as bit sequences are in base2. In computing, bits are usually stored and manipulated in groups of 8 ("bytes"), so numbers stored as bytes are in base(2^8) == base256.

I will need to convert dice roll results from base6 to base256. An integer is always the same value - it doesn't matter in which base the integer is written.

Converting between bases can be done by converting the value of each digit in the old-base number into a number in the new base and summing the results. However, I prefer to avoid the need to perform BigNumber calculations.

Instead, I'd prefer to make a lookup table that maps a value space in base6 to a value space in base256. In order to preserve the quality of the entropy, all output values in the base256 value space must be equally possible.

Prime factorisation of 6 = 2 * 3

Prime factorisation of 256 = 2 ^ 8 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

Shared factors of 6 and 256: 2

Hm. Since 6 has a prime factor (3) that is not among the prime factors of 256, then no matter which powers 6 and 256 are raised to, the resulting value space will never be identical. No one-to-one mapping of the spaces 6^x and 256^y is possible.

However, some values in base6 can be discarded, converting the resulting value space to one formed from a base that shares all its prime factors with 256.

Suppose, out of the value space [0,1,2,3,4,5], the possible values 4 and 5 are always discarded. Then the result will always be in base4.

Prime factorisation of 4 = 2 * 2

Prime factorisation of 256 = 2 ^ 8 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

Shared factors of 4 and 256: [2,2]

All factors in 4 are present in 256.

256 = 4^4

A sequence of 4 base4 digits will map directly onto 1 base256 digit.

It looks to me as though the mapping I was looking for is only possible if one base (256) is a integer power of the other (4).

Writing base256 strings in ASCII characters will probably be cumbersome. Working in half-bytes (4 bits) will be easier - 4 bits describes the value space 2^4 = 4^2 = 16, and the values can be written in hex characters.

Hex characters:
0123456789abcdef

A sequence of 2 base4 digits will map directly onto 1 base16 digit.

Let's write the mapping ("lookup table"). There are 16 values.




So, the procedure:
- Gather some dice.
- Roll the dice.
- Record the results in a digit sequence.
- Proceed through the digit sequence in groups of 2, ignoring any results in the list [5,6].
- Subtract 1 from each value in order to move to a 0-based value domain.
- Use the lookup table above to convert 2-digit sequences from base4 to base16.
- Record the results in a new base16 digit sequence.
- The final base16 digit sequence must have a length divisible by 2 in order to be directly convertible into full bytes. Discard the extra base16 digit if one exists.

The last 5 steps can be automated with e.g. a Python script.

A single dice roll has a 2/6 = 1/3 probability of no entropy generation and a 4/6 = 2/3 probability of a base4 number.
4 = 2^2, so 1 base4 number (randomly generated) is 2 bits of entropy.

(2/3) * (2 bits) + (1/3) * (0 bits) = 4/3 bits of entropy are expected per dice roll. 4/3 ~= 1.33 bits per roll.

If I want to generate 1 byte (8 bits) of entropy, I would expect this to require 8 / 1.33 ~= 6.015 dice rolls, or 7 dice rolls when rounded up.

If I want to generate 32 bytes (256 bits) of entropy, I would expect this to require 256 / 1.33 ~= 192.481 dice rolls, or 193 dice rolls when rounded up.

I have 5 dice and a tray with raised edges in which to roll them. I'll roll them 200 / 5 = 40 times and record the results below. 200 is 193 rolls plus a slight margin. I'll also measure and record how much time this entropy generation takes.

12224
32455
43512
63552
22164

14133
41133
33313
32336
61214

24161
64534
43126
65454
13563

25466
26462
61651
25156
45236

33631
13365
22211
42146
15162

61523
56355
65313
43624
32555

33364
26155
52361
11545
66244

15162
64235
63343
21244
12313


Time taken: 6:10
I proceeded quickly but without hurrying.

6:10 = 6*60+10 = 310 seconds

200 dice rolls in 310 seconds. 310/200 ~= 1.5 seconds per dice roll. 1.33 bits of entropy per 1.5 seconds = 1.33 / 1.5 ~= 0.89 bits of entropy per second.


I'll write a Python script to convert these results into hex bytes.

Create a work directory "work".

Copy the dice roll results above into a text file and save this file in the work directory as "dice_rolls.txt". I'll leave the whitespace in and write some code to remove it.

Create new file in work directory:
convert_dice_rolls_to_hex_bytes.py



[development occurs here]







Run the script.







Excellent. 34 bytes of entropy generated.




That's the end of this project.