How to create and use nonces

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:

1. 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).
2. 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.
3. 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:

1. Which of the above schools of thought are most relevant to the problem you are trying to solve?
2. How are you generating the nonce?
3. 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.

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

1. PHP Nonce Library
2. 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;
}

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 :).