Subject: [karp] Security Extension for OSPFv2 when using Manual Key Management

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Thu, 13 Jan 2011 06:13:21 +0530

Hi,

Sam, Dacheng and I have written a small draft attempting to fix the issues that exist when using OSPFv2 with manual keying. It introduces two additional variables - the Nonce and the Session ID, that need to be maintained per neighbor, that will, we believe, fix most issues that currently exist as described in RFC 6039.

As per the KARP design guide we first need to fix the manual keying before we move to a fully automated key management system for the routing protocols. This draft attempts to address the first part, i.e., fixes the issues that exist when using manual keying for OSPF.

It would be great to hear the feedback from the WG.

http://www.ietf.org/id/draft-bhatia-karp-ospf-ip-layer-protection-01.txt

Cheers, Manav

--
Manav Bhatia,
IP Division, Alcatel-Lucent,
Bangalore - India

---

From: Michael Barnes <[email-masked]>
Date: Thu, 13 Jan 2011 20:59:44 -0800

Hello Manav,

First I want to applaud you and your co-authors for addressing these 
security problems for OSPF. Thank you.

I have some initial questions and comments.

During the challenge and response are the hello packets sent immediately 
to each other or by the standard hello timer?

During the challenge and response on a broadcast links, are the packets 
unicast or multicast?

Regarding the new format for hello packets, is this format to be used 
only during challenge and response, or for all hello packets when this 
new form of authentication is enabled?

RFC2328 defines the AuType field, you've chosen to rename it to 
AuthType. I suggest we continue to use AuType for continuity.

In the figures which illustrate the header and hello packet fields, I 
suggest that instead of showing two words as just "Authentication" that 
the figure shows the sub-fields. In the context of this specification 
those words will have a single definition, so there is no reason to 
leave them loosely defined.

Please describe how LLS will be covered using this new authentication type.

Regards,
Michael

On 01/12/2011 04:43 PM, Bhatia, Manav (Manav) wrote:
> _______________________________________________
> karp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/karp
>

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Fri, 14 Jan 2011 14:25:24 +0530

Hi Michael,
 
> security problems for OSPF. Thank you.

Thanks Mike!

> to each other or by the standard hello timer?

I think it should be done immediately without waiting for the Hello timer to expire.

> During the challenge and response on a broadcast links, are 

Multicast.

> new form of authentication is enabled?

This has to be used *all* the time.

> AuthType. I suggest we continue to use AuType for continuity.

Sure, will do that.

> leave them loosely defined.

It's a typo. We need to remove the two fields shown as Authentication from the two figures!

> Please describe how LLS will be covered using this new 

This extension has no bearing on the LLS since LLS isnt really a part of the OSPF payload. Its length is not included in the length of the OSPF packet, but is included in the IPv4 packet length.

Is there something specific that you are looking at?

And thanks for your comments!

Cheers, Manav
> > Sam, Dacheng and I have written a small draft attempting to 
> fix the issues that exist when using OSPFv2 with manual 
> keying. It introduces two additional variables - the Nonce 
> and the Session ID, that need to be maintained per neighbor, 
> that will, we believe, fix most issues that currently exist 
> as described in RFC 6039.
> >
> > As per the KARP design guide we first need to fix the 
> manual keying before we move to a fully automated key 
> management system for the routing protocols. This draft 
> attempts to address the first part, i.e., fixes the issues 
> that exist when using manual keying for OSPF.
> >

---

From: Michael Barnes <[email-masked]>
Date: Fri, 14 Jan 2011 02:42:18 -0800

Hi Manav,

> This has to be used *all* the time.

Please clarify the above three points in the document.

> Is there something specific that you are looking at?

LLS part of OSPF also needs to be authenticated so this draft really 
needs to cover it as well.

Thanks,
Michael

---

From: Michael Barnes <[email-masked]>
Date: Fri, 14 Jan 2011 02:48:23 -0800

Hi Manav,

I wanted to address this point separately.

> This has to be used*all*  the time.

I'm not very excited about a 3x increase in the number of bytes per 
neighbor. (For those who haven't read the draft, it changes the Hello 
packet so that it contains 12 bytes for each neighbor over the current 4 
bytes per neighbor.) I have to wonder if this is really necessary for 
each and every hello packet. I'm certainly not a security expert, but it 
seems to me that once we have verified the neighbor's session ID we 
shouldn't continue to need to receive our own session ID and nonce back 
in every hello packet. Did you consider if this can't be optimized?

Thanks,
Michael

---

From: Michael Barnes <[email-masked]>
Date: Fri, 14 Jan 2011 03:03:12 -0800

Hi Manav,

> It's a typo. We need to remove the two fields shown as Authentication from the two figures!

If you remove those, then where are sequence number, Key ID & Auth Data 
Length fields in the Hello packets?

Thanks,
Michael

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Fri, 14 Jan 2011 17:07:58 +0530

Hi Michael,

Thanks for catching this - will fix it in the next revision.

I think the OSPF header should remain as is. Each router should prepend its Nonce and Session ID information before the Auth payload. 

Cheers, Manav

> -----Original Message-----
> From: Michael Barnes [mailto:[email-masked]] 
> Sent: Friday, January 14, 2011 4.33 PM
> To: Bhatia, Manav (Manav)
> Cc: [email-masked]; [email-masked]
> Subject: Re: [karp] Security Extension for OSPFv2 when using 
> Manual Key Management
> 
> Hi Manav,
>

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Fri, 14 Jan 2011 17:07:56 +0530

Hi Michael,

> > This extension has no bearing on the LLS since LLS isnt 
> really a part of the OSPF payload. Its length is not included 
> in the length of the OSPF packet, but is included in the IPv4 
> packet length.
> >

The LLS processing remains exactly the same. Will cover this too in the next cut.

Thanks, Manav

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Fri, 14 Jan 2011 17:05:50 +0530

Hi Michael,

> in every hello packet. Did you consider if this can't be optimized?

Nonce and Session IDs are essential to protect against inter and intra-replay attacks. While I think we need to carry them all the time, I am not precluding the possibility of some optimization that can get in here. The idea behind submitting this draft was to initiate a discussion on how to start securing OSPF when its using manual keying. I am also ok if we start this discussion and arrive on a solution that's quite divergent from the one that's presented here!

Cheers, Manav

---

From: Sam Hartman <[email-masked]>
Date: Fri, 14 Jan 2011 07:34:31 -0500

>>>>> "Michael" == Michael Barnes <[email-masked]> writes:

    Michael> Hi Manav, I wanted to address this point separately.

    Michael> On 01/14/2011 12:55 AM, Bhatia, Manav (Manav) wrote:
    >>> > Regarding the new format for hello packets, is this format to
    >>> be used > only during challenge and response, or for all hello
    >>> packets > when this > new form of authentication is enabled?

    >> This has to be used*all* the time.

    Michael> I'm not very excited about a 3x increase in the number of
    Michael> bytes per neighbor. (For those who haven't read the draft,
    Michael> it changes the Hello packet so that it contains 12 bytes
    Michael> for each neighbor over the current 4 bytes per neighbor.) I
    Michael> have to wonder if this is really necessary for each and
    Michael> every hello packet. I'm certainly not a security expert,
    Michael> but it seems to me that once we have verified the
    Michael> neighbor's session ID we shouldn't continue to need to
    Michael> receive our own session ID and nonce back in every hello
    Michael> packet. Did you consider if this can't be optimized?

We can certainly look at optimizing.  However, note that currently we
don't really have a well defined state of challenging.  You need to look
at a neighbor's idea of your session ID and nonce whenever the state is
not at least two-way.
So, one of the tricky questions is how does a neighbor  know when to
include this information?

We could have separate authentication challenge packets.  However, the
advantage of the current approach is that I think we can get to a point
where we have one or two extra packets total for a cold-start situation,
rather than an extra packet or two per neighbor.  I don't know that the
current rules for receiving and sending packets actually achieve this,
but I believe we can get there with some minor changes.

However, we can definitely think about optimizations.

I believe the current text does actually say that hellos are sent
immediately if we need to challenge someone, at least if we have not
sent a challenge hello too recently.  Take a look at the detailed
description of the section on nonce triggers.

--Sam

---

From: Glen Kent <[email-masked]>
Date: Sun, 16 Jan 2011 03:53:05 +0530

I'll confess that it took me some time to really understand the
challenge protocol that you have introduced and the utility of the
nonce and the session IDs that you are carrying. I attribute that to
the language used in the draft which i think can be considerably
improved. I, as someone else also noted in the list, could not find
the Key ID and the cryptographic sequence number associated with each
packet in the current draft. This was perhaps overwritten by the nonce
and the session details that you have defined. You will have to move
this information out somewhere else and bring back these two
parameters so that this scheme works. Assuming that this can be done,
i must say that this is i believe the first serious attempt at really
solving the inter session replay attacks in any protocol that uses
manual keying.

Kudos to the authors for that. I hope to see this being presented in Prague.

Glen

On Fri, Jan 14, 2011 at 6:04 PM, Sam Hartman <[email-masked]> wrote:
>    >>> > Regarding the new format for hello packets, is this format to
>    >>> be used > only during challenge and response, or for all hello
>    >>> packets > when this > new form of authentication is enabled?
>
>    >> This has to be used*all* the time.
>

---

From: Michael Barnes <[email-masked]>
Date: Wed, 19 Jan 2011 09:35:46 -0800

Hi Sam,

> but I believe we can get there with some minor changes.

I've been giving this some thought, and I think exchanging a couple of 
additional packets in the cold start situation is more desirable than 
overloading the Hello packet with an additional security role. The Hello 
packet already services two very important purposes - discovery and keep 
alive. It is highly desirable not to add to the processing overhead for 
these packets.

Have you and the other authors already given thought to a design using a 
new packet type for challenge/response packets?

Thanks,
Michael

---

From: Sam Hartman <[email-masked]>
Date: Wed, 19 Jan 2011 13:13:24 -0500

>>>>> "Michael" == Michael Barnes <[email-masked]> writes:

    Michael> Hi Sam,
    Michael> On 01/14/2011 04:34 AM, Sam Hartman wrote:
    >> We could have separate authentication challenge packets.
    >> However, the advantage of the current approach is that I think we
    >> can get to a point where we have one or two extra packets total
    >> for a cold-start situation, rather than an extra packet or two
    >> per neighbor.  I don't know that the current rules for receiving
    >> and sending packets actually achieve this, but I believe we can
    >> get there with some minor changes.

    Michael> I've been giving this some thought, and I think exchanging
    Michael> a couple of additional packets in the cold start situation
    Michael> is more desirable than overloading the Hello packet with an
    Michael> additional security role. The Hello packet already services
    Michael> two very important purposes - discovery and keep alive. It
    Michael> is highly desirable not to add to the processing overhead
    Michael> for these packets.

I'd like to understand your concerns here.  Are you concerned about CPU
for processing the hello packet? Bandwidth of the hello packets?  I'd
like to actually get educated about the tradeoffs enough that I can have
an intelligent discussion.

--Sam

---

From: Michael Barnes <[email-masked]>
Date: Wed, 19 Jan 2011 10:37:47 -0800

Hi Sam,

On 01/19/2011 10:13 AM, Sam Hartman wrote:
>>>>>> "Michael" == Michael Barnes<[email-masked]>  writes:
>
>      Michael>  Hi Sam,

I don't think the bandwidth is really an issue, but CPU is. It is 
important that processing of these packets can be completed as quickly 
as possible. We are constantly being asked to scale to ever larger 
number of neighbors and adding overhead to Hello packets could make this 
security mechanism undesirable in those settings.

Regards,
Michael

---

From: Glen Kent <[email-masked]>
Date: Thu, 20 Jan 2011 05:58:53 +0530

Can i request the authors to post a revised ID fixing the
Authentication details in the OSPF header. At present, i am confused
as i dont see the Key ID, Sequence Numbers anywhere in the packets.

I agree that some discussion on overloading of the Hellos must happen.
However, i would also like to see some discussion on whether the
proposed mechanism of Nonces and Session IDs would work. I think that
is the key element in this work. If that is verified then everything
else can be built around that.

Glen

On Thu, Jan 20, 2011 at 12:07 AM, Michael Barnes <[email-masked]> wrote:
>>     >>  We could have separate authentication challenge packets.
>>     >>  However, the advantage of the current approach is that I think we
>>     >>  can get to a point where we have one or two extra packets total
>>     >>  for a cold-start situation, rather than an extra packet or two
>>     >>  per neighbor.  I don't know that the current rules for receiving
>>     >>  and sending packets actually achieve this, but I believe we can
>>     >>  get there with some minor changes.
>>
> I don't think the bandwidth is really an issue, but CPU is. It is important
> that processing of these packets can be completed as quickly as possible. We
> are constantly being asked to scale to ever larger number of neighbors and
> adding overhead to Hello packets could make this security mechanism
> undesirable in those settings.
>
> Regards,
> Michael

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Thu, 20 Jan 2011 06:51:57 +0530

Hi Glen,
 
> as i dont see the Key ID, Sequence Numbers anywhere in the packets.

The revised draft has been updated and posted. Its available here:
http://www.ietf.org/id/draft-bhatia-karp-ospf-ip-layer-protection-02.txt

> else can be built around that.

Yup, I agree!

Cheers, Manav

---

From: Sam Hartman <[email-masked]>
Date: Fri, 21 Jan 2011 09:13:37 -0500

Michael> Hi Sam,
    Michael> Hi Sam,
    Michael> On 01/14/2011 04:34 AM, Sam Hartman wrote:
    >> >> We could have separate authentication challenge packets.  >>
    >> >> can get to a point where we have one or two extra packets
    >> total >> for a cold-start situation, rather than an extra packet
    >> or two >> per neighbor.  I don't know that the current rules for
    >> receiving >> and sending packets actually achieve this, but I
    >> believe we can >> get there with some minor changes.
    >> 
    >> 
    >> I'd like to understand your concerns here.  Are you concerned
    >> about CPU for processing the hello packet? Bandwidth of the hello
    >> packets?  I'd like to actually get educated about the tradeoffs
    >> enough that I can have an intelligent discussion.

    Michael> I don't think the bandwidth is really an issue, but CPU
    Michael> is. It is important that processing of these packets can be
    Michael> completed as quickly as possible. We are constantly being
    Michael> asked to scale to ever larger number of neighbors and
    Michael> adding overhead to Hello packets could make this security
    Michael> mechanism undesirable in those settings.

So, I don't think we can avoid a bit of overhead when we are bringing up
a new neighbor association: we're trying to do new things in that
situation.  I've thought about it and the overhead in that situation of
having the exchange in the hello is less than with extra challenge
response packets.

So, we're left with the question of what's the overhead when we already
have a neighbor relationship That's the common path and so it is our
primary goal for optimization.

I went to read the description of receiver behavior in the draft to
confirm my understanding of what the overhead is.  I found a bug: it
turns out that the behavior of hello packets for neighbors in two-way or
greater is unspecified.  It's intended to be the same as the behavior
for non-hello packets.
So, let's look at what that behavior is:

        <t>If a packet other than a hello is received with the new
        cryptographic authentication option, it must correspond to an existing
        neighbor relationship in at least the 2-way state. If the neighbor is
        not in 2-way state or greater, the packet is discarded. If the session
        ID does not match the session ID recorded with the neighbor, the
        packet is discarded. If the sequence number in the cryptographic
        authentication option is not strictly greater than the sequence number
        associated with the neighbor, then the packet is discarded. If the
        cryptographic verification of the checksum fails, the packet is
        discarded. Otherwise, the packet is accepted by the cryptographic
        authentication and the sequence number associated with the neighbor is
        updated to be the sequence number in the packet.</t>

So, if we update that first sentence to say that section applies to all
packets where the neighbor is in 2-way state or greater, we get correct
behavior.  So, what new overhead do we need?  First, we need a compare
against the neighbor state; if it is not 2-way or greater, we need to go
to a less optimal path.  Then we need to compare the session ID.

That's the only new behavior.  We change the sequence number check from
greater than or equal to to strictly greater than, but on all hardware
I'm aware of, that's the same performance.  So, we've added two
operations to the reception of packets for existing neighbors. The
operations can be executed in parallel. On a general purpose CPU, both
operations would be single instructions.

My opinion is that is likely to be acceptable to any environment where
cryptographic authentication is acceptable.

Note that while we send additional information in a hello packet, we
only need to look at that information when setting up a new neighbor.

So, let's take a look at what we've done to sending a hello packet
because that's also a common operation.

We've added two items of state for each neighbor: the session ID and
nonce. I guess copying these values into a constructed outgoing packet
could be considered per-neighbor overhead. However, an implementation
could choose to construct the neighbor list of the outgoing hello packet
and store it in a buffer, updating only when the neighbor list
changes. So, there is an implementation strategy that does not change
the cost of sending a hello in the steady state.

I'll also note that the effort required for the "slow" path (updating
set of neighbors) is modest: we're talking about a couple of compares
and neighbor structure updates. 

This conversation has been fairly useful.  I've noticed a couple of
places where we can optimize receiver behavior to reduce number of
packets and to improve convirgence in case of reboot.  We might even be
able to optimize what locks you're likely to hold when a bit. (I realize
that where locks are in a data structure is very implementation
dependent, but there are things we can do like minimizing the cases
where fields need to be updated that are valuable here.)

So, I'll work with the other authors to fix the bug I pointed out above
and to improve the receiver behavior.

Now that I've thought about the tradeoffs between challenge packets and
using the hello, I think that the CPU impact of hello packets will be
lower than that of challenge packets. So, my preference is to stick with
our original design.

---

From: Acee Lindem <[email-masked]>
Date: Fri, 21 Jan 2011 18:52:29 -0500

Hi Manav,

I've finally read this draft and I'm less enamored with it than Michael. I think the requirement to protect the source address is valid. However, I think the assumptions regarding sequence number management which are used to justify the challenge/nouce are flawed. 
If you tie the sequence number to the clock (which I'd guess most rational implementations already do), then there is no reason for this nouncense :^).  Even with a 32 sequence number, one could increment it every 1/10 second and get 13.3 years since the last cold boot. If you were willing to live with 1 second between sequence number increments, you'd get 133 years. 
Furthermore, since a new auth type will be required to protect the source address, the sequence number could also be extended to 64 bits to allow for greater precision. 

Thanks,
Acee 

On Jan 13, 2011, at 11:59 PM, Michael Barnes wrote:

> Hello Manav,
> 
> First I want to applaud you and your co-authors for addressing these security problems for OSPF. Thank you.
> 
> During the challenge and response are the hello packets sent immediately to each other or by the standard hello timer?
> 
> During the challenge and response on a broadcast links, are the packets unicast or multicast?
> 
> Regarding the new format for hello packets, is this format to be used only during challenge and response, or for all hello packets when this new form of authentication is enabled?
> 
> RFC2328 defines the AuType field, you've chosen to rename it to AuthType. I suggest we continue to use AuType for continuity.
> 
> In the figures which illustrate the header and hello packet fields, I suggest that instead of showing two words as just "Authentication" that the figure shows the sub-fields. In the context of this specification those words will have a single definition, so there is no reason to leave them loosely defined.
> 
> OSPF mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ospf

---

From: Glen Kent <[email-masked]>
Date: Sat, 22 Jan 2011 06:22:48 +0530

Hi Acee,

Is it reasonable to assume that the router will never reboot (crash,
upgrade and maintenance, etc). If it is then i believe this is a
better alternative and the authors should consider this.

Glen

---

From: Sam Hartman <[email-masked]>
Date: Sat, 22 Jan 2011 15:33:30 -0500

>>>>> "Acee" == Acee Lindem <[email-masked]> writes:

    Acee> Hi Manav, I've finally read this draft and I'm less enamored
    Acee> with it than Michael. I think the requirement to protect the
    Acee> source address is valid. However, I think the assumptions
    Acee> regarding sequence number management which are used to justify
    Acee> the challenge/nouce are flawed.  If you tie the sequence
    Acee> number to the clock (which I'd guess most rational
    Acee> implementations already do), then there is no reason for this
    Acee> nouncense :^).  Even with a 32 sequence number, one could
    Acee> increment it every 1/10 second and get 13.3 years since the
    Acee> last cold boot. If you were willing to live with 1 second
    Acee> between sequence number increments, you'd get 133 years.
    Acee> Furthermore, since a new auth type will be required to protect
    Acee> the source address, the sequence number could also be extended
    Acee> to 64 bits to allow for greater precision.

I think it's fairly obvious that to protect against the replay attacks
OSPF needs to require strictly increasing sequence numbers.  No matter
how small you slice it if two packets are ever sent with the same
sequence number, an attacker can do significant damage.
That's obviously true for database packets, but is generally true for
hellos as well.

However, if you are willing to base things on the time, you can have a
timestamp plus a packet counter.  You give up a few things for that.  If
you ever need to roll a clock back a significant period, you will lose
the adjacency. In addition, you will introduce significant DOS
opportunities unless you rekey the link.  These will last until the time
catches up and becomes greater than any time ever used.

You also lose protection against nodes that are down.  I'm reasonably
sure that you could get a 2-way association up simply by replaying
packets.  I'd need to think about how the database sequence numbers are
generated to understand whether you could actually manage to inject a
route with replays from a down node.  You could defend against this by
requiring that the clocks be synchronized within some period, not just
strictly increasing.

So, yes, there are simpler options than a challenge/response protocol if
you are willing to require clocks loosely synchronized to real time.

---

From: Acee Lindem <[email-masked]>
Date: Sun, 30 Jan 2011 15:12:53 -0500

On Jan 30, 2011, at 12:55 PM, Jack Kohn wrote:

> Acee:
> 
>> I've finally read this draft and I'm less enamored with it than Michael. I think the >
>> requirement to protect the source address is valid. However, I think the assumptions
> 
> Yes, i agree and there has been a discussion that this should be done.
> 
>> regarding sequence number management which are used to justify the challenge/nouce
>> are flawed.
> 
> And why do you think this is flawed?
> 
>> If you tie the sequence number to the clock (which I'd guess most rational
>> implementations already do), then there is no reason for this nouncense :^).  Even with a
> 
> You should not tie anything to the clock since the time can go back.
> This is also one reason why we dont use the clock to give us the
> sequence numbers for regular OSPF and IS-IS.

I wasn't suggesting using the time of day clock but the system clock (which will never go backwards and is required for other reasons). 

However, I can see that a patient enough attacker could simply wait for a cold start using the same manual key. 

Given how much extra signaling and complexity is required in this solution, it may better to wait for a solution to the manual keying problem.  

Acee 

> Jack

---

From: Jack Kohn <[email-masked]>
Date: Sun, 30 Jan 2011 23:25:31 +0530

Jack