Cheat-Proof Playout for Centralized and Distributed Online Games
by Nathaniel E. Baughman and Brian Neil Levine
In Proceedings IEEE InfoCom, pages 104 - 113, 2001
Paper: (ps)
CiteSeer
Presented by Georg Wittenburg on
March 24, 2004 as part of
538A (201): Topics in Computer
Systems.
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 the
Proceedings of IEEE InfoCom in 2001. Nathaniel E. Baughman was presumably
working as a post-graduate student with newly appointed Prof. Brian Neil Levine
at the University of Massachusetts. It is unknown to the author what Nathaniel
E. Baughman did after writing this paper; Brian Neil Levine has continued to
publish papers, although not directly related to the one that is topic of this
summary.
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 generally
classified as falling into one of the following areas, depending on the
underlying 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 intentionally
delay her actions as long as the dead reckoning can compensate for this. During
this delay however, an advantage may be gained by observing the timely actions
of other players and adjusting the reactions accordingly. No solution has been
proposed to this problem other than to avoid implementations based on dead
reckoning that allow for packets to be delayed.
- Lookahead Cheat: In turn based games (which includes most
real-time games as the real-time simulation is approximated by very short
turns), a player may wait for all other players to submit their actions before
choosing her own action, thereby gaining an unfair advantage. The proposed
solution to this is to exchange cryptographic hashes of the chosen actions, and
only sending the actions once the hashes of all other players have been
received. A cryptographic hash is the return value of function that has the
original data as input. It is not possible to find the original data based on
the hash value, except by brute force. The complete procedure to defend against
the lookahead cheat is referred to as "Lockstep Protocol." It has performance
issues as it requires the players to synchronize all their actions. The authors
propose to avoid this by defining Spheres of Influence (SoI) of a player and
only using the lockstep protocol if the spheres of influence overlap, or might
overlap during the next turn.
- Verifying Secret Possessions: Occasionally, players need to
verify that other players have reached their current state, e.g. the possession
of an artifact, by legal means in the past. On the other hand, this information
should not be available to all players, as it is a strategic in the game. In
order to solve this problem, the authors suggest that players send hashes of
critical parts of their state to a trusted entity -- a "Logger" -- which
timestamps the information and releases it when required to do so by the
gameplay.
- Verifying Hidden Positions: Sometimes a piece of
information, e.g. the positions of players, needs to be compared without
actually releasing that information. The authors offer a cryptological
solution to this problem based on the use of commutative cryptosystem and a
series of operations on the data that allows for the results to be compared and
yielding the correct result, while keeping the initial data hidden.
Of the four attacks / weaknesses discussed, the main focus of the paper is on
the lockstep protocol. The paper contains a proof of correctness and a
performance 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 that
has provable anti-cheating guarantees. The authors rather model online games,
and list a set of possible weaknesses to some of which they also propose a
solution. The structure of the paper is slightly confusing.
Discussion
- Pipelining of the Lockstep Protocol: The lockstep protocol
could be further optimized by interleaving the interchange of hashes and
complete actions. This idea is central to the next paper presented in
class.
- Denial of Service on Spheres of Influence: Overlapping
spheres of influence incur a performance penalty for all affected players. This
might be exploited to perform denial of service attacks.
- Generality of Spheres of Influence: The general
applicability of the spheres of influence concept is not obvious. What a player
can influence depends highly on the game, and may be unrelated to physical
proximity in the simulation (think sniper rifle).
Other interesting questions that were not addresses due to time constraints
are: Is the definition of cheating and fairness adequate? What kind of attacks
should the defense architecture concentrate on? Is there a more general
classification for attacks? How much overhead are players willing to accept for
additional security?
Further Reading
Georg Wittenburg - March 30, 2004
