Using Multiplayer Games to Create Secure Communication

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

Content

We all need Entropy/Randomness (e.g. conferences are a good example), but we are forcing Entropy/Randomness to be an endangered component of our Environment -
there is a need for new sources of Entropy/Randomness
The traditional 'top-down' model of Internet security has become questionable, top-level certificates are on sale in Internet Dark Markets for 150..250 USD
Many new platforms are based on local security: blockchain, Antara (blockchain), BYOK etc
A growing number of people are finding Entropy/Randomness from computer/video games, when playing these games they are creating new Entropy/Randomness
Randomness created by players of on-line video games can be used for creating local secure communication
(not depending on higher-level security authorities)

Growing need for Randomness

Humans have a built-in need to explore, learn

Humans need to systemize, order/organize, flatten
- to reduce entropy in our environment

If the cement industry were a country, it would be the third largest carbon dioxide emitter in the world after China and US (The Guardian)

For many people the main source of entropy have become videogames

Entropy

Entropy is a measure of structuredness
Structre enables encoding
Entropy is a measure of possibilities to encode information
Or equivalently - the (maximal) reduction in uncertainty removed when we reseive the message

Randomness is a non-compressable, i.e. maximized entropy

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

Randomness in Multiplayer Video Games

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

"In multiplayer games is created randomness" is not a provable statement -
its truth follows from our experience - we play games 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)

In (economics-based) game theory the mechanism of rewarding is not detailed - rewards are based on unpredictable markets

In videogames rewards should be quick and deterministic - videogame is a deterministic algorithm (finite-state machine), which to player's inputs decides their rewards

Game Automaton

Game is a quadruplet
$G = < P, M, R, A >$
$P$ - set of players, $| P | = n \geq 2$
$M$ - set of legal inputs (moves)
$R$ - set of rewards (payoffs), $| M | = | R |$
$A$ - game automaton (finite-state machine), which in every state implements (deterministic, quick) algorithm for mapping
$\bar{ρ} : M^{n} \to R^{n}$

The mapping $\bar{ρ}$ is usually split into submappings over subsets of players (e.g. players who are in the same room etc), in the following are considered pairs of players, i.e.
$ρ : (m_{}^{i}, m^{j}) \to ({\tilde{r}}^{i}, {\tilde{r}}^{j})$ , thus
$r_{t}^{i} = \sum_{1 \leq i \leq n} ρ (m_{t}^{i}, m_{t}^{j})$

In server-based multiplayer games players do not see actions of other players - they see only results of these actions

Players see the result of their move
$M^{n}$
do not know arguments $M^{n}$ of the game mapping $\bar{ρ} : M^{n} \to R^{n}$ -

In order to compete, win, they try to learn/quess moves of other players, i.e. the vector $M^{n}$

They try to quess/calculate (some) reverse function
${\bar{ρ}}^{'} : R^{n} \to M^{n}$
such that
$\bar{ρ} {\bar{ρ}}^{'} \bar{ρ} \approx 1_{M}$

But game designers try to make learning the game (reversing the payoff function) difficult

In a (large) class of non-learnable games (i.e. rock-paper-scissors) the reverse function is not uniquely defined and there are several alternatives with the same expectation:

Thus the best strategy is total randomness

Both the player's moves and payoff-s can be considered as symbols, thus the game is a (possibly partial) mapping
$A^{*} \to A^{*}$
of strings from some alphabet
$A, | A | \geq 2$

The problem of reversing such a (partial) mapping has connections with some deep problems in complexity theory, e.g. in
J. C. Birget, Inverse monoids associated with the complexity class NP, Semigroup Forum (2019) 98:369–397
it is shown, that a semigroup of partial deterministic polynomial-time functions on a set of strings from some alphabet (at least binary) is not inverse (i.e. all elements have an inverse) iff the one-way functions exist (i.e. inverse/reverse functions are not any more polynomial-time deterministic)

Non-learnable games

Game payoff/reward (for two players) 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

In zero-sum games $r_{i j}^{2} = - r_{i j}^{1}$

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 (all players) is total randomness

Group-like games

The class of non-learnable games is too wide - it includes e.g. all constant games, where all elements of the payoff matrix are equal (all moves produce the same payoff) .

Players want that their moves have distinct effects (and there are no excessive moves), thus the subclass of group-like games is defined by conditions:

In every situation (selection of moves of all players) every player has a move for every possible payoff (if moves of all other players are fixed)
for every pair of moves there is a situation where they create different payoffs (there are no excessive moves)

Most games (e.g. 'rock-paper-scissors', 'odd-even', all shooting games etc) have these properties

It is easy to see, that in a payoff matrix of a group-like game all rows and columns should include all possible payoffs (condition 1)

Thus the payoff matrix for a group-like game could be constructed from any vector ${{\tilde{r}}_{0}, {\tilde{r}}_{1}, ..., {\tilde{r}}_{m - 1}}$ including all payoff values using any substitution $π$ without sub-cycles on the set of playoffs:

It is easy to check, that conditions for group-like games are satisfyed

In a wider class of extended group-like games payoff-s in every row and column could be different (but the game still satisfies conditions 1., 2.); a matrix for these games could be created by rectangular manipulation of a group-like game matrix:

With the operation of rectangular manipulation every two (extended) group-like games with isomorpic automatons could be transformed to each other, thus all group-like games with the same number of actions (and isomorhic automatons) are nearly isomorphic (a bit wider notation than isomorphism); the near-isomorphism does not depend on number of players (in economics-based game theory could be compared only games with the same number of players).

The best strategy for group-like (which all are also non-learnable) games is total randomness, thus every player of such a game produces a random sequence of moves; together these sequences create a new source of good randomness

To improve the quality of randomness of players move sequences could be included also a computer-generated player

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.

Using Randomness created in Multiplayer Games to Create Secure Local Communication

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)

Summary

There is a Growing Need for new sources of Randomness
A growing number of people are finding Entropy/Randomness in computer/video games, when playing these games they are creating new Entropy/Randomness
Randomness created by players of on-line video games can be used for creating local secure communication
(not depending on higher-level security authorities)

Using Multiplayer Games to Create Secure Communication

Content

Growing need for Randomness

Humans have a built-in need to explore, learn

Entropy

We all depend on Digital Data

Growing need for Randomness

Randomness in Multiplayer Video Games

Randomness in Multiplayer Games

What is a Multiplayer Game ?

Game Automaton

Non-learnable games

Group-like games

The quality of produced randomness

Using Randomness created in Multiplayer Games to Create Secure Local Communication

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

Summary

Thank You!