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, they just needed to get a high score, and duplicate the http request, headers and all.

Previously I'd been prohibited from protecting against this attack because it was considered unlikely. However, now that it has happened, I can. 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 1:

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

PHP Nonce Library
OpenID Nonce Library

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;
}

Solution 2:

Nonces are a can of worms.

No, really, one of the motivations for several CAESAR entries was to design an authenticated encryption scheme, preferably based on a stream cipher, that is resistant to nonce reuse. (Reusing a nonce with AES-CTR, for example, destroys the confidentiality of your message to the degree a first year programming student could decrypt it.)

There are three main schools of thought with nonces:

In symmetric-key cryptography: Use an increasing counter, while taking care to never reuse it. (This also means using a separate counter for the sender and receiver.) This requires stateful programming (i.e. storing the nonce somewhere so each request doesn't start at 1).
Stateful random nonces. Generating a random nonce and then remembering it to validate later. This is the strategy used to defeat CSRF attacks, which sounds closer to what is being asked for here.
Large stateless random nonces. Given a secure random number generator, you can almost guarantee to never repeat a nonce twice in your lifetime. This is the strategy used by NaCl for encryption.

So with that in mind, the main questions to ask are:

Which of the above schools of thought are most relevant to the problem you are trying to solve?
How are you generating the nonce?
How are you validating the nonce?

Generating a Nonce

The answer to question 2 for any random nonce is to use a CSPRNG. For PHP projects, this means one of:

random_bytes() for PHP 7+ projects
paragonie/random_compat, a PHP 5 polyfill for random_bytes()
ircmaxell/RandomLib, which is a swiss army knife of randomness utilities that most projects that deal with randomness (e.g. fir password resets) should consider using instead of rolling their own

These two are morally equivalent:

$factory = new RandomLib\Factory;
$generator = $factory->getMediumStrengthGenerator();
$_SESSION['nonce'] [] = $generator->generate(32);

and

$_SESSION['nonce'] []= random_bytes(32);

Validating a Nonce

Stateful

Stateful nonces are easy and recommended:

$found = array_search($nonce, $_SESSION['nonces']);
if (!$found) {
    throw new Exception("Nonce not found! Handle this or the app crashes");
}
// Yay, now delete it.
unset($_SESSION['nonce'][$found]);

Feel free to substitute the array_search() with a database or memcached lookup, etc.

Stateless (here be dragons)

This is a hard problem to solve: You need some way to prevent replay attacks, but your server has total amnesia after each HTTP request.

The only sane solution would be to authenticate an expiration date/time to minimize the usefulness of replay attacks. For example:

// Generating a message bearing a nonce
$nonce = random_bytes(32);
$expires = new DateTime('now')
    ->add(new DateInterval('PT01H'));
$message = json_encode([
    'nonce' => base64_encode($nonce),
    'expires' => $expires->format('Y-m-d\TH:i:s')
]);
$publishThis = base64_encode(
    hash_hmac('sha256', $message, $authenticationKey, true) . $message
);

// Validating a message and retrieving the nonce
$decoded = base64_decode($input);
if ($decoded === false) {
    throw new Exception("Encoding error");
}
$mac = mb_substr($decoded, 0, 32, '8bit'); // stored
$message = mb_substr($decoded, 32, null, '8bit');
$calc = hash_hmac('sha256', $message, $authenticationKey, true); // calcuated
if (!hash_equals($calc, $mac)) {
    throw new Exception("Invalid MAC");
}
$message = json_decode($message);
$currTime = new DateTime('NOW');
$expireTime = new DateTime($message->expires);
if ($currTime > $expireTime) {
    throw new Exception("Expired token");
}
$nonce = $message->nonce; // Valid (for one hour)

A careful observer will note that this is basically a non-standards-compliant variant of JSON Web Tokens.

Solution 3:

One option (which I mentioned in comment) is recording gameplay and replay it in secure environment.

The other thing is to randomly, or at some specified times, record some seemingly innocent data, which later can be used to validate it on server (like suddenly live goes from 1% to 100%, or score from 1 to 1000 which indicate cheat). With enough data it might just not be feasible for cheater to try to fake it. And then of course implement heavy banning :).

Solution 4:

This very simple nonce changes every 1000 seconds (16 minutes) and can be used for avoiding XSS where you are posting data to and from the same application. (For example if you are in a single page application where you are posting data via javascript. Note that you must have access to the same seed and nonce generator from the post and the receiving side)

function makeNonce($seed,$i=0){
    $timestamp = time();
    $q=-3; 
    //The epoch time stamp is truncated by $q chars, 
    //making the algorthim to change evry 1000 seconds
    //using q=-4; will give 10000 seconds= 2 hours 46 minutes usable time

    $TimeReduced=substr($timestamp,0,$q)-$i; 

    //the $seed is a constant string added to the string before hashing.    
    $string=$seed.$TimeReduced;
    $hash=hash('sha1', $string, false);
    return  $hash;
}

But by checking for the previous nonce, the user will only be bothered if he waited more than 16.6 minutes in worst case and 33 minutes in best case. Setting $q=-4 will give the user at least 2.7 hours

function checkNonce($nonce,$seed){
//Note that the previous nonce is also checked giving  between 
// useful interval $t: 1*$qInterval < $t < 2* $qInterval where qInterval is the time deterimined by $q: 
//$q=-2: 100 seconds, $q=-3 1000 seconds, $q=-4 10000 seconds, etc.
    if($nonce==$this->makeNonce($seed,0)||$nonce==$this->makeNonce($seed,1))     {
         //handle data here
         return true;
     } else {
         //reject nonce code   
         return false;
     }
}

The $seed, could be the any function call or user name, etc. used in the process.