Subject: Re: [Idr] [sidr] Levels of BGPsec/RPKI validation, was: Re: wglc for draft-ietf-sidr-bgpsec-protocol-11

From: Matthew Lepinski <[email-masked]>
Date: Thu, 30 Apr 2015 13:48:18 -0400

Iljitsch,

Thank you for the feedback. With regards to bgpsec-protocol and/or
bgpsec-overview, I am not sure what text would be helpful.

For path validation (as opposed to origin validation), the path validation
algorithm returns one of two states. That is, either an update has a valid
signed path or it doesn't. (We discussed previously in SIDR whether there
was a useful third case for path validation, and the working group wasn't
able to come up with one.)

This means that there are six possible states that come from SIDR
validation (assuming you are using both origin validation and path
validation). That is, three possible origin validation states and two
possible path validation states yields six possible joint states. Of
course, one's local policy is free to collapse that state-space if they
wish to treat of some of those states as identical. (Perhaps if origin is
invalid, then it doesn't matter whether path is valid or not ... maybe it
is foolish to care about whether there are signatures on a path if the path
is headed to a bad destination. I don't know ... but it is a matter of
local policy, and it is perfectly fine for different operators to handle
such cases differently.)

In any case, with regards to path validation, I think that in general  one
wants to prefer routes with valid, signed paths over routes that lack
valid, signed paths. However, personally, for path validation, I would not
recommend throwing out all route advertisements where path validation
returns invalid. That is, if the only route you know of to get to a
particular block of address space has a signature that doesn't valid (or
lack signatures because someone in the middle doesn't have BGPsec turned
on), I think it is probably a good idea to use that route despite the lack
of valid signature chain. (But again, this is a matter of local policy, and
I don't want to mandate policy decisions for network operators in the base
protocol specification.)

- Matt Lepinski

On Tue, Apr 28, 2015 at 2:01 PM, Iljitsch van Beijnum <[email-masked]>
wrote:

> On 28 Jan 2015, at 23:38, Sandra Murphy <[email-masked]> wrote:
>
> > idr folk, your attention and comments would be appreciated as well.
>
> Since you ask...
>
> I'm sending this to both idr and sidr as I think this needs broader input
> than just sidr. (And it seems I'm no longer on the sidr list.)
>
> I read draft-ietf-sidr-bgpsec-protocol-11 and
> draft-lepinski-bgpsec-overview-00.txt as well as RFC 6483.
>
> I think what's lacking here is any discussion of what happens when
> certificates etc expire. Please stay with me for a bit:
>
> RFC 6483 talks about RPKI route validation, which suggests that there are
> three possible states:
>
> valid
> unknown
> invalid
>
> where valid is preferred over unknown and unknown over invalid, and:
>
> "It is a matter of local routing policy as to whether routes with an
> "invalid" validity state are considered to be ineligible for further
> consideration in a route selection process."
>
> Actually, I think the only reasonable approach is to filter out invalids
> and prefer valids over unknowns. The important part here is that if there's
> a ROA for 193.0.0.0/21 and then someone announces a more specific like
> 193.0.7.0/24, that /24 will be "invalid", so even in partial deployment
> RPKI users are protected against malicious or accidental more specifics.
> But if invalids are accepted, even with a very low preference, then they
> still get to divert traffic.
>
> So far, so good.
>
> But now what if a certificate expires? We know from the web that this is
> extremely common. If an expired certificate means the prefixes involved are
> marked invalid, this means that filtering invalids becomes very
> problematic: not only will prefixes randomly drop off the net as people
> forget to generate or install certificates or RPKI caches get stale, but if
> things get really bad the resulting lack of connectivity makes it
> impossible to correct the problem...
>
> So what we need is for expired certificates to make the affected prefixes
> revert to unknown rather than invalid. Turns out, that's what happens today:
>
> http://mailman.nanog.org/pipermail/nanog/2014-December/071907.html
>
> However, unless this is specified in one of the related documents other
> than the three mentioned above, this seems to be an implementation choice.
>
> I think the above issue needs to be discussed in an update of RFC 6483 or
> in one of the BGPsec documents.
>
> And there's probably a bit more to think about: wouldn't it make sense to
> be able to filter on the signature algorithm at some point during the
> transition from one algorithm to the next? Or to be able to filter on
> "expired" explicitly? A binary valid/invalid isn't enough.
> Valid/unknown/invalid is workable, but maybe four or five levels is even
> better.
>
> (And have a look at how this works in practice:
> http://www.cisco.com/c/en/us/td/docs/ios-xml/ios/iproute_bgp/command/irg-cr-book/bgp-m1.html
> search for PEX.)
>
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
>

---

From: Matthew Lepinski <[email-masked]>
Date: Fri, 1 May 2015 15:24:41 -0400

My apologies for dropping the distinction between "Path Unsigned" (no
BGPsec attribute) vs "Path Not Valid" (Path validation algorithm fails to
validate). You are certainly correct that there are Nine possible states
(and Randy's table is correct).

That being said, I have some concern about treating "Path Unsigned"
differently than "Path Not Valid", since it is trivial for a malicious
adversary to transform "Path Not Valid" into "Path Unsigned" if doing so
will yield better treatment for some bad route.

On Thu, Apr 30, 2015 at 4:39 PM, Iljitsch van Beijnum <[email-masked]>
wrote:

> On 30 Apr 2015, at 19:48, Matthew Lepinski <[email-masked]>
> wrote:
>
> > For path validation (as opposed to origin validation), the path
> validation algorithm returns one of two states. That is, either an update
> has a valid signed path or it doesn't. (We discussed previously in SIDR
> whether there was a useful third case for path validation, and the working
> group wasn't able to come up with one.)
>
> I think expired certificates qualifies. And a case can be made for strong
> crypto algo vs weak crypto algo is a fourth one.
>
> possible path validation states yields six possible joint states.
>
> Actually nine, assuming < 100% BGPsec deployment:
>
> 1. BGPsec=valid, RPKI=valid
> 2. BGPsec=valid, RPKI=unknown
> 3. BGPsec=valid, RPKI=invalid
> 4. no BGPsec, RPKI=valid
> 5. no BGPsec, RPKI=unknown
> 6. no BGPsecd, RPKI=invalid
> 7. BGPsec=notvalid, RPKI=valid
> 8. BGPsec=notvalid, RPKI=unknown
> 9. BGPsec=notvalid, RPKI=invalid
>
> Only with type 1 can we be sure that the prefix is advertised legitimately.
>
> Type 5 indicates no BGPsec or RPKI deployment and may or may not be
> legitimate. These should have a lower local_pref than type 1. Type 2 is
> strange, but can probably be treated the same as type 5, or perhaps a
> loc_pref higher than 5 but lower than 1.
>
> Types 3, 6 and 9 are bad news, as they may be unauthorized more specifics,
> so it's important to filter these.
>
> Type 4 can happen because BGPsec hasn't been fully deployed yet (remember
> that the whole path must support it while RPKI can be deployed by just the
> "end" AS) but once that's no longer common it will be the attack vector of
> choice because it's easy to fake the origin AS if there's no BGPsec, so at
> some point, these need to be filtered, too.
>
> That leaves 7 and 8, which SHOULD be filtered if they're legitimate BGPsec
> validation failures and not incidental mistakes such as expired
> certificates.
>
> > it is perfectly fine for different operators to handle such cases
> differently.)
>
> Famous last words. Obviously we don't want to be overly prescriptive, but
> I don't think there's as much room for creativity as you suggest.
>
> > However, personally, for path validation, I would not recommend throwing
> out all route advertisements where path validation returns invalid. That
> is, if the only route you know of to get to a particular block of address
> space has a signature that doesn't valid (or lack signatures because
> someone in the middle doesn't have BGPsec turned on), I think it is
> probably a good idea to use that route despite the lack of valid signature
> chain.
>
> Actually I don't think that case can happen. Consider the following path:
>
> 6 5 4 3 2 1
>
> If AS 4 doesn't support BGPsec but the others do, then AS 3 will convert
> the BGPsec_Path to an AS_PATH, removing all the signatures. ASes 5 and 6
> are not in the position to repair this, so as far as they're concerned, the
> path is completely unprotected.
>
> However, what you say here is problematic:
>
> > That is, if the only route you know of to get to a particular block of
> address space has a signature that doesn't valid (or lack signatures
> because someone in the middle doesn't have BGPsec turned on), I think it is
> probably a good idea to use that route despite the lack of valid signature
> chain.
>
> Considering whether a route is "the only route you know" is explicitly
> forbidden by RFC 4271:
>
>   "The function that calculates the degree of preference for a given
>    route SHALL NOT use any of the following as its inputs: the existence
>    of other routes, the non-existence of other routes, or the path
>    attributes of other routes."
>
> However, you can get the same result by simply giving the invalid path a
> low local preference.
>
> However 2, the real problem with allowing prefixes that don't RPKI/BGPsec
> validate is that these invalid prefixes could be more specifics of
> legitimate prefixes, and no matter how high the local_pref of the valid
> prefixes and low the local_pref of the invalid more specifics, the packets
> will be forwarded as per the invalid more specifics.
>
> Therefore, the only workable approach is to completely filter out prefixes
> that don't validate.
>
> However, the downside of such a strict policy is that if the certificates
> used for BGPsec signatures expire, the path will become notvalid and the
> associated prefixes disappear from the internet. That's why we need the
> ability to treat paths that don't validate because of expired certificates
> differently from paths that don't validate for other reasons.
>
>

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 1 May 2015 21:58:34 +0200

On 01 May 2015, at 21:24, Matthew Lepinski <[email-masked]> wrote:

> You are certainly correct that there are Nine possible states (and Randy's table is correct).

Randy's table? I must have missed that one.

> That being said, I have some concern about treating "Path Unsigned" differently than "Path Not Valid", since it is trivial for a malicious adversary to transform "Path Not Valid" into "Path Unsigned" if doing so will yield better treatment for some bad route.

That's a good point. But then, how do you treat those? By filtering the affected prefixes? You can only do that once _all_ paths are signed.

So basically, we're stuck with our AS path filters until BGPsec deployment hits 100%.

It would have been better if BGPsec would have had provisions for partial deployment, so that you can have a path that is partially BGPsec protected even if it can't be fully be BGPsec-protected. That way, the filtering issue shrinks in scope as the BGPsec-enabled core grows and non-BGPsec branches turn into leaves and finally go away.

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Sun, 3 May 2015 02:51:36 +0000

>It would have been better if BGPsec would have had provisions for partial deployment, 
>so that you can have a path that is partially BGPsec protected even if it can't be fully be BGPsec-protected. 
>That way, the filtering issue shrinks in scope as the BGPsec-enabled core grows 
>and non-BGPsec branches turn into leaves and finally go away.

“path that is partially BGPsec protected” – I wouldn’t call that “partial deployment”.  
That is just partial path signing.
Partial deployment, on the other hand, connotes that there are islands within which 
BGPsec is deployed, and the rest of Internet is non-BGPsec. 
In this sense, partial deployment is synonymous with incremental deployment.   
Let us discuss incremental deployment and “path that is partially BGPsec protected” separately.

(1) Incremental Deployment:

BGPsec is amenable to incremental deployment, and does provide benefit to early adopters within BGPsec islands. 
For examples, you can have a BGPsec island in Asia in which, say, 30K prefixes are originated. 
And another BGPsec island in Europe in which, say, 50K prefixes are originated. 
All prefix-routes for those 30K (or 50K) prefixes within an island have the full protection of 
BGPsec while they originate from an AS within the island and propagate fully signed to other 
ASes within the same island. When those prefix-routes cross from a BGPsec island 
into non-BGPsec Internet, then they lose the signatures entirely and lose the protection.

Down the road, when ASes from the two islands in this example interconnect using 
BGPsec peering, then the combined BGPsec island will be much bigger, providing protection 
for prefix-routes for all 80K prefixes while they originate from an AS within the combined island 
and propagate fully signed to other ASes within the combined island. 
So incremental deployment can start within islands, 
and grow as islands expand and/or interconnect with each other.

Some additional thoughts on incremental deployment can be found in Section 6.3 of 
the BGPSEC design discussion document:

https://tools.ietf.org/html/draft-sriram-bgpsec-design-choices-07#page-21 
 
(2) “path that is partially BGPsec protected” or Partial Path Signing
If an update with partially signed path is given some sort of preference over an unsigned update 
that would encourage cut-and-paste attacks.  Additional thoughts on why partial path signing 
is disallowed can be found in Section 6.4 of the BGPSEC design discussion document:

https://tools.ietf.org/html/draft-sriram-bgpsec-design-choices-07#page-21 
 
Sriram

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 5 May 2015 22:46:50 +0200

> That is just partial path signing.

The latter is a way to allow for the former.

> BGPsec is deployed, and the rest of Internet is non-BGPsec.

Hm, could be islands of BGPsec in a non-BGPsec sea or islands of non-BGPsec in a BGPsec sea. In practice, what will happen very soon is that there will be a BGPsec core with non-BGPsec leaves and branches.

> ASes within the same island.

Sure. But what if one of those BGPsec-capable ASes has a customer that doesn't run BGPsec? So:

5+ 4+ 3+ 2+ 1-

(where + is BGPsec and - is no BGPsec)

In this case the entire path will be unprotected, even though four of the five ASes in the path are capable of using BGPsec. I fair argument can be made that if it's only the origin AS that's non-BGPsec, the protection afforded is very nearly as good as in the case where the complete path is BGPsec-protected.

And in general it would be better for BGPsec to be more opportunistic and protect whatever it can protect, even if that falls short of full end-to-end protection. Every protected hop takes away an opportunity for malicious parties to do bad things.

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 5 May 2015 23:02:52 +0000

>In practice, what will happen very soon is that there will be a
>BGPsec core with non-BGPsec leaves and branches.

That is a possibility. To encourage leaves (stub ASes) to get on board with BGPsec, the specification 
allows for BGPsec capability to be negotiated independently in each direction (send and receive).
This means that a stub AS can negotiate with its upstream to send signed updates (to the upstream) 
but receive only unsigned updates (i.e. trusts its upstream).
Thus it avoids processing and memory costs associated with processing signed updates and storing them. 
This facilitates the stub AS to avoid expensive HW upgrade, but still benefit from BGPsec.
Please see Section 2 of the BGPsec specification. Also see Sections 6.5 and 6.6 in the 
BGPSEC design discussion document:
http://tools.ietf.org/html/draft-sriram-bgpsec-design-choices-07#page-21 

>In this case the entire path will be unprotected, even though four of the five
>ASes in the path are capable of using BGPsec. I fair argument can be made that
>if it's only the origin AS that's non-BGPsec, the protection afforded is very nearly
>as good as in the case where the complete path is BGPsec-protected.
>

Steve Kent summed it up nicely (in his most recent post on the SIDR list) about the pitfalls 
of allowing partial path signing. 
In your specific example above, let us say, there is also an 8+ who is *malicious* and a BGPsec neighbor of 5+.
8+ does not peer with 1-, but nevertheless sends an update with the following malicious AS path to 5+:

8+ 1-  (for the same NLRI as in your example above)

8+ is basically faking that it got an unsigned update from 1- and 
it is forwarding the same to 5+ with a signature (i.e. 8+ signing to 5+).
How will 5+ know that the partially signed update with AS path of {4+ 3+ 2+ 1-} is legitimate 
and that the other partially signed update with AS path {8+ 1-} is malicious? 
It has no way of knowing that.

Sriram