1
$\begingroup$

I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao.

each user generates n sha3 hashes recursively of a random seed : e.g. H[0] = sha3(sha3(seed)) H[1] = sha3(sha3(H[0])) ... H[n] = sha3(sha3(H[n-1]))

During the nth round, we xor the H[nth] value of each user to be used as a random value for that round:random_result

My Question: What is the best strategy to map the 256 bit random_result to a 6 sided dice without completely botching the entropy?

$\endgroup$
  • 3
    $\begingroup$ if the seed has full entropy and is greater than or equal to the sha-3 size, then random_result also has full entropy. Then you can use random_result mod 6 . This is not a totally exact uniform distribution but the error is negligible. $\endgroup$ – user27950 Jul 6 '18 at 5:47
  • $\begingroup$ @Cryptostase yes seed is full entropy 32bytes, Is mod DICE_FACE the best solution to ensure entropy transfers over near uniformly? Is there a variable bit hash sponge function I can run through possibly? $\endgroup$ – user462003 Jul 6 '18 at 9:40
  • $\begingroup$ ah clearly that effects the security property a great deal: crypto.stackexchange.com/questions/15080/… $\endgroup$ – user462003 Jul 6 '18 at 9:44
  • 1
    $\begingroup$ @Cryptostase If you were to enumerate the error, I'm sure that would be an acceptable answer. It's very very negligible and would be a real PITA to disprove empirically... $\endgroup$ – Paul Uszak Jul 6 '18 at 11:16
  • $\begingroup$ @PaulUszak "enumerate the error"? I do not think that word means what you think it means. $\endgroup$ – forest Jul 7 '18 at 1:03
3
$\begingroup$

Method 1 - Big Integer Math

Convert the 256 bit random_result to an unsigned big-integer. Divide by 6 and take the remainder. Your die roll result is the remainder plus one.

$6$ does not evenly divide $2^{256}$. It divides about $1.93\times10^{74}$ times with an exact remainder of $4$. That means values $1$-$4$ are over represented but by a negligible amount, since they're only represented once more than $5$ and $6$ over a gigantic range.

The bias towards low die rolls is much much much much less than $2^{-128}$, modern cryptography's slightly arbitrary threshold for the maximum detectable amount of bias in probability.

Method 2 - "Small" Integer Math

Let $M = 6 \times floor(2^{32} \div 6) = 4294967292$, ie. the largest multiple of 6 that fits into a 32-bit unsigned integer.

Split the 256 bits into 8 32-bit unsigned numbers. Find the first value one of those values less than $M$ and return one plus the remainder of its value divided by 6. This returns value has a value a range of values $[1, 6]$.

The reason for using values in the range $[0,M-1]$ instead of $[0, 2^{32}-1]$ is because the latter is not evenly divided by 6. Random numbers in the former range lead to a perfectly uniform distribution.

The probability of one 32-bit value being rejected is $p = (2^{32} - M) \div 2^{32} \approx 9.32 \times 10^{-10}$. All 8 are rejected with $p^8 \approx 5.66 \times 10^{-73}$ probability which is very unlikely. The exact probabilities happen to be $p = 2^{-30}$ and $p^{8} = 2^{240}$. Again, this is less than $2^{-128}$, so you shouldn't expect it to happen.

If it does fail 8 times you can derive more 256 bit numbers by hashing random_result concatenated with a counter. Or you can just use the final 32 bit value if the first 7 fail. The probability of that happening is small and the resulting bias is smaller.

The reason why I specify 32 bit numbers is for ease of implementation and for optimization reasons. There isn't any cryptographic relevance. 64-bit numbers and 64-bit division works as well, but it might not be available in some scripting languages and 32-bit division may be faster than 64 bit division on 32-bit and 64-bit architectures.

You could use 3 bit chunks. Then you could eliminate division entirely because 6 only divides 8 once. Rejecting an individual chunk happens with $1/4$ chance. Rejecting 85 times is less than $6.7 \times 10^{-52}$ or $2^{-170}$.

Method 3 - Seed a PRNG

This would be a really easy if CS-PRNGs were implemented in standard language libraries or popular add-on libraries with a similar API to those for non-secure PRNGs. Using standard PRNGs doesn't work for every application either because of statistical artifacts, small state space, predictability, or lack of a good seeding algorithm.

Edit: Avoid this method. I don't have a single example I can cite. There are too many ways it could go wrong.

 

No method has significant bias and therefore the entropy of the die roll has very close to $\log_2 6$ bits of entropy. (Assuming reasonably high entropy seed, like 128 bits of entropy. It doesn't need to have 256 bits of entropy.)

I don't think you want an answer based on entropy. I don't know what you mean by "botching the entropy" and I assume you don't know either.

For each method you can estimate entropy of the result by treating the entropy of the hash output about equal to $min(256, \text{seed-entropy})$ and calculating the probability of each outcome 1 through 6 by computing how many hash outputs map to that die-roll-value.

Since we already know the bias to be incredibly small we know that the die-roll result is about uniform. Since it is about uniform we know it has about the maximum entropy you can get out of 6 element discrete uniform distribution, $\log_2 6$.

$\endgroup$
  • $\begingroup$ Different Java runtimes may behave different ways of handling SecureRandom and it may not be deterministic at all. The exact PRNG hasn't been specified, bad implementations exist. This is NOT a secure option in Java, not even if you keep to the standard runtime. $\endgroup$ – Maarten Bodewes Jul 7 '18 at 0:32
  • $\begingroup$ @MaartenBodewes I could have sworn there was backwards compatibility unless you requested a non-default algorithm. Research time. Got any references or examples to save me some time? $\endgroup$ – Future Security Jul 7 '18 at 1:09
  • $\begingroup$ Well you could look into the SecureRandom debacle for getRawKey. Or the changes in the algorithm implementation for different versions of Android. $\endgroup$ – Maarten Bodewes Jul 7 '18 at 1:12
  • $\begingroup$ Using a stream cipher, XOF or KBKDF would work, but you'd still have to convert that to a number and - for the stream cipher - a seed into a key. You can easily steal one of the algorithm implementations that you've specified from open source libs or runtimes though. $\endgroup$ – Maarten Bodewes Jul 7 '18 at 13:08
-1
$\begingroup$

This post has nothing to do with cryptography. Using of SHA does not automatically mean the question is related to cryptography. If one is developing a game that uses random generator based on a Geiger counter and an A-bomb, this doesn't mean the post is related to WMD or physics.

The most important thing in the OP is that each player gets equal chances. This has nothing to do with how (cryptographically) good the number generator is, how good the numbers are distributed, etc. Here is why.

A) Two players use the same device (smartphone, tablet, laptop, PC). The both have equal chances to win, no matter how good the number generator is. This is obvious. If not, I'll answer your questions below.

B) Two players use different devices (smartphone, tablet, laptop, PC). As Maarten Bodewes mentioned, a specific device and even specific OS version can be important. Numbers on one device may have better chance to win against the numbers on another device. Solution is easy: Make the applications on both devices communicate with each other. The applications should swap the generated numbers for each 2nd round: one round app uses its own randomly generated number, the next round it uses the number generated by the peer device, next round - own number, next round - again the peer number. Again, no matter how (cryptographically) good random generators on each device are, the players have equal chances.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jul 9 '18 at 20:33
  • $\begingroup$ Skipping the superfluous fluff, I read a bit about equal chances of players... but nothing seems to answer the question (quote): What is the best strategy to map the 256 bit random_result to a 6 sided dice without completely botching the entropy?Maybe you could edit your answer accordingly so that it actually fits the question? Of course, you don't have to; I'm just thinking out loud. $\endgroup$ – e-sushi Jul 9 '18 at 20:38
  • $\begingroup$ @e-sushi: Please look the problem the OP wants to solve: To create random dice roles. You don't need cryptography for this. The fact of using PRNG or SHA does not mean this problem relates to the crypto domain. If you want to generate name of temp file and use PRNG for this, does your case relate to cryptography? $\endgroup$ – mentallurg Jul 9 '18 at 21:02
  • $\begingroup$ That's not the conclusion I draw when reading the question, and actually the quoted part should have been an according heads-up. Yet, everyone is free to interpret things as he/she wants and I'm definitely not going to start an extended discussion in the comments about dice rolls or the need for cryptographic security in certain scenarios (eg online casino dice games). Oh well... can't say I didn't try to help you form a better answer. ∎ $\endgroup$ – e-sushi Jul 10 '18 at 22:23
  • $\begingroup$ Regarding A: The both have equal chances to win, no matter how good the number generator is So if it alternates between outputting 1, 7 than the distribution/bias of the numbers is irrelevant? One player would always roll a 1 and the other would always roll a 7 - this is clearly not fair or equal. Regarding B: what's to stop the second player from outputting highly biased outcomes every time they send number to the opposing device? The players can't trust the other players device as a black box if they have any stake in the game that is being played. $\endgroup$ – Ella Rose Jul 10 '18 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.