How to create and use nonces

I am running a website, and there is a scoring system that gives you points for the number of times you play a game.

It uses hashing to prove the integrity of http request for scoring, so users cannot change anything. However, as I feared might happen, someone figured out that they didn't need to change it; instead they just needed to get a high score, and then duplicate the http request, headers, and all the rest.

Previously I'd been prohibited from protecting against this attack because it was considered unlikely. However, now that it has happened, I may. The http request originates from a flash game, and then is validated by php, and php enters it into the database.

I'm pretty sure nonces will solve the issue, but I'm not exactly sure how to implement them. What is a common, and secure way of setting up a nonce system?

Solution

It's actually quite easy to do... There are some libraries out there to do it for you:

Or if you want to write your own, it's pretty simple. Using the WikiPedia page as a jumping off point, In pseudo-code:

On the server side, you need two client callable functions

getNonce() {
    $id = Identify Request //(either by username, session, or something)
    $nonce = hash('sha512', makeRandomString());
    storeNonce($id, $nonce);
    return $nonce to client;
}

verifyNonce($data, $cnonce, $hash) {
    $id = Identify Request
    $nonce = getNonce($id);  // Fetch the nonce from the last request
    removeNonce($id, $nonce); //Remove the nonce from being used again!
    $testHash = hash('sha512',$nonce . $cnonce . $data);
    return $testHash == $hash;
}

And on the client side:

sendData($data) {
    $nonce = getNonceFromServer();
    $cnonce = hash('sha512', makeRandomString());
    $hash = hash('sha512', $nonce . $cnonce . $data);
    $args = array('data' => $data, 'cnonce' => $cnonce, 'hash' => $hash);
    sendDataToClient($args);
}

The function makeRandomString really just needs to return a random number or string. The better the randomness, the better the security... Also note that since it's fed right into a hash function, the implementation details don't matter from request to request. The client's version and the server's version don't need to match. In fact, the only bit that needs to match 100% is the hash function used in hash('sha512', $nonce . $cnonce . $data);... Here's an example of a reasonably secure makeRandomString function...

function makeRandomString($bits = 256) {
    $bytes = ceil($bits / 8);
    $return = '';
    for ($i = 0; $i < $bytes; $i++) {
        $return .= chr(mt_rand(0, 255));
    }
    return $return;
}