Re: [Isis-wg] draft-bhatia-manral-crypto-req-isis-01.txt

On Mar 2, 2007, at 11:56 AM, Vishwas Manral wrote:

> Collisions are however against the basic design of hash functions.

Vishwas,

Hashing functions necessarily produce collisions.  The input to a  
hashing function is usually a set of bits that are a function of the  
packet being sent and some secret: f(secret, packet).  f() is usually  
something simple, such as concatenation.  The number of bits produced  
by f() is usually large, say on the order of 10,000.  As an example a  
1200 byte LSP is going to inject 9600 bits.

The hashing function H(), then performs a transform:

	h = H(f(secret, packet))

where h is the hash result that we insert into the packet.

The hashing function then takes these 10,000 bits and produces a much  
smaller result.  In the case of HMAC-MD5, it's producing 128 bits.   
Simple combinatorics tells us that if you map 2^10,000 possible  
inputs to 2^128th possible results, on average, there will be many  
different inputs for any given output.

Thus, collisions with a hashing function are *inevitable*.

This does not make them insecure.  Our purpose in using a hashing  
function is to provide authentication.  We wish to ensure that an  
attacker cannot take an arbitrary packet P' and compute a similar  
hash without knowing the secret.  Collision attacks do not give an  
attacker that capability.

They do give the attacker the ability to compute some arbitrary  
packet P" that will result in the same hash value.  Once again,  
injecting arbitrary packets P" is not a very interesting attack.  You  
might as well just generate random packets and throw them at the  
system.  Both will result in a DoS attack, but both should be  
rejected by the simple and straightforward integrity and syntactic  
checks of the protocol.

Regards,
Tony

_______________________________________________
Isis-wg mailing list
Isis-wg@ietf.org
https://www1.ietf.org/mailman/listinfo/isis-wg