Subject: [Sidrops] draft-ietf-sidrops-aspa-verification-01: Handling unknowns

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Thu, 25 Jul 2019 05:04:30 +0000

I believe the path verification algorithm works when all ASes in the as-path
make attestations. If some of the ASes make no attestations, then a more complete
algorithm is as follows:

For every sequence (A, B, C) of consecutive ASes in an AS-path:
If A attests that B is not a provider and C attests that B is not a provider,
then B leaked the route: B is transiting for free. The segment is invalid.
If either A or C attests that B is a provider, then the AS-path segment  (A, B, C) is valid.
If neither A nor C make an attestation, then the leak state is unknown. Even if B lists both A and C as providers, it is not necessarily a leak, because either A or C could consider B as a provider for some of their routes, even though they don't attest to it.

If all the path segments are valid, then the whole path is valid.
If any of the path segments is invalid, then the whole path is invalid.
Else, at least one path segment is unknown and one more rule must be applied: for any sequence of ASes (A, B1, ..., Bn, C), if A attests that B1 is not a provider and C attests that Bn is not a provider, then the AS-path is invalid. This is for any number of Bx greater than 1.

This algorithm breaks the AS-PATH into triples instead of pairs.
For example, the AS_PATH (A,B,C,D,E) is broken into the triples:
(A,B,C), (B,C,D), (C,D,E).
I find it easier to reason about it like that.
It can probably be re-worded into pairs.

An additional point:
If AS-SETs exist then complete sequences between the AS-SETs can be checked for invalidity.
The best such an AS-PATH can get is unknown, but it can also be verified invalid.

Regards,
Jakob.

-----Original Message-----
From: Sidrops <[email-masked]> On Behalf Of [email-masked]
Sent: Monday, July 8, 2019 1:24 PM
To: [email-masked]
Cc: [email-masked]
Subject: [Sidrops] I-D Action: draft-ietf-sidrops-aspa-verification-01.txt

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the SIDR Operations WG of the IETF.

        Title           : Verification of AS_PATH Using the Resource Certificate Public Key Infrastructure and Autonomous System Provider Authorization
        Authors         : Alexander Azimov
                          Eugene Bogomazov
                          Keyur Patel
                          Job Snijders
	Filename        : draft-ietf-sidrops-aspa-verification-01.txt
	Pages           : 10
	Date            : 2019-07-08

Abstract:
   This document defines the semantics of an Autonomous System Provider
   Authorization object in the Resource Public Key Infrastructure to
   verify the AS_PATH attribute of routes advertised in the Border
   Gateway Protocol.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-sidrops-aspa-verification/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-ietf-sidrops-aspa-verification-01
https://datatracker.ietf.org/doc/html/draft-ietf-sidrops-aspa-verification-01

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-sidrops-aspa-verification-01

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

_______________________________________________
Sidrops mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidrops

---

From: Alexander Azimov <[email-masked]>
Date: Thu, 25 Jul 2019 23:20:20 +0300

Jakob,

I believe your reading of the ASPA verification procedure is incorrect.

Section 4 defines pairs wise verification procedure (let's call
pair_verification) which returns valid, invalid and unknown.
Sections 5.1 and 5.2 define verification procedure for upstream and
downstream path respectively.

In these procedures, the 'valid' and 'unknown' outcome of pair_verification
is the same. These procedures return 'valid', 'invalid' and 'unverifiable'
(in case of valid AS_SEQ + presence of AS_SET). So, your assumption that
the algorithm works when all ASes in the as-path make attestations is
incorrect.

To perform verification you don't need to split ASPATH into triplets (or
even bigger windows). I sent previously a linear function that makes
verification for the downstream path, for the upstream path it even
simpler. Since you are already working on the implementation I suggest to
discuss it in person before the end of this meeting. It makes me really
anxious if the specification is unclear for implementers.

чт, 25 июл. 2019 г. в 08:04, Jakob Heitz (jheitz) <[email-masked]>:

> If neither A nor C make an attestation, then the leak state is unknown.
> Even if B lists both A and C as providers, it is not necessarily a leak,
> because either A or C could consider B as a provider for some of their
> routes, even though they don't attest to it.
>
> Else, at least one path segment is unknown and one more rule must be
> applied: for any sequence of ASes (A, B1, ..., Bn, C), if A attests that B1
> is not a provider and C attests that Bn is not a provider, then the AS-path
> is invalid. This is for any number of Bx greater than 1.
>
>         Title           : Verification of AS_PATH Using the Resource
> Certificate Public Key Infrastructure and Autonomous System Provider
> Authorization

-- 
Best regards,
Alexander Azimov

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Fri, 26 Jul 2019 05:38:46 +0000

If you receive an AS-PATH of 2 ASes and neither of them make any attestation,
then your procedure calls it valid. It could be invalid,
so it must be considered unknown.

If an AS-PATH contains an AS-SET, then the segments on either side of
the AS-SET can still be verified. If any such segment turns out to be
invalid, then the whole path must be considered invalid, not unverifiable.

My procedure accounts for these cases and more.
For the cases where every AS makes an attestation, my procedure agrees with yours.

BTW, you have a copy/paste error in 5.2 Downstream paths:
If a route from ROUTE_AFI address family is received from a customer
should be:

If a route from ROUTE_AFI address family is received from a provider

s/ ot / or /

Regards,
Jakob.

From: Alexander Azimov <[email-masked]>
Sent: Thursday, July 25, 2019 1:20 PM
To: Jakob Heitz (jheitz) <[email-masked]>
Cc: [email-masked]
Subject: Re: [Sidrops] draft-ietf-sidrops-aspa-verification-01: Handling unknowns

Jakob,

Section 4 defines pairs wise verification procedure (let's call pair_verification) which returns valid, invalid and unknown.
Sections 5.1 and 5.2 define verification procedure for upstream and downstream path respectively.

In these procedures, the 'valid' and 'unknown' outcome of pair_verification is the same. These procedures return 'valid', 'invalid' and 'unverifiable' (in case of valid AS_SEQ + presence of AS_SET). So, your assumption that the algorithm works when all ASes in the as-path make attestations is incorrect.

To perform verification you don't need to split ASPATH into triplets (or even bigger windows). I sent previously a linear function that makes verification for the downstream path, for the upstream path it even simpler. Since you are already working on the implementation I suggest to discuss it in person before the end of this meeting. It makes me really anxious if the specification is unclear for implementers.

чт, 25 июл. 2019 г. в 08:04, Jakob Heitz (jheitz) <[email-masked]<mailto:[email-masked]>>:
I believe the path verification algorithm works when all ASes in the as-path
make attestations. If some of the ASes make no attestations, then a more complete
algorithm is as follows:

An additional point:

Regards,
Jakob.

-----Original Message-----
From: Sidrops <[email-masked]<mailto:[email-masked]>> On Behalf Of [email-masked]<mailto:[email-masked]>
Sent: Monday, July 8, 2019 1:24 PM
To: [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>
Subject: [Sidrops] I-D Action: draft-ietf-sidrops-aspa-verification-01.txt

Abstract:

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org<http://tools.ietf.org>.

_______________________________________________
Sidrops mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/sidrops

_______________________________________________
Sidrops mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/sidrops

--
Best regards,
Alexander Azimov

---

From: Alexander Azimov <[email-masked]>
Date: Fri, 26 Jul 2019 18:48:07 +0300

In this email, I will answer Jacob's comments + make a brief follow up of
our f2f discussion.

> so it must be considered unknown.
It is an interesting point. When I was writing verification

> *From:* Alexander Azimov <[email-masked]>
> *Sent:* Thursday, July 25, 2019 1:20 PM
> *To:* Jakob Heitz (jheitz) <[email-masked]>
> *Cc:* [email-masked]
> *Subject:* Re: [Sidrops] draft-ietf-sidrops-aspa-verification-01:
> Handling unknowns
>
>
>
> Jakob,
>
>
>
> In these procedures, the 'valid' and 'unknown' outcome of
> pair_verification is the same. These procedures return 'valid', 'invalid'
> and 'unverifiable' (in case of valid AS_SEQ + presence of AS_SET). So, your
> assumption that the algorithm works when all ASes in the as-path make
> attestations is incorrect.
>
>
>

-- 
Best regards,
Alexander Azimov

---

From: Alexander Azimov <[email-masked]>
Date: Fri, 26 Jul 2019 19:07:35 +0300

I'm sorry for the last email. It was supposed to be bigger.

> so it must be considered unknown.
It an interesting point. When I was writing the ASPATH verification
procedure I had in mind that we need to detect invalids. But for debugging
purposes, it might be also useful to distinguish fully verified paths where
all pairs are valid and those paths that represent a combination of valid
and unknown pairs. It will also require clarification that for backward
compatibility such unknown paths MUST be treated as valid. We should add
this option into consideration.

> invalid, then the whole path must be considered invalid, not unverifiable.
I do agree and that's how both downstream path upstream path procedures are
defined in the draft.
As we discussed in person, we might need additional clarification in the
beginning where {AS(I), AS(I-1)...} sequence is defined.

> For the cases where every AS makes an attestation, my procedure agrees
If you have ASPA(1, 2) you can't make assumptions about relations of 2.
Otherwise, it may lead to incorrect results in the case of siblings.

BTW, you have a copy/paste error in 5.2 Downstream paths:
> Yes, you are right. Copy-paste can become tricky. Will be fixed in the
next version.

---

From: "Jakob Heitz (jheitz)" <[email-masked]>
Date: Sat, 27 Jul 2019 01:35:29 +0000

The draft states:

An ASPA attests that a Customer AS holder (CAS) has authorized a particular Provider AS (PAS) to propagate the Customer’s IPv4/IPv6 announcements onward, e.g. to the Provider’s upstream providers or peers.

I suggest to make this more precise and to add the "otherwise" condition:

An ASPA attests that a Customer AS holder (CAS) has authorized a particular Provider AS (PAS) to propagate the Customer’s IPv4/IPv6 announcements to all of the provider's neighbors. If an AS, AS-A publishes at least one ASPA and it lists AS-B as a provider and AS-C is connected to AS-A, but AS-A does not list AS-C in an ASPA, then AS-A authorizes AS-B to propagate the announcements of AS-A to all of AS-B's neighbor ASes and authorizes AS-C to propagate AS-A's announcements only to ASes that consider AS-C to be their provider. I.e., AS-A prohibits AS-C from propagating the announcements of AS-A to AS-D if AS-D does not consider AS-C to be provider for AS-D.

Consequently, a chain of ASPAs can be used to verify the plausibility of an AS-PATH.

Thanks,
Jakob.

On Jul 26, 2019, at 11:08 AM, Alexander Azimov <[email-masked]<mailto:[email-masked]>> wrote:

пт, 26 июл. 2019 г. в 08:38, Jakob Heitz (jheitz) <[email-masked]<mailto:[email-masked]>>:
If you receive an AS-PATH of 2 ASes and neither of them make any attestation,
then your procedure calls it valid. It could be invalid,
so it must be considered unknown.
It an interesting point. When I was writing the ASPATH verification procedure I had in mind that we need to detect invalids. But for debugging purposes, it might be also useful to distinguish fully verified paths where all pairs are valid and those paths that represent a combination of valid and unknown pairs. It will also require clarification that for backward compatibility such unknown paths MUST be treated as valid. We should add this option into consideration.

If an AS-PATH contains an AS-SET, then the segments on either side of
the AS-SET can still be verified. If any such segment turns out to be
invalid, then the whole path must be considered invalid, not unverifiable.
I do agree and that's how both downstream path upstream path procedures are defined in the draft.
As we discussed in person, we might need additional clarification in the beginning where {AS(I), AS(I-1)...} sequence is defined.

My procedure accounts for these cases and more.
For the cases where every AS makes an attestation, my procedure agrees with yours.
If you have ASPA(1, 2) you can't make assumptions about relations of 2. Otherwise, it may lead to incorrect results in the case of siblings.

Yes, you are right. Copy-paste can become tricky. Will be fixed in the next version.