Subject: Re: [RPSEC] BGP Security Requirements Document

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 28 Dec 2004 14:02:59 +0100

[Catching up... Does anyone have working URLs for the documents under 
discussion the past months?]

On 16-nov-04, at 4:20, Russ White wrote:

> +----B---+
> |    |   |
> A    |   C
> |    |   |
> +----D---+

> -- D owns 10.1.0.0/16.
> -- D suballocates 10.1.1.0/24 to A. D can provide a certificate 
> proving this suballocation to any and all interested parties in the 
> network--this, we can all agree on.
> -- A determines it would like to advertise 10.1.1.0/24 to D and B, but 
> would not like B to readvertise 10.1.1.0/24 to C. A therefore marks, 
> in some way, it's route to B so B cannot readvertise 10.1.1.0/24. We 
> don't care how this marking works, just so long as we assume such a 
> marking exists, and B will always honor this marking.

BGP has no way to make this happen today, unless B has configured 
community support for this.

(I'm not a big fan of the word "readvertise" in this context, BTW.)

> -- D continues to advertise 10.1.0.0/16 to B.
> -- B continues to adveritse 10.1.0.0/16 to C

> Now, a series of questions:

> -- Does 10.1.0.0/16 contain 10.1.1.0/24? I assume the answer is yes.

> -- Does B, in fact, "gain authorization" to advertise 10.1.1.0/24 as a 
> part of "gaining authorization" to advertise 10.1.0.0/16? Yes.

> -- Can A, then, prevent B from advertising 10.1.1.0/24? No, as long as 
> we agree that 10.1.1.0/24 is a part of 10.1.0.0/16.

> In what sense, then, is A "given" the address space 10.1.1.0/24? D is 
> still advertising it, without A's consent, correct? Either we must 
> specify that D can no longer advertise address space it has 
> suballocated (in other words, there can be no overlapping 
> advertisements in the protocol), or the concept of "ownership" in this 
> case is looser than we are expecting. In fact, the concept of 
> "ownership" of address space, in this context, prevents A from ever 
> controlling where address space it "owns" is avertised.

[...]

> If you can find some hole in the logic, other than asserting that A 
> shouldn't have such a policy, or that it all works without 
> aggregation, and we can't expect the aggregation case to work anyway, 
> then I would like to hear it.

(I think that trying to express policies that disallow ASes further 
upstream from advertising stuff to ASes even further upstream is a road 
that doesn't lead anywhere useful.)

However, you pose a very interesting question. It sure looks like a lot 
of people are assuming the following addressing hierarchy:

ICANN -> RIRs -> origin AS

The problem with this model is that it doesn't allow for aggregation of 
any kind, and now that routing table growth has kicked into a somewhat 
higher gear again, this is really a child we shouldn't throw out with 
the bath water.

Note that today aggregation doesn't work very well as there is no 
reasonable way to do it automatically. Either I have to configure that 
96.0.0.0/8 and 97.0.0.0/8 are always aggregated into 96.0.0.0/7, or it 
never happens. What I as an operator want, is that aggregation happens 
if the underlying BGP attributes are the same or close enough, and if 
they aren't, it doesn't happen. However, adding these mechanisms to BGP 
isn't trivial as it requires exceptions to the longest match first rule 
to be useful across AS boundaries.

If we want to do this, it makes sense to propagate aggregates with 
holes in them as aggregates with holes in them, i.e., it would be 
possible to advertise "10.1.0.0/16 except 10.1.1.0/24". But in order 
for this to work well, an AS that sees both this route and 10.1.1.0/24 
would have to be able to propagate 10.1.0.0/16 _without_ the exception, 
which is an "interesting" thing to do, authorization wise.

All of this begs the question: if we're going to rebuild so many parts 
of BGP, wouldn't it make more sense to start with a clean slate? It 
would be great if we could separate the authenticity and authorization 
issues from the reachability issues. This would increase performance 
and decrease complexity.

_______________________________________________
RPSEC mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rpsec

---

From: Russ White <[email-masked]>
Date: Tue, 28 Dec 2004 08:12:42 -0500 (Eastern Standard Time)

> (I'm not a big fan of the word "readvertise" in this context, BTW.)

I don't know of a better word. Wish I could think of one, then I'd be 
famous (not rich, but at least halfway towards the dream of all mankind, it 
seems! :-) ).

>> In what sense, then, is A "given" the address space 10.1.1.0/24? D is still 
>> advertising it, without A's consent, correct? Either we must specify that D 
>> can no longer advertise address space it has suballocated (in other words, 
>> there can be no overlapping advertisements in the protocol), or the concept 
>> of "ownership" in this case is looser than we are expecting. In fact, the 
>> concept of "ownership" of address space, in this context, prevents A from 
>> ever controlling where address space it "owns" is avertised.

> higher gear again, this is really a child we shouldn't throw out with the 
> bath water.
>
> never happens. What I as an operator want, is that aggregation happens if 
> the underlying BGP attributes are the same or close enough, and if they 
> aren't, it doesn't happen. However, adding these mechanisms to BGP isn't 
> trivial as it requires exceptions to the longest match first rule to be 
> useful across AS boundaries.

http://www.ietf.org/internet-drafts/draft-hardie-bounded-longest-match-05.txt

There should actually be a later version available, but I can't seem to 
find it (?).

:-)

Russ

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

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 28 Dec 2004 14:31:12 +0100

> famous (not rich, but at least halfway towards the dream of all  
> mankind, it seems! :-) ).

I would describe this as "announcing an aggregate covering a more  
specific" but typing that all the time gets time consuming of course...

>> reasonable way to do it automatically. Either I have to configure  
>> that 96.0.0.0/8 and 97.0.0.0/8 are always aggregated into 96.0.0.0/7,  
>> or it never happens. What I as an operator want, is that aggregation  
>> happens if the underlying BGP attributes are the same or close  
>> enough, and if they aren't, it doesn't happen. However, adding these  
>> mechanisms to BGP isn't trivial as it requires exceptions to the  
>> longest match first rule to be useful across AS boundaries.

> There should actually be a later version available, but I can't seem  
> to find it (?).

Didn't you co-write it??

Unfortunately, you don't address the part that I'm concerned about in  
this draft: if I receive an aggregate from ISP1 and the original route  
from ISP2, longest match first dictates that I must always use ISP2.  
With the draft in effect I'd use ISP1. The latter case can be harmful  
if there is no reachability through ISP1 (which I can't tell from  
looking at the aggregate) and in both cases I don't get to distribute  
traffic as per my choice.

Now obviously the way this is done today (where I get the aggregate  
from one ISP and the more specific from both) isn't what we want. A  
good step in the right direction would be to be able to compare the  
attributes of the aggregate and the more specific without taking the  
prefix length into account. And in order to be able to avoid  
unreachability within an aggregate, we need to know either a list of  
exceptions, or at least whether or not exceptions exist.

---

From: Russ White <[email-masked]>
Date: Tue, 28 Dec 2004 08:47:16 -0500 (Eastern Standard Time)

> I would describe this as "announcing an aggregate covering a more specific" 
> but typing that all the time gets time consuming of course...

Another place where we need to invent a word, I suppose... :-)

>> There should actually be a later version available, but I can't seem to 

Yes, I have a later version locally, but I'm not certain what happened to 
the posting. :-)

> from ISP2, longest match first dictates that I must always use ISP2. With 
> the draft in effect I'd use ISP1. The latter case can be harmful if there 
> is no reachability through ISP1 (which I can't tell from looking at the 
> aggregate) and in both cases I don't get to distribute traffic as per my 
> choice.

Actually, that isn't true, the way the draft is currently written. You have 
to have the overlap on a single router, so you have to have the aggregate 
plus the component on a single route to mark the component as not 
advertised. This is because you want to make certain you have the same next 
hop for both the aggregate and the component. The draft also knocks out the 
component learned on other edges, but you have to do that, in order to keep 
the component from being advertised at the outbound edge.

We've also discussed doing the overlapping check on the outbound edge, but 
we decided against it, for some reason that I can't remember at this point.

> Now obviously the way this is done today (where I get the aggregate from 
> one ISP and the more specific from both) isn't what we want. A good step 
> in the right direction would be to be able to compare the attributes of 
> the aggregate and the more specific without taking the prefix length into 
> account. And in order to be able to avoid unreachability within an 
> aggregate, we need to know either a list of exceptions, or at least 
> whether or not exceptions exist.

The problem is you don't always know what the exceptions are, to generate 
them. Longest match routing works because you assume either one of two 
things about each possible aggregate:

-- It can reach all the destinations implied in the aggregate.

-- Destinations it cannot reach are simply unreachable (nonexistant).

Most of the time, the exception to these two assumptions involves 
policy--yes, x _is_ reachable along this path, but I don't want it to be 
reached along this path--rather than actual reachability problems. In other 
words, I don't know of any case where these two aren't true where filtering 
of routing information within an aggregate isn't involved, as well (?). At 
that point, we spiral down the long rathole of filtering, and the other 
possible bad side effects of it, etc, etc.... :-)

<technically, this part of the conversation should probably be moved to 
GROW, but since GROW won't accept the bounded-longest-match draft as a WG 
item, I don't think there's much interest there in this set of problems?>

:-)

Russ

---

From: "Stephen J. Wilcox" <[email-masked]>
Date: Tue, 28 Dec 2004 14:16:10 +0000 (GMT)

On Tue, 28 Dec 2004, Iljitsch van Beijnum wrote:

> Note that today aggregation doesn't work very well as there is no reasonable
> way to do it automatically. Either I have to configure that 96.0.0.0/8 and
> 97.0.0.0/8 are always aggregated into 96.0.0.0/7, or it never happens. What I
> as an operator want, is that aggregation happens if the underlying BGP
> attributes are the same or close enough, and if they aren't, it doesn't
> happen. However, adding these mechanisms to BGP isn't trivial as it requires
> exceptions to the longest match first rule to be useful across AS boundaries.

this is only useful for leaf networks, transit networks will NOT want this to 
occur as longest match will ensure that their competitors routes are installed. 
but if i'm a leaf network i have a bag of tricks to reduce the routing table 
anyway eg filter aggressively and default to upstreams. therefore i dont think 
auto-aggregation by anyting but the source is useful.

> If we want to do this, it makes sense to propagate aggregates with holes in
> them as aggregates with holes in them, i.e., it would be possible to advertise
> "10.1.0.0/16 except 10.1.1.0/24". But in order for this to work well, an AS
> that sees both this route and 10.1.1.0/24 would have to be able to propagate
> 10.1.0.0/16 _without_ the exception, which is an "interesting" thing to do,
> authorization wise.

this equates to advertising two routes - route /16, ignore /24 - which seems to 
suggest you increase the amount of bgp data being propagated and also the amount 
of processing when switching packets (both forward and drop routes would need to 
be installed into the routing and forwarding table of routers).

> All of this begs the question: if we're going to rebuild so many parts of BGP,
> wouldn't it make more sense to start with a clean slate? It would be great if
> we could separate the authenticity and authorization issues from the
> reachability issues. This would increase performance and decrease complexity.

Well, thats a whole different question. But even if you create BGP-5 I dont see 
how you are addressing the fundemental issues

Steve

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 28 Dec 2004 17:43:11 +0100

On 28-dec-04, at 15:16, Stephen J. Wilcox wrote:

>> reasonable
>> way to do it automatically.

[...]

>> However, adding these mechanisms to BGP isn't trivial as it requires

> occur as longest match will ensure that their competitors routes are 

Hence the need to modify the longest match first rule. If it's only 
useful in leaf networks there is little point:

> anyway

>> holes in
>> them as aggregates with holes in them, i.e., it would be possible to 
>> advertise "10.1.0.0/16 except 10.1.1.0/24".

> this equates to advertising two routes - route /16, ignore /24

Or more. Worst case would be 129: a /16 and alternating /24 
holes/non-holes. (Assuming /24 as the longest usable prefix.)

> which seems to suggest you increase the amount of bgp data being 
> propagated

Yes. This would only be useful if there are also (bigger) savings 
somewhere else. Note that these holes could be encoded quite 
efficiently in on or more bitmaps, so the above worst case would be a 
regular /16 route along with a 32 byte bitmap.

These savings would happen if the holes + more specifics are only 
present in part of the network, and only a single aggregate is present 
elsewhere.

> and also the amount of processing when switching packets (both forward 
> and drop routes would need to be installed into the routing and 
> forwarding table of routers).

Well, either you don't care about the holes and your tables will be 
smaller, or you do care and there is more stuff in your tables. But 
with an n-way trie it's hard to tell the difference, as long as you 
have the memory... With what we have today there is no choice.

>> All of this begs the question: if we're going to rebuild so many 
>> parts of BGP, wouldn't it make more sense to start with a clean 
>> slate?

> Well, thats a whole different question. But even if you create BGP-5 I 
> dont see how you are addressing the fundemental issues

The fundamental issues have been discussed here in this wg for some 
time, especially the problem of how the source of a route / destination 
of a packet gets the destination of a route / source of a packet from 
using the route by sending a packet for individual ASes beyond the 
immediate next hop AS. This essentially takes us outside the realm of 
hop-by-hop routing, but, from RFC 1771:

   "To characterize the set of policy decisions that can be enforced
    using BGP, one must focus on the rule that a BGP speaker advertise to
    its peers (other BGP speakers which it communicates with) in
    neighboring ASs only those routes that it itself uses.  This rule
    reflects the "hop-by-hop" routing paradigm generally used throughout
    the current Internet.  Note that some policies cannot be supported by
    the "hop-by-hop" routing paradigm and thus require techniques such as
    source routing to enforce.  For example, BGP does not enable one AS
    to send traffic to a neighboring AS intending that the traffic take a
    different route from that taken by traffic originating in the
    neighboring AS.  On the other hand, BGP can support any policy
    conforming to the "hop-by-hop" routing paradigm."

I haven't read any drafts as I seem to have managed to miss any working 
links to them, but from the discussion here it's clear that we're not 
just talking about making what BGP does today secure, but rather make 
securely what we think BGP should have been doing all along.

---

From: Stephen Kent <[email-masked]>
Date: Tue, 28 Dec 2004 11:54:09 -0500

Iljitsch,

>	<SNIP>
>However, you pose a very interesting question. It sure looks like a 
>lot of people are assuming the following addressing hierarchy:
>

Not sure exactly what you are referring to here. There is an 
important distinction between an address allocation hierarchy, and 
the ability to determine who is authorized to advertise itself as an 
orign AS.

In the papers we've written on BGP security, we do describe an 
address allocation hierarchy that is rooted at ICANN and that goes 
through RIRs to ISPs (or subscribers), etc.  We also note that some 
subscribers get allocations directly from an RIR. Do you think that 
this is an inaccurate model for allocation?

With regard to the authorization to advertise an AS as an origin for 
a prefix, we understand that one needs an explicit authorization 
mechanism, one that accommodates dual homing, subscribers who leave 
ISPs and take their addresses with them, etc.  S-BGP includes a 
mechanism that accommodates this.

>The problem with this model is that it doesn't allow for aggregation 
>of any kind, and now that routing table growth has kicked into a 
>somewhat higher gear again, this is really a child we shouldn't 
>throw out with the bath water.

You are right that a simplistic model, one that looks only at address 
allocation, and does not take into account the various ways that an 
AS can be authorized to originate prefixes, also would be unlikely to 
accommodate aggregation.

>	<SNIP>
>slate? It would be great if we could separate the authenticity and 
>authorization issues from the reachability issues. This would 
>increase performance and decrease complexity.

I'm not sure what you mean by this last paragraph. When we approached 
BGP security we did so cognizant of the limitations of the extant 
protocol. We started from the premise of what a speaker assumes is 
true when it gets an Update, and then worked from that basis to 
determine what the security requirements were, and then proposed 
mechanisms to satisfy those requirements.

In the BGP context, we are interested in authentication, integrity, 
and authorization only to the extent that the support the goal of 
allowing a speaker to verify inputs to the reachability/routing 
computation.

Anothr way of saying this, that I think we should articulate in the 
document (if there is agreement) is that main purpose of BGP security 
should be to enable speakers to verify Updates, because speakers make 
routing (reachability) decisions based on a combination of dynamic 
info from Updates and static config data. That suggests a two-pronged 
approach, one that provides a speaker with data to verify the dynamic 
aspects of an Update, and one that supports distribution of (static) 
data to support verification of the less dynamic aspects of an Update.

Steve

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 29 Dec 2004 13:20:41 +0100

Steve,

> Not sure exactly what you are referring to here.

Russ is concerned with the situation where it's like:

ICANN -> RIRs -> ISP -> origin AS

If this is just the allocation chain, that's not a problem, but if the 
ISP also sources an aggregate that covers the prefix sourced by "origin 
AS" things get complicated.

> In the papers we've written on BGP security, we do describe an address 
> allocation hierarchy that is rooted at ICANN and that goes through 
> RIRs to ISPs (or subscribers), etc.  We also note that some 

Not necessarily "inaccurate", but things can be a bit more complex in 
the real world. The only thing we know for sure is that there is always 
ICANN/IANA at one end and the origin AS at the other end. There is a 
RIR involved most of the time. Then there are NIR (national internet 
registries, mostly in the APNIC region) and LIRs (=== ISPs) which are 
both optional. There is also a distinction between the address holder 
(not owner, as addresses can't be owned as per RIR policy) and the 
origin AS. For instance, an organization with portable address space 
may have it announced by the ISP du jour, or the address holder can 
lend the address space to another organization that then announces it 
without actually transferring the address space.

> mechanisms to satisfy those requirements.

In other words, you added jet engines to the pig.  :-)

> data to support verification of the less dynamic aspects of an Update.

The way I see it, there are four topologies, each a subset of the 
previous one:

- the logical topology determined by the way BGP speakers are 
interconnected
- the topology that's allowed by policy
- the topology for which authorization can be verified successfully
- the actually reachable topology

I would be much happier if we had mechanisms other than the update 
message to build topology maps for the first three.

---

From: Stephen Kent <[email-masked]>
Date: Wed, 29 Dec 2004 14:02:32 -0500

At 1:20 PM +0100 12/29/04, Iljitsch van Beijnum wrote:
>>>However, you pose a very interesting question. It sure looks like 
>>>a lot of people are assuming the following addressing hierarchy:
>
>If this is just the allocation chain, that's not a problem, but if 
>the ISP also sources an aggregate that covers the prefix sourced by 
>"origin AS" things get complicated.

In the papers we have published, it is always described just as an 
allocation chain, and thus a suitable basis for a PKI.

>Not necessarily "inaccurate", but things can be a bit more complex 
>in the real world. The only thing we know for sure is that there is 
>always ICANN/IANA at one end and the origin AS at the other end. 
>There is a RIR involved most of the time. Then there are NIR 
>(national internet registries, mostly in the APNIC region) and LIRs 
>(=== ISPs) which are both optional. There is also a distinction 
>between the address holder (not owner, as addresses can't be owned 
>as per RIR policy) and the origin AS. For instance, an organization 
>with portable address space may have it announced by the ISP du 
>jour, or the address holder can lend the address space to another 
>organization that then announces it without actually transferring 
>the address space.

Yes, I omitted the NIRs and LIRs for simplicity, but they are easy to 
accommodate in a PKI that parallels the allocation chain.  And yes, I 
tend to use "owner" too loosely; "holder" is the more appropriate 
term. We recognize the fact the address holder may not be the origin 
AS, and thus needs to explicitly authorize some AS to originate the 
address prefix he holds. in the S-BGP work there is no notion of the 
name of the address prefix holder, only the fact that someone to whom 
an RIR/NIR/LIR/ISP allocated a prefix has signed an attestation for 
some time interval identifying an AS to advertise the prefix. So even 
the lending of addresses is accommodated.

>>I'm not sure what you mean by this last paragraph. When we 
>>approached BGP security we did so cognizant of the limitations of 
>>the extant protocol. We started from the premise of what a speaker 
>>assumes is true when it gets an Update, and then worked from that 
>>basis to determine what the security requirements were, and then 
>>proposed mechanisms to satisfy those requirements.
>

yes, but they're really cool engines :-)

>>document (if there is agreement) is that main purpose of BGP 
>>security should be to enable speakers to verify Updates, because 
>>speakers make routing (reachability) decisions based on a 
>>combination of dynamic info from Updates and static config data. 
>>That suggests a two-pronged approach, one that provides a speaker 
>>with data to verify the dynamic aspects of an Update, and one that 
>>supports distribution of (static) data to support verification of 
>>the less dynamic aspects of an Update.
>
>- the logical topology determined by the way BGP speakers are interconnected

Our goal in S-BGP was to create an infrastructure and  mechanism that 
would allow #3 to match #4, in realtime. Building maps for the first 
three is tough, especially since I have bee told that many ISPs do 
not wish to divulge local policy info that is needed to represent #2. 
Also it seems likely that topology maps are not a good way to 
represent the dynamic status implied by #4. If we use anything other 
than Updates to convey data for #4, then there will always be sync 
problems.  But yes, I agree, that, from a technical perspective, one 
could create maps for #2, and try to create a security infrastructure 
to transform this into #3. What you would have then is a bound on the 
extent to which an AS compromise or configuration errors would be 
tolerated by other ASes participating in the security scheme.

Steve