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

[Vishwas Manral <[e-mail]>]

Tony,

I am sorry again. I guess I need to clarify further. Thanks for pointing 
it out.

If we use a function to compress a set a of size X to a result set of 
size output x, where X > x , then there are bound to be collisions. I 
think same way when for a message of any length(0 to infinite) we 
compress it to a message of size 32 bits it is meant to collide. The 
number of inputs is more than the number of outputs.

What I mean is not that hashing wont have collisions, but that finding 
them should not be easy. That was the intention. I gave you the typical 
example served for the same about two documents with the same hash and 
hence the same signature.

Thanks,
Vishwas

Tony Li wrote:
>
> 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
[e-mail]
https://www1.ietf.org/mailman/listinfo/isis-wg