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

From: Sam Hartman <[email-masked]>
Date: Tue, 01 Feb 2011 19:11:10 -0500

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

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

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

I think there are three solutions:

1) Require a time-of-day clock and have significant consequences when it
goes backwards. This solution tends to also permit attackers to keep an
adjacency alive when it goes down. So an attacker can prevent fail-over
to redundant links.

2) Some sort of freshness exchange, like the one Dacheng, Manav and I
are putting together. We can probably do better in terms of reducing
signaling than we do now.
However  I think you'll have to introduce a couple of extra packets
whenever an adjacency is lost before any new adjacencies can be
introduced.

3) Use automated key management.  Note that automated key management
will probably be as chatty as option 2 in the election phase.

I personally think that option 1 is not acceptable unless we find a
solution to the fail-over prevention.

I'd like to understand your objections to our approach in option 2.
Is it number of extra packets? Is it just that it feels really complex?
Any chance you'd be up for an Im session or phone call to brainstorm
what the minimum complexity is and see whether it's that you think the
problem is too expensive to solve or just that our solution is too
expensive?

---

From: Acee Lindem <[email-masked]>
Date: Tue, 1 Feb 2011 21:46:46 -0500

> adjacency alive when it goes down. So an attacker can prevent fail-over

While most modern routers have a clock with fine enough granularity that will never go backwards, it is typically not preserved across cold restarts. 
If one used a 64 bit sequence number (for the required precision) and had a relative clock that was never reset, it would fit the bill. 

> Is it number of extra packets?

For one thing, I don't like the fact that multicast hellos contain the session ID and nounce for every router on the network (as shown in figure 6). 

> Is it just that it feels really complex?

I won't be able to do this before the IETF in Prague as I already have too many things left undone. However, I will at least make it a point to understand the proposal better before the meeting. 

Thanks,
Acee

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Wed, 2 Feb 2011 08:23:37 +0530

Hi Acee,

> While most modern routers have a clock with fine enough 
> granularity that will never go backwards, it is typically
>  not preserved across cold restarts. 
> If one used a 64 bit sequence number (for the required precision)
>  and had a relative clock that was never reset, it would fit the bill. 

One could store this value in a non volatile memory so that its also preserved across cold rebootd but I don't this would be an acceptable solution. Or would it be?

[clipped]

> For one thing, I don't like the fact that multicast hellos 
> contain the session ID and nounce for every router on the
>  network (as shown in figure 6). 

If this is the only thing that you don't like then I am sure this is something that could be optimized. I think the bigger question is if the WG thinks that our current proposal of using Session IDs and Nonces along with the crypto sequence numbers *will* work? If we have an agreement there, then optimizing the bits on wire may not be very difficult.

> I won't be able to do this before the IETF in Prague as I 
> already have too many things left undone. However, I will 
> at least make it a point to understand the proposal better before the meeting.

That'll be very good.

Cheers, Manav

---

From: Glen Kent <[email-masked]>
Date: Wed, 2 Feb 2011 17:50:40 +0530

Hi Acee,

> For one thing, I don't like the fact that multicast hellos contain the
> session ID and nounce for every router on the network (as shown in figure
> 6).

I dont understand this concern; I see several service providers
running OSPF in point-to-point mode even on ethernet links because
nobody wants the complexity of DR and bDR that one gets on a broadcast
medium. Even if they dont do this i have never seen large LANs with
lots of OSPF neighbors chatting away till glory. The point that i am
trying to make is that you will never see an OSPF hello message with
lots of neighbors. Given this, i think the whole concern about adding
extra information in hellos is moot.

Glen

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Wed, 2 Feb 2011 18:28:28 +0530

Hi Rajesh,

> Pre-Condition:  Nonce stable in the network (no new 
> neighbors) and single
> key ID with infinite life time is used. 

Sure!

>  
> Scenario:
> Initially Session ID X is used between router A and Router B and when
> sequence space exhausts in router A, router A will start 
> sending the packet
> with Session ID Y. On receiving packet with Session ID Y, 

Router A will also change the Nonce from N to N' when it changes the Session ID.

> Router B will
> Update Y as router A Session ID (after validating Nonce and 
> auth checksum.
> Sequence number cannot be checked since wrap around scenario).

Router B will also change its own Nonce from Nold to Nnew. It has to do this because it will need to challenge A when it sees a new Session ID from A. It needs to know if its indeed A or somebody else replaying an old packet from A. When it sees the new Session ID from A, B will include a new Nonce in its HELLOs and still carry the old Session ID and Nonce values that it had heard from A.

A upon receiving this would respond with a HELLO citing the new Nonce that it has heard from B. 

B upon seeing its new Nonce in A's HELLO would update its HELLO to include the new Session ID and Nonce from A.

> 
> Now attacker Replays session ID X Packet and brings the 
> adjacency down in
> the below sequence. Attacker Replays two way Hello which is 
> having Session
> ID X to Router B.On receiving packet with Session ID X, 

When somebody replays this packet B will again challenge it with a new Nonce value. You will not be able to attack as you need to use the new nonce value in your subsequent packets. This is also one reason why we were keeping both the Nonce and the Session IDs in all the packets.

> Router B will Update
> X as router A Session ID(after checking Nonce and auth 
> checksum.sequence
> number cannot be checked). Now attacker sends Initial DD Packet having
> Session ID X and brings the adjacency down.
> 
> FYI: As per the draft:"When the sequence space is exhausted, 
> a router simply
> chooses a new session ID".

.. and a new Nonce. If this isnt there in the draft then it must be added.

Cheers, Manav

---

From: Sam Hartman <[email-masked]>
Date: Wed, 02 Feb 2011 08:01:52 -0500

It's quite possible that this bug exists in the current draft.  I'll
check when I'm editing receiver behavior later today or the next couple
of days.

I think the issue is handled if we make sure that the nonce is updated
before a hello is accepted that would change the session ID.
I agree the current text does not say to do this.
however would it fix the problem?

--Sam

---

From: "Bhatia, Manav (Manav)" <[email-masked]>
Date: Wed, 2 Feb 2011 18:39:16 +0530

Yup, when we were designing this mechanism we had discussed that Nonce must get updated each time a Session ID or something significant changes. It may have dropped out when converting that discussion into the draft format.

Cheers, Manav 

> -----Original Message-----
> From: Sam Hartman [mailto:[email-masked]] 
> Sent: Wednesday, February 02, 2011 6.32 PM
> To: Rajesh Shetty
> Cc: Bhatia, Manav (Manav); [email-masked]; 'Sam Hartman'; [email-masked]
> Subject: Re: [OSPF] [karp] Security Extension for OSPFv2 when 
> using Manual KeyManagement
>

---

From: "t.petch" <[email-masked]>
Date: Wed, 2 Feb 2011 12:53:32 +0100

----- Original Message -----
From: "Bhatia, Manav (Manav)" <[email-masked]>
To: "Acee Lindem" <[email-masked]>; "Sam Hartman" <[email-masked]>
Cc: <[email-masked]>; <[email-masked]>; <[email-masked]>
Sent: Wednesday, February 02, 2011 3:53 AM

> One could store this value in a non volatile memory so that its also preserved
across cold rebootd but I don't this would be an acceptable solution. Or would
it be?

SNMPv3 introduces a requirement for non-volatile memory in which to store
snmpEngineID and snmpEngineBoots [RFC3411] in order to avoid the
requirement for a real time clock.  I do not know how strictly this
requirement is being implemented.

Tom Petch

<snip>

>
>
> Cheers, Manav
> _______________________________________________
> OSPF mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ospf

---

From: Rajesh Shetty <[email-masked]>
Date: Wed, 02 Feb 2011 17:58:02 +0530

Dear All,

possible security threats in the sequence space exhaust scenario.Please
check.

Pre-Condition:  Nonce stable in the network (no new neighbors) and single
key ID with infinite life time is used. 
 
Scenario:
Initially Session ID X is used between router A and Router B and when
sequence space exhausts in router A, router A will start sending the packet
with Session ID Y. On receiving packet with Session ID Y, Router B will
Update Y as router A Session ID (after validating Nonce and auth checksum.
Sequence number cannot be checked since wrap around scenario).

Now attacker Replays session ID X Packet and brings the adjacency down in
the below sequence. Attacker Replays two way Hello which is having Session
ID X to Router B.On receiving packet with Session ID X, Router B will Update
X as router A Session ID(after checking Nonce and auth checksum.sequence
number cannot be checked). Now attacker sends Initial DD Packet having
Session ID X and brings the adjacency down.

FYI: As per the draft:"When the sequence space is exhausted, a router simply
chooses a new session ID".

Thanks
Rajesh

This e-mail and attachments contain confidential information from HUAWEI,
which is intended only for the person or entity whose address is listed
above. Any use of the information contained herein in any way (including,
but not limited to, total or partial disclosure, reproduction, or
dissemination) by persons other than the intended recipient's) is
prohibited. If you receive this e-mail in error, please notify the sender by
phone or email immediately and delete it!

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Bhatia, Manav (Manav)
Sent: Thursday, January 20, 2011 6:52 AM
To: Glen Kent; Michael Barnes
Cc: [email-masked]; Sam Hartman; [email-masked]
Subject: Re: [OSPF] [karp] Security Extension for OSPFv2 when using Manual
KeyManagement

Hi Glen,
 
> 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.

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

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

Yup, I agree!

Cheers, Manav

---

From: Acee Lindem <[email-masked]>
Date: Wed, 2 Feb 2011 11:49:04 -0500

Hi Tom, Manav,

> requirement is being implemented.

I don't think we can put a requirement on the underlying hardware platform to solve this replay problem. A non-decreasing clock tick value is normally available on router platforms (for many other reasons) but the hardware to preserve it indefinitely is not. If one must preserve it manually with software, it decreases the attractiveness of the clock tick as a 64 bit sequence number since it needs to be updated very frequently in order to provide the required granularity. 

Thanks,
Acee

---

From: Michael Barnes <[email-masked]>
Date: Mon, 28 Feb 2011 18:14:21 -0800

Hi Sam,

On 01/21/2011 06:13 AM, Sam Hartman wrote:
>>>>>> "Michael" == Michael Barnes<[email-masked]>  writes:
>
>      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.

I do have a concern which I don't think you addressed. The size of the 
packet may have increased significantly (for some link types we may have 
more than a handful of neighbors). So when considering a stable link it 
may be hundreds of thousands of Hello packets exchanged for a given 
interface where that extra data is not needed yet the hash algorithm 
must be run, on both sender and receiver, for all of that unused data. 
Multiply by dozens or perhaps even hundreds of interfaces. I disagree 
that over the long term the CPU impact will be lower than if challenge 
response packets were used. I'm not really happy about wasting CPU 
cycles that way.

Regards,
Michael