Subject: Re: [sidr] Comment about aggregators and AS_SETs

From: Pradosh Mohapatra <[email-masked]>
Date: Sun, 1 Aug 2010 23:20:48 -0700

I support Jeff's proposal for matching the "first AS after AS_SET" with the 
[AS4_]AGGREGATOR attribute. If I understand correctly, the suggestion is to
follow the below algorithm for deriving origin_as:

1. origin_as = rightmost AS in the final AS_SEQUENCE of the AS_PATH attribute
2. If the UPDATE carries [AS4_]AGGREGATOR and AS_SET attributes
         if (first AS after AS_SET == AS encoded in [AS4_]AGGREGATOR), then
             origin_as = first AS after AS_SET
         else
             origin_as = NONE

Sriram, a quick question on your enumeration tree: the right hand side in the tree
starts with "No AS_SET", but later you have nodes that say "Matches the first AS
after AS_SET"... What does that mean? Also, IMO, the attack vector you mention
in the slides are more related to path validation than origin validation.

- Pradosh

---

From: Jeffrey Haas <[email-masked]>
Date: Mon, 2 Aug 2010 16:03:47 +0000

On Sun, Aug 01, 2010 at 11:20:48PM -0700, Pradosh Mohapatra wrote:
> [AS4_]AGGREGATOR attribute.

Just to be clear, this is Sriram's proposal.  I'm just suggesting some
additional language for protocol clarity. :-)

> If I understand correctly, the suggestion is to

Since this has come up again, let's try to formalize this according to 
RFC 4271 AS_PATH semantics.

RFC 4271, section 5.1.2 provides the context of "left" and "right" with
regard to the AS_PATH.  

-------8<---- cut here ---->8-------

0. In the presence of the RFC 4893 AS4_PATH path attribute, the AS_PATH
   SHALL first be reconstructed per RFC 4893 rules.
   
   If the AS_PATH cannot be successfully re-constructed or there is
   structural or semantic ambiguity with regard to AS numbers or path
   segment types, the origin AS SHALL be treated as None.

1. If the AS_PATH segment types solely consist of confederation segment
   types, then the origin AS SHALL be treated as Local.

2. If there is no segment type of AS_SEQUENCE, then the origin AS SHALL be
   treated as None.

3. If the rightmost path segment type is AS_SEQUENCE, then the origin AS
   SHALL be the rightmost AS in the AS_PATH.

4. If the rightmost path segment type is NOT an AS_SEQUENCE, then locate the
   rightmost path segment of type AS_SEQUENCE.

   If an AGGREGATOR path attribute is present, including the reconstructed
   AGGREGATOR per RFC 4893 rules, and the rightmost AS of the rightmost path
   segment of type AS_SEQUENCE matches the AGGREGATOR AS, then this AS SHALL
   be treated as the origin AS.

   If the rightmost AS of the rightmost path segment of type AS_SEQUENCE
   does not match the AGGREGATOR AS, then the origin AS SHALL be treated as
   None.

   If no AGGREGATOR path attribute is present, then the rightmost AS of the
   rightmost path segment of type AS_SEQUENCE MAY be treated as the origin
   AS.

-------8<---- cut here ---->8-------

(Renumber the base as you feel appropriate.)

Discussion:

4-byte ASes (RFC 4893) introduces some interesting headaches for purposes of
choosing our AS for origin validation.  In the simplest possible case, we
must always reconstruct the path according to the rules prior to choosing
the origin AS.  If we fail reconstruction (more on that below), then we
probably shouldn't use the original AS_PATH for purposes of doing origin
authentication.

Our two malicious cases when reconstruction fails are that the AS_PATH has
been tampered with but that the AS4_PATH is correct or vice-versa.

Our non-malicious case has to do with ambiguities in RFC 4893 that should
probably be clarified prior to placing a dependency on this mechanism for
origin validation.  The problem comes with the rules for reconstruction:

:   If the number of AS numbers in the AS_PATH attribute is larger than
:   or equal to the number of AS numbers in the AS4_PATH attribute, then
:   the AS path information SHALL be constructed by taking as many AS
:   numbers and path segments as necessary from the leading part of the
:   AS_PATH attribute, and then prepending them to the AS4_PATH attribute
:   so that the AS path information has an identical number of AS numbers
:   as the AS_PATH attribute. 

Effectively this says that you ignore mis-matches in the ASes.  E.g.

AS_PATH: 1 2 3 4
AS4_PATH:    3 7

Similarly, the RFC is unclear about the case when the ASes are correct but
the structural semantics don't match:

AS_PATH: 1 2 3 4
AS4_PATH:   [3 4]

I don't intend to try to drive clarification of RFC 4893 within SIDR - I owe
my comments to the author of the -bis document in IDR.  However, I would
suggest that this clarification is an important issue for SIDR and should be
monitored.

An additional point that John Scudder had pointed out to me is that valid
"brief" AS_PATH aggregation may yield an AS_PATH and an AGGREGATOR where the
above rules would fail.  E.g.:

AS_PATH1: 1 2 3
AS_PATH2: 1 4 5

Aggregated path: 1 [2 3 4 5]

If AS 100 is the aggregating AS, then the AGGREGATOR AS will not match the
right-most AS.  Sriram's analysis of existing BGP routing data
shows that this isn't problematic.  I would recommend that this case should
be documented for completeness.

-- Jeff

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Wed, 11 Aug 2010 17:42:40 -0400

Sorry for the delay in responding. Please see answers inline below.

Sriram

> -----Original Message-----
> From: Pradosh Mohapatra [mailto:[email-masked]]
> Sent: Monday, August 02, 2010 2:21 AM
> To: Jeffrey Haas
> Cc: Sriram, Kotikalapudi; [email-masked]
> Subject: Re: [sidr] Comment about aggregators and AS_SETs
> 
> after AS_SET"... What does that mean? 

It was a typo. I meant "Matches the origin AS (i.e., the AGGREGATOR ASN 
and the right most AS of the AS_SEQUENCE match).  
Please see the corrected updated slides:
http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf

 >Also, IMO, the attack vector you mention

I think the attack vector is possible for path validation as well as origin validation.
But if you require, in the algorithm, that 
the first AS after AS_SET == AS encoded in AGGREGATOR
and only then take that AS to be origin (Jeff Haas's modification to what I suggested),
then the attack vector goes away. 
The attack vector is possible if we take the AGGREGATOR ASN to be origin 
(for origin validation) without paying attention to the first AS after AS_SET.

Sriram