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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: David Stafford <david_stafford@xxxxxxxxxxxxxxxxx>

   I'm afraid I'm stepping into something I'll regret but I don't
   want to let this one pass:

   > This is complete nonsense.  So I challenge you to create a text
   > file or document that matches this checksum using md5:
   > 
   >   cc07388b323368808343a852538aea42
   > 
   > You obviously  don't  realize what cryptographically  secure
   checksums
   > are all about.   THE WHOLE POINT  is that you are  not supposed
    to  be
   > able  to  create   a document  that   matches this  checksum, 
   > even  a completely nonsense document.
   > 
   > If  you somehow  manage  to actual do  this,  then you will  be
   > richly rewarded with fame (and possibly fortune) in the science
   > community.
   > 
   > I don't  make bets  because I  consider  it a  type  of greed,
   > but  in principle I  could make a  whopper of one here, and  my
   money
   > would be extremely safe.

   You might want to research the counting argument for data
   compression.  You can find a description of it here:

   http://www.landfield.com/faqs/compression-faq/part1/

   If one signature could match one and only one file then we would
   have a remarkably good compression method (just send the
   signature) but it would also violate the counting argument.

   Any signature of N bits can only represent, uniquely, a message
   of N bits.  For each additional bit added to the message the
   signature will represent two more possible messages.  For
   example, a 32-bit signature would match a random message with a
   probability of one in 4 billion.  Longer signatures result in
   smaller probability of a mismatch.  The 128-bit MD5 signature
   will match one in 2^128 messages.  That is a very low
   probability, for sure, but it doesn't uniquely represent one and
   only one message.

   -Dave



Actually, any signature you generate will represent an infinite number
of messages!  In principle, after   I checksum my program and  publish
the  signature, an infinite number  of programs could  be written with
the very same signature!   

That's why a checksum does not really "prove" authorship.  The same is
true of  human fingerprints.  It's  "possible" that  another person on
this planet has the   same fingerprint  as I do.    If there  were  an
infinite number   of people in  the universe,  then there  would be an
infinite number of people with fingerprints like mine!

The only reason  a checkum like md5 is  considered "secure" is because
it has been desgined in such as way as to  make it extremely difficult
to  construct another message  with the same  checksum (even though an
infinite number of them exists!)  For all  practical purposes, this is
secure   enough,  because I  can  be  certain, with  a   high level of
confidence,  that you  cannot write a  program that  has the  same md5
checksum as mine.

How would you do it?  You could make systematic 1  bit changes to your
program until you hit on the  correct md5 checksum.  This method works
flawlessly.  Unfortunately, it would take a huge amount of time to hit
on the right  checksum, more time that  the universe has  even been in
existence, so you might as well look for a faster way.  The faster way
is to  analyze  the md5 checksum  algorithm  and  try to somehow  take
advantage of  what  you  learn  about  the   way these  checksums  are
constructed.  It's  possible that someday  someone will come up with a
way to "break" it.

Don