Re: computer-go: Authenticating the identity of a remote go-play

[tjohnson@xxxxxxxxxxxxxxxxxxxxxxxx]

Don Dailey wrote:
> This is complete nonsense.  So I challenge you to create a text
> file or document that matches this checksum using md5:
> 
>   cc07388b323368808343a852538aea42
>
> [...]
>
> If  you somehow  manage  to actual do  this,  then you will  be
> richly rewarded with fame (and possibly fortune) in the science
> community.

Dave Stafford responded:
> 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.

The point is not that there is no other message that matches this checksum -
clearly, as Dave says, there are - in fact they are plentiful (infinite even
;^) ).  The point is that your chances are very slim of finding a second
plaintext to match the first between when the competition is held and when the
validation occurs (probably less than a month).

In fact, one's chance of finding a second plaintext message that matches the
first are so slim that you'd be lucky to do so at all.  Going brute force, you'd
have to try on average at least 2^128 messages - that's 3 * 10^38 messages for
you non-binary lovers.  How many random plaintext's and md5 checksums can your
computer or even your network of computers do in a day?

If you somehow find a way to do this without going brute force (ie. there's a
short cut), that's when all the fame and fortune get poured down on you.

-Tom J.