Subject: [sidr] Enumerating all scenarios with AS-set (was: RE: Comment on draft-ietf-sidr-roa-validation-05)

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 6 Apr 2010 00:31:00 -0400

> ....
> So, for a wild example, suppose the validation check looked to see if one
> single AS in the origin AS_SET matched a valid ROA for the prefix, and
> passed the BGP route as valid.  That would give a malicious person a way
> to ensure that their bogus route would be accepted.  If on the other hand,
> the validation code looked to see if all ASs in the AS_SET matched a valid
> ROA, that might break legitimate uses.
> .... 
> --Sandy

Sandy's hypothetical attack example as well John's original message made me think about 
enumerating all the use-case scenarios for {Prefix, Origin} validation with AS-sets.

These are the use-case scenarios that I am able enumerate when the origin in an update is an 
AS-set (please let me know if you can think of any other reasonable use case that is not listed below):

A1: The AS-set consists of a single unrepeated ASN; No ROA exists with a covering prefix.
A2: The AS-set consists of a single unrepeated ASN; ROA exists with a covering prefix; AS mismatch.
A3: The AS-set consists of a single unrepeated ASN; ROA exists with a covering prefix; AS match.

B1: The AS-set contains the same ASN repeated multiple (>1) times and no other ASNs; No ROA exists with a covering prefix.
B2: The AS-set contains the same ASN repeated multiple (>1) times and no other ASNs; ROA exists with a covering prefix; AS mismatch.
B3: The AS-set contains the same ASN repeated multiple (>1) times and no other ASNs; ROA exists with a covering prefix; AS match.

C1: The AS-set contains at least two distinct ASNs; No ROA exists with a covering prefix.
C2: The AS-set contains at least two distinct ASNs; multiple ROAs exist with a covering prefix; AT LEAST ONE of the ASNs in the AS set DOES NOT MATCH with any ASN from the collective set of ASNs in said multiple ROAs.
C3: The AS-set contains at least two distinct ASNs; multiple ROAs exist with a covering prefix; EVERY ONE of the ASNs in the AS set MATCHES with an ASN from the collective set of ASNs in said multiple ROAs.

There are two essential things that the address-resource owner needs to be made aware of about validation:
1. In the long run, when deployment is deemed complete, an update with an AS set will be considered Invalid except in cases A3, B3, and C3.
2. NO concession is made during validation by way of aggregation of more specific prefixes in ROAs to “effectively” create a ROA for a less specific prefix. 
Example: Existence of the following four ROAs, namely, ROA-1: {10.1.0.0/18, AS64496}, ROA-2: {10.1.64.0/18, AS64497}, ROA-3: {10.1.128.0/18, AS64498}, ROA-4: {10.1.192.0/18, AS64499} WILL NOT by itself result in positive validation of an update that has the aggregate prefix 10.1.0.0/16 with the AS set {AS64496, AS64497, AS64498, AS64499} as origin.

Note: Sandy’s hypothetical attack scenario is easily mitigated if the outcome of validation in use case C2 is always “Invalid.” The algorithms should be designed to carefully consider all of the nine use-case scenarios listed above (assuming we are not missing any that are of any consequence).

Sriram

---

From: Sandra Murphy <[email-masked]>
Date: Tue, 6 Apr 2010 13:48:50 -0400 (Eastern Daylight Time)

Comments in line.

> enumerating all the use-case scenarios for {Prefix, Origin} validation with AS-sets.

<snip>
> Example: Existence of the following four ROAs, namely, ROA-1: {10.1.0.0/18, AS64496}, ROA-2: {10.1.64.0/18, AS64497}, ROA-3: {10.1.128.0/18, AS64498}, ROA-4: {10.1.192.0/18, AS64499} WILL NOT by it…

You seem to be presuming specific validation outcomes here.  I'm not 
saying you are wrong, but I'm not certain the use cases document should be 
saying ANYTHING about the validation algorithm.

I also don't know if we have a consensus of the security concerns with 
AS_SETS to be making presumptions about the validation outcomes.  It 
appears that John, for one, does not care for the roa-validation draft's 
suggested outcome.

As wg chair, I'd appreciate some more discussion on what to do with 
AS_SETS.  Jump in any time folks.  As I tried to say yesterday, the object 
here is to avoid leaving a hole in the spec implementers would have to 
imaginatively fill, creating inter-op problems and maybe a vulnerability.

About point 2:  There is this thing called "proxy aggregation" where an 
ISP discovers two external peer BGP routes that are aggregatable and 
announces the aggregate.  Long long ago, IIRC, we decided that proxy 
aggregation was too hard and too rare and we would declare it out of 
scope.  Your point 2 would specifically disallow proxy aggregation.  Not 
saying that's a bad thing, for a feature that was declared out of scope. 
Just warning about the side effect.

--Sandy

---

From: Sandra Murphy <[email-masked]>
Date: Tue, 6 Apr 2010 15:34:48 -0400 (Eastern Daylight Time)

On Tue, 6 Apr 2010, Sriram, Kotikalapudi wrote:

> Responses inline.
>
>> -----Original Message-----
>> From: Sandra Murphy [mailto:[email-masked]]
>> Sent: Tuesday, April 06, 2010 1:49 PM
>>
>> Comments in line.
>>
<snip>

> My point 2 was not to say that proxy aggregation would be disallowed.
> In that example, if the prefix owner of 10.1.0.0/16 wants the proxy aggregation to pass the ROA validation, then they should be aware enough to create four ROAs
> for the _aggregate_ prefix (/16) as follows:
> ROA-5: {10.1.0.0/16, maxlength =18, AS64496},
> ROA-6: {10.1.0.0/16, maxlength =18, AS64497},
> ROA-7: {10.1.0.0/16, maxlength =18, AS64498},
> ROA-8: {10.1.0.0/16, maxlength =18, AS64499}.
> That is, they should not merely create ROAs for the more specifics
> as stated in my point 2 above, and hope that the router
> algorithm will magically combine the ROAs for the more specifics
> and hence figure it out that the proxy aggregation is OK.
> No ... they should know that will not work.
> The way to make it work is to create ROAs for the aggregate
> as illustrated in ROA-5 through ROA-8 above.
> With this set of ROAs for the aggregate, the four
> ASs listed above can still originate the more specifics (/18s),
> and when an upstream ISP's AS does proxy aggregation, then
> that proxy aggregation will pass ROA validation.
> That is what I think we want to happen.
> It is just a matter of cautioning the user and their ISP about what specific
> ROAs they should create if they wish to do proxy aggregation.

As I understand proxy aggregation, an ISP receives updates from two peers 
and discovers that the NLRI in the two updates coincidentally aggregate 
and the ISP wants to announce the aggregate.  (If I'm wrong, I should be 
corrected - I'm thinking of description in rfc2519 and Geoff's example 
in http://www.potaroo.net/ispcol/2006-05/bgp.html.)

So neither origin AS has authority over the aggregate prefix.  So neither 
origin AS would be able to issue a ROA for the proxy aggregated prefix.

--Sandy

P.S.  I found the long ago discussion on the pre-wg sidr list starting 
with:

http://www.ietf.org/mail-archive/web/sidr/current/msg00025.html

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 6 Apr 2010 14:39:43 -0400

Responses inline.

> > 1. In the long run, when deployment is deemed complete, an update with an AS set will
> be considered Invalid except in cases A3, B3, and C3.
> > 2. NO concession is made during validation by way of aggregation of more specific
> prefixes in ROAs to "effectively" create a ROA for a less specific prefix.
> > Example: Existence of the following four ROAs, namely, ROA-1: {10.1.0.0/18,
> AS64496}, ROA-2: {10.1.64.0/18, AS64497}, ROA-3: {10.1.128.0/18, AS64498}, ROA-4:
> {10.1.192.0/18, AS64499} WILL NOT by itself result in positive validation of an update
> that has the aggregate prefix 10.1.0.0/16 with the AS set {AS64496, AS64497, AS64498,
> AS64499} as origin.
> 

You are right. ONLY the use cases will be recorded in the use case document.
Nothing needs to be said there about the algorithm or validation outcomes.
I mentioned some example validation decisions (which I think are inline
with the current approach in the ROA validation documents)
only to help further this email discussion. 

Sriram

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 6 Apr 2010 17:53:07 -0400

> ________________________________________
> From: Sandra Murphy [[email-masked]]
> Sent: Tuesday, April 06, 2010 3:34 PM
> .... snip ....

You are right. What you describe may indeed be more often the case with proxy aggregation.
I was considering the other (may be less common) case when the deaggregate blocks are all owned
by one common entity, and originated by different ASs which are also owned by that entity.
In the case which you described (possibly the more common case), I agree it is not possible 
to have multiple ROAs for the aggregate.
I would lean towards having such proxy aggregated updates receive a "Not known"
validation assertion during partial deployment period (if no conflicting ROA is found),
and disallow them (i.e., Invalid) when deployment is considered to be complete.     

Sriram 

>
> P.S.  I found the long ago discussion on the pre-wg sidr list starting with:

---

From: Sandra Murphy <[email-masked]>
Date: Wed, 7 Apr 2010 16:13:20 -0400 (Eastern Daylight Time)

> to have multiple ROAs for the aggregate.

If I'm understanding, you are suggesting that the common entity (say 
AS900) holds an aggregate block as well as holding two other ASNs (AS901 
and AS902), that AS901 and AS902 are each originating a distinct more 
specific of the aggregate block and AS900 wants to propagate the aggregate 
route as an aggregation of the two more specific routes, rather than just 
originate a route to the aggregate block on its own.

That seems odd to me, but I've learned not to bet against the existence of 
odd routing policies.  I'd be curious to hear if this is a recognized 
corner case.

Your suggestion is that AS900 could sign a ROA allowing AS901 and AS902 to 
originate the aggregate, if I understand.  That is not what is really 
happening here; but the artificial construct would allow the aggregated 
route to validate.

> I would lean towards having such proxy aggregated updates receive a "Not 
> known" validation assertion during partial deployment period (if no 
> conflicting ROA is found), and disallow them (i.e., Invalid) when 
> deployment is considered to be complete.

By "such proxy aggregated updates" do you mean subcases like what you have 
just described?  Or do you mean cases of proxy aggregation in general?

Are you suggesting a change to the roa-validation draft's handling of 
AS_SETS originations?

Are you suggesting that the roa-validation draft should discuss different 
validity outcomes in different deployment periods?

--Sandy

---

From: Geoff Huston <[email-masked]>
Date: Thu, 8 Apr 2010 09:07:20 +1000

[I was under the impression that the working practice of this WG is for the co-chairs to either explicitly state their particular role and interests in making each and every posting, or, if any such explicit disclaimers are missing, then its reasonable for the WG participants to assume that the Co-Chairs' postings are related specifically to matters that fall within the purview of the functions of a WG chair. To what extent this current thread of enumeration of proxy aggregation use cases relates to the procedures of the WG or a consensus call is not clear to me, so I am a bit puzzled as to why one WG co-chair appears to be so engaged in this thread in what I can only assume is a WG Chair role.]

To quote RFC 4271:

   When a BGP speaker aggregates several routes for the purpose of
   advertisement to a particular peer, the AS_PATH of the aggregated
   route normally includes an AS_SET formed from the set of ASes from
   which the aggregate was formed.

I use the term "proxy aggregation" to describe this action - others may have different terms to describe this practice. 

The efforts to conflate security credentials associated with origination and proxy aggregation have been less than successful, and as John Scudder pointed out its probably a far more direct path to look at origination and proxy aggregation as distinct.  So, in that vein, I'm still comfortable in using the text I proposed earlier in response to John's original observation, namely:

"A route's "origin AS" is the final element of the route object's
 AS_PATH attribute.  If the final AS_PATH element is an AS Set,
 indicating that the route is an aggregate, then the origin AS
 cannot be determined."

This wording, in effect, leaves the entire issue of proxy aggregation and the associated security credentials that would allow relying parties to be assured of the integrity of the proxy aggregation action to be validated by some to-be-determined mechanism that is not necessarily a ROA. In thinking more about the original suggestion of John's it strikes me that an effort to shoehorn the specification of security credentials relating to proxy aggregation into the current constraints of a ROA is not going to be a productive one.

  Geoff

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Mon, 12 Apr 2010 13:23:00 -0400

Sandy:

My responses in line below.
I was traveling last week and had limited access to my NIST email.
Hence the delay in responding. 

Sriram

> Sent: Wednesday, April 07, 2010 4:13 PM
> 

I meant the general case as you stated previously,
"As I understand proxy aggregation, an ISP receives updates from two peers
and discovers that the NLRI in the two updates coincidentally aggregate
and the ISP wants to announce the aggregate."  

> Are you suggesting a change to the roa-validation draft's handling of

Yes, what I had in mind was that if the 9 use cases (w.r.t. AS_SETs)
that I outlined in my email (link below) were duly considered,
then the treatment of AS_SETs would be possibly much more adequate.
Not calling for any fundamental change in the _principles_ behind the
validation methodology; I was merely suggesting enumeration and
consideration of more (hopefully an exhaustive set of) use case scenarios
for updates involving AS_SETs. With this approach, the adversary cannot
exploit or misuse AS_SET to gain advantage. And also, any updates with
with a single ASN (put in once or repeated multiple times) in an AS_SET 
are duly treated, and can be declared "Valid" if there exists a 
ROA for the prefix with that ASN.
The email where I described the 9 use cases with AS_SETs is at:
http://www.ietf.org/mail-archive/web/sidr/current/msg01524.html

Probably no one is proposing changing the ROA structure -- 
nevertheless, I also think that changing the ROA structure to allow
inclusion of an AS_SET as origin is not worth the effort given that
there is an extremely small number of proxy originations observed
per Danny's email:
http://www.ietf.org/mail-archive/web/sidr/current/msg01519.html

> validity outcomes in different deployment periods?

I think this is not an issue really. I was merely thinking that what is considered
"Unknown" (i.e., when ROA is not found) during "partial" deployment would change to
"Invalid" if and when deployment is considered or declared COMPLETE(!) someday. 
But now I think that it does not matter if the algorithm never makes that transition. 
I think there is no harm in continuing on with the decision outcome 
"Unknown" when covering ROA is not found even far out into the future. 
(Here I am speaking in the context of what is already described in the two
ROA validation algorithm documents.)

Sriram

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Mon, 12 Apr 2010 18:40:11 -0400

Comments inline.

Sriram

> From: [email-masked] [mailto:[email-masked]] On Behalf Of Geoff Huston
> Sent: Wednesday, April 07, 2010 7:07 PM
> To: [email-masked]
> Subject: Re: [sidr] Enumerating all scenarios with AS-set (was: RE: Comment on draft-ietf-
> sidr-roa-validation-05)
>
> --- snip ---
>
> The efforts to conflate security credentials associated with origination and proxy
> aggregation have been less than successful, and as John Scudder pointed out its probably a
> far more direct path to look at origination and proxy aggregation as distinct.  So, in that vein,
> I'm still comfortable in using the text I proposed earlier in response to John's original
> observation, namely:
> 

This approach (i.e., "the origin AS cannot be determined" interpretation stated above)
is vulnerable to attacks if the validation decision that goes with it is "Unknown".
(That would be the case if you give the user the benefit of the doubt.) 
The adversary can insert his false origin as an AS_SET (artificially)
and thus attempt to get away with it. But this type of attack can
be prevented as explained below.

Why not look inside the AS_SET and attempt to validate the update? 
If there is a single ASN in the AS_SET --
occurring just once or repeated multiple times -- that is a straight forward case to try 
to test for validation. Danny's data shows 51 of 61 updates with AS_SETs are like that.
http://www.ietf.org/mail-archive/web/sidr/current/msg01515.html 

If there are two or more distinct ASNs in the AS_SET and there is no covering ROA,
then we go with "Unknown" as validation decision. 
If there are two or more distinct ASNs in the AS_SET and there is a covering ROA
and the ASN in the ROA does not match any ASN in the AS_SET, then
clearly we go with "Invalid" as validation decision.
I enumerated other cases (9 cases in all) in my earlier email:
http://www.ietf.org/mail-archive/web/sidr/current/msg01524.html
I tried not to assign validation outcomes there -- I think one can determine those 
rationally following the principles of your current validation algorithm.

This approach (such as the one I proposed above) prevents an adversary 
from taking advantage of AS_SET to try get past the validator. 
And in most cases involving AS_SETs (referring again to Danny's data),
we would be able to decisively evaluate the update as "Valid" or "Invalid" 
when a covering ROA exists for the prefix.
Not much shoehorning is involved as I see it
(unless I am missing something).
 
Sriram
> 
> This wording, in effect, leaves the entire issue of proxy aggregation and the associated
> security credentials that would allow relying parties to be assured of the integrity of the
> proxy aggregation action to be validated by some to-be-determined mechanism that is not
> necessarily a ROA. In thinking more about the original suggestion of John's it strikes me
> that an effort to shoehorn the specification of security credentials relating to proxy
> aggregation into the current constraints of a ROA is not going to be a productive one.
> 
>   Geoff
>

---

From: Geoff Huston <[email-masked]>
Date: Tue, 13 Apr 2010 09:24:25 +1000

Hi,

Personally I I am very unsure of the wisdom of attempting to use a origination authority to infer validation of a proxy aggregation action, regardless of what lies inside the AS Set. It makes more sense to me to consider the requirements for validation of proxy aggregation as an initial step rather than this attempt to retrofit an existing mechanism that has different semantics to the problem. However, as I noted last week, I really am unsure whether this WG is chartered to look at requirements, and hence my question (still unanswered!) to the WG chairs on the charter.

regards,

   Geoff

---

From: Andrei Robachevsky <[email-masked]>
Date: Tue, 13 Apr 2010 11:50:09 +0200

Sriram, Kotikalapudi wrote on 13/4/10 12:40 AM:
[...]

> (unless I am missing something).

I agree with Geoff's point that proper handling of cases of proxy
aggregation depends on the requirements of as-path validation.

But at the current stage of SIDR work, since ROAs do not really protect
against anything malicious, I am more in favour of the original
validation process as stated in draft-ietf-sidr-roa-validation-05. I
think that in reality aggregation is not coincidental and relates to the
fact that the aggregator has the rights to use of the address space of
the covering prefix, and, therefore, is the only one able to issue the
appropriate ROA.

Andrei