Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks

posted by Craig Gidney on November 12, 2013

In this post: how to beat map hacks, without a server to hide the information on, using cryptography.

Map Hacks and Publicly Private Information

Map hacks are a common problem in real time strategy games.

Most RTS’s use a networking model called lockstepping. When lockstepping, the state of each player’s game is not synchronized so much as kept synchronized. Actions that players perform are queued, instead of being applied immediately, to give time to tell all players to apply that action at the same game time. This allows each player’s simulation to advance in exactly the same way; in lockstep. It would have been impossible for Age of Empires to keep thousands of units synchronized if they hadn’t used lock-stepping.

The downside of lock-stepping, besides the fact that it does a poor job hiding perception of lag, is that it makes the game vulnerable to map hacks. Lock-stepping requires every player’s game to know where every player’s units are. Your game can’t advance its simulation of your enemy’s units if it doesn’t know where they are! Because all the information is present, just not shown, making a maphack can be as easy as nop-ing over the code checking if a unit is visible (and there’s not much game developers can do about it beyond obfuscation).

Another reason the game needs to know about each enemy units is to figure out when units are crossing paths. This is difficult, because each player doesn’t have enough information to solve it on their own. Contrast that with (most) tabletop games, where players never need information they don’t have in order to know what moves they’re allowed to make.

For example, imagine a Magic the Gathering card with the following attribute: Discard if another player has this card in their hand; otherwise do not reveal you have this card in your hand. Imagine you draw the card. You’re faced with a dilemma: you have to ask your opponents if they have the card, otherwise you might break the rules by failing to discard it. But you can’t ask your opponents if they have the card, because if they don’t then asking about it reveals you have it and breaks the rules!

One way to solve these sorts of problems, where a result depends on two private inputs, is to introduce a trusted third party. A judge looks at everyone’s hands, and tells you when you must discard. A server looks at the units of every player, and tells them about units they can see.

But… what if you don’t want to need a judge around in order to play your game? Can it still be done? It turns out that it is possible, using secure multi-party computation. That’s what we’ll be experimenting with today.

Secure Multi Party Computation

I’ve previously explained how to do basic secure multi-party computation (SMPC) in the physical world by using locked suggestion boxes. The locked suggestion boxes allow you to perform an oblivious transfer, and oblivious transfer can be used as the basis for any SMPC protocol. So if we want to do some SMPC-ing in software, we just need a way to do oblivious transfer.

Unfortunately, there aren’t any established software libraries that implement oblivious transfer and implementing it ourselves would be… non-trivial. Really, really non-trivial. Dozens-of-people-checking-each-other’s-work-then-waiting-years-to-see-if-dedicated-cryptographic-analysis-fails-to-find-any-attacks-but-attacks-are-found-so-you-do-it-again levels of non-trivial.

Fortunately, there’s another technique that can be used as a basis for SMPC: secret sharing. Secret sharing lets you split a secret value into multiple shares, and recover the secret value if enough shares are present. Using secret sharing will force us to have at least three players present, but there are also upsides.

Secret sharing is simple enough that implementing it requires only a basic understanding of modular arithmetic and polynomials. Also, because secret sharing has information theoretic security, instead of security based on computational hardness, there’s no risk of a clever algorithm being discovered and ruining our day (though there are still ways to be wrong).

How Everybody Computes

So we’re going to use secret sharing to do secure multi-party computation. What does that mean exactly?

Well, you can think of SMPC as simulating a virtual machine. Players do specific things in order to write private inputs to the machine, read private outputs from the machine, and perform operations within the machine. Let’s start with how to transfer a private value known only to one of the players into the simulated machine.

Input

When a player wants to input a value into the simulated machine, they use secret sharing to split the value into a share for each player. We’ll be using Shamir’s Secret Sharing Scheme, which uses polynomials over a finite field. We need at least four x-coordinates in the finite field we’re doing arithmetic in (one for the secret and one for each of the three shares), so we’ll be doing arithmetic modulo 5 (the smallest prime not less than 4).

To split a secret value into shares, such that only two of the shares are needed to reconstruct the point, we will create a line. The line’s offset will be the secret value, and the line’s slope will be a random value. The line’s y-coordinate at x=0 is the secret, and the y-coordinates at x=1 , x=2 , and x=3 are the shares for players 1, 2, and 3 respectively.

All in all, inputting a private value looks like this:

Let’s go through an example. Suppose the private value is v=2 . First, we pick a random slope . Suppose it happens to be s=4 . That means the equation for our line is $y(x) = v+s \cdot x = 2 + 4x \pmod{5}$ . To make shares we just evaluate at each x-coordinate. Player 1 gets the share $y(1) = 2+4 = 6 = 1 \pmod{5}$ , player 2 gets $y(2) = 2+8 = 10 = 0 \pmod{5}$ , and player 3 gets $y(3) = 2+12 = 14 = 4 \pmod{5}$ .

Notice that, by changing the slope, we could have made player 2’s share be any of the five possible values in our finite field (just 0, 1, 2, 3 and 4). The reverse is true as well: holding player 2’s share fixed, we find that each possible slope corresponds to a different secret value. This is fundamentally why each player knows nothing about what the secret input is: the slope is hiding it.

Output

To extract a value from the simulated machine, player’s must combine their shares. Every player sends their share to the player, or players, that are supposed to get the output. The receiving players do polynomial interpolation on the points to recover the line (or parabola, since there’s three points) and evaluate it at x=0 to recover the secret output value.

Because we know we’re working with the integers modulo 5, and that there are always 3 players, this whole process actually simplifies quite a bit. We just multiply each share by a constant and sum them up:

Reveal Private Value

Let’s continue our example from before. Suppose the shares owned by each player happen to be the ones we generated in the input example: a_1=1 , a_2=0 , and a_3=4 . We could figure out that these points are on a line with slope of -1 = 4 and work from there… but for three players working modulo five, interpolating then evaluating at zero always simplifies down to this expression: 3 a_1 + 2 a_2 + 1 a_3 . Computing that gives $v = 3 \cdot 1 + 2 \cdot 0 + 1 \cdot 4 = 7 = 2 \pmod{5}$ . As required, that’s the private input from the first example.

Addition

Addition of values in the simulated machine is dead simple: each player just adds their share of the value. The value encoded by the resulting shares is the sum of the two inputs. There’s not even any communication, as shown in this diagram:

Addition dataflow

Just to show that this works, let’s do an addition all the way from input to output.

Suppose player 1 has the private value v_1 = 1 and player 2 has the private value v_2 = 3 . They input them into the simulated machine, with the random slope hiding v_1 ending up as s_1=1 and the random slope hiding v_2 ending up as s_2=2 .

The degree-1 polynomial (a.k.a. a line) encoding v_1 is $p_1(x) = s_1 x + v_1 = x + 1 \pmod{5}$ , meaning the players’ respective share are p_1(1)=2 , p_1(2)=3 , and p_1(3)=4 . The polynomial for v_2 is $p_2(x) = s_2 x + v_2 = 2x + 3 \pmod{5}$ , giving respective shares of p_2(1)=0 , p_2(2)=2 , and p_2(3)=4 .

Once each player has been given their share, they add them together. The resulting shares are points on the polynomial p_3 that encodes the result. We have the points p_3(1) = 2+0 = 2 , p_3(2) = 3+2 = 0 , and p_3(3) = 4+4 = 3 . A player with all three points can figure out that the polynomial’s equation is $p_3(x) = 4+3x \pmod{5}$ , which encodes the value v_3 = p_3(0) = 4 , which is in fact the sum of and .

Multiplication

Multiplication of private values is more complicated than addition. You start in the same way, multiplying each player’s share of the inputs together, but this causes a problem. Multiplying polynomials together creates a polynomial of higher degree: the resulting polynomial is quadratic instead of linear. If we didn’t have three shares we wouldn’t even be able to interpolate the result and, if we want to be able to do more multiplications without adding more players, we need to reduce that quadratic polynomial back to a linear one before continuing. (Also the extra degree of freedom would leak bits of private state.)

The way degree reduction is done is kind of amazing in a how-the-heck-does-that-work way: each player splits their share as if they were creating a private value, broadcasts the shares-of-shares to the corresponding players, then recombines the shares-of-shares that they received as if to reveal a private value. The resulting values are shares of the product. I don’t remember what paper I got this from, but there’s all kinds with the necessary information if you google around (like this thesis).

Here’s a diagram showing the process:

This one definitely needs an example from input to output.

Suppose we have private values encoding v_1 = 3 and v_2 = 4 , and that the slope hiding v_1 is s_1=2 and the slope hiding v_2 is s_2=1 . We want to compute $v_3=v_1 \cdot v_2$ , using only the shares.

The polynomial for v_1 is $p_1(x) = 2x + 3 \pmod{5}$ , meaning the players’ respective share are p_1(1)=0 , p_1(2)=2 , and p_1(3)=4 . The polynomial for v_2 is $p_2(x) = x + 4 \pmod{5}$ , meaning the players’ respective share are p_2(1)=0 , p_2(2)=1 , and p_2(3)=2 .

By multiplying the shares each player has together, we get the points $q(1) = 0 \cdot 0 = 0$ , $q(2) = 2 \cdot 1 = 2$ , $q(3) = 4 \cdot 2 = 3$ . The polynomial running through these points is q(x) = 2x^2 + x + 2 , which has the correct value at x=0 : $q(0) = 3 \cdot 4 = 2 \pmod{5}$ . (We could have avoided interpolation by just using the simplified expression: $3 \cdot 0 + 2 \cdot 2 + 1 \cdot 3 = 4+3 = 2$ .) The players never see this polynomial, because they do degree reduction.

Degree reduction starts by splitting each share as if to input it into the machine. Suppose player 1 uses the slope to hide q(1) = 0 , player 2 uses the slope to hide q(2) = 2 , and player 3 uses slope to hide q(3) = 3 . So player 1’s share splits into 1,2,3 , player 2’s share splits into 4,1,3 , and player 3’s share splits into 1,4,2 . They send the corresponding shares to each player. Player 1 ends up with 1,4,1 , player 2 ends up with 2,1,4 , and player 3 ends up with 3,3,2 .

Degree reduction finishes with each player privately recombining the shares-of-shares they received as if to read an output, with player 1 getting $p_3(1) = 3 \cdot 1 + 2 \cdot 4 + 1 \cdot 1 = 3+3+1 = 2$ , player 2 getting $p_3(2) = 3 \cdot 2 + 2 \cdot 1 + 1 \cdot 4 = 6+2+4 = 2$ , and player 3 getting $p_3(3) = 3 \cdot 3 + 2 \cdot 3 + 1 \cdot 2 = 9+6+6 = 2$ .

The polynomial p_3 interpolates as p_3(x) = 2 , which has degree less-than-2 like we wanted and still encodes the correct answer ( $p_3(0) = 2 = 3 \cdot 4 \pmod{5}$ ).

Implementation

I used the SMPC explained above to implement a “game” with fog of war computed peer-to-peer, without a server, in Javascript. You can view the source in the below JSFiddle, or play the “game” (I keep using quotes because all you can do is move around) by clicking the ‘Result’ button at the top:

(In case JSFiddle is down, as it was intermittently while I was writing this post, you can view the code on github.)

(I count at least five things in the above code that betray the fact that it’s essentially the first time I’ve written javascript that’s longer than a dozen lines.)

The code implements a stack-based SMPC virtual machine. There are operations to hide+push, pop+reveal, add, and multiply.

To determine who can see what, the code uses those operations to rebuild the primitive we couldn’t start with (oblivious transfer). For each location on the map, and for each player taking their turn acting as the one receiving the result, the information at that location is obliviously transfer to the player.

The oblivious transfer is done by having the two sending players push 1 if they have a unit at that location, or 0 otherwise. That pushes two values onto the stack, which are then added. Since units can’t occupy the same location, the result pushed onto the stack is always either 0 or 1. Then the querying player pushes 0 onto the stack if they can’t see the location in question spot, or 1 if they can. Then a multiplication is performed, and the result is revealed to the querying player. When they can’t see, the result is always 0. When they can see, the result is 1 when there’s a unit present.

All three players are simulated locally, but could be communicating over the network with essentially no architectural changes. They don’t touch each others private information or anything like that.

Impracticalities

If you’ve been considering how what I’ve been describing would work in more practical scenarios, you’ve probably realized that the answer is: not very well. I’ll quickly go over the issues:

Trusting players not to lie. We’re not using a verifiable secret sharing scheme and we’re not checking (after the game has finished) that players didn’t simply lie about what they could see. Dealing with adversarial players makes things a lot more complicated, but in practice you must.
Trusting players not to collude. If two of the three players work together, they can reveal the private information in the “secure” computation. This is fine for an example, but in reality players gang up on each other all the time. Again, dealing with this makes things a lot more complicated, but in practice you must.
Huge bandwidth requirements. The required network bandwidth is proportional to the size of the map! Players do an oblivious transfer for every location a unit might be in. This is worse even compared to synchronizing every unit, which was already significantly worse compared to just sending actions.
High sensitivity to network hiccups. RTS games usually allow a player to fail to check in a few times before pausing to wait for them, but we need all three players for our computations to advance. If a player’s connection hiccups for even half a second, and the game is scheduling actions at a leisurely rate of 4Hz, the game will have to pause and wait for a moment. This basically means you’d need to be on a LAN to play the game, or else it would need to be redesigned into a turn based game.
Lots of round trips. A sequence of multiplications requires one network round trip per multiplication. The time it takes to compute anything non-trivial is going to be measured in seconds.
High implementation costs. Working with partial information makes the game simulation and resynchronization code a lot harder to write and get right.

I think those points more than justify this being an impractical experiment.

Summary

Secure multi-party computation can do all the things, except be practical.

Discuss on Reddit

My Twitter: @CraigGidney

2 Responses to “Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks”

Terry A Davis says:

November 12, 2013 at 1:05 pm

The NIST number is updated once every 60 seconds. You think I check for bad ones and skip them? How about I pull the 9:05 one.

CraigGidney says:

November 12, 2013 at 1:31 pm

I have no idea what you are talking about.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks