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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: Mika Kojo <mkojo@xxxxxxxxxxxxxxxxx>

   David Stafford wrote:
   >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.

   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.


Yes,  this   is  exactly  equivalent  to the    birthday paradox.  The
protection  we   are looking for  in  the  context of  our discussion,
however, is not a birthday paradox issue.  The characteristic we would
desire is   that  it should  be   incredibly  difficult  to produce  a
"tampered with" version of a SPECIFIC program.   So we are still talking
about 2^128, not 2^64. 


   On the otherhand, I believe that no actual collision for MD5 has ever
   been found or described in the (open) literature.

But   they  surely  exist!  I  have   written  software that generates
hundreds  or thousands of  md5   signature per  day to  perform useful
functions, I  think there must be business  in every city of the world
producing millions or  billions of these  every day.  Surely, some  of
these collide!   Finding them might take an  enormous amount of effort
however!


   The currently recommended (cryptographic) hash function SHA-1 has
   160-bit hash digest. Finding collision takes thus at most 2^80
   messages, but even this is not beyond all suspicion.

   Indeed, NIST has recently issued variants of SHA for 256, 384 and
   512-bit hash digests. These should be resistant to birthday paradox
   based collision attacks for the life time of this planet (assuming
   that there is no algorithmic weakness, and no major breakthrough in
   cryptanalysis).

   Scott Dossey <sdossey@xxxxxxxxxxxxxxxxx> writes:
   > First of all, I am using the phrase "MD5 digital signature", because the
   > word "checksum" isn't quite applicable to MD5, even though it is in common
   > parlance.  MD5 is what cryptographers call a one way hash, not a
   > checksum.  

   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.

I typically use the term checksum too, and I don't think it's wrong,
but "digital signature" is clearly more descriptive.

Don

   -- 
   Mika Kojo
   SSH Communications Security Corp