Implementing a trusted guess

• Technical description

  Problem statement

  • A server (a website) asks a client (a human user) to guess a value. This could be a number (say, between 1 and 10), or any other string.
  • The server already has a value chosen, which it (obviously) does not reveal to the client beforehand.
  • Thus, the goal of the client is to guess what value the server has chosen.
    For example, if the guess is correct, the client recieves an award. If it is not correct, no award

  The issue

  • The resolution -- did the client guess correctly -- should be quickly determined. That is, within seconds of the users submission of his guess.
  • Most importantly: all parties (the client and the server) should be confident that there was no cheating:
    The client can trust: that the server does not change its pre-chosen value after seeing the client's guess
    The server can trust: that the client can not easily determine a priori what the pre-chosen value is.

  A few sub optimal solutions

  Both of these are a bit different that then the problem statement -- they don't select a pre-chosen value. Instead, a value is chosen after the guess is made, and the server can not predict what this value will be.

  • A spinner or other random number generator on a web page (say, implemented using javascript or Flash) that selects a value.
    This is quick and easily implemented, but any sophisticated user will know that he is depending on the honesty of the server. And no amount of bells and whistles can hide this from a skeptical user.
  • Referring to a result (such as a number) that will be generated in the future by a trusted third party. For example, one of the numbers drawn in a future state-run lottery.
    This is trustworthy, but it requires a delay. Perhaps a several day delay. This could be problemmatic -- say, if it means a client has to come back to the site after a a several day wait.

  Proposed solution: use a hash function, a validation key, and a nonce.

  The solution has several steps:

  1. Before the client is asked for his guess, the server displays a validation key. This key remains visible throughout the choice process
  2. The value of the validation key was computed by applying the hash function to a concatenation of the actual value, and a nonce that the server selects.
  3. The client submits his guess
  4. The server returns the actual value, and the nonce. Thus: the client is shown the value of the nonce after he submits his guess.
  5. The user can apply the actual value, and the nonce, to his own copy of the hash function -- and ensure that the result is the same as the (pre-announced) validation key.
  6. This validates that the server did not change the actual value once seeing the guess.

  Requirements

  • The hash function should be cryptographically secure.
    That means it should return (for all practical purposes) a unique value regardless of the input string. More importantly, it must be very difficult to find any other input string that will return the same value.
    Such hash functions are common, and are used in many secure web applications. A well known example is the use of hash functions in block chains, which are the core technology for cryptocurrencies (such as Bitcoin).
    Examples of hash functions include: MD5, SHA1, and SHA-256.
    That is, it is easy to find code, or on-line apps, that implement these hash funcitons -- that make it very easy for a user to input a string and view the result.
  • The nonce should be easy for the client (who will see it after he makes his guess) to work with
    Definition: a nonce is simply a string. It is often a set of dozen random digits, but can be any length
    A nonce is used to randomize the results of applying a hash function to a given string.
    That is: different values of a nonce, when combined with a fixed value, will yield completely different values when fed into the hash function.
    Examples, using the MD5 hash function (for this example, I use the MD5 app at http://onlinemd5.com/).

    Value	nonce	input string	hash function (MD5) result
    dog	1bc321	dog_1bc321	F079C577BB105272BD3C6D5234B6E21D
    dog	cba3as	dog_cba3as	33D01F53555B7A416018CA14B1529A3C
    dog	cba3at	dog_cba3at	B08FCC4FE52C6E4B4681D711ADD34F38
    dog2	cba3at	dog2_cba3at	94A8118AFA535E815386A2492DAC1243

    Note that small changes in the nonce (such as changing cba3as to cba3at) completely change the hash function's result.
    Similarly, the same nonce with a slightly different value (using a nonce of cba3at with dog versus dog2) yields a completely different result.

    While playing with this app won't prove it, it is well known that is extremely difficult to find a string (or more than one string) that produces a pre-detemined value when used as the input to MD5 (or other hash functions). While not impossible, it would require immense amounts of processing.

  • It should be hard for a client to figure out the actual value from the validation key
    This depends on the complexity of the nonce.
    If the client can guess what values the nonce might take, and has sufficient computer resources -- he could combine all possible values of the nonce, with all possible values of the guess, and find the value that yields the validation key.
    For example, consider the table of examples above ...

    1. The nonces are 6 characters long.
    2. Lets assume that only digits and lower case letters are used -- that means 36 different values for each characters.
    3. If the guess can be a number between 1 and 10
    4. That means there 21,767,823,360 (10*(36^6)) unique combinations of the guess with a possible nonce
    5. Is that a lot? Or could a sophisticated client harness a powerful computer to crack this in a quick enough amount of time?
    6. Thus: there is a tradeoff between complexity of the nonce (its length and its randomness) and the difficulty of guessing the actual value.
       The longer and more random, the more secure. But the longer and more random, the harder for the client to work with (if/when he choses to double check the value of the validation key).
    7. Perhaps 10 randomly generated characters, using digits and upper and lower case letters, is enough: if the value can be a number between 1 and 10, that yields 8,392,993,658,683,402,000 possible combinations!
  • Extra consideration: very suspicious clients
    If clients are exceedingly suspicious, they may worry that the server has spent a lot of time to generate a validation key that is the same for several different input strings. That the server has found two different nonces that, when combined with two different guesses, yield the same validation key.

    For example (and this is fake, since finding such nonces is really hard)...

    Value	nonce	input string	function result
    5	nonce1	5_nonce1	7AD5CA72B24078644D3C0EC479E43EE7
    6	magicNonce	6_magicNonce	7AD5CA72B24078644D3C0EC479E43EE7

    If the client thinks this is feasible, then the client will worry that the server will return the nonce that proves the client make an incorrect guess (even if his guess was correct). For example:

    the value was 5, the client's guess is 5

    the server returns a nonce of magicNonce

    and the server claims sorry, the value was 6 -- here's the nonce (magicNonce) that proves it!

    A solution:

    Before the client submits his guess, he supplies a clientNonce. The client should be encouraged to enter a totally random value, since he won't have to remember it for long. For example by randomly hitting keys.

    The server combines the clientNonce with its own nonce (and the actual value), and generates a validation key

    This validation key is returned to the client.

    The client makes his guess

    The server returns the actual value, and its own nonce

    The client can test for validity

    For example ...

    Value	clientNonce	nonce	input string	function result
    dog	JumpUp	1bc321	dog_jumpUp_1bc321	539E035CCD4243481F05C8C269001E0A
    dog	JumpUp2	1bc321	dog_jumpUp2_1bc321	11F4F53FB8B4BFADF25C455A0832A15B

    The key point: although a wicked smart server could (possibly) find a magicNonce, it is well nigh impossible to quickly (within a few minutes) find a magicNonce that works when it is also combined with a clientNonce -- which the server does not know beforehand!

  Demo of trusted guess algorithim

  This demo uses hard coded values -- so is completely insecure. When you are ready -- you can try a real demo.

  ---

  Hello bigBoy!

  Thank you for making choices for lots of alternatives! Now, its time to determine which (if any) of these alternatives will be used.
  To do this, we ask you choose a number between 1 and 10.

  • If your guess matches a number selected by our server -- a value that is chosen before you submit your guess -- we will then randomly select an alternative. We will use your choice in this alternative, and compute your earnings. These earnings will be added to your $50.00 participation payment.
  • If your guess does not match this number -- no alternatives are used. You will recieve just your $50.00 participation payment.

  Can you trust us? We use a cryptographically secure method -- using the validation key displayed below --to guarantee that the value chosen by the server is not changed. This validation key can be easily checked using readily available tools. See below for further details (after you make your guess)!

  Please select a value between 1 and 10:	And then
  Is your guess correct?	shown after you submit your guess!
  The validation key is:	263DCF1EB8B73C5263675CF90B424DD3
  The actual value is:	shown after you submit your guess!
  The nonce is:	shown after you submit your guess!
  How to validate the actual value ...	Before you submit your guess, the server selects an actual value. It then uses the MD5 hash function to create a validation key that depends on this actual value. You can recreate this validation key, using any MD5 function or app (for example, at http://onlinemd5.com/). First: create a validation string by combining the actual value, an underscore, and the nonce. This yields: 5_myNonce Second: use this validation string as an input to an MD5 function The result should match the validation key! If it doesn't match? Please make sure your validation string is exactly as specified -- there should not be any spaces before or after! If it still doesn't match-- that means we might of cheated.