Geoff: I feel this still needs more careful consideration and more work (in the part of the algorithm that deals with AS_SETs). My responses to your comments inline.
Sriram >________________________________________ >From: Geoff Huston [[email protected]] >Sent: Wednesday, October 13, 2010 7:03 PM >To: Sriram, Kotikalapudi >Cc: [email protected] wg >Subject: Re: [sidr] draft-ietf-sidr-roa-validation-07 submitted > >On 14/10/2010, at 6:52 AM, Sriram, Kotikalapudi wrote: > >> Hi Geoff: >> >> I just wanted to provide you some more comments for clarity. > > >Unfortunately, I'm not sure that this note had your intended effect. I think you misunderstood the attack vector that I described which I feel is made possible by the AS_SET-related portion of the algorithm described in your draft. It undermines ROA-based origin validation for any and all prefixes, not just those with aggregation using AS_SET. Please see examples below. > >> For updates with AS_SET, the algorithm in your draft >> only checks the ASN in the AGGREGATOR field >> to see if it matches with the ASN in the ROA. >> This approach allows tools for a would be attacker to >> hijack a prefix in one of these two ways: >> 1. Artificially inserts an AS_SET (possibly an empty AS_SET or >> with just his ASN in the AS_SET), places a matching ASN from the covering >> ROA for the prefix being hijacked into the AGGREGATOR field, >> and places his own ASN as the first AS after the AS_SET to attract traffic >> toward him. > >But surely this can work for ANY prefix - i.e. replace the >received AS path with a bogus AS path and leave only the (valid) Origin AS. >If one is going to lie about the Path than politely asking the liar to >only lie in ways that this particular framework can detect is surely a little >far-fetched isn't it? I feel you may have misunderstood the attack vector (sorry if I failed to word it carefully the first time). Please consider the example: Valid ROA exists: {10.1.1.0/24, Origin = AS1} Hijacker owns AS2 and propagates an update as follows: AS2 [AS2], AGGEGATOR = AS1, 10.1.1.0/24, where [AS2] is an AS_SET that the hijacker has inserted to take advantage of your algorithm. Note that he did not even insert the true origin before his ASN! Your algorithm treats this update as one with AS_SET and AGGREGATOR present, and it would assign status “Valid” to this the update from the hijacker. That is because you take the AGGREGATOR ASN, i.e., AS1 to be the origin and the ROA check passes. But in reality the hijack succeeds (to the extent BGP shortest path algorithm works in favor of the hijacker) and the traffic in part goes to AS2 (the hijacker). Am I right? In my view this is not path modification; it is simply origin manipulation. A straight forward heuristic that is derived from empirical evidence fixes this problem (makes the hijack infeasible). If you had a chance to look into my slides, http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf what we have empirically established there is that the ASN in the AGGREGATOR attribute is practically identical to the first AS element of the last path segment of type AS_SEQUENCE (i.e. the AS in the rightmost position immediately preceding the final AS_SET path segment in the protocol message). For simplicity, we have called this “first AS element ...” the “First AS after AS_SET.” Please see slides 2, 3 and 4. The above stated empirical observation is true for 97% BGP updates with AS_SET and 98.5% in RIB entries with AS_SET (based analysis of extensive Routeviews data) – please see slides 3 and 4. The residual 3% in updates or 1.5% in RIB (where the AGGREGATOR ASN does not match the first AS element of the last path segment of type AS_SEQUENCE) are because the AGGREGATOR fields contains private ASN – that does not seem RFC 4271 compliant. So we need not care about these residual cases. Now based on the above evidence, to identify the origin AS when AS_SET is present, we need NOT look at the AGGREGATOR; instead we look at the AS that “follows” the AS Set (where "follows" is defined as "to the left of" in a Right to Left sequence ordering of the path from origin to local). Based on the above set of observations, a simple heuristic for the algorithm is as follows: If the final path segment of the AS_PATH is of type AS_SET, indicating that the route is an aggregate, then the origin AS is taken the AS that “follows” the AS Set (where "follows" is defined as "to the left of" in a Right to Left sequence ordering of the path from origin to local). (Does not matter if AGGREGATOR attribute is present or absent). (Note: We looked hard at lots of update/RIB data and found ZERO BGP updates and RIB entries which have more than one AS_SET. Thus, when an AS_SET is found in an update, there is one and only one. Also, the AS_SET always -- in 100% of updates with AS_SET and 100% of RIB entries with AS_SET -- appeared in the right most position in the AS path.) With the above approach to the algorithm, the hijack vector talked about above goes away. The hijacker now has to insert the true origin AS (per ROA) prior to his ASN to have a chance at success – that is the minimum we expect with ROA-based origin validation. He can no longer get away with substituting his ASN in place of the AS that “follows” the AS Set (with my suggested heuristic algorithm). We are in no way requiring BGP router to do anything non-compliant with RFC 4721. We simply have a heuristic based on a solid empirical fact that works, and preserves the fundamental premise of RPKI ROA, namely, the first AS of the right most AS_SEQUENCE must be that of the valid originator. > >>2. Takes any legitimate update he sees with an AS_SET in it; >>leaves the AS_SET and AGGREGATOR field unmodified; places his >>own ASN immediately next to the AS_SET and propagates the update. >>(He doesn't need to insert the true origin before his own ASN!). > >But surely if the check is on the AGGREGATOR field then this >would not alter anything. I'm not sure what your point is here in this second >case. > I am arguing that check on the AGGREGATOR attribute alone leads to this attack vector as already explained above. > >> >>There is a rather simple modification to your algorithm >>which mitigates these types attacks. > >I honestly don't think so. > >>Looking at the update/RIB data analysis in my presentation, >>it is clear for all practical purposes, that the ASN in the AGGREGATOR field >>is the same as the "first AS after the AS_SET" with very high probability >>(when they do not match, it is because the update is evidently flaky >>involving private ASNs, etc.). >>So the obvious remedy seems to be as follows: >>Check if the ASN in the AGGREGATOR field matches the >>the "first AS after the AS_SET". >>If true, then call that ASN the origin. >>Else, consider the origin indeterminable. >> >>If you take look at the data analysis in my slides (slides 2-4), >>the above approach seems quite well supported for determining >>the origin and at the same time mitigating the type of attacks noted above. >> >>Please let me know if this seems reasonable. Thanks. >> > >Its as reasonable as any other mechanism for origin validation that leaves the >AS PATH >untouched. i.e. its a wafer thin veneer of potential plausibility masking >a rather large and gaping hole of vulnerability. :-) The new attack vector I am concerned about is not about path modification; it is still origin modification that the attacker seems to get away with as explained above. > >Presumably if one were to introduce some form of path validation >to replace that gaping hole with something a little more substantial >one would also add a mechanism that would validate the aggregator as well. >In which case, if the aggregator and path are validated then why >would the origin AS definition require this double-barrelled approach of >having both match? > >So I'm at a loss to understand why adding a further constraint >(that the AGGREGATOR matches the "first AS after the AS_SET") >helps in any way. Why do you think that this additional constraint >in the definition of an origin AS is a net improvement? As stated above, the problem (new attack vector) goes away if the origin AS is taken the AS that “follows” the AS Set (where "follows" is defined as "to the left of" in a Right to Left sequence ordering of the path from origin to local). Basically, it is not advisable to go by the AGGREGATOR attribute to define the origin AS. > >I'm also unsure as to your approach ere - surely the appropriate >analysis here is to ensure that the definition encompasses valid >(as per the BGP spec) actions by BGP speakers. i.e. if a BGP speaker >acts in accordance with RFC4271, and generates ROAs as appropriate, >then shouldn;t we be worried here is there are cases where acting >within the spec produces outcomes that are judged to be not valid. > >So rather than "mitigating attack" lets look at this from the other >perspective - does this definition fail to encompass legitimate >actions on the part of BGP speakers? > >Back to basics - in the current BGP definition (you know, the one >that still allows silly stuff to happen with proxy aggregation and AS Sets), >isn't the Aggregator path attribute meant to denote the AS identity of >the BGP speaker who performed the more recent proxy aggregation >that formed this particular aggregate prefix? And its thats the case >then surely that AS is the origin of the aggregated route? Yes? I feel this is where the mistake is that makes possible the new attack vector. Empirically, the AS that “follows” the AS Set matches with the ASN in the Aggregator path attribute. That is catch. Therefore, always take the first AS of the rightmost AS_SEQUENCE to be the origin – for all updates, regardless of presence of AS_SET or not. This eliminates the attack vector. > >As far as I can tell your case would be stronger if you proposed "use >Aggregator, >if present, otherwise use the AS that follows (where "follows" is defined as >"to the left of" in a Right to Left sequence ordering of the path from >origin to local) the AS Set. If there are multiple instances of AS Set in >the path and no aggregator, then abandon all hope and surrender to >the gods with an unknown origin AS" as this would align wioth >the text of the BGP spec that makes AGGREGATOR optional. >But requiring a match is going one step further than the BGP spec, surely. We are not requiring anything like that from BGP speaker. Our observation is purely empirical that leads to a more robust approach in the algorithm for validating updates with AS_SETs without compromising the normal updates. > > >So I'd like to propose the following text in section 3,. which adds a >sentence immediately before the final sentence in the paragraph: > >If the final path segment of the AS_PATH is of type AS_SET, indicating >that the route is an aggregate, then the origin AS is taken as the AS > component of the AGGREGATOR attribute [RFC4271], if present. If the >AGGREGATOR attribute is missing, then the origin AS is the first AS >element of the last path segment of type AS_SEQUENCE (i.e. the AS in >the rightmost position immediately preceding the final AS_SET path >segment in the protocol message. Otherwise the route's origin AS >cannot be determined." This still does not resolve the issue we are discussing. Sriram ------------ >It does not attempt to impose a greater constraint on the definition than that >of the BGP standard itself, which notes that AGGREGATOR is an optional >transitive attribute containing the last AS number that formed the aggregate >route. So either its there and therefore its the most recent aggregator or its >not there in which case look at AS the immediately precedes the AS Set. > >(Frankly, deprecating AS-Sets is a far better answer to this particular >definitional problem you have noted, and having some form of mechanism that >validates path is about the only way I know how to detect folk who lie about >the path. You can't substitute an origin validation technique for path >validation. Square pegs, round holes, etc.) > >regards, > Geoff > >Regards, >Sriram >> >>-----Original Message----- >>From: [email protected] [mailto:[email protected]] On Behalf Of >>Sriram, >>Kotikalapudi >>Sent: Monday, October 11, 2010 10:14 AM >>To: Geoff Huston; [email protected] wg >>Subject: Re: [sidr] draft-ietf-sidr-roa-validation-07 submitted >>> >>Geoff: >>> >>I have a concern about the way the origin is determined >>when AS_SET is present in an update. >>Quoting from draft-ietf-sidr-roa-validation-07: >>"If the final path segment of the AS_PATH is of type AS_SET, indicating >>that the route is an aggregate, then the origin AS is taken as the AS >>component of the AGGREGATOR attribute [RFC4271], if present. >>Otherwise the route's origin AS cannot be determined." >>> >>At the Maastricht SIDR WG meeting, I gave a presentation in which >>I highlighted a new attack vector that is possible due to the >>above quoted way of determining the origin AS. >>Please see slide 7 of said presentation: >>http://www.ietf.org/proceedings/78/slides/sidr-4.pdf >>http://www.antd.nist.gov/~ksriram/AS_SET_Aggregator_Stats.pdf >>(The second link has slightly revised slides with corrections.) >>> >>In the presentation, I also pointed out a simple method for >>avoiding the new type of attack (also on slide 7). >>This method (or remedy) draws support from the >>data that I presented in the preceding slides (slide 2-4). >>> >>After my presentation, there was significant interest in this topic >>and some good discussions followed on the list; links to some of which are: >>http://www.ietf.org/mail-archive/web/sidr/current/msg01780.html >>http://www.ietf.org/mail-archive/web/sidr/current/msg01794.html >>http://www.ietf.org/mail-archive/web/sidr/current/msg01791.html >>> >>Of course, a different take on all this is to deprecate the AS_SET. >>http://www.ietf.org/mail-archive/web/sidr/current/msg01772.html >>Warren Kumari has submitted a draft to IDR to try to accomplish that. >>Until that is accomplished, if we think we have to be compliant with >>RFC 4271, then I think my suggested solution makes sense. >>> >>You may also factor in some comments/augmentation that Jeff Hass >>and Pradosh have made to my proposal: >>http://www.ietf.org/mail-archive/web/sidr/current/msg01791.html >>http://www.ietf.org/mail-archive/web/sidr/current/msg01794.html >>> >>Regards, >>Sriram >>________________________________________ _______________________________________________ sidr mailing list [email protected] https://www.ietf.org/mailman/listinfo/sidr
