RE: computer-go: Authenticating the identity of a remote go-playi ng computer program

[sdossey@xxxxxxxx]

Mika Kojo comments:
>To me checksum sounds better than MD5 digital signature, as digital
>signatures imply public key cryptography. If the writer remembers to
>mention that the checksum must be collision resistant then I suspect
>there is no harm done.
Perhaps MD5 digest or MD5 hash would be better.  I'm going back to using
checksum for the rest of this document.

Mika Kojo also points out:
>David, recall birthday paradox: in a set of just 23 people there is
>probability > 1/2 that some have the same birthday. That is, in just
>2^64 messages you will observe collision of 128-bit strings with
>probability ~ 1/2.

Mika Kojo, thanks for pointing out the birthday paradox.  I myself did not
bring it up because it does not directly apply to the problem at hand.  

The problem is of matching a PARTICULAR MD5 checksum (the one you
submitted), not matching any one in a huge set of checksums.
Also, the typical number of contestants in a computer go contest is not
large enough to make the birthday paradox a plausible method for
"pretending" to be another program.

There are potentially ways to generate two programs with the same checksum
by, say, generating 2^80 programs with randomized blocks inside them.  Then,
quite likely, two of the 2^80 programs will have the same MD5 checksum.
However, this doesn't help you at all.  Both programs content would
basically have to be determined prior to contest entry.  Either that, or the
contest would have to accept a VERY VERY large number of applicant programs
from you and then you can find a match afterwards.

Quite frankly, 2^80 is still a REALLY big number too.  Seeing as we've just
gotten cheap and effective ways to brute force 56 bit keys, and 64 bit key
cracking is still very, tough.  2^80 is not exactly that feasible right now.
I also don't see how the birthday paradox applies to the problem at hand.
If you can see it, please enlighten me.  

By the way, can you BELIEVE IT?  The Ipsecure protocol uses 12 byte
truncated SHA or MD5 macs.  That's a small enough mac to make me very wary
about birthday attacks.

-Scott Dossey
sdossey@xxxxxxxxxxxxxxxxx