What about MD5 hashing the body of the message...

Ian Freislich iang at uunet.co.za
Wed Jul 19 14:25:21 UTC 2000


Content-Type: text/plain; charset=us-ascii

Jaye Mathisen wrote:
> To give a minimal level of non-corruptedness of the article?
> Might be a boon for newsreading clients.
> Of course, it's not the same as digitally signing the article or
> anything, but for quick-and-dirty, it may be viable.
> Stuff it in the overview database perhaps...
> Was just reading in n.s.nntp about corrupted articles running around
> that passed through Cidera, and was bouncing around ideas on how to
> catch it relatively painlessly.

Some second hand crypto I've picked up along the way:

 MD5 has not yet (1999-02-11) been broken, but sufficient attacks have
 been made that its security is in some doubt. The attacks on both
 MD4 and MD5 are both in the nature of finding ``collisions'' -
 that is, multiple inputs which hash to the same value; it is still
 unlikely for an attacker to be able to determine the exact original
 input given a hash value.

This means that MD5 is vulnerable in a way known as 'birthday
attack'.  This is similar to the problem: how many people are needed
in a room for the probability that two people share the same birthday
is high? The answer is close to 12 in stead of the 365 that seems more

In the same way the number of MD5 hashes generated before you get
a clash (the same hash for differing input) is significantly less
than 2^128 which is the largest number that may be represented by
the MD5 digest.  The likelihood that MD5 will produce that same
hash for diffrent inputs increases as the size of the input data
decreases.  It is also fairly easy given an MD5 hash to generate
some data that will produce the same hash.

The application of this information is more relevant to INN's
history file than to the proposed 'X-Body-MD5: ' type header problem
since news admins are not likely to forge the body of a message,
and then they would be able to forge the MD5 hash for the body,
and it is fairly easy to forge a news article any way.

My concern is that (last time I looked, anyway) the MessageID was
hashed using MD5 to give a key for history lookup and insertion.
I'm not sure if this is still the case, but given the volume of
news and the small size of MessageIDs it is extremely likely that
duplicate keys will be generated for different MessageIDs.

Our resident crypto fanatic suggests that SHA-1 be used in place
of MD5, or better still, two different hasing algorithms are used
on the same data to produce a compsite  hash since it is very
unlikely that the data will have the same 'birthday attack'
vulnerability yielding the same composite hash from the two different
hasing algorithms.

- -- 
Ian Freislich
UUNET S.A. (Pty) Ltd

Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv


More information about the inn-workers mailing list