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

From: Tony Li <[email-masked]>
Date: Fri, 2 Mar 2007 11:33:10 -0800

Hi,

I'd like to take exception to some language found in this draft.  I  
quote:

   The HMAC-MD5 scheme is also not good enough as there have recently
    been reports about attacks on the collision resistance properties of
    MD5 [MD5-attack]. MD5CRK, was a distributed computing project to
    break the MD5 hash algorithm in a short period of time. The project
    closed down with the publication of the paper [MD5-attack].

    It was discovered that collisions can be found in MD5 algorithm in
    less than 24 hours, making MD5 very insecure.

I find this language to simply be irresponsible in that it  
misconstrues an attack vector and then draws a completely incorrect  
conclusion and reports it using the most incendiary language possible.

It is correct that it is possible to quickly find a collision for an  
MD5 hash.  However, just finding a collision does not give an  
attacker a mechanism to compute a correct hash for an arbitrary  
packet.  Thus, the attacker does not have a mechanism to forge  
arbitrary packets and have them injected into IS-IS.  In fact, the  
most that this process will do is allow the attacker to calculate  
some other, effectively pseudo-random packet that would have an  
identical hash.  The odds of such a packet being a syntactically  
correct IS-IS PDU are long indeed (e.g., is the Fletcher checksum  
correct?), and the odds of it further performing some attack  of  
interest within an IS-IS domain are longer still.

Note that I do not disagree that there is a need for replacement  
algorithms.  Experience has shown that all cryptographic algorithms  
will eventually be compromised in serious ways.  However, the attack  
cited is simply not in that category and it is wholly unreasonable to  
claim that the sky is falling.

I recommend that the WG not accept this draft until this language is  
revised.

Regards,
Tony

_______________________________________________
Isis-wg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/isis-wg

---

From: Vishwas Manral <[email-masked]>
Date: Fri, 02 Mar 2007 11:56:36 -0800

Hi Tony,

I understand your concern. I understand the statement saying "making MD5 
very insecure" needs to be well qualified. I agree it is a problem when 
MD5 is used for hashing before a document is signed, as two different 
documents could then have the same hash and hence the same sign. It may 
not necessarily be true in the IS-IS case.

I totally understand that the collision in Hash Functions does not 
necessarily cause the hash mechanism as used in IS-IS to break. 
Collisions are however against the basic design of hash functions. May 
be the text needs to be clarified.

Infact you will see that in the document sighting issues with current 
security mechanisms I have stated the fact that having the checksum 
mitigates the attack However some protocols (OSPF for sure, not sure 
about IS-IS) disable checksum calculation when the security hashing is 
used.

Do let me know if I am wrong here?

Thanks,
Vishwas

Tony Li wrote:
> MD5 hash.  However, just finding a collision does not give an attacker 
> a mechanism to compute a correct hash for an arbitrary packet.  Thus, 
> the attacker does not have a mechanism to forge arbitrary packets and 
> have them injected into IS-IS.  In fact, the most that this process 
> will do is allow the attacker to calculate some other, effectively 
> pseudo-random packet that would have an identical hash.  The odds of 
> such a packet being a syntactically correct IS-IS PDU are long indeed 
> (e.g., is the Fletcher checksum correct?), and the odds of it further 
> performing some attack  of interest within an IS-IS domain are longer 
> still.
>

---

From: Vishwas Manral <[email-masked]>
Date: Fri, 02 Mar 2007 13:53:27 -0800

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
>
>
>

---

From: Vishwas Manral <[email-masked]>
Date: Fri, 02 Mar 2007 14:07:38 -0800

Hi Tony,

Just so that we clear all confusion on the list of any probable wrong 
terminology.
 > 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.
What you talk about above is pre-image attack and not a collision 
attack. The two are similar though not the same.

We will further qualify the statement "making MD5 very insecure" in the 
draft. You can actually find the right version of the draft at
http://www.ietf.org/internet-drafts/draft-ietf-isis-hmac-sha-01.txt

Thanks a lot for bringing forth the discussion on the draft,
Vishwas

---

From: Vishwas Manral <[email-masked]>
Date: Fri, 02 Mar 2007 14:18:37 -0800

James,

I agree it is hard to get two valid inputs with the same hash. However 
from what I was told, many characters not part of the standard character 
set and hence are invisible(so just the same as if they were not there).

That is the reason I gave the example given by the security people for 
the collision attack. I agree it is not IS-IS related and we can 
probably shift this discussion to some security list (we have discussed 
this on RPSec a couple of years back and I am giving you the gist of the 
discussion there).

Thanks,
Vishwas

James Carlson wrote:
> Vishwas Manral writes:
> There's a huge difference between being able to find collisions with
> arbitrary input, and being able to find a collision on specifically
> modified input.
>
> In other words, there's a serious threat if someone can use known good
> messages to construct a new and different message that's syntactically
> correct and meaningful with a hash that passes validation.
>
> As far as I know, nobody knows how to do that for MD5, and conflating
> an academic exercise with a security problem in an actual protocol is
> probably not a worthwhile contribution.
>
>

---

From: "Parker, Jeff" <[email-masked]>
Date: Fri, 2 Mar 2007 17:25:43 -0500

> many characters not part of the standard character set and hence 
> are invisible(so just the same as if they were not there).

Fortunately, we don't depend upon people reading the TLVs to spot problems.  

The question is not how many packets hash to the same value, but 
"Can you produce a valid, but different packet quickly?" 

- jeff parker

---

From: Vishwas Manral <[email-masked]>
Date: Fri, 02 Mar 2007 14:39:09 -0800

Jeff,

> Fortunately, we don't depend upon people reading the TLVs to spot problems.  
Agree. :) This was the document case which is given as a typical example 
for issues that might occur with hash collisions.
> "Can you produce a valid, but different packet quickly?" 
Ok, let me clarify the whole thing. Being able to find collisions goes 
against the design of the hash function. There are now programs 
(referenced in the document) that can result in that. Though no known 
attacks are there for protocols currently, but because vulnerabilities 
have been found in the hashing mechanisms, the Security area currently 
does not promote the use of the hash functions. It suggest replacement 
of these hash functions. Infact NIST in the same theme as they developed 
AES have now made an open call for new Hash functions.

Just to clarify HMAC-MD5 and HMAC-SHA-1 do not suffer from collision 
attacks that are suffered by the non-HMAC versions.

The aim of the draft is to bring forward the issues with the current 
hash functions and clearly state the new mechanisms. As Tony said we 
need to clarify that further, so that no confusion results.

Thanks,
Vishwas

---

From: Tony Li <[email-masked]>
Date: Fri, 2 Mar 2007 13:14:10 -0800

Vishwas,

	h = H(f(secret, 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.

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

---

From: Russ White <[email-masked]>
Date: Fri, 02 Mar 2007 18:45:57 -0500

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

The question is, as I've always understood it (?), how long does it take
to produce such a collision? The most recent number I saw, probably two
years ago, I think, was in a presentation by Russ Housley, and was on
the order of 14 seconds.

> without knowing the secret.  Collision attacks do not give an attacker

No, but if you can find a large number of packets with a matching hash
in a short period of time, then you may be able to find one that does
have all the correct syntax of a normal IS-IS packets.

I don't think any of us have the definitive answers here, we're just
going by what we've seen in presentations, and on mailing lists, etc. My
general understanding is that there's always points of argument in the
security world, of course, but the idea is to point the way forward
before this becomes an issue, and not after, I think.

:-)

Russ

- --
[email-masked] CCIE <>< Grace Alone

---

From: Russ White <[email-masked]>
Date: Fri, 02 Mar 2007 18:45:57 -0500

:-)

Russ

- --

---

From: James Carlson <[email-masked]>
Date: Fri, 2 Mar 2007 17:09:25 -0500

-- 
James Carlson, Solaris Networking              <[email-masked]>
Sun Microsystems / 1 Network Drive         71.232W   Vox +1 781 442 2084
MS UBUR02-212 / Burlington MA 01803-2757   42.496N   Fax +1 781 442 1677

om [10.91.34.44] (helo=ietf-mx.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.43) id 1HNFwQ-0005m6-R0
	for [email-masked]; Fri, 02 Mar 2007 17:09:31 -0500
Date: Fri, 2 Mar 2007 17:09:25 -0500
From: James Carlson <[email-masked]>
To: Vishwas Manral <[email-masked]>
Subject: Re: [Isis-wg] draft-bhatia-manral-crypto-req-isis-01.txt
Cc: Tony Li <[email-masked]>, [email-masked]

-- 
James Carlson, Solaris Networking              <[email-masked]>
Sun Microsystems / 1 Network Drive         71.232W   Vox +1 781 442 2084
MS UBUR02-212 / Burlington MA 01803-2757   42.496N   Fax +1 781 442 1677