Re: replay field size

["Theodore Y. Ts'o" <[e-mail]>]

   From: "Niels Ferguson" <[e-mail]>
   Date: Wed, 12 Feb 1997 14:21:00 +0100

   I'm a bit concerned with all the people that are happy to truncate hash
   values to shorter sizes. This should only be done if there is a thorough
   understanding of the threats and desired security level. In particular, SHA
   has a 160 bit output _because_ a 128-bit output was deemed too short. If
   you truncate SHA to 128 bits, the work effort to create a collision goes
   down from 2^80 to 2^64.

Fundamentally, there's a design tradeoff going on here.  If MD4, MD5 and
SHA are truly random functions, then the only way to attack the hash
function would be via a brute-force attack.

However, those cryptoanalysis who have been working on breaking MD5 or
MD4 are *not* making this assumption, and it's likely that if they do
"break" either crypto hash function, it will be because they have found
a way to find dependencies in the output bits.  (Much like differential
crypto exploited very small, probablistic dependencies in the output of
DES.)

So, the argument goes that with SHA-1, we can give up some amount of its
protection against brute-force attacks by shortening it from 160 to 128
bits (assuming that 128 bits in length is "good enough"), and hopefully
gaining some protection against the analytic attacks that cryptographers
might later bring to bear on SHA-1.  So this is an engineering tradeoff,
trading off protection against one attack with protection against
another.  Furthermore, like most engineering tradeoffs, we're working
with only partial knowledge of how helpful it will really be, versus how
dangerous it is to allow brute force attacks against the shortened SHA-1
hash.

Also note that if someone performs a brute-force attack against one off
these hashes, they will only be able to break the integrity protection
for one packet, not for an entire document (as in the case in more uses
of this technology for digital signatures).  In general, the
requirements for integrity protecting an IP stream aren't quite the same
as those required for digital signature in commerce.

							- Ted