Games and Randomness

Jaak Henno, TalTech, Estonia
Hannu Jaakkola, Tampere University of Technology, Pori
Jukka Mäkelä, University of Lapland, Rovaniemi, Finland

We all depend on Digital Data

But our data is exposed in numerous breaches ...

Something for everyone ...

The main method of defence is encryption

For encryption are needed Sequences of Random Numbers

Growing need for Randomness

Randomness is vital for computer security - in order to generate cryptographic keys are needed random numbers

The research company Gartner predicts that by 2019 already 80 percent of web traffic will be encrypted

The e-mail encryption market is expected to have 24% annual growth through 2020

Growing need for Randomness

After Snowden and with movement to clouds is rapidly increasing 'Bring Your Own Key (BYOK)' practices (enterprizes create and manage their own cryptographic keys) - a source of pain already to 59% of respondents to reacent 2018 survey by the Ponemon Institute
Randomness is essential in many methods of prediction and simulation - a random sample of just 400 people from 300 million of the U.S. population can accurately estimate election result with 95 percent certainty
Randomness is widely used in Games and very important to ensure secure communication, both client-server and clients-messaging.
In games are needed lightweight sources of randomness with on-site generation of keys (e.g. for every new player)

Randomness

Computer is a deterministic device and can not generate random numbers

(if it can, then it is severely broken)

True randomness is in computers created from physical processes (e.g. from fluctuations of proccessor temperature, processor load, keypress-timings etc)
All operating systems collect this randomness and use it in order to create random numbers

Pseudo-randomness

The physical and outside sources of randomness are limited and it is impossible to create/calculate good randomness just from one source - several independent sources are needed - for instance, computers and humans.
If the generation process should be repeatable (e.g. in another computer), a pseudo-random generators are used - large loops from where a number is extracted using a key.

Pseudo-random generators

For instance, the popular C-language library glibc produces in a pseudorandom order a cycle with length

2^{\land} 31

using the recurrence formula

x_{i + 1} = (1103515245 * x_{i} + 12345) \mod 2^{\land} 31

But in order to use this source of randomness should be installed the C-language compiler and user should have considerable computer skills
Such a heavy-weight sources of randomness are in games nearly useless

Randomness assessment

Kolmogorov: a sequence is random if it can't be compressed i.e. expressed by a function/program which has (essentially) shorter description than the sequence itself

Randomness tests for real sources use a series of simple fixed tests, e.g the Diehard suite contains (at least) 13 tests: Birthday spacings, Overlapping permutations, Ranks of matrices, Monkey tests, Count the 1/0 -s, Parking lot test, Minimum distance test, Random spheres test, The squeeze test, Overlapping sums test, Runs test, The craps test (a game).

but "... tests fail even with 10M inputs generated by Dieharder's own generator..." and nobody can quarantee, that this set of tests is sufficient ...

Collecting Randomness

All Operating systems (OS) collect randomness.
In Linux it is stored in two files: dev/random, dev/urandom
Linux is the main OS which is used in network servers and its creators (Thorvalds) are very concerned about quality of randomness used.
However, visual assessment of the forst 7 KB of the file dev/random (Ubuntu 16.4) revealed a strange irregularity:

The starge peak in centre is the code for € ...

Our measures of entropy
are not perfect

The famous Shannon's formula does not consider order/placement...

According to Shannon's formula

H = \sum p_{k} \log_{2} (p_{k})

(if only pixel's level and not their x-y coordinates are used) the entropy of both images is exactly the same - 8 bits

Image from
https://stats.stackexchange.com/questions/235270/entropy-of-an-image

Randomness in Multiplayer Games

When playing games and competing, trying to win, humans behave non-predictably, create random moves.

Non-predictability, randomness is the main source of game enjoyment; without randomness we would not play (this is not a game !) - but we are playing more and more...

- and this randomness could be collected and used for generating encryption keys .

What is a Multiplayer Game ?

In a (multiplayer/any) game (also in economy) players perform actions trying to get an advantage, to win

GAME resolves these actions and gives players rewards (the utility/payoff fuction)

Game is a finite-state machine, which to player's inputs decides their payoff's

Game Automaton

Every player has a finite number of available actions

Game has a finite number of possible payoffs

The source of payoffs is limited - when one player gets more (wins), another gets less (looses)
play is a competition with hidden/random payoffs !

When playing games and competing, trying to win, humans behave non-predictably, create random moves.

Non-predictability, randomness is the main source of game enjoyment; without randomness we would not play (this is not a game !) - but we are playing more and more...

- and this randomness could be collected and used for generating encryption keys .

Collecting Randomness from Multiplayer Games

In multiplayer games competing players all try to behave non-predictably, i.e. randomly

If results from all player's actions are equally probable, then the best strategy for players is use totally random moves, i.e. the sequence of player's moves is a random sequence (the game is non-learnable).

There are many games, where any pattern (non-randomness) in player's moves could be used by other players and will reduce player's result, thus the best result requires total randomness of player's moves

Examples of such games are
"Odd-Even"
Rock-Paper-Scissors
Rock-paper-scissors - m-ary - a generalization of the 'Rock-paper-scissors' game to m > 3

Collecting Randomness from Multiplayer Games

The game "Odd-Even" is a simple zero-sum quessing game: two players (call them 'Odd' and 'Even') should simultaneously select either '0' or '1'; player 'Odd' wins, if the sum of selected numbers is odd (1), player 'Even' winns, if the sum is even (0 or 2) - both events have equal probability.
There are many versions of such a game, e.g. this is a symmetric version (zero-sum) version of the game )Man vs Machine (this game is not symmetric, computer has advantage - can skip its move)

The 'Odd-Even' game

('Matching Pennies')

If the strategy of the player 'even' for selecting '0' or '1' is
$p_{e} = [p_{e 0}, 1 - p_{e 0}]$
and the strategy of the player 'odd' is
$p_{o} = [p_{o 0}, 1 - p_{o 0}]$
then the possibility for 'Even' to win is
$P_{e W} = p_{e 0} p_{o 0} + (1 - p_{e 0}) (1 - p_{o 0}) = 1 - p_{e 0} - p_{o 0} + 2 p_{e 0} p_{o 0}$

The optimal strategy (the 'Nash Equilibrium') is the extremum of this function, i.e follows from equation
$\frac{d P_{e W}}{d p_{e 0}} = p_{o 0} - (1 - p_{o 0}) - (1 - p_{o 0}) + p_{o 0} = 0$

Best strategy in the 'Odd-Even' game

Solving this simple equation shows, that the best strategy for player 'Even' is equal probabilities of selecting '0' or '1', i.e.
$p_{e 0} = p_{e 1} = 1 / 2$
From symmetry it follows that the strategy
$p_{o} = [p_{e 0}, 1 - p_{o 0}]$ of player 'Odd' should also be
$p_{o 0} = p_{o 1} = 1 / 2$

Winning strategy in the 'Odd-even' game

The Nash equilibrium of the surface (game polytope): $P_{e W} = p_{e 0} p_{o 0} + (1 - p_{e 0}) (1 - p_{o 0})$ which describes winning possibilities of the player 'even' (or 'odd') is the saddle point in the center of the play area:
..

Both players should select '0' or '1' with equal probability, but so, that the opponent could not quess their selection

Both players should be maximally random !

Players should learn the opponent's startegy!

Learning from interactions

J. Henno. Information and Interaction.
Information Modelling and Knowledge Bases XXVIII
IOS Press 2017, pp 426-449>

Suppose two automata are interacting and trying to quess each other's algorithm ('pwn' other)

Their interaction vocabulary

| V | = v

contains

v

symbols and for storing the interaction they have correspondingly

m

and

m_{1}

memory cells.
Each cell can store one symbol from the interaction vocabulary

V

, thus e.g. the automaton

M

has alltogether

v^{m}

possible states -

v^{m}

ways to fill its memory.
Thus after

v^{m}

steps it 'goes into loop', it runs out of memory and starts repeating itself.
If the other automatom has enough memeory, i.e.

m_{1} > v^{m}

then when it discovers that opponent is looping - it knows all its following moves (opponent is deterministic !).

The Algorithm

In the game this strategy can be used for revealing opponent's (non)randomness
a random sequence can not have (long) repeated subsequences)
otherwise it can be comprssed using e.g. the Zipfel-Lem Algorithm

In the game computer stores all moves as a sequence of pairs (as pairs from left to right, first the opponent's move).

When on move, it searches this sequence backwards with its preffix for longest repeated subsequence ('is the opponent already in loop?')
- this is the main idea of the Zipfel-Lem compression algorithm

The Algorithm

For instance, if the sequence of played moves is (the game vocabulary contains all numbers)
$1, 7, 2, 1, 2, 3, 4, 2, 1, 2, 4, 3, 1, 2, 3, 5, 7, 5, 9, 8, 9, 1, 2, 3, 4, 7, 4, 3, 1, 2, 3, 5$
then the algorithm returns sequence (the longest repeating suffix)
$4, 3, 1, 2, 3, 5$

Now computer selects move, which beats opponents earlier move in this situation: "7"
- The Zipfel-Lem algorithm can not use this subsequence for compression and has to enter a new item to it's dictionary

Use of the algorithm

This algorithm is very successful against human players
- in games with >50 moves algorithm (always) wins

(tested by authors and with participants of the Game Programming course of the first author in Tallinn University of Technology)

To succeed, human players usually get some source of random numbers and use this - this essentially improves their result
Playing against already established source of randomness allows to assess the quality of this source of randomness - how often/quickly computer wins or loses?

Searching for loops

The main idea of the algorithm is to check wether the opponent is already in loop, i.e. repeating moves
Speed of appearing loops and their length is another test for quality of randomness source

Below are results of one test - length $λ$ of repeated suffix and number $n$ of such loops appearing in 10 tests in Firefox, every test with 10000 moves (JavaScript random() against computer)

$λ$	2	3	4	5	6	7	8	9	10	11	12
$n$	982	932	756	416	153	46	11	5	3	1	0

Differences of Browsers

The program used quite many repetitions to improve/learn against well-programmed pseudo-randomness sources
Below are results of 10 cumulative tests: 'player1 = window.crypto.getRandomValues(), player2 = computer', each with 10000 moves executed in Firefox and Google Chrome
(under Windows 7, 64 bit).

Better player 1						Better player 2
Firefox			Chrome			Firefox			Chrome
0	1	1	1	0	0	1	0	0	0	1	1
1	1	1	1	1	0	1	1	1	1	1	2
2	2	2	2	1	1	1	1	1	1	2	3
2	2	2	3	2	1	2	2	2	1	2	3
3	2	2	3	2	1	2	3	3	2	3	4
4	3	3	3	2	1	2	3	3	3	4	5
5	4	4	3	3	1	2	3	3	4	4	6
6	5	5	3	3	1	2	3	3	3	5	5
6	5	5	3	3	1	3	4	4	6	6	8
7	6	6	3	4	2	3	4	4	7	6	8

Non-learnable games

Game payoff/reward can be expressed with game matrix (as in economics-based game theory): in rows are moves (inputs) for player1, in columns for player2 and the (i,j)-cell indicates player's payoffs

r_{i j}^{1}, r_{i j}^{2}

for move

i

from player1, move

j

from player2

The game is non-learnable, if the sums of all rows and columns are equal - the expectation of payoff for any move is the same:

\sum_{i} r_{i 0}^{1} = \sum_{i} r_{i 1}^{1} = ... = \sum_{i} r_{i m - 1}^{1} = \sum_{i} r_{0 i}^{1} = \sum_{i} r_{1 i}^{1} = ... = \sum_{i} r_{m - 1 i}^{1} =

\sum_{i} r_{i 0}^{2} = \sum_{i} r_{i 1}^{2} = ... = \sum_{i} r_{i m - 1}^{2} = \sum_{i} r_{0 i}^{2} = \sum_{i} r_{1 i}^{2} = ... = \sum_{i} r_{m - 1 i}^{2} = V

In such a game the average (expected) payoff of any move is $V / m$

Even the TensorFlow can not learn such games ...

The best strategy for a player is total randomness

The 'Odd-Even' (and its 3D interpretation) allow to create random binary sequences.

Generalizations of the well-known rock-paper-scissors game allow to create random sequences of m-ary integers {0,1,...,m-1} for any m > 2

Winner (with payoff

{\bar{p}}_{1} - {\bar{p}}_{2}

) is the player, who is (in clockwise direction) closer to opponent, i.e. player

p_{1}

is winner, if

({\bar{p}}_{1} − {\bar{p}}_{2} + m) % m \leq m / 2

\bar{p}

- input from the player

p

, % - the mod operation

The quality of produced randomness

The randomness test program "Ent" shows, that the string produced by interactions in the 'Odd-Even' game is nearly uncompressable, i.e. good.

Use of randomness created in games for secure communication

Multiplayer games (e.g. the ones considered before) could be used for generating encryption keys for symmetric cryptosystems (e.g. TEA) in chat/communication systems for multiuser network systems - replace the public-key round of key exchange with game
When a player wants to start chat, server considers player's results (or proposes to play a short game - one of the games discussed above). If the results of players do not differ more than 5% (both played honestly, no bots), the sequence of moves of players is used to create an e.g. AES key (128 bit)
If players played honestly (both wanted to win) they behave differently, their moves would be different, thus the sequence of moves random and could be used to create a key for symmetric encryption system.

Security surfaces of multiplayer games

A game/chat system will have two security surfaces:

Game server is responsible for game security:
- maintains players usernames/passwords;
- creates secure communication for player's moves(nobody should be able to intercept)
- follows player's behavior - players with extreme results (exceptionally good or exceptionally bad) should/could be dispelled (bots ?)

Security surfaces of multiplayer games

A chat system in a multiplayer game is a separate process (to unlade server's task) :

Inside chat system are used only players usernames and there are no information about game's progress

Key generation for symmetric encryption:

A secure key for symmetric encryption is created combining two pieces of information:
- The sequence of moves from all players (this knows only server)
from this sequence are removed player's moves (this makes this sequence useless even when intercepted)
- player inserts into this sequence his own moves - this will be the new (strong) key for the chat
In order not to reveal moves of other players server may applie to the sequence of all moves a substitution

Key generation for symmetric encryption - the move sequences combination method:

When player asks for chat to start server sends the sequence of players moves; from this sequence are removed player's own moves; the sequence could be encrypted (weak one-time key for symmetric encryption) using the sequence of players moves as the key
- player inserts into this sequence his own moves - this will be the new (strong) key for the chat

The move sequences combination method:

Server has the sequence of moves made by all (both) players:

p_{11} p_{12} p_{21} p_{22} p_{31} p_{32} ...

p_{i 1}

- the i-th move of player 1

p_{i 2}

- the i-th move of player 2

Players have only their own moves, e.g. player1 has sequence
$p_{11} p_{21} p_{31} ...$ $p_{i 1}$

When a player asks for key server sends the sequence of moves, where player's own moves are removed;
the sequence could encrypted as all game moves
or(weak one-time key for symmetric encryption) using the sequence of players moves as the key
- player inserts into this sequence his own moves - this will be the new (strong) key for the chat

Key generation procedure - preconditions

All the following messages are secured/encrypted with the means used in game for sending player's moves and rewards.

Players store their moves in the order they made them.

When player enters the game (logs in) he receives together with his gameplay client also (a link to) a cryptographic library (for symmetric encryption), e.g. some member from the W3C list or (when using node.js) Node.js Crypto module (easy tutorial)

Key generation procedure - steps

1. Player1 sends to server: chat(playerList);
here playerList is a list of players or the word all - player wants to start global chat

2. Server checks wheather there is already enough entropy (at least e.g. 12 moves have been made) and Player1 does not look like a bot - has comparable rewards

3.Server sends invitations to start chat to all members of playerList (with time limit for answer)

4. After time limit server removes from playerList all players who did not answer the invitation

Key generation procedure - steps (cont)

5. If the remainig list contains some players, server adds to list also the player1 and sends to all members the global list of moves from which the moves of player himself are removed (replaced by '*') - with time limit for answer

6. Players replace the '*' in received list with their own moves(in the correct order)

7. To check, players send to server (encrypted with the new key) message "Encryption OK"

8. Server removes from playerList the players, whose messages were not decipherable

9. If there still remain players (>1), server sends them all list of addresses of other members, thus they can start a chat forum.

The move sequences combination method - properties

This method allows to create keys for different subsets of players - for any two of them or for the whole population

The randomness needed for key is constantly generated by player's themselves, thus they can easity generate a new key e.g. sending a message:
"From now on use moves from time moments t₀ to t₁"

To increase randomness of the sequence of moves it could filtered, e.g. used only these moves which produced (or did not produce) a fixed result

In order to speed up the key generation multi-moves may be used, e.g. (in 'Odd-Even') both players select e.g. a 4-bit string (byte) - in this regime generation of 128-bit key sequence requires only 32 moves (and with 16 bit strings only 16)

Games and Randomness

We all depend on Digital Data

Growing need for Randomness

Growing need for Randomness

Randomness

Pseudo-randomness

Pseudo-random generators

Randomness assessment

Collecting Randomness

Our measures of entropy are not perfect

Randomness in Multiplayer Games

What is a Multiplayer Game ?

Game Automaton

Collecting Randomness from Multiplayer Games

Collecting Randomness from Multiplayer Games

The 'Odd-Even' game

Best strategy in the 'Odd-Even' game

Winning strategy in the 'Odd-even' game

Learning from interactions

The Algorithm

The Algorithm

Use of the algorithm

Searching for loops

Differences of Browsers

Non-learnable games

The quality of produced randomness

Use of randomness created in games for secure communication

Security surfaces of multiplayer games

Security surfaces of multiplayer games

Key generation for symmetric encryption:

Key generation for symmetric encryption - the move sequences combination method:

The move sequences combination method:

Key generation procedure - preconditions

Key generation procedure - steps

Key generation procedure - steps (cont)

The move sequences combination method - properties

Thank You!

Our measures of entropy
are not perfect