13
\$\begingroup\$

I have been working on a P2P architecture for secure gaming and I have divided the problem into five sub-problems:

  • Unlawful modification of sent game state
  • Accurately drop cheaters
  • Agreeing on a game state
  • Avoiding "look ahead" cheat
  • Hiding sensitive information from opponents

The first four I have pretty much all solved but it is the last one which I am having trouble with.

Before I go into details I just want to ask if there's anything I've missed in my list of making a "cheat proof" p2p network. I am not interested in cheats such as using aimbots, I am only interested in making the p2p network as secure as a centralized server.

So in my effort so far on hiding sensitive information I've focused on the position of players in a game where the position of your opponent should not always be known. The problem then becomes how to determine if you should send you position to your opponent without knowing the position of your opponent.

I have ruled out methods such as the opponent sending multiple false positions for you to compare yours too since your opponent can easily abuse such a system since he will get your position if one of the false positions happened to be "visible" from your position.

The method I have been focusing on one in which you receive a "visual field" from your opponent and can thereby determine if you should send your position or not. This is however a problem in games such as League of Legends where the visual field of your opponent is also highly sensitive information. I have tried to solve this by transforming the visual field using a singular matrix meaning you cannot go from the transformed version of the visual field back to the original version, but since it is a linear transformation you can still figure out if your position is inside the visual field or not.

This does not however work perfectly, the exact visual field cannot be restored after transformation, but information about the "slopes" in the visual field (the visual field is constructed by several lines, and the slope of each line can be determined) can be restored and this can be used to relatively inexpensively reconstruct the original visual field.

In essence, what I need is a function which can determine if a position is "visible" or not, and reconstructing this function/visual field has to be so computationally demanding that once you are done reconstructing the visual field it is no longer relevant for the game in action. Is there any super smart person out there who happens to know of such a method?

Edit People seam kind of confused about the whole "vision field" so I aim to give a more detailed explanation here. The vision field consists groups of a set of lines, you can easily check if a position is inside one of these groups by just checking which side of the line your position is, if it's on the same side for all lines in that group you know it's inside that group and thus inside the vision field.

The information being sent however is not this line, but a transformation of the line and the transformation (2 by 2 singular a matrix), you can still check which side of the line your position is on by first transforming it using the transformation you received and comparing that value to the transformed line. The key here is that the transformation is singular, meaning it is impossible to find an inverse to go back to the original line. However it is possible to determine the slope of the line which makes reconstructing the line by just checking on which side of the transformed line a lot of points lie until you have pinpointed the origin of the line a lot computationally cheaper than if you did not know the slope of the line.

What I am looking for is a method for determining if a point is inside of an area, where reconstructing the area from the method is either impossible (which I doubt exists since you can always brute force it) or very computationally heavy.

\$\endgroup\$
  • 1
    \$\begingroup\$ I've spent about 11 years focused on this exact problem, and the first 4 things you listed are trivial but the one you've asked about would not fit into an SE answer. I'll eventually get a whitepaper out on it. \$\endgroup\$ – MickLH Mar 6 '17 at 18:55
  • \$\begingroup\$ I would think that this would be very dependent on your approaches to the other problems \$\endgroup\$ – Phoenix Mar 6 '17 at 19:24
  • \$\begingroup\$ @MickLH What's the best method you have come up with to solve this problem? :) And what do you think about using transformed visual/interaction fields? Is this something you have looked into? \$\endgroup\$ – Elon Mar 6 '17 at 20:04
  • \$\begingroup\$ I've investigated transformed fields and shown that it's utterly insecure. One player will always be able to infer the position of the other player, no matter how you hide the transformation, since neither player can learn anything until one of them has all of the required information, at which point they learn the other player's position and can terminate the protocol without telling the other player. \$\endgroup\$ – MickLH Mar 6 '17 at 20:20
  • \$\begingroup\$ As for the "best" method... I was serious above, even the simplest method is an intricate topic that really needs an entire whitepaper to explain. \$\endgroup\$ – MickLH Mar 6 '17 at 20:21
1
\$\begingroup\$

I think that even if you had an irreversible algorithm for a vision field, people could still gain advantage by calculating if nearby points to them would result in an intersection of that location and an opponents visual field would intersect. In a bad case (of a large enough vision field to map ratio) you could calculate by process of elimination the exact point of your enemy.

I think instead maybe all connected peers should announce which part of the map they are in, to determine if it possible if they can see each other or not. First split the map into 2x2 or 2x2x2 if the 3rd dimension is important. Then everyone tells each other if they are in 1,0 1,1 0,1 or 0,0. If they are not in the same quadrant, their conversation is over until next check. This protects their exact location. If they exist in the same quadrant, they will split this space up into 4 new quads, and continue until they determine that they are close enough to be seen by each other.

Of course there are problems with the borders of the quadrants, but it should be solvable by additional queries to neighboring quadrants.

\$\endgroup\$
-1
\$\begingroup\$

Don't take this as a definitive answer, the topic is really broad (I won't be suprised if someone flag your question infact).

You can solve it by using some players as server, and when a player is used as server it cannot participate in the game of players that are actually playing that server.

If your game is not too demanding you could as well run multiple servers from the same player machine (of course that would be useful, since not all players can run as server due to NAT problems, thanks you IPv6!!).

The main problem here is that since a random player will be used as server, there's a slight chance it will be a "compromised" player or that it will pass the simulation to a "compromised" player, allowing sensitive information to be passed on (well, in reality at that point the server could send arbitrary data and force the win anyway).

If you use a central server to check authorizations and logins then you could allow to organize games better and to ban players easily (however that would no longer be a pure P2P network).

You could also divide the world into slices and compute a hash of the visible slices, but this could be easily tricked, the most common visible slices will allow to build a table of hashes pretty quickly.

To me your question is like trying to search for a cryptographic function. The test should be quick, but brute force should be slow..

The simplest thing that comes to my mind (also related to my work) is to use some quick vision recognition algorithm (Augmented reality-like).

If you manage to make a quick "snapshot" of your location (similiar to slices), than can be recognized only when placed around something visible then you are going to have it. Especially if there are timed elements in the map that allow to generate quick throw away recognition patterns.

However, even if such algorithms become pretty fast even on mobile, I don't think those will be fast enough for a First Person shooter.

Also if you make them too fast, you will have fake positives! And a player can anyway create a game that try some "Common visuals" so that one of the visuals match positive to the feature detection algorithm.

I will not be surprised the only possible solution to your problem would be possible in Quantum Computing, and within some years someone publish a paper prooving that intrinsic limit in P2P networks.

\$\endgroup\$
  • \$\begingroup\$ Yeah I supposed that. Even with 4GB of data you can store enough hashes to cheat easily. I readed about a math field that was about transformations on encrypted data (like summing a value to a encrypted value so that it gets increased without disclosing the real value), maybe you can find something in that field, but honestly I don't understand that field ^^ \$\endgroup\$ – GameDeveloper Mar 6 '17 at 19:46
  • \$\begingroup\$ Maybe I should have been clearer on the "vision field", it consists of a bunch of lines so you can calculate which side of this line a point is, groups of such lines make up convex areas and groups of such areas make up the whole "vision field". The transformation transforms each line into a point and then all points that were on one side of that line gets transformed to one side of this point so you can still calculate which side of the line it was originally, even tho you can't calculate the original line. \$\endgroup\$ – Elon Mar 6 '17 at 19:58
  • \$\begingroup\$ "and when a player is used as server it cannot participate in the game of players that are actually playing that server" So you mean like dropping P2P? \$\endgroup\$ – Hobbamok Nov 8 '18 at 13:22
-3
\$\begingroup\$

When you say 'Hiding sensitive information from opponents', you mean you want to avoid people with packet sniffers from listening to your traffic and getting info about your game?

If so, there's an easy answer to this; most AAA games (and certainly console games) use encryption. In fact, its so common that many of the networking middlewares used in games already have packet encryption built-in.

Usually it works like this: When you open a connection to another machine, before the socket becomes active, a Key exchange happens. I know that on XBox it used to be Diffie-Hellman key exchange; I've no idea if they still use it now. Then once you have your keys, all data sent is encrypted using the keys and unencrypted on receipt. If someone uses a sniffer to read your packets, they will look like gibberish and it's unlikely they can decrypt them since they don't have the keys. (Advanced hackers may be able to get them by accessing the process memory of the running game, but that is rare and unlikely.)

The only exception to the encryption rule is VoiceChat data; by law in the US, voice chat must be sent in-the-clear so that the CIA can listen in if they want to. Consoles usually provide a way to tag voice data so that it's not encrypted.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.