Maybe, some of you remember having to pick one person during playing as kids. That person would than have to catch the others for example. The methods to pick given person often would either depend on a "random" number one of the kids picked or on other factors like the shoe size.
Inspiried by some children playing, I started thinking about a secure decentralized method to create a consent about a pseudorandom number which everyone can influence but not predict or be manipulated to give an attacker an advantage e.g. force the method to always pick one person.
The very first idea I came up with was that every party shares a random number. Now, everyone can combine the numbers by appending, calculate a hash and then choose the person who would have to catch the others based on the hash.
To do so we define the function $f(x)$ which can reduce an input of an arbitrary length to a number between 0 and n, for example $f(x) = x\ mod\ n$.
There is a very obvious attack to this scheme: The last person to share it's random number can manipulate force the output to any output he want's by choosing random numbers for $x$ until $f(H(r_0\ ||\ r_1\ ||\ ...\ ||\ r_{n-2}\ ||\ x))$ equals the desired output.
The only way I can come up with to prevent such an attack is preventing one can be in hold of every other random number but binding everyone to their random number. This can be archieved by following protocol:
- Every party chooses a random number $r$ and shares $H(r)$ thus binding itself to $r$ since any modification to $r$ can be detected unless $H$ has easily findable collisions.
- After every party has shared it's $H(r)$, the $r$'s are exchanged. While doing so, the $r$'s are validated to match with the hashes.
- The output is $f(H(r_0\ ||\ r_1\ ||\ ...\ ||\ r_{n-1}))$.
This protocol has no extra security if the random numbers are small enough to be bruteforced and / or have been precomputed. Given $r$ is in a range of $2^n$ an attacker can run through every $i$ in $[0\ ...\ 2^8]$ and store $H(i)$. The attacker then can lookup these hashes during step one and then choose an arbitrary $r$ which matches his needs. That's why I suggest that the number should be at least 128 bit big.
Have I missed something? Are there other ways for an attacker to set the outcome of the algorithm to a greater extend than just "adding it's entropy"?
