by Nathaniel E. Baughman and Brian Neil Levine
In Proceedings IEEE InfoCom, pages 104 - 113, 2001
Paper: (ps)CiteSeer
We propose a cheat-proof peer-to-peer protocol for implementing online trading card games. We break down actions common to all TCGs and explain how they can be executed between two players without the need for a third party referee (which usually requires an unbiased server).
Presented by Georg Wittenburg onMarch 24, 2004 as part of538A (201): Topics in ComputerSystems.
Slides: (ppt)(pdf)
Background
The paper 'Cheat-Proof Playout for Centralized and Distributed Online Games'was written by Nathaniel E. Baughman and Brian Neil Levine and published in theProceedings of IEEE InfoCom in 2001. Nathaniel E. Baughman was presumablyworking as a post-graduate student with newly appointed Prof. Brian Neil Levineat the University of Massachusetts. It is unknown to the author what NathanielE. Baughman did after writing this paper; Brian Neil Levine has continued topublish papers, although not directly related to the one that is topic of thissummary.
Summary
The paper deals with attacks and other potential weaknesses of online games.The aim is to offer a formalization of these attacks, suggest counter-measures,and assess their implications on the performance of a game. Games are generallyclassified as falling into one of the following areas, depending on theunderlying architecture chosen to control gameplay and data storage:
The paper then goes on to discuss security relevant weaknesses in detail:
- Suppress-Correct Cheat: In a dead reckoning environment,i.e. when basing real-time information on estimates rather than on actual data,which may be unavailable due to network problems, a player may intentionallydelay her actions as long as the dead reckoning can compensate for this. Duringthis delay however, an advantage may be gained by observing the timely actionsof other players and adjusting the reactions accordingly. No solution has beenproposed to this problem other than to avoid implementations based on deadreckoning that allow for packets to be delayed.
- Lookahead Cheat: In turn based games (which includes mostreal-time games as the real-time simulation is approximated by very shortturns), a player may wait for all other players to submit their actions beforechoosing her own action, thereby gaining an unfair advantage. The proposedsolution to this is to exchange cryptographic hashes of the chosen actions, andonly sending the actions once the hashes of all other players have beenreceived. A cryptographic hash is the return value of function that has theoriginal data as input. It is not possible to find the original data based onthe hash value, except by brute force. The complete procedure to defend againstthe lookahead cheat is referred to as 'Lockstep Protocol.' It has performanceissues as it requires the players to synchronize all their actions. The authorspropose to avoid this by defining Spheres of Influence (SoI) of a player andonly using the lockstep protocol if the spheres of influence overlap, or mightoverlap during the next turn.
- Verifying Secret Possessions: Occasionally, players need toverify that other players have reached their current state, e.g. the possessionof an artifact, by legal means in the past. On the other hand, this informationshould not be available to all players, as it is a strategic in the game. Inorder to solve this problem, the authors suggest that players send hashes ofcritical parts of their state to a trusted entity -- a 'Logger' -- whichtimestamps the information and releases it when required to do so by thegameplay.
- Verifying Hidden Positions: Sometimes a piece ofinformation, e.g. the positions of players, needs to be compared withoutactually releasing that information. The authors offer a cryptologicalsolution to this problem based on the use of commutative cryptosystem and aseries of operations on the data that allows for the results to be compared andyielding the correct result, while keeping the initial data hidden.
Of the four attacks / weaknesses discussed, the main focus of the paper is onthe lockstep protocol. The paper contains a proof of correctness and aperformance analysis based on an implementation in an online multi-player game.The other points are handled with less emphasis.
The paper falls a bit short of its initial claim to propose a protocol thathas provable anti-cheating guarantees. The authors rather model online games,and list a set of possible weaknesses to some of which they also propose asolution. The structure of the paper is slightly confusing.
Discussion
- Pipelining of the Lockstep Protocol: The lockstep protocolcould be further optimized by interleaving the interchange of hashes andcomplete actions. This idea is central to the next paper presented inclass.
- Denial of Service on Spheres of Influence: Overlappingspheres of influence incur a performance penalty for all affected players. Thismight be exploited to perform denial of service attacks.
- Generality of Spheres of Influence: The generalapplicability of the spheres of influence concept is not obvious. What a playercan influence depends highly on the game, and may be unrelated to physicalproximity in the simulation (think sniper rifle).
Cheat Proof Game Protocols Pdf
Other interesting questions that were not addresses due to time constraintsare: Is the definition of cheating and fairness adequate? What kind of attacksshould the defense architecture concentrate on? Is there a more generalclassification for attacks? How much overhead are players willing to accept foradditional security?
Further Reading
- Chris Chambers. SystemsSoftware Lab Reading Group PresentationDepartment of ComputerScience, OGI School of Science & Engineering (January 27, 2004).
- Chris GauthierDickey. 'CheatproofPlayout Summary'Computer and Information Science, University ofOregon
Georg Wittenburg - March 30, 2004
Cheat Proof Game Protocols Free
Abstract
Cheat Proof Game Protocols 2020
Abstract—We explore exploits possible for cheating in real-time, multiplayer games for both client-server and serverless archi-tectures. We offer the first formalization of cheating in online games and propose an initial set of strong solutions. We propose a protocol that has provable anti-cheating guarantees, is provably safe and live, but suffers a performance penalty. We then develop an extended version of this protocol, called asynchronous synchro-nization, which avoids the penalty, is serverless, offers provable anti-cheating guarantees, is robust in the presence of packet loss, and provides for significantly increased communication perfor-mance. This technique is applicable to common game features as well as clustering and cell-based techniques for massively mul-tiplayer games. Specifically, we provide a zero-knowledge proof protocol so that players are within a specific range of each other, and otherwise have no notion of their distance. Our performance claims are backed by analysis using a simulation based on real game traces. Index Terms—Gaming, multimedia communication, peer-to-peer networking, security. I.
