Is this approach to generating a "random" number from a sha512 hash effective?

Question

I'm looking to run a small raffle but i'd like people to be able to verify that the number chosen was fair. I know some sites use a "Provably Fair" system to achieve this where user input is combined with a secret string which is then hashed to determine the winner. Once the secret string is released, participants can verify using the hash that the correct winner was chosen.

From a sha512 hash a "random" number from 0-n (n varies in length but is 255 at most) should be generated to determine the winner. This is what I thought up:

Creating an array of n length and inserting pairs of characters that can appear in a sha hash. If n was 255 for example, the array would have: array('aa','ab','ac'...'fd','fe','ff'...'97','98','99'). Basically it'd have every combination of two characters using a-f and 0-9.

It'd then look at the first two characters of the hash and use array_search to see if that pair exists in the array. If it does, it's index is the number picked, otherwise it moves over to the next pair of characters and searches those. In the rare scenario it doesn't find a match it'll continually hash itself and use the new hash returned to continue the search.

$values = array('a','b','c','d','e','f','0','1','2','3','4','5','6','7','8','9');
    $numbers = array();
$ENTRANTS = 100;
    $rand =  md5(uniqid(rand(), true));
$hash = hash('sha512',$rand);

$values_index = 0;
    $current = $values[$values_index];
$options = 0;
    while ($options < $ENTRANTS){
    	$remaining = ($ENTRANTS - $options > 15)? 16: $ENTRANTS-$options;
    	for ($n=0; $n < $remaining ;$n++){
    		array_push($numbers, $current . $values[$n]);
    		$options++;
    }

    $values_index++;
    	$current = $values[$values_index];
}

$outcomes = array();
    $winning = null;
$i = 0;

while (empty($winning)){

    while ($i+1 < 64 && empty($winning)){
        $combo = $hash[$i] . $hash[$i+1];
    		$number = array_search($combo,$numbers);
        if ($number !== false){
    			$winning = $number;
        }

        $i++;
    }

    if (!empty($winning)){
    		echo "<pre>" . print_r($numbers,true) . "</pre>";
    		echo $hash . "<br>" . $winning;
    	}
    	else {
    		echo "re-hashing" . "<br>";
    		$hash = hash("sha512",$hash);
    		$i = 0;
    }
}

This is working when tested but I'm unsure if it is effectively generating a random number. Are the characters in a sha512 hash for the most part evenly and unpredictably distributed? If you can see any issues with this or have any advice on how it could be improved please let me know!

Answer 1

In general, your way to select one of the entries seems unnecessary complicated. As fgrieu pointed out, you should be fine by reducing the hash value modulo the number of participants (But with $n$ people, you calculate $h$ mod $n$, and assign the numbers from $0$ to $n-1$).

An important question though, is how you determine the input to your hash function. If you seed it with something random, people can't really be sure you didn't cheat (by trying out different seeds).

In order to provide confidence, you might want to do something like this:

• Initially you provide a commitment to some secret value of your choice. After everything is done, you can unveil the commitment and show the secret value.
• Then you run your raffle. People can sign down their names, and you keep the list public. This way they can make sure that their name is in the raffle. The list index also gives the "lucky number" to each participant.
• Afterwards you first reveal the secret value by publishing the decommitment. Then you create a long bitstring: concatenate all the names in the list and the secret value. Use this bitstring as input to a hash function (SHA512 does the trick, but with an final result of at most $2^8$ possibilities, any cryptographic hash function should work). Calculate the number modulo the number of participants. If you want results from $1$ to $n$ instead of $0$ to $n-1$, then just add 1 (or interpret the $0$ as $n$).

Why can no one cheat in this scenario?

• You can't cheat, because your input to the function is fixed before the raffle starts (at least if your commitment scheme is binding; btw. you can also just use something like "I encrypt my name with AES. The commitment is the ciphertext and the secret value is the used key")
• The other people can't cheat either, because without knowledge of your input they should not be able to change the outcome in their favor on purpose.
• Since the growing list of names changes with each additional entry the hash result, no one could predict the outcome before the last person entered his name.
• The worst attack scenario I can think of, is that you work together with the last person added to the list. This person could try out different variations of his name and calculate the result with knowledge of the secret. But right now I can' think of anything to solve this problem.