Subject: Re: [RPSEC] proposed message to the IESG

From: Sandy Murphy <[email-masked]>
Date: Fri, 21 Jan 2005 18:42:21 -0500 (EST)

>Suppose you state: "A speaker 
>should be able to prove the update has passed through the AS' listed in the 
>as path," as a requirement. Now, my question is going to be: "Why? What do 
>you want to prove by verifying this in this way? Your answer is going to 
>be: "Because proving this proves the path actually exists, and can prove 
>non-repudiation, and...."

Well, no, that's not what my answer would be.

My answer would be:

Answer 1: that's what the spec says happens

If you were teaching a class in BGP and people had been studying the
spec, and you put the following question on the test:

AS A receives an update from B containing a route with the AS_PATH set to
{B,C,D}.  Which of the following does your implementation assume in
deciding what to do with this update?  (Choose the most complete
answer.)

(a) AS A is connected to AS B
(b) B peers with C. C peers with D. D is connected to the NLRI.  We don't
know how B came by this AS_PATH.
(c) B received an update from C containing (C,D) and C received an update
from D containing {D}, and D is connected to the NLRI
(d) traffic to the NLRI sent to B will be passed to C and then to D.

I would say that the correct answer was (c).  And, yes, I know that the
correct answer is not (d).

--------------------

Answer 2:  that's a fairly succinct statement that covers (all, most)
of the cases of things we want to prevent.

Case 1: The spec says that the AS_PATH is used to detect loops.
Therefore, noone should be able to delete AS's from the AS_PATH.

And I don't think this is OK even if the resulting AS_PATH has valid
adjacencies.  Do you think it would be OK?  (Question, not challenge.)

Case 2: The operational common practice is that a shorter AS_PATH is
the better AS_PATH.  So no one should be able to change the length of
the AS_PATH.  (This is not a spec requirement, but it is so widely
implemented, it comes close.  And, incidentally, IMHO, derived from
the expectation that the AS_PATH represents the AS's through which
this information has traveled.)

If someone changed the length of the AS_PATH, but the resulting
AS_PATH had valid adjacencies, do you think it would be OK?
(Question, not challenge.)

Case 3: Suppose when an AS is composing the AS_PATH of an update, it
completely scrambles the order of the AS's from their sequence in the
AS_PATH of the Loc_RIB_In entry it choose.  The resulting order
accidentally matches valid adjacencies, but bears no relationship to
the order of AS's by which the information got there.  Is that OK?
Honestly, I have no opinion whether that is OK or not.  It's not going
to hurt the length checking and its not going to hurt loop checking -
but as soon as someone decides to make a policy on the basis of
AS order in the AS_PATH, you'd have a problem.

Case 4: Suppose an AS chooses a route which would have an AS_PATH of
length X, and it puts an AS_PATH in the update it sends which has length X
but has no other bearing to the AS_PATH of the route it has chosen.
It uses this same length X AS_PATH for all updates it sends for which
the route it chose would have an AS_PATH of length X.  So the length
is correct, and the AS_PATH adjacencies all check.  Is that OK?
I would say not, because it removes the ability to check for loops.

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

---

From: Russ White <[email-masked]>
Date: Fri, 21 Jan 2005 22:27:14 -0500 (Eastern Standard Time)

>> Suppose you state: "A speaker should be able to prove the update has 
>> passed through the AS' listed in the as path," as a requirement. Now, my 
>> question is going to be: "Why? What do you want to prove by verifying 
>> this in this way? Your answer is going to be: "Because proving this 
>> proves the path actually exists, and can prove non-repudiation, and...."
>

> correct answer is not (d).

Let me ask this: If you were teaching a class on IPsec to a bunch of 
routing geeks, would you use "colliqual" terms, like "IPsec tunnel" to 
explain how it works, or would you delve into the real terms, and 
operation, immediately? Does the IPsec draft use the term "tunnel?" Is it 
really a "tunnel?" There are no instances you can think of where you'd use 
terms that model the reality, but don't reflect the actual way things work?

Before I answer your question directly, and while you're thinking about the 
question above, let point out that routing protocol specifications actually 
provide a model of behaviour; they are "loose."

For instance, if you were to read the BGP specification, how would you 
describe the BGP peering FSM, specifically in the case of a connection 
collision? You would state: "When the second TCP connection is received, a 
new BGP process starts. The collision is resolved using x means, and one of 
the two processes on each BGP speaker is terminated." You'd be right, based 
on the current spec (not the draft), but that's not the way BGP is 
implemented. In fact, I don't know of any implementation that actually runs 
a different process for each speaker. I'm certain cisco, Juniper, Procket, 
and Redback don't (didn't in some cases). It's easier to describe in terms 
of multiple processes, so that's what the BGP spec does.

Another example is the concept of the loc-rib-in and loc-rib-out. The BGP 
specification relies on these concepts heavily. In reality, there's no 
implementation that has a loc-rib-in or a loc-rib-out. They don't exist. 
They're useful for explaining the model, but they they are never used in an 
implementations. At least I don't know of that have a loc-rib-in and a 
loc-rib-out.

Another example, in another protocol. The OSPF and IS-IS specifications 
both specify the use of the Dijkstra algorithm to find the shortest paths 
through the network. In reality, and SPF algorithm will do, as long as it 
has the same results as Dijkstra. In other words, an implementation of 
either of these protocols could use any SPF algorithm, and still be 
compliant with the specifications.

Take a look at Alex's alternative ABR implementations draft, as another 
instance. You'll find a number of places where implementations optimize the 
specification, not in a way that contradicts the specifications, per se.

In the routing world, we consider this sort of thing "normal operation."
There are two classes of things that we look at when considering compliance 
with a specification. The first is "on the wire." The second is 
"implementation specific." The "area" the concept of "implementation 
specific" covers in the security world is, I believe, rather narrow, things 
like what sort of data structure to use, etc.

In the routing world, the concept of "implementation specific" is much 
wider. The specifications tend to be models, rather than "strict 
specifications." If everyone implemented what was actually described in the 
BGP specification, down to the last period, BGP wouldn't be very efficient, 
and the internet wouldn't work. A protocol implemenation is "specification 
compliant" if it interoperates with another implementation that is 
"specification compliant." Look at the RP implementation reports, they 
don't say: "Cisco has implemented BGP based on the specification, to 
examine the loc-rib-in, use the command x, etc." They say: "Cisco 
interoperates with vendor x, y, and z, in these areas."

What's on the wire counts. The rest is implementation specific. Now, back 
to your question, and a short answer, with that as background. My answer 
would be: it depends. Who am I talking to?

-- If I'm talking to a new BGP coder, trying to explain how the code works 
in relation to the specification, I would say none of the above. I would 
say we take the route (nlri/attribute) pair out of the update, and check 
the AS Path for any instances of my local AS number. If there are no 
instances of my local AS number in the AS Path, I will process the route. 
If there are, then I discard it. That's it.... I don't care what the AS 
Path says, as long as it doesn't include my route. Even in the best path 
decision, I only care about the length of the AS Path, I've no care in the 
world about the AS' listed in the AS Path at all.

-- If I'm talking to a routing protocol engineer, who understands graph 
theory, and is just picking up BGP, I would say "B has sent me update 
containing a route stating it has a path to the NLRI via {B,C,D}. The AS 
Path is used to detect loops." I probably wouldn't discuss updates in any 
context other than the way routes are transported between BGP speakers 
(peers).

-- If I were talking to a new networking class, trying to explain BGP for 
the first time, I would draw an as graph on the board, and show how the AS 
Path proves the path is loop free. I would probably use the terms you used 
in (c), until I got to policy explanations, then I would note instances 
where the AS Path isn't going to match the path the route takes through the 
network.

> adjacencies.  Do you think it would be OK?  (Question, not challenge.)

Yes, I do believe there are valid, operational reasons why an AS would 
remove AS' from the AS Path. For instance, there's a command to remove all 
the private AS' from an AS Path in cisco routers. It's common enough 
practice to remove the private AS' from an AS Path that we've actually 
built a specific command for it.

Further, this is specifically what re-origination (rather than aggregation, 
to use the "correct" term), does, as well. It removes elements from the AS 
Path. So, in your question above, there could be another AS behind D that 
actually contains the destination, that I can't see. It's a common 
occurance. We take great pains to explain this when we teach BGP, most of 
the time.

And, finally, confederations, by definition, remove AS information from the 
AS Path.

> this information has traveled.)

Actually, this isn't true. In a large number of cases, the as path length 
is not the major determinate of the "better" path. More specifically, any 
route you learn from a customer is probably going to be decided on local 
preference. Any route you learn from a peer is probably going to be decided 
by igp metric, and then possibly as path. A large number of the routes you 
learn are going to fall all the way to the last point in the decision tree, 
the router id, or in cisco's case, the older route (ask Blaine about this, 
it's an area he has heartburn with!). :-)

> If someone changed the length of the AS_PATH, but the resulting AS_PATH 
> had valid adjacencies, do you think it would be OK? (Question, not 
> challenge.)

Yes, I do. It's common operational process to insert multiples of the same 
as in an as path. In fact, I've just discovered a case where the origin and 
as path length are intentionally changed to implement a specific policy. 
I'd never heard of this before, but....

I'll point something out here.... The variety of things people do with BGP 
would astound you. The cases are almost unbelievable. Just cruise through 
the knobs available in the major vendor's implementations, and try to 
figure out what they're there for. Yet I've seen every one of those things 
used, in real life. Conditional advertisement, conditional injection, AS 
Path stripping, local AS spoofing, AS migration and merge, re-origination, 
aggregation, .... There are several hundred pages of BGP configuration 
guides, command references, and feature guides on cisco.com.

> AS order in the AS_PATH, you'd have a problem.

I wouldn't use the as path to build policy, for the most part. I might make 
policy based on the origin, and the next hop, but everything in the middle 
is up for grabs. Let me put it this way--if you already acknowledge the 
traffic forwarded along this route may not follow the AS Path listed in the 
packet, then what sort of policy would you enforce based on the AS Path?

Let me put it another way: Is there any sense in which the policy will not 
be based on the desirability of forwarding traffic via the advertised 
route? If you already know the AS Path isn't gaurenteed to bear any 
relation to the path of the packet, in real life, then isn't is illogical 
to base your packet forwarding policy on an AS Path that may not represent 
the actual path of the packet? IMHO, if you trust the as path in this 
situation, you get what you deserve. :-)

> length X, and it puts an AS_PATH in the update it sends which has length 
> X but has no other bearing to the AS_PATH of the route it has chosen. It 
> uses this same length X AS_PATH for all updates it sends for which the 
> route it chose would have an AS_PATH of length X.  So the length is 
> correct, and the AS_PATH adjacencies all check.  Is that OK? I would say 
> not, because it removes the ability to check for loops.

This is closely related to the case you've listed above.

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

What you're asking is what if A advertises 10.1.1.0/24 to B, but B 
advertises that route with a path of {D,A} to C, rather than just {A}, 
correct? I know, you've said if the as path is the same. Now, D wont' get 
this route, right, because the as path has been messed with. I would point 
out two things:

-- D will receive the route through A directly, in most situations, right? 
Well, A may have a policy set so D doesn't receive this route through A 
directly, but ignoring that possibility, the impact of this attack is nil.

-- If B wants to disrupt communications between A and D, why doesn't it 
just filter the route, or the traffic? If I'm on the path, you can't stop 
me from disrupting your traffic in a number of other ways, so defending 
against this attack is, essentially, a null proposition. I can't think of 
any way to make this attack work when you're not already on the path (?).

I hope that helps....

:-)

Russ

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