Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm using the sha256 algorithm to generate a number in one of my programming projects. A sha256 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!

share|improve this question
    
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. –  fgrieu May 28 at 16:03
    
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. –  Stephen Touset May 28 at 18:57

1 Answer 1

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.

share|improve this answer
1  
"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}$. –  otus May 28 at 17:48
    
@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. –  user2441938 May 28 at 17:57
    
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. –  jbms May 28 at 18:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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