Subject: [RPSEC] Back to the Basics: The AS Path

From: Russ White <[email-masked]>
Date: Sat, 22 Jan 2005 08:37:07 -0500 (Eastern Standard Time)

Sandy:

My last message last night actually drove me back into the BGP
specification, to discover what the specification really says. Note that
throughout this email, I've used your preferred wording, using the term
"update" as if updates were transitive objects being sent through a BGP
network, and I've attempted to be as precise as possible in all definitions
and wordings.

Now, if we are going to claim something close to this as a requirement:

"On receiving an update, any proposed solution MUST verify the update has
passed through the pairwise peerings represented by the AS Path attribute
contained in the update."

With this as our basis:

"Because the specification says so."

Then I think we should really go look at the specification, and see what it
actually says, no? I used the most current version of the specification,
currently in line for draft-standard state, which I found here:

http://www.ietf.org/internet-drafts/draft-ietf-idr-bgp4-26.txt

On searching the document for all occurances of the words: "as_path," or:
"as path," I found only a few instances. The one I _believe_ is relevant is
here, on page 25:

        b) When a given BGP speaker advertises the route to an external
        peer, then the advertising speaker updates the AS_PATH attribute
        as follows:

           1) if the first path segment of the AS_PATH is of type
           AS_SEQUENCE, the local system prepends its own AS number as the
           last element of the sequence (put it in the leftmost position
           with respect to the position of octets in the protocol mes-
           sage). If the act of prepending will cause an overflow in the
           AS_PATH segment, i.e. more than 255 ASs, it SHOULD prepend a
           new segment of type AS_SEQUENCE and prepend its own AS number
           to this new segment.

When I examine this text, I find two interesting things:

-- First, there is no mention of any conditions under which information may
be removed from the AS Path, or the AS Path is reordered. I believe, based
on reading of the specification (without outside reference to operational
or implementation experience), this means the AS Path may be reordered, or
information may be removed from the AS Path. Let me at least say neither of
these are strictly prohibited.

-- Second, when describing the operation of a BGP speaker, the draft
doesn't say the speaker MUST prepend its own AS number as the last element
of the sequence, it simply says: "the local system prepends its own AS 
number as the last element of the sequence." In my experience, when draft 
authors intend to make a restrictive requirement, they use the phrase MUST 
in the requirement. In this case, it appears the wording is explanitory, 
rather than a requirement (?).

-- Third, that the MUST is missing implies the authors, reviewers, and 
contributors to this specification (if you refer to page 7, you'll find I'm 
listed as a contributor) believed there were valid situations when a BGP 
speaker would not follow the operational procedure described here.

Would you say this is all correct? I believe, then, that you cannot get the
proposed requirement listed above from the BGP specification itself. At
least I can't find any justification for it. If you believe the
specification should say "MUST" at this point, I would say that's an
argument for the IDR WG, not for RPsec. :-)

--

Now, let's expand this further, and say we'd like to state this:

"On receiving an update, any proposed solution MUST verify the update has
passed through the pairwise peerings represnted by the AS Path attribute
contained in the update."

And base it on this reasoning:

"The sense of the BGP specification is that the protocol will not operate 
correctly is this rule is not followed, or that's what the BGP 
specification authors meant to say, or that's what the BGP specification 
should say, and it was just missed."

This is a slightly less strong justification, but let's deal with it,
anyway, just for argument's sake (because I happen to know that someone on 
this list is going to use one of the above justifications in their reply).

I would point out numerous instances have been cited where operational
requirements, in running, live networks, have caused operators to:

-- Add additional information to an AS Path, causing it to _not_ represent
the list of peerwise AS peerings the update has passed through. A common
example of this is AS Path prepend.

-- Remove information from the AS Path, causing it to _not_ represent the
list of peerwise AS peerings the update has passed through. A common
example of this is stripping private AS numbers out of the AS Path at an
autonomous system boundary.

-- Advertise a set of reachable addresses which contains address space
reachable through a different AS Path than that listed in the update. A
common instance of this is the re-origination of routing information at an
autonomous system border.

With these thoughts in mind, we must choose between one of three
alternatives:

-- These examples are a figment of my imagination. If you want to choose
this option, you'll need to consult my psychologist. I'm afraid I can't 
help you any further. :-)

-- Operators shouldn't be doing these things, and therefore the
justification above stands. In fact, the security requirements document
should be defined so such modifications are not allowed, and the BGP
specification should be modified in accordance with this. I would contend 
this is operationally unteneble.

-- The requirement, as listed, in some way, doesn't truly define what
"valid" means as applied to an AS Path, based on operational and
implementation experience.

I would suggest the third option as the logical choice.

Now, if we can't base the definition of "valid" in reference to the AS Path 
on the BGP specification, because the required MUST isn't there, and 
operational experience shows we can't base it on what we think the "sense 
of the BGP draft is or should be," then how can we define "valid" in 
reference to an AS Path?

I would suggest the definition contained in the current BGP security 
requirements draft, as published, is a good start. The wording may be 
formalized, etc., but the sense of the definition in that draft is based on 
the sense of the BGP specification combined with operational and 
implementation experience, IMHO.

I hope it helps to clarify things by starting from the beginning, and
summarize the overall picture.

:-)

Russ

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

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

---

From: Stefan Mink <[email-masked]>
Date: Sun, 23 Jan 2005 15:01:38 +0100

Hi Russ,

> network, and I've attempted to be as precise as possible in all 

for me, the word "update" is an inprecise reference fo "UPDATE message" 
which is
clearly a message beween to BGP neighbors, and not somthing transitive. The
BGP draft also states that
"Routes are stored in the Routing Information Bases (RIBs): namely,
the Adj-RIBs-In, the Loc-RIB, and the Adj-RIBs-Out, as described in
Section 3.2.". So no updates are stored, but routes (= content of an update)
are put into different RIBs.

> these are strictly prohibited.

I agree that MUSTs must be followed, but not that missing "MUST NOTs"
mean its allowed. I'm sure no document is complete in this sense.
I fear there is an inherent conflict between MUST NOTs and extensibility...

> number as the last element of the sequence." In my experience, when 
> draft authors intend to make a restrictive requirement, they use the 
> phrase MUST in the requirement. In this case, it appears the wording 
> is explanitory, rather than a requirement (?).
>
> contributors to this specification (if you refer to page 7, you'll 
> find I'm listed as a contributor) believed there were valid situations 
> when a BGP speaker would not follow the operational procedure 
> described here.

yes, there are: route servers at IXPs. They collect and redistribute
routes of connected ISPs via EBGP sessions but try to stay as invisible
as possible. This also includes not to put its AS into the path because
it would make the path less favorable compared to directly exchanged
routes. But I guess route-servers generally are special, so they definitely
are a pain for security architectures...

> "The sense of the BGP specification is that the protocol will not 
> operate correctly is this rule is not followed, or that's what the BGP 
> specification authors meant to say, or that's what the BGP 
> specification should say, and it was just missed."

the AS-PATH attribute is important functionally  to avoid loops and is
somewhat important as a metric. From a security point of view, the
as-path is much more important in my eyes. When you want to check,
wether the route of the route is authorized, the as-path would be a
logic basis for this. If the as-path does not mirror the route of the 
route,
on what basis would you otherwise want to check this?

> example of this is AS Path prepend.

agreed, this is a valuable usage e.g. when merging ASes

> autonomous system boundary.

not quite aggreed: even if the BGP spec would be hurted by this behavior,
it's an internal operation and not visible for the rest of the internet. 
This
could impact security but does not necessarily...

> autonomous system border.

I didn't get this :-/
If the routing path differs from the forwarding path, this can lead to
loops on the forwarding plane. For this reason this is very dangerous
and should never be constructed intentionally. I know there are con-
stellations with route reflectors and more specifics where this can
occur without anybody doing "something wrong", but this should not
be a basis to consider this behavior as accepted.

> this option, you'll need to consult my psychologist. I'm afraid I 
> can't help you any further. :-)
>
> specification should be modified in accordance with this. I would 
> contend this is operationally unteneble.
>

I aggree that operators practise and software features differ from the exact
wording of the BGP spec and at least use grey space for some of the example
you describe. For that reason I also think that the BGP spec as single basis
is not sufficient.

   tschuess
             Stefan Mink
-- 
Stefan Mink, Schlund+Partner AG (AS 8560)
Primary key fingerprint: 389E 5DC9 751F A6EB B974  DC3F 7A1B CF62 F0D4 D2BA

---

From: Russ White <[email-masked]>
Date: Sun, 23 Jan 2005 12:52:57 -0500 (Eastern Standard Time)

> which is clearly a message beween to BGP neighbors, and not somthing 
> transitive. The BGP draft also states that "Routes are stored in the 
> Routing Information Bases (RIBs): namely, the Adj-RIBs-In, the Loc-RIB, 
> and the Adj-RIBs-Out, as described in Section 3.2.". So no updates are 
> stored, but routes (= content of an update) are put into different RIBs.

Correct. I would actually much rather discuss this in terms of routes, 
rather than updates, but the entire current language is built around 
updates, rather than routes.....

Of course, actual implementations don't have an adj-rib-in, loc-rib, and 
adj-rib-out (I always confuse all of these names, and call them the wrong 
thing), so these are models of behaviour, not requirements.

> as-path is much more important in my eyes. When you want to check, wether 
> the route of the route is authorized, the as-path would be a logic basis 
> for this. If the as-path does not mirror the route of the route, on what 
> basis would you otherwise want to check this?

I'm not certain what you mean by authorizing: "the route of a route." I 
suppose there are a number of ways I could take this. Suppose I have:

A---B---C

Are you saying you want to show that A is authorizing B to send routing 
information to C? But, if the AS Path doesn't always actually reflect the 
path the routing information has taken (as you acknowledge in at least 
one case), ....

> agreed, this is a valuable usage e.g. when merging ASes

....how can you prove this using the AS Path? I'm not certain how to get to 
"authorization to advertise routing information" from "prove the route has 
followed the path listed in the AS Path?", since the AS Path doesn't 
actually represent the path the routing information took through the 
network, in all cases?

Beyond this, why do we want to prove this "authorization chain?" Is it to 
prove the sender is authorizing packets to flow along the reverse path than 
the one the routing information took? Since you can't ever prove traffic 
flows along the reverse path the routing information takes, this doesn't 
seem to be helpful, either. draft-white-pathconsiderations-04 shows some 
examples of this occuring.

Finally, you could say you're actually trying to authorize the 
advertisement of reachability information, since the route is actually made 
up of a prefix and attributes, which is what we would call reachability 
information. "Is my peer authorized to advertise reachability to 10.1.1.1 
to me?" is the sort of question we're talking about here. And, here again, 
draft-white-pathconsiderations-04 shows how this doesn't work in the real 
world, the first example is the simplest.

So, I suppose I'm confused by the concept of "authorization" in the context 
of the AS Path as carried in BGP routes. What does it mean, exactly? What 
are we attempting to authorize?

> it's an internal operation and not visible for the rest of the internet. This

The path of the routing information is actually {65100,1,2,3}, but you're 
reporting the path of the routing information as {1,2,3}. It's not a matter 
of the operation being "internal," it's a matter of the path of the routing 
information not matching the reported path of the routing information.

Another example is confederations, where AS' are inserted into, and then 
removed from, the AS Path. Again, the confed AS appears to be a single AS 
to the remainder of the internetwork, but there are path elements that are 
added and removed, showing the AS Path is not a sacrosant version of the 
actual path of the routing information.

> be a basis to consider this behavior as accepted.

draft-white-pathconsiderations-04, first example. I would consider each 
entity's actions within the internetwork perfectly acceptable and normal 
behaviour.

> I aggree that operators practise and software features differ from the 
> exact wording of the BGP spec and at least use grey space for some of the 
> example you describe. For that reason I also think that the BGP spec as 
> single basis is not sufficient.

Agreed.

There are two camps here:

-- The requirements document should state any proposed solution must 
verify/prove/etc. the path the routing information actually took is the 
same as the AS Path attribute of the route.

-- The requirements document should state and proposed solution must verify 
the AS Path attribute of any received route exists (represents a valid set 
of peerings within the internetwork), since this is all we can actually 
prove or validate. We can't prove authorization using any of the various 
definitions we've tried to use, so we shouldn't require any proposed 
solution to prove authorization.

I think the second is the most logical choice, but I'm willing to allow 
both to be included in the draft as alternatives, in either of the two ways 
I've proposed on list. Either word the requirements to cover both options, 
or have two separate requirements.

:-)

Russ

---

From: Blaine Christian <[email-masked]>
Date: Sun, 23 Jan 2005 16:38:01 -0500

> same as the AS Path attribute of the route.

Hey Russ, can we work this backwards a bit and see it if still makes sense?
Perhaps we can list the cases where the path can not be proven and still
allow for path verification?

So, path can not be proven for...

1. Reoriginations: This is information reduction/expansion for the sake of
performance and it could be argued that it is a tacit agreement between the
provider of reoriginated information and the reoriginatee.  If it is an
agreement between originator and originatee then security would most likely
also be an agreement betwixt the two.  Heck, if I do BGP with a customer and
advertise default this is essentially the same thing.

2. Confederations: These happen "internal" to an AS so I suppose this could
just be captured and dealt with separately.

3. Private AS stripping:  Most folks do not allow this type of stuff to
propagate beyond the initial two networks involved so again it should fall,
mostly, in the realm of a private agreement.

4. Route propagators (really just packet forwarders for all intents and
purposes).  A packet forwarder is a packet forwarder.  As long as whatever
security information is necessary is passed along as well I don't think this
is really germane to the discussion.

Can anyone think of other special cases such as the above?  Would everything
else be "verifiable"?  Just above every one of the above path manipulations
is based on either a private agreement or an internal optimization for a
network.

You know that, no matter what happens with the specification, the ability to
track signatures across an entire AS path is quite attractive as a means of
identifying miscreants or potential issues.  Even if noting and ignoring the
special cases does not work.

Another thought... We did build into the requirements draft language that
allows for non-secure things.  Wouldn't unverifiable stuff just end up in
the "not secured" realm anyway?

Regards,

Blaine

---

From: Russ White <[email-masked]>
Date: Sun, 23 Jan 2005 20:53:40 -0500 (Eastern Standard Time)

> Hey Russ, can we work this backwards a bit and see it if still makes 
> sense? Perhaps we can list the cases where the path can not be proven and 
> still allow for path verification?

Hmmm.... What do you mean by "path verification?" Do you mean proving the 
routing information has actually passed through the AS' listed in the AS 
Path? I'll assume so....

Let me start out by stating this: The claim is that this wording:

"The receiver of a specific prefix/attribute MUST be able to verify the 
routing information has passed through every AS peering pair in the AS 
Path."

Should replace the current wording in the BGP requirements draft, because 
it is supported by this:

"According to the BGP specification (or according to what the BGP 
specification SHOULD read), each AS handling the AS Path MUST insert their 
AS in the AS Path. Further, no information may be removed from the AS 
Path."

I believe you've already conceded, below, that this simply isn't the case. 
I'll work with that assumption, since the tenor of the rest of your email 
seems to assume that, but it would, actually, be nice to get a statement on 
whether you believe using the sense of the BGP specification, or the BGP 
specification itself, justifies changing the current wording.... :-)

Based on my reading of your email, I'll assume you're now trying to justify 
changing the wording on the draft to something close to the one listed 
above based on a desire for non-repudiation--that's it's important to know 
who, exactly, forwarded a specific piece of routing information, so you can 
hold the originator and forwarders of that routing information liable 
(legally or socially) for originating or forwarding false routing 
information. I'll deal with this more at the end of this email.

> 1. Reoriginations: This is information reduction/expansion for the sake 
> of performance and it could be argued that it is a tacit agreement 
> between the provider of reoriginated information and the reoriginatee. 
> If it is an agreement between originator and originatee then security 
> would most likely also be an agreement betwixt the two.  Heck, if I do 
> BGP with a customer and advertise default this is essentially the same 
> thing.

This doesn't negate my argument that informaiton is removed from the AS 
Path, and therefore the AS Path attribute of the route doesn't actually 
match the path of the routing information through the network. However, 
you're claiming that since this only occurs in the context of a customer 
and their provider, it just doesn't matter that information is removed from 
the AS Path.

Okay, I understand your argument, I believe. The problem is you don't know 
if the customer has actually authorized, from the information in the 
reoriginated route, the advertisement of this routing information. So, you 
can't prove authorization, in this case, only non-repudiation. You can try 
to prove the customer's provider actually advertised the route, you can't 
prove the customer authorized the provider to do so.

In fact, the provider could be maliciously advertising the customer's 
address space, even though a previously valid agreement allowing them to do 
so has now been voided because of some "falling out" between the two.

> 2. Confederations: These happen "internal" to an AS so I suppose this 
> could just be captured and dealt with separately.

Again, the point of the argument is that information is, in fact, removed 
from the AS Path, not that it's "internal" to an AS or not, simply that it 
happens. It would be different if the Confed AS' were inserted in a 
completely separate attribute that could be removed separately, rather than 
modifying the AS Path, but in reality, they aren't. They are inserted into 
a confederation set within the AS Path itself, and the confed set is 
stripped out of the AS Path at the other side of the confed.

> propagate beyond the initial two networks involved so again it should 
> fall, mostly, in the realm of a private agreement.

Again, however, just because it happens in the private context doesn't show 
that information isn't being removed from the AS Path, correct? Again, 
you're arguing, as above, that it doesn't matter, because it's a private 
context.

A BGP speaker receiving this route would only be able to assume it has the 
entire AS Path, and that the originator is authorized to originate it. 
However, unknown to the receiver, there is actually another AS in the AS 
Path, and there's no way for the receiver to know of the original AS 
actually authorized the advertisement of the routing information by the 
apparent originator from the routing information itself.

Seems like a lot of assumptions, to me. Again, we're in the same position 
as reorigination, where we can try to prove non-repudiation, but not 
authorization.

> purposes).  A packet forwarder is a packet forwarder.  As long as 
> whatever security information is necessary is passed along as well I 
> don't think this is really germane to the discussion.

?? I don't really understand this one.

> Can anyone think of other special cases such as the above?  Would 
> everything else be "verifiable"?  Just above every one of the above path 
> manipulations is based on either a private agreement or an internal 
> optimization for a network.

Just about.... But, you're dealing with a separate problem here. You're 
morphing the issue from:

-- "Does the BGP specification support changing the requirements currently 
listed in the requirements draft to some other wording?"

  -- TO --

-- "Does the requirement for non-repudiation support changing the 
requirements currently listed in the requirements draft to some other 
wording?"

I believe non-repudiation is already covered in the current text of the 
draft, and I don't have an argument with it being there. So, I'm not 
certain why the wording would need to change to include non-redudiation. 
But let's run with the argument that non-repudiation _could_, possibly 
justify changing the current wording, and see where it takes us.

What do we know about non-repudation, as a concept? We know that other RFCs 
state, quite clearly, that non-repudiation isn't possible. So, you're 
making something acknoweldged as not possible a MUST. IMHO, that's not a 
good idea. In fact, I'll just about bet the wording on non-redudiation is 
removed from the draft or, at the least, altered radically, before it's 
actually pupblished, based on the reasoning I've seen from the security 
folks in the past. :-)

Now, let's run a different direction, and see where it takes us. Let's 
assume we _do_ make this wording change, and then we have to build a 
justification for the wording in the draft. What would the justification 
be? Since we can't justify the requirement with: "Because the BGP 
specification says so, or it should say so, and it doesn't," then we have 
to find some other justification, correct?

That justification would be the requirements, as they are currently stated 
in the draft. Interesting.... If you have to justify the requirement with 
the current requirements, why change to some other requirement at all? I 
suppose I'm just confused on this point.... If I justify a requirement with 
something previously listed as requirements, it sounds like I'm moving into 
the solution space, instead of the requirements space.

> You know that, no matter what happens with the specification, the ability 
> to track signatures across an entire AS path is quite attractive as a 
> means of identifying miscreants or potential issues.  Even if noting and 
> ignoring the special cases does not work.

This is a solution, not a requirement, so I won't go there....

The special cases, combined with the problems inherent with 
non-repudiation, kill off non-repudiation as a justifaction for the change 
in wording, IMHO.

> the "not secured" realm anyway?

You don't know if they are or aren't. If you remove information from the AS 
Path, you can't tell what that information was, so you can't say: "Oh, this 
is just less secure, because information has been removed from the AS 
Path." Second, you can't deny that in many of these situations, the removal 
of information is such that the originator should still expect their routes 
to be treated in a secure way.

:-)

Russ

---

From: Stefan Mink <[email-masked]>
Date: Mon, 24 Jan 2005 14:07:55 +0100

Hi Russ,

Russ White wrote:
> adj-rib-out (I always confuse all of these names, and call them the 
> wrong thing), so these are models of behaviour, not requirements.

sure, but requirements should rather be based on these models of
behavior than on how it is usually implemented. Otherwise it would
make unusual and may be better ways of implementation impossible.

> information to C? But, if the AS Path doesn't always actually reflect 
> the path the routing information has taken (as you acknowledge in at 
> least one case), ....

the fact that there are currently situations, where the as-path does
not reflect the actual forwarding path, is at least partially based
on the fact, that it wasn't a critical requirement. As you wrote many
things are being done today because it didn't hurt anybody so far.
If now it starts hurting, maybe we should more think about how to
avoid these situations.

For me, origin authorisation is just the beginning. The authorization,
to pass on routes (and by this permit traffic to flow in the opposite
direction) is relevant to network stability (what happends if a big
traffic flow due to a wrong announcment starts to use a network path
that doesn't have the capacity to carry it) and can have an impact on
the economic  result, i.e. who is earning money with which traffic.

I don't want my customers to announce my prefixes to another transit
of them and my wish would be, that a future security architecture
would be able to actually make it verifiable, wether a received route
was sent by the other side in an authorized way. You can not keep
"an attacker" from announcing routes he isn't authorized to announce
to another BGP neighbor. On the other hand as an honest BGP neighbor
you should be able to check, if an advertisement is not authorized.

How do you verify, wether an announcement is authorized? Not by checking
the RIR database but by checking contracts between BGP neighbors. And
thats exactly the point where current policies are not precise enough.
The only contain what's beeing announced to whom but not what he is
allowed to do with it.

Now if you want to check that authorization chain, on which data
do you base it? There's just the as-path, that in many/most cases
reflects the ASes it traversed, but in many cases it does not. My
point is that in the latter case, authorization is just not verifiable
without adding another bgp attribute that truely reflects the path
the update took.

Concerning the difference between routing path and forwarding path,
you still have the problem, that you can avoid loops on routing plane
but you can not on forwarding plane. For me a routing protocol with
this behavior is a real danger. You didn't reply to this so far.

> ....how can you prove this using the AS Path? I'm not certain how to get 
> to "authorization to advertise routing information" from "prove the 
> route has followed the path listed in the AS Path?", since the AS Path 
> doesn't actually represent the path the routing information took through 
> the network, in all cases?

I don't see any problems here. If two ASes merge, authorizations don't
change for that reason. If there is still a physical separation of the
networks or not is not relevant for the rest of the internet.

> Beyond this, why do we want to prove this "authorization chain?" Is it 
> to prove the sender is authorizing packets to flow along the reverse 
> path than the one the routing information took? Since you can't ever 
> prove traffic flows along the reverse path the routing information 
> takes, this doesn't seem to be helpful, either. 
> draft-white-pathconsiderations-04 shows some examples of this occuring.

just because something is broken, it doesn't mean we shouldn't try
to fix ist :)

> advertisement of reachability information, since the route is actually 
> made up of a prefix and attributes, which is what we would call 
> reachability information. "Is my peer authorized to advertise 
> reachability to 10.1.1.1 to me?" is the sort of question we're talking 
> about here. And, here again, draft-white-pathconsiderations-04 shows how 
> this doesn't work in the real world, the first example is the simplest.

that means to me, that a verification of authorization is not achievable :(

> So, I suppose I'm confused by the concept of "authorization" in the 
> context of the AS Path as carried in BGP routes. What does it mean, 
> exactly? What are we attempting to authorize?

the current state is: if you have a route, you can do what you want
with it and the only thing you can do is withdraw a route from a BGP
peer if he's announcing it in a way it's not authorized from your point
of view (e.g. a customer announces one of your prefixes to a peer or
transit provider, the only thing you can do is withdraw the route).
I hate it but it seems to be a similar problem the media industry
is facing with music/video...

> The path of the routing information is actually {65100,1,2,3}, but 
> you're reporting the path of the routing information as {1,2,3}. It's 
> not a matter of the operation being "internal," it's a matter of the 
> path of the routing information not matching the reported path of the 
> routing information.

I consider AS65100 as not being autonomous, but as being part of
AS1.

> removed from, the AS Path. Again, the confed AS appears to be a single 
> AS to the remainder of the internetwork, but there are path elements 
> that are added and removed, showing the AS Path is not a sacrosant 
> version of the actual path of the routing information.

same point here. The sub-ASes of the confederations are not autonomous.
They can only interoperate with other ASes by using the official ASN.

> entity's actions within the internetwork perfectly acceptable and normal 

sorry, for me it's not acceptable and is far from normal.
Just one example to show how fragile such constructs are: Assume
AS D somehow looses the route to E, then B is blackholing
all traffic to E.

> same as the AS Path attribute of the route.

that's me. But I also see that this is hard to achieve at the moment,
but it could be achieved, if people would understand, that its dangerous
if routing plane and forwarding plane do differnt things. I'd be glad
if somebody would tell me that I got it all wrong and there's no problem
but so far nobody did. You could be the first one, who illustrates me
not only that this is common practise, but also that there are no
disadvantages and dangers whatsoever with this practise...

    tschuess
              Stefan Mink

---

From: Stephen Kent <[email-masked]>
Date: Mon, 24 Jan 2005 11:44:55 -0500

>example of this is AS Path prepend.

Again, you seem to be ignoring the following quote from my analysis 
of BGP message, discussion section 5.1.2 of the document:

... The end of this subsection explicitly allows for adding multiple 
instances of the ASes own number; this is not seen by the spec as 
conflicting the notion of the UPDATE having traversed the path it 
contains, e.g., indicating a loop.

The text I was referring to was this:

Whenever the modification of the AS_PATH attribute calls for 
including or prepending the AS number of the local system, the local 
system MAY include/prepend more than one instance of its own AS 
number in the AS_PATH attribute. This is controlled via local 
configuration.

This shows that the example you cite is explicitly allowed in the spec.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Mon, 24 Jan 2005 11:52:21 -0500

At 3:01 PM +0100 1/23/05, Stefan Mink wrote:
>Content-Type: multipart/signed; micalg=pgp-sha1;
>	protocol="application/pgp-signature";
>	boundary="------------enig16C79B98A61BD3940547B207"
>
>Hi Russ,
>
>Russ White wrote:
>
>for me, the word "update" is an inprecise reference fo "UPDATE 
>message" which is

yes, the UPDATE message per se is not passed through ASes. For 
example, a set of withdrawn routes in an UPDATE message is purely a 
local transmission of that data. Selected AS path attribute data is 
transitive, and it makes up the bulk of the UPDATE message. A route 
is a set of NLRI and associated path data, and that is what is stored 
in these nominal databases, as per the spec. The BGP spec indicates 
which path attributes are transitive and which are not, and thus 
which ones need to be passed on (transitively) to neighbors, if the 
speaker decides to propagate the route.

Steve

---

From: Jeffrey Haas <[email-masked]>
Date: Mon, 24 Jan 2005 12:06:32 -0500

> these are strictly prohibited.

When adding to an AS_SEQUENCE, the operation is a prepend.  When you
overflow an AS_SEQUENCE path segment, you prepend a new AS_SEQUENCE.

Thus, a compliant implementation will only _prepend_ AS numbers.

An AS_PATH may be changed by the specification under the following
circumstances:

Aggregation using AS_SETS will cause the generation of AS_SETS.  These
sets are unordered but are suggested to be sorted.  An AS_SET will
count as a length of 1 towards AS_PATH length in the decision process.

Aggregation using the "brief" form will cause the truncation of the
AS_PATH.  When the path is truncated, ATOMIC_AGGREGATE must be attached.

Confederations modify the AS_PATH by adding the confederation versions
of AS_SETS and AS_SEQUENCES.  These are removed upon advertisement
to a confederation external peer.  They follow the same rules.

In operational practice:
o When utilizing private AS numbers, trailing private AS numbers may
  be stripped.  I am unaware of implementations that will strip non
  private AS numbers.
o Some implementations will allow an operator to insert an arbitrary
  set of AS numbers into the AS_PATH, however it will also prepend
  it's own AS number upon advertising the route to an external peer.

My own conclusions are:
o Re-ordering does not happen inside of sequences.  AS_PATHs may be
  truncated during aggregation (by the specification) or by removing
  private AS numbers (outside of the specification).

  Removing private AS numbers may introduce loops if done improperly.
  However, the scope of these loops are usually localized to the
  private ASes which are usually stub ASes.

o Even when additional ASes are introduced into the AS_PATH (outside of
  the specification), loops are not introduced.  They effectively prune
  path availability.

  This is the only common operational practice that I'm aware of
  that potentially breaks pair-wise AS adjacency verification.
  The operational requirements of this feature in a "secure" BGP infrastructure
  are somewhat dubious but beg the question of "authorization to advertise".

  Note that implementations have knobs that allow one to accept advertisements
  that are a local-loop.

> rather than a requirement (?).

This is reinforced by the following:

:   If the UPDATE message is received from an external peer, the local
:   system MAY check whether the leftmost (with respect to the position
:   of octets in the protocol message) AS in the AS_PATH attribute is
:   equal to the autonomous system number of the peer that sent the mes-
:   sage. If the check determines that this is not the case, the Error
:   Subcode MUST be set to Malformed AS_PATH.

> speaker would not follow the operational procedure described here.

The only operational scenario that I'm aware of that allows for the
adjacent AS check to be disabled (which defaults to on in most of
the implementations that I'm aware of) is proxy BGP routing (a
route server).

> argument for the IDR WG, not for RPsec. :-)

I believe we (or at least I) made the suggestion that the requirements
allow for route servers.  So, with the exception of the two operationally
common exceptions I listed above, the spec is generally followed.

All of these situations can be reasonably accomodated by a
suggested infrastructure.  To make suggestions:

o Private AS removal is similar to our truncation arguments when we're
  talking about aggregation.  So long as the AS at the rightmost side
  is the one that the security infrastrucutre says is allowed to 
  originate the AS in the public Internet, truncation is fine and
  would not violate globally visible security.
o Route servers could be accomodated a few different ways:
  + Actually put the server's AS in the path, follow normal practice.
  + Treat this as a special zone of trust (much like internal BGP) and
    don't verify adjacent AS (but use transport layer security), make
    sure that the recipient of the proxied route executes the normal
    security practices.
o Arbitrarily inserting ASes to deny "authorization" to receive a route is
  a harder case.  This almost suggests a new AS_PATH type specifically
  to accomodate this in the security infrastructure.  

> should say, and it was just missed."

Here's where I'll make the other side of the argument:

The specification says to prepend.  I've given the known cases where we
may change things beyond prepending.

Operationally, people rely on the adjancencies for policy.  This is 
outside the protocol specification.

Loop detection is a condition of phase two of the route selection process:
:   If the AS_PATH attribute of a BGP route contains an AS loop, the BGP
:   route should be excluded from the Phase 2 decision function.  AS loop
:   detection is done by scanning the full AS path (as specified in the
:   AS_PATH attribute), and checking that the autonomous system number of
:   the local system does not appear in the AS path.  Operations of a BGP
:   speaker that is configured to accept routes with its own autonomous
:   system number in the AS path are outside the scope of this document

Ergo, the only requirement for loop free operation of the protocol
is that the AS be present in the path.  In general, you should receive
your routes with your peer's AS at the start of the AS_PATH.  The
protocol will work properly if the path is re-ordered.

However, if implementations start reordering the path for no good
reason, operators will be very, very upset.

[Russ gives a similar list above]

> autonomous system border.

Re-origination may potentially lead to loops.  However, I don't think
this violates the security infrastructure so long as the route is
allowed to be originated (by the security infrastructure) by multiple parties.

> implementation experience.

Four: The security infrastructure should just deal with these things
as they're not insurmountable.  Only the arbitrary addition of ASes
is problematic.  Compliant implementations will follow the prepend rule.
Truncating the path must be dealt with for aggregation.

> of the BGP draft is or should be," then how can we define "valid" in 

I think I've presented arguments to the contrary, above.

Final notes:
At no step of the above process is "authorization" included.  BGP, in 
general, does not express the ability to propogate or not propagate a
reachability.  The operational practice of injecting someone's AS number
in a route to prevent them from receiving a route could be considered
a form of "denial of authorization", but that's largely out of scope of
the protocol.

In any case, I'm not trying to prove authorization using any of the
above information.

I'm not sure "non-repudiation" is the security property we actually want
out of verifying pairwise adjacencies.  I don't want to say "you're
claiming to not have sent me this".  Instead I want to say "each of
these parties have touched this route and propagated it".  I don't think
they're exactly the same thing.  I also seem to remember a comment either
on rpsec or bgpsecreq asserting the same thing, but I can't find the
relevant message.

-- 
Jeff Haas 
NextHop Technologies

---

From: Jeffrey Haas <[email-masked]>
Date: Mon, 24 Jan 2005 12:14:03 -0500

Steve,

> of BGP message, discussion section 5.1.2 of the document:

Russ, I believe, was speaking of the Cisco "as path prepend" operation
in their CLI.  This option is what is used to insert an arbitrary
number of ASes beyond that of the local AS number.

-- 
Jeff Haas 
NextHop Technologies