Covert Channels in Combinatorial Games

A general framework for exploiting covert channels in combinatorial games is presented. The framework is applicable to all combinatorial games, including Chess and Go, but is applied to the game of Tic-Tac-Toe for ease of experimental analysis. The security and capacity of the resulting covert channel are analyzed experimentally. By considering the ways in which a passive adversary can attempt to detect and neutralize the usage of the channel, it is shown that the passive adversary cannot distinguish games which contain hidden information from games which do not. It is also shown that, even by enforcing a perfect-play requirement, the adversary cannot reduce the capacity of the channel to zero in order to prevent covert communication. Additionally, the framework is shown to be generalizable to multiplayer games and games without perfect information by identifying covert channels in two other games.