3
$\begingroup$

I'm using the SHA-256 algorithm to generate a number in one of my programming projects. A SHA-256 hash is calculated from three strings: one the user can edit, one the user can view but not edit and one the user cannot view or see until it is changed to a new string.

From the hash, the first two characters are looked at to determine the number. Each of the 256 combinations of two letters/numbers that can appear in a sha256 hash are arbitrarily assigned a value with the following pattern. aa=1, ab=2, ac=3...fd=84, fe=85, ff=86...97=254, 98=255, 99=256: In the project a number from 1-100 is needed so all of the combinations of two characters are looked at from left to right until a number in that range is found.

After testing this by generating thousands of hashes from seemingly random inputs (with php I made the input md5(uniqid(rand()))) multiple times, the average number from 1-100 was around 51.

Any idea what is causing the number to be weighted more towards combinations from "dc" to "0d" (51-100) compared to "aa" to "da" (1-49)? Is this a flawed way to determine a random number even if the input is random? What if the player has control over one of the strings added to the input like described in the first paragraph?

Note: I don't study cryptography so explanations without intense cryptography jargon would be the most useful!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ When generating random uniformly distributed integers in range $[1\dots100]$ (your goal, and what I think your technique yields in a convoluted way), the expected mean is $50.5$, not $50$. Beside, some deviation of the actual mean from the expected mean is expected. This is basic statistics, and off-topic. $\text{ }$ Note: the SHA-256 algorithm yields 256 bits, often represented as 32 octets (1 octet = 8 bits), more rarely as 64 "letters/numbers" each coding a quartet in hexadecimal (1 quartet = 4 bits). PHP uses the later form unless PHP $raw_output = true is given. $\endgroup$
    – fgrieu ♦
    Commented May 28, 2014 at 16:03
  • 1
    $\begingroup$ FYI, the letter/number pairs are just a base-16 representation of bytes (values 0-255). $\mathrm{00}_h = 0_d$, $\mathrm{10}_h = 16_d$, $\mathrm{f1}_h = 241_d$. There is no need to come up with your own (extremely odd) mapping between these bases. $\endgroup$
    – Stephen Touset
    Commented May 28, 2014 at 18:57
  • $\begingroup$ @StephenTouset If you think about it, it's not that weird. The OP just placed the letters before numbers in base16. i.e. abcdef0123456789 $\endgroup$
    – Ron
    Commented Sep 30, 2015 at 22:48

1 Answer 1

Reset to default
4
$\begingroup$

It may be that you did not actually observe an unexpected deviation from the desired mean of 50.5 for a uniform distribution over integers in [1,100]. However, you say that all combinations of two characters are considered, which I assume to mean that first you look at characters 0 and 1, then characters 1 and 2, and so on. This means that when you look at characters 1 and 2, since you've already rejected characters 0 and 1, the distribution of character 1 is necessarily biased (there are 156 combinations that lead to rejection, and 16 does not divide this evenly).

To obtain an unbiased sample, you should not reuse any characters. If you used your same scheme but didn't reuse any characters, you would most of the time generate an unbiased sample but with probability $(156/256)^{32}$ (about 1 in 8 million) you would run out of characters before accepting. To reduce your chance of running out of characters, you can accept numbers 1 to 200 (but then divide by 2, rounding up). This reduces your chance of running out of characters to $(56/256)^{32}$ (about 7.56e-22). You can improve on this by considering blocks of 8 characters (32-bits) or 16 characters (64-bits) at a time.

You can also simplify your method by using the usual hexidecimal convention and relying on existing hex string to integer conversion, or better yet, avoid the conversion completely since the SHA256 hash is always computed as a sequence of bytes, and then converted to a hex string.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ "You can improve on this by considering blocks of 8 characters (32-bits) or 16 characters (64-bits) at a time." – With a 64-bit number you can just take it modulo 100. The bias is only $2^{-60}$. $\endgroup$
    – otus
    Commented May 28, 2014 at 17:48
  • $\begingroup$ @jbms How much of an effect does the bias have on the outcome would you say? And to make it unbiased I would look at numbers 0-1, then 2-3, 4-5, etc? If it runs out of characters it takes a hash of the existing hash to generate new ones. Anyway thanks for the response. $\endgroup$
    – user2441938
    Commented May 28, 2014 at 17:57
  • $\begingroup$ With your initial scheme the bias is not that small: the lower 4 digits hex digits have a probability of $9/256$ while the higher hex digits have a probability of $10/256$. In any case there is no reason to do it in a biased fashion. $\endgroup$
    – jbms
    Commented May 28, 2014 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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