Subject: [secdir] Review of draft-ietf-opsec-routing-protocols-crypto-issues-04

From: Nicolas Williams <[email-masked]>
Date: Thu, 20 May 2010 12:23:11 -0500

I have reviewed this document as part of the security directorate's
ongoing effort to review all IETF documents being processed by the
IESG. Document editors and WG chairs should treat these comments
just like any other last call comments.

This document aims to be an Informational RFC describing security
problems with various routing protocols.

Aside from various spelling and other nits that the RFC-Editor can
easily handle, I have no issues with this document and it is ready for
publication.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Thu, 27 May 2010 14:47:40 -0400

>>>>> "Nicolas" == Nicolas Williams <[email-masked]> writes:

    Nicolas> I have reviewed this document as part of the security
    Nicolas> directorate's ongoing effort to review all IETF documents
    Nicolas> being processed by the IESG. Document editors and WG chairs
    Nicolas> should treat these comments just like any other last call
    Nicolas> comments.

    Nicolas> This document aims to be an Informational RFC describing
    Nicolas> security problems with various routing protocols.

    Nicolas> Aside from various spelling and other nits that the
    Nicolas> RFC-Editor can easily handle, I have no issues with this
    Nicolas> document and it is ready for publication.

This document talks a lot about collision attacks against MD5 and then
draws the conclusion that MD5 should not be used as part of a MAC.  I
agree that it is prudent to provide alternatives to MD5.  However, I
think the current text implies that collision attacks against MD5 are
applicable to attacks against the use of MD5 in routing protocols.

There is an introductory section that describes the difference between
pre image and collision attacks, but the rest of the document seems to
ignore the advice of that section.

---

From: Sandra Murphy <[email-masked]>
Date: Thu, 27 May 2010 14:56:26 -0400 (Eastern Daylight Time)

I was discussing this just this morning with a colleague.

The discussion of pre-image and collision points out that using collisions 
as an attack on a routing protocol is not that easy since routing 
protocols have format requirements - the attacker would have to find a 
collision that is also a validly formatted protocol packet.

Even beyond that, if the authors can point to some damage an attacker 
could do in a routing protocol using a collision, that would be very 
interesting.

--Sandy

On Thu, 27 May 2010, Sam Hartman wrote:

> _______________________________________________
> secdir mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/secdir
>

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 27 May 2010 14:28:50 -0500

> applicable to attacks against the use of MD5 in routing protocols.

I noticed this, but decided it was a non-issue for me.  The document
isn't intended to provide advice, though advice is effectively implied.
And as for MD5, I won't be sorry to see it go, whether used as the
foundation for a MAC or not.

Nico
--

---

From: Sandra Murphy <[email-masked]>
Date: Thu, 27 May 2010 15:30:03 -0400 (Eastern Daylight Time)

On Thu, 27 May 2010, Vishwas Manral wrote:

> Hi Sam/ Sandra,
>
> I agree with what you guys have said, we can work to refine the wording to
> make it clear that there are no known attacks.
>
> There may not be known attacks based on collision, but that does not
> preclude future issues that may result. One thing I can see is if we can
> change the topology field and still have the right/ same hash, it could lead
> to basic issues like traffic redirection, black holes and routing loops. I
> agree the fact that the packet needs to be a valid format packet makes the
> attack considerably harder.

I really did mean what I said - if you can think of cases where routing 
protocols could be damaged by a collision attack, speak up.

Most of the things I could think of were attacks that resulted from a 
legitimate participant behaving badly, and we all know just how much 
risk routing protocols face from legitimate participants behaving badly 
anyway - collisions would be no more risk.

--Sandy

>
> Thanks,
> Vishwas
>
> -----Original Message-----
> From: Sandra Murphy [mailto:[email-masked]]
> Sent: Thursday, May 27, 2010 11:56 AM
> To: Sam Hartman
> Cc: Nicolas Williams; [email-masked]; [email-masked];
> [email-masked]; [email-masked]; [email-masked]
> Subject: Re: [secdir] Review of
> draft-ietf-opsec-routing-protocols-crypto-issues-04
>

---

From: Sandra Murphy <[email-masked]>
Date: Thu, 27 May 2010 15:34:37 -0400 (Eastern Daylight Time)

On Thu, 27 May 2010, Vishwas Manral wrote:

> Hi Sandra,
>
> You may look at the draft I have added below (which I sent to the list but
> never posted)
>
> http://www.ietf.org/mail-archive/web/saag/current/msg01732.html
>
> It talks about the fact that there is another (like in your case a validly
> formatted protocol packet) check which can greatly reduce the effect of
> collision.
>
> Do let me know what you think about the same with respect to the draft at
> hand?

Well, until we figure out that a collision would lead to bad things 
happening, there's no real need to make a check to reduce the chance of a 
collision.

Which is why I asked.

There's a general concern that MD5 is showing weakness and so we're all 
happy to see movement away from MD5.  But the collision risk at the moment 
is not clear.

--Sandy

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 27 May 2010 14:38:02 -0500

On Thu, May 27, 2010 at 03:30:03PM -0400, Sandra Murphy wrote:
> I really did mean what I said - if you can think of cases where
> routing protocols could be damaged by a collision attack, speak up.

I'd rather not bother because I'd rather be conservative in the design
of new protocols and fixes to existing ones.

Provide for key exchange, PSK and/or PK authenticatoin methods and use
modern MICs, then feel the relief of not having to care about
collisions :)

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Thu, 27 May 2010 20:23:26 -0400

>>>>> "Sandra" == Sandra Murphy <[email-masked]> writes:

    Sandra> I was discussing this just this morning with a colleague.
    Sandra> The discussion of pre-image and collision points out that
    Sandra> using collisions as an attack on a routing protocol is not
    Sandra> that easy since routing protocols have format requirements -
    Sandra> the attacker would have to find a collision that is also a
    Sandra> validly formatted protocol packet.

I actually find this argument uncompelling.  Certificates have format
requirements, but we've generally found that extensible data structures
typically have space somewhere for the bits that you need to make an
attack possible.

What's more interesting to me is the affect of the key on the ability to
prepare for such an attack.

---

From: Sam Hartman <[email-masked]>
Date: Thu, 27 May 2010 20:33:00 -0400

>>>>> "Bhatia," == Bhatia, Manav (Manav) <[email-masked]> writes:

    Bhatia,> this - "Attacks on many applications of MD5 are practical
    Bhatia,> on modern computers. For this reason the general use of
    Bhatia,> these algorithms should to be discouraged.[

Right.  I think this text is misleading to the point of being false.
There are attacks against md5 as a hash.  However we have not yet found
a mechanism to turn attacks on md5 as a hash into attacks on hmac-md5 as
a MAC.
It's not a question of the computer power--it's that thes attacks
haven't managed to give an advantage for attacking HMAC.

For other keyed md5 varients more analysis is required, but I would not
at all be surprised if the conclusion were the same: the class of md5
attacks we know about do not apply to md5 in these MAC constructions.

I think the best we can say for discouraging the use of md5 is something
like "There have been attacks against the use of md5 as a hash; while
these attacks do not directly apply to the use of MD5 in routing
protocols, it is prudent to have other options available."

The current text implies that the format of the routing packets, rather
than the format of the MAC construction is what provides protection.
Based on what we've learned about attacking certificates and based on
the fact that all our routing protocols have some extension mechanisms,
I'd find a defense based on the structure of the packets incredibly
weak.

---

From: Sam Hartman <[email-masked]>
Date: Fri, 28 May 2010 09:32:37 -0400

Hi.  I was attempting to reconcile this draft against
draft-ietf-rpsec-ospf-vuln, an old draft on OSPF vulnerabilities.
Section 4.2.2.4 of the rpsec draft disagrees with the last paragraph of
section 2 of the opsec draft.  That paragraph talks about the attack in
which the IP address of a hello packet is replayed in order to cause a
node to think that a connection is not bidirectional.  The rpsec draft
argues that attack doesn't work because the router ID, not the source
address is used.  The rpsec draft also kind of implies this may depend
on implementations.

I'm not sure which draft is right.  However, since there has been
argument about whether this attack is possible,the opsec draft needs to
either acknowledge or resolve this issue.  (Obviously, I'd prefer that
you resolve the issue: it makes our lives easier in karp, but if you
don't have time, I understand just describing it.)

In particular, I believe the opsec draft should cite as an informative
reference section 4.2.4 of draft-ietf-rpsec-ospf-vuln                  9
aand do one of the following:

* Agree with the conclusions

* State it is an implementation matter whether a particular
  implementation is vulnerable

* Explain why the rpsec draft is wrong

* Note that the issue is open

Thanks,

--Sam

---

From: Sandra Murphy <[email-masked]>
Date: Fri, 28 May 2010 11:22:30 -0400 (Eastern Daylight Time)

On Thu, 27 May 2010, Vishwas Manral wrote:

> I am sorry if you anywhere felt that I did not feel you really meant what
> you said.

Here I was, trying to be reassuring that there really was no sly subtext 
to what I said, and you seem to have taken it as a complaint, so I 
further confused things.  Sorry.

>
> What you seem to be saying is pretty well known. I have given you an example
> where if we can get a changed valid packet with a different topology, we can
> cause blackholes, loops and redirection.
>
> Are you trying to figure out how a wrong topology description packet can
> cause problems?

Certainly wrong topology descriptions are a bad thing.

I'm trying to distinguish damage that can be caused by collision attacks 
only.

To be a collision attack, the attacker must be able to produce two packets 
that have the same hash.  Since the use here is a keyed crypto hash, the 
hash also has to be validatable by the recipient - or there's no problem.

Since we are NOT discussing failures in keyed MD5 that would permit 
someone who did not know the key to produce a valid digest, it must be the 
case that the attacker is someone who knows the key - in other words a 
valid participant.

So.  What would a collision attack allow a valid participant to do that a 
valid participant could not already do?  We know for sure that valid 
participants can transmit "wrong topology descriptions" without resorting 
to the trouble of finding a hash collision between packets.

I'm not taking potshots.  I'm genuinely interested in the answer.  Do you 
see any new damage that could be done only with a collision attack?

--Sandy

> Sent: Thursday, May 27, 2010 12:30 PM
> To: Vishwas Manral
> Cc: 'Sam Hartman'; 'Nicolas Williams'; [email-masked];
> [email-masked]; [email-masked]; [email-masked]
> Subject: RE: [secdir] Review of

---

From: Sam Hartman <[email-masked]>
Date: Fri, 28 May 2010 12:53:05 -0400

Sandra> Since we are NOT discussing failures in keyed MD5 that would
    Sandra> permit someone who did not know the key to produce a valid
    Sandra> digest, it must be the case that the attacker is someone who
    Sandra> knows the key - in other words a valid participant.

    Sandra> So.  What would a collision attack allow a valid participant
    Sandra> to do that a valid participant could not already do?  We
    Sandra> know for sure that valid participants can transmit "wrong
    Sandra> topology descriptions" without resorting to the trouble of
    Sandra> finding a hash collision between packets.

O!
I finally understand your question.
Intuitively the answer is that the attacker should not be able to do
anything with a collision  that they cannot already do by knowing the
key, so I didn't even consider that you could be asking this question.

Of course, with many intuitive things, when you actually question the
intuition, it's not obvious why it's true.  However I think I've come up
with an argument.

For a collision attack  to be valuable to the person producing the hash,
the hash needs to be consumed at multiple points in time.
The attacker wins by having the hash consumed associated with m1 at one
point and m2 at another point.

For example, consider the attack where I sign m1 and then later claim to
have signed m2.
That attack is interesting because someone remembers the hash or at
least depends on the hash  and then later is asked to consider the
second message with a given hash.

>From this, I think that if the cryptographic hash is only used to verify
a packet transmitted along-side the hash that a collision is not useful.
The attacker could have simply sent another packet with a different
hash.

Here are some cases though  which a protocol might engage in where this
does not fit:

1) Participants use the hash to identify which packets they've seen in
the past

2) Participants use hashes  to see which packets other participants have
already seen

3) Participants use hashes to identify the base of some delta to an
object

So any case where the lifetime of the hash is longer than just the MAC
verification, I think there is at least the potential for a collision to
be valuable.

I believe at least for OSPF, the attacker gains nothing from collision
attacks.  IS-IS may be more complicated because I think there it's the
content that is MACed not the packet.

---

From: Sam Hartman <[email-masked]>
Date: Mon, 31 May 2010 03:36:10 -0400

>>>>> "Bhatia," == Bhatia, Manav (Manav) <[email-masked]> writes:

    Bhatia,> I am aware of some implementations that look at the IP
    Bhatia,> header to determine the source. I think it's a very good
    Bhatia,> catch and we could append the following before the original
    Bhatia,> text: "In some OSPF implementations neighbors on broadcast
    Bhatia,> .. "

    Bhatia,> Does this sound acceptable?

Yes.  I'd still add a citation to the old draft, but I think that your
text change brings things nicely into alignment.  Then, in KARP, we can
figure out what we recommend about this.

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Fri, 28 May 2010 04:31:55 +0530

Hi Sam,

> applicable to attacks against the use of MD5 in routing protocols.

Not really. We do mention this at the beginning:

"  The ability to produce a collision does not currently introduce any
   obvious or known attacks on routing protocols. Pre-image attacks have
   the potential to cause problems in the future albeit due to the
   message length there are serious limitations to the feasibility of
   mounting such an attack.

   Protocols themselves have some built-in protection against collision
   attacks. This is because a lot of values for fields in a protocol
   packet are invalid or will produce an unusable packet. For example,
   in OSPF the LSA type can be from 1 to 11. Any other value in the
   field will result in the packet being discarded.

   Assume two packets M and M' are generated which have the same hash.
   The above condition will further reduce the ability to produce a
   message which is also a correct message from the protocol
   perspective, as a lot of potential values are themselves not valid."

> ignore the advice of that section.

I think what we're trying to say is the following:

Routing Protocols currently use MD5. There are attacks against MD5, but they may not lead to routing vulnerabilities (Sec 1.1). However, we discourage the use of such algorithms. The exact text that we used for OSPF is this - "Attacks on many applications of MD5 are practical on modern computers. For this reason the general use of these algorithms should to be discouraged.[RFC5709] adds support for using HMAC-SHA with OSPF."

We have currently not found direct vulnerabilities when using MD5 with Routing protocols, but going forward one could actually construct a packet that could adversely affect routing protocol functioning.

Manav

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Sat, 29 May 2010 05:07:56 +0530

I am aware of some implementations that look at the IP header to determine the source. I think it's a very good catch and we could append the following before the original text:

"In some OSPF implementations neighbors on broadcast .. " 

Does this sound acceptable?

Cheers, Manav

> From: Sam Hartman [mailto:[email-masked]] 
> Sent: Friday, May 28, 2010 7.03 PM
> To: Sam Hartman
> Cc: Bhatia, Manav (Manav); [email-masked]; 
> [email-masked]; [email-masked]; [email-masked]

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Sat, 29 May 2010 05:29:55 +0530

> I'd find a defense based on the structure of the packets incredibly

Though I agree that the current attacks on MD5 do not currently apply to MD5 as used in routing protocols, I still think very strongly about our point that for an attack to happen we would need a completely acceptable packet format which may not happen and thereby reducing the probability of an attack. In cryptography one can never be sure of what all has already been broken (It was several years till it became common public knowledge about "enigma" cipher being broken) and its precisely the routing protocol packet format that provides an additional level of security. Assume a 64 byte OSPF HELLO packet using keyed MD5 as described in 2328. Assume that we have been able to find collisions with MD5 as used by OSPF. Even if we are able to find collisions, the probability of an attacker doing something meaningful is in the order of 1/2^64 for a given source and a dest IP.

Thus this really is the clincher in my opinion.

Thanks, Manav