Re: computer-go: Authenticating the identity of a remote go-playing computer program

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Mon, Dec 11, 2000 at 03:41:06PM +0100, Nicol N. Schraudolph wrote:
> On Sun, 10 Dec 2000, William Harold Newman wrote:
> 
> > If you have a proposal for preventing [cheating] without making it
> > impossible for programs to use real-time clocks for time management,
> > bring it on.
> 
> Easy enough:
> 
> 1) Managing your own time: require that the program measures time solely
> by querying a game clock on the tournament server (make that part of the
> communications protocol).  This is not limiting since the game clock is
> indeed the only time that matters - just like "true randomness", "real
> time" is quite irrelevant here.  During tournament play, the server
> records all the program's time queries together with its own answers
> to them.  During verification, the server expects the same sequence of
> queries, and responds with the same recorded answers, regardless of the
> actual timing.

[..]

> Any holes in this?

I see two possible problems with this.

The smaller problem is that this method is likely to introduce delay,
on the order of a millisecond on a LAN, or hundreds of milliseconds on
the Internet. Even the LAN delay is a significant nuisance compared to
what you can do with a local real-time clock (polling on every
position you examine, or just arranging for a timer interrupt when
your time runs out). And it's a particularly annoying nuisance for
people who are writing programs primarily to entertain human
customers, because any engineering effort you put into dealing with
the delay of a networked clock is completely useless when playing
against a human customer.
 
The larger problem is one that I mentioned in my previous message
(which I sent just before downloading your current message): once you
allow a covert channel to influence the system, the cheater can do
other things besides fooling with the clock. For example, he can
suspend the process, or just fiddle with the process priority. Neither
of those cheats would be hindered by requiring the time query to go
through a remote clock. (And this does not begin to approach the level
of deviousness that people sometimes use to break security protocols
and encryption schemes! See e.g. any number of security holes found in
IETF protocols or in Unix, and see also Schneier's _Applied
Cryptography_.)

So I still prefer the earlier ideas: physical security to shut down
any covert channels, or running the tournament at a pace where covert
human input can't help, or using a strongly deterministic program
(with no real-time clock input).

He also wrote:

> 2) Using your opponent's time: if your program does this, it's bound to be
> organized such that its computation can be interrupted by the opponent's
> move at certain well-defined points.

Not necessarily. I think that in a system with good support for
unwinding the stack cleanly (like C++'s destructors, or Common Lisp's
UNWIND-PROTECT) it's probably feasible to interrupt calculation at an
arbitrary time, with e.g. a Unix "signal" (basically a software
interrupt). I may never implement time control this way in my program,
but I have at least considered it.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C