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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Yes,  you are absolutely right about  this and I missed  that one.  In
order to work,  there can be  no freedom  of choice (like  picking and
choosing a  timeout) that cannot  be completely verified  by using the
copy of the program that the organizers have access to.

As I've said, there are deterministic solutions that are workable, but
it's asking too much to require them to be implemented by everyone.

The real  problem is  that  we have a  nasty  source of chaotic  input
coming into the program, the time time clock!   

In  my last email  I noted that some  parallel programs are written in
such a fashion  that they cannot be deterministic  (at least  based on
way  current hardware  works.)   This  is one   case that refutes   my
theoretical  proposal  that we   can  make any  program  deterministic
without hurting it.   

In theory,  every program is  already  completely deterministic if you
are able to identify each and every source of "input" but in practice,
it's not so easy to do this.


Don



   From: Mika Kojo <mkojo@xxxxxxxxxxxxxxxxx>

   Don Dailey writes:
   > 
   > I think  I  was  accused of  over-engineering,  but I   think  Nicol's
   > solution is more than good enough.  It's one of  many possible ways to
   > handle time control,  there are also  ones that can be managed locally
   > that won't severly cripple your program.
   > 
   > If  we really wanted  to get paranoid,  we  could use secure protocols
   > that are in common use already for network communication.
   > 
   > No one claimed any of  this was easy, but  it's easy to  make it a lot
   > more  commplicated than   it needs  to be by   requiring  more than is
   > necessary.

   My point was that Nicol's approach is not secure. It indeed makes
   cheating rather easy (at least in theory).

   Example. Suppose programs are allowed to query once per move the
   current time from the server. By keeping local timer the program can
   look at the most significant digits of the time and request a server
   to record that time when it wishes. Thus if the 7-dan is quick enough
   (say, 1 minute per move) then the program just queries at the right
   moment to encode the move. Now, when the organizers verify the winner,
   which showed remarkable 7-dan ranking, the program just instantly
   queries the move from the server and outputs it. Perhaps organizers
   are slightly surprised by the fact that the program is so quick now,
   but the programmers just state that they runned it on slow machine at
   the tournament. 

   If the protocol is wanted to be secure, then the method of tracing the
   programs execution does not work. (Except in the case where the
   tournament program and the program used in verification are exactly
   same.)

   Usual cryptographical protocols can guard against external cheaters
   (e.g. who intercept the connection between the server and the
   tournament program), but not against cheating Go playing programs.

   -- 
   Mika Kojo
   SSH Communications Security Corp