Friday, September 14, 2007

one-time Pats and other conundra

As a Patriots fan and a computer scientist, I'm having a really hard time getting concerned about the current "Videogate" or whatever brouhaha surrounding the team. It takes 3 hours to play a football game. Only 60 of those 180 minutes are spent in game action; the other 120 are spent with each side trying to figure out what the other side's going to do so they can beat it, and concealing or obscuring what they're going to do so the other side can't beat them. Because the game mostly stops between each set-piece play, allowing each side to decide on and set up a complex move, American football today is about 33% execution and 67% information warfare. It should be surprising not that the Patriots have a sophisticated real-time SIGINT program to puzzle out the intentions of their opponents, but that more other teams don't. Seriously, the Pats were running a football Bletchley Park, and to hear the other teams and their fans howl, you'd think they were all still using CrackerJack decoder rings. Additionally, teams that get signals stolen have nothing to cry about; the methodology for creating a virtually uncrackable system has existed for about a hundred years, and the technology to implement it has been around since the invention of Kinko's. Seriously.

If you really want to avoid having your defensive signals stolen, here's a system that's going to work as well as anything:

Say you have a total of 80 defensive looks, but prepare only 60 for any given game, based on opponent tendencies. Each look is assigned a normal play call sign, which is referenced to a number in a card work on a wristband on each defensive player. Before each game, a set of 30 new cards is prepared, each 'run' of reference cards bearing a unique permutation of the looks assigned to the numbers 1 to 60. This allows for 30 defensive drives per game, as the cards are changed at the end of each drive and subsequently destroyed -- and the defense is seldom on the field for more than 15 drives per game. Since no team will play more than 20 games in a season, this is a true one-time pad; 600 possible cards is an infinitesimal fraction of the [80|60]x60! possible permutations. (That number, incidentally, is about 3 googol - 2.94e100. For comparison, the number of atoms in the universe is generally reckoned to be on the order of 1e80. Given that there's going to be a core range that will represent most of the defenses called, the important factor is those 60! possible arrangments, which evaluates to 8.32e81.) There are going to be occasional collisions, but the space is large enough that the same signal is probably not ever going to represent the same play after the drive on which it is called -- and absolutely cannot be deterministically associated with any particular call over the course of several games.

For more obfuscation, give each defensive assistant two sheets: one containing the drive's play permutation, which is changed after every drive and destroyed, and the other containing 100 randomly generated numbers in the range covered on the wristband, which is destroyed only at the end of the game. Before each drive, the defensive staff informs the players who's going to be calling the signals in -- a responsibility chosen, also, by random-number generation. Before each play, that coach calls in the signal -- and everyone else, about the same time, some before and some after, calls in the next unused random number on their sheet. The DC still makes the call, but with the miracle of headsets everyone else can get the call simultaneously and transmit message or noise as agreed on. Because the play call is a one-time pad, there's no way to tell what is signal and what is noise, and the "transmitting frequency" changes stochastically. Ideally, the coach calling in the actual play should change on every play as well, because there's a trivial known-plaintext attack to be made (only by, of course, a team with an appropriately-developed SIGINT operation, but now, if you don't assume your apponent has one, you're as bad as Henry Stimson insisting that gentlemen don't open each others' mail) as soon as a defense is repeated in the same drive: the opposition is tracking all the coaches' signals per play, and once the defense runs the same look again, there is likely to be only one signal in common on the two events, and they now know who to watch for the rest of the drive. However, getting players to switch between signal-callers on a per-play basis when they're also trying to play football is probably too much to ask and opens the door to a lot of confusion. There are some other tricks with repetition of plays and otherwise gaming the space that can be done from a multiple-coach setup, but we have to leave something to the professionals to develop.

The expense of creating and managing the piles of cardstock that this plan created needs to be considered, and the team has to be trained and disciplined to execute it, but the actual encryption can be done in less than an hour per week by an intern using UNIX rand() or a more solid function if so desired -- if, say, the team is run by a Wesleyan graduate who might be able to appreciate the value of hard random numbers from radioactive decay over 'soft' random numbers coming from clock and salt. ;) Of course, the real problem is that most teams don't know about combinatorics, or cryptography, or one-time-pad usage, and can't see a way out of the trap....but do understand that Belichick might, or would at least have someone on staff who might, and once it's revealed that one side can penetrate another's signals, the way to one-time pads is short, and perilous for those who can't implement them.


If you don't care about football or cryptography, you can either stop here and go to Edguy like I'm doing, or look at this and laugh yourself stupid. (Laughter not guaranteed for non-German-speakers.)

No comments: