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

[Mika Kojo <mkojo@xxxxxxx>]

(To the moderator: I would appreciate if you would delete my old
subscription for mkojo@xxxxxxxxxxxxxxxxx I further suspect that Antti Huima
would appreciate if you would change his subscription from
huima@xxxxxxxxxxxxxxxxx to huima@xxxxxxxxxxxxxxxxx Thank you.)

(This is just a continuation to the MD5 discussion.)

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.

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

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.

-- 
Mika Kojo
SSH Communications Security Corp