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

[David Stafford <david_stafford@xxxxxxxxx>]

Hi Don,

Your analysis is correct.  I misunderstood your original message
to say that it was impossible for another message to arrive at
the same checksum.

Thanks,
Dave


--- Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:
> 
>    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


__________________________________________________
Do You Yahoo!?
Yahoo! Shopping - Thousands of Stores. Millions of Products.
http://shopping.yahoo.com/