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 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!

share|improve this question
1  
The output of a hash function is at best as random as the input. No hash function can "generate" a random number. –  Stephen Touset Feb 11 at 7:30
1  
The archetypal reduction from a 512-bit value $h$ (assumed uniformly random) to a value in set $\{0…n\}$ for small $n$ is simply: $r=h\bmod(n+1)$. Compute this as the exact remainder of the Euclidean division of $h$ by $n+1$. Whatever small bias there is can not be detected. If you want theoretically zero bias, reject $h$ less than $2^{512}\bmod(n+1)$, which should never happen if $h$ is the output of SHA-512, for any practical definition of never. Beware that one who can manipulate the input of the hash that produces $h$ can bias $r$. This is a comment, for it does not answer the question. –  fgrieu Feb 11 at 8:10
2  
Hello and welcome to Crypto.SE. Keep in mind that although posting properly-formatted code is appreciated, code of this scope is usually discouraged in this site. That's because a) for the most part it's the code to a raffle system, not a crypto-specific task and b) mathematical notation is much preferred over pseudocode. As an aside peerbet.org has done the same thing using the Bitcoin blockchain as their entropy source. I hope this helps. –  rath Feb 11 at 9:44
    
@user2441938: It is nice, and common, that an ounce of math can replace a pound of code. –  fgrieu Feb 11 at 16:59
1  
Cross posted to stackoverflow.com/questions/21695256/… where I've given a more PHP/programming related answer. Please do not cross-post. –  owlstead Feb 12 at 14:55
add comment

1 Answer

up vote 4 down vote accepted

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.
share|improve this answer
    
Thanks for the answer! Just verifying that I understand your suggestion: I'd have a secret string which is combined with user input like their names and then hashed to determine the winner. Throughout the raffle a hashed version of the secret string would be public which could be verified once the secret string is released after the drawing? –  user2441938 Feb 11 at 14:44
    
Yes. Using a hash as commitment is also possible (it has to be a collision resistant hash of course). –  tylo Feb 11 at 15:51
1  
A different attack scenario is that the OP works with one or more people who are added to the list near the end, when he has some idea of who else might join. $\:$ I think the best way to defend against would be to use scrypt (and have already committed to the [the initial secret and the salt] and revealed the other scrypt parameters). $\;\;\;$ –  Ricky Demer Feb 11 at 19:56
    
Good answer! I'd also like to refer the author to crypto.stackexchange.com/q/767/351. –  D.W. Mar 21 at 7:25
    
The list of participants' names might not have enough entropy to prevent you from cheating even without help from others. In particular, if you can guess who might sign up for the raffle (and in what order), you could compile a bunch of likely participant lists in advance, and, after testing a large number of possible secret inputs against those lists, select the one that has the best chance of giving you a favorable outcome if the actual participant list happens to match one of your guesses. –  Ilmari Karonen Mar 23 at 18:43
add comment

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.