Re: [Sidrops] On validating AS paths

Alexander Azimov <a.e.azimov@gmail.com> Wed, 26 June 2019 16:52 UTC

Return-Path: <a.e.azimov@gmail.com>
X-Original-To: sidrops@ietfa.amsl.com
Delivered-To: sidrops@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3C5A512003E for <sidrops@ietfa.amsl.com>; Wed, 26 Jun 2019 09:52:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id S5JggGP7fIYz for <sidrops@ietfa.amsl.com>; Wed, 26 Jun 2019 09:52:07 -0700 (PDT)
Received: from mail-ot1-x334.google.com (mail-ot1-x334.google.com [IPv6:2607:f8b0:4864:20::334]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A690C120100 for <sidrops@ietf.org>; Wed, 26 Jun 2019 09:52:07 -0700 (PDT)
Received: by mail-ot1-x334.google.com with SMTP id r21so3229408otq.6 for <sidrops@ietf.org>; Wed, 26 Jun 2019 09:52:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=HAtUELjnxQ9V/LjJRdTPRWdChhNiGjjn32bHMSAfeqc=; b=Nnqh/Pv2XhK7kudWN+j8m7yWBukj6Tes2KFG3t14/SPH+yt3Pw46tA219YElQTRTG0 pUI5HE+hP44i+Ed8s66nbEWUtIbcK3+vDJdZFDxwWg4smNtENeiSUPLXJSSJ3Fe6W2bZ x2ZH9PGvGtwXSqV3StyI1prBneLQbPPm4Pk1KyY9qrIjCRNl5pU4RT+Xgz1Un46k+5es uRvwsZTVruoW2w7fS6scRfAr9zvOZVN9A7ukVANPNX5tmFScBvjlLRL3maJd1AuFAEwq 57OGHtU/8+YFEfi/9tNTllkW7AFOqKBCobw10qRjZUwOyB45woViHjEG8b2lV2vd0c9i F03Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=HAtUELjnxQ9V/LjJRdTPRWdChhNiGjjn32bHMSAfeqc=; b=h2UA0m1Pf0qMd/Ag9L1iTyyF1wukcWmp3MeqJrNGRfwdv5Q1QnAh8BifbmMrf/O8Oc mnJMH9EjTlDPqq8YXfLMJR3bs9iLkyWcFDc0aSBpXGWGpj2AP1jViJ2LxCBehWSPxEiS 0kWTNAFsKtpbaPoVGedOVIg7mjM3D8U6/Abpim7OMFCGSrYlgr86GdmEXJqlIrJbKZ67 yXmGVwKvazDPreIqD3x3ifzSP/cCo9563GgSahFzP+aFSTSo0lqdnoldHSUJHQcmzyb3 z9O+gOZIFCmnSeHBtRWLmhBRYF1BHxgic6rpevNKaPiPenSvZRayWpddxdxDso77ymtV TWUQ==
X-Gm-Message-State: APjAAAVfNbZUOIOCFLHtJRT50hoYspKGM5FG39oSqxeGha+F6DaWQF/o Mal1spqm83WX5Ulv37dMnF0DRcnhMBHAZAW7hgg=
X-Google-Smtp-Source: APXvYqzE9Qz8l2TU4a56rdAPzGzx6MNcZbz7xUt6p1ImM/4ePeCLF8APPGpf0TeWdDr4wzwBDGfRkoEjB2zN80QPZRk=
X-Received: by 2002:a9d:76d3:: with SMTP id p19mr4113516otl.18.1561567926913; Wed, 26 Jun 2019 09:52:06 -0700 (PDT)
MIME-Version: 1.0
References: <9D1926FB-30B0-4A28-8AAF-32527BCC2F9F@muada.com> <CAEGSd=AAQqL6kbZKOEjRABd00n27VKSnMRW6W3Xyb=6y6q-ziA@mail.gmail.com>
In-Reply-To: <CAEGSd=AAQqL6kbZKOEjRABd00n27VKSnMRW6W3Xyb=6y6q-ziA@mail.gmail.com>
From: Alexander Azimov <a.e.azimov@gmail.com>
Date: Wed, 26 Jun 2019 19:51:55 +0300
Message-ID: <CAEGSd=BApqEEy5oaAvLE1GYySy15z2Mcn0Za0Ek+_xOxxtYT1w@mail.gmail.com>
To: Iljitsch van Beijnum <iljitsch=40muada.com@dmarc.ietf.org>
Cc: sidrops@ietf.org
Content-Type: multipart/alternative; boundary="000000000000939174058c3cdd5c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/sidrops/wliLelBEdSq1ccDkphj-ilSco6s>
Subject: Re: [Sidrops] On validating AS paths
X-BeenThere: sidrops@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: A list for the SIDR Operations WG <sidrops.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/sidrops>, <mailto:sidrops-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/sidrops/>
List-Post: <mailto:sidrops@ietf.org>
List-Help: <mailto:sidrops-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/sidrops>, <mailto:sidrops-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 26 Jun 2019 16:52:11 -0000

And to follow up my previous email, if we have a network with malicious
intent that would hijack/disaggregate prefixes + create a 'virtual peering
link' between it and victim ASN, its customers will not able to detect it
anyway since it will look like a valid path: '-\'.

And we can't properly specify peerings because of transparent IXes.

ср, 26 июн. 2019 г. в 19:39, Alexander Azimov <a.e.azimov@gmail.com>om>:

> Hi Iljitsch,
>
> I assume that after talking with Job Snijders you are aware of ASPA drafts.
> They cover the detection of anomalies (invalid ASPATHs) that are received
> from customers and peers + specify RPKI object exactly for
> customer-to-provider pairs.
>
> It has a different specification for unknown relations - (a1, a2) is
> unknown if only there are no ASPA records for a1.
> And of course, a path //^\ (in your notation) received from customer or
> peer is invalid. But I assume that you also had this in mind.
>
> What I find curious in your proposal is the goal to extend the detection
> of invalid paths for prefixes that are received from providers.
> I was also considering this option, but it will not work with c2p database
> only. The problem occurs with siblings.
>
> Take a look at the next example:
> a1 *p2p* a2 *c2c *a3 *p2c *a4 (p2p for peering, c2c for sibling, a4 is
> checking ASPATH)
> If records for a1 exists (so we know that a2 isn't in the set of providers
> of a1), (a2, a3) records exist, but (a3, a2) doesn't, the outcome of
> verification procedure at a4 will be invalid.
>
> Maybe it can be fixed by adding a sibling flag to the c2p record, but at
> the moment I'm not sure about security consequences.
>
>
> ср, 26 июн. 2019 г. в 18:19, Iljitsch van Beijnum <iljitsch=
> 40muada.com@dmarc.ietf.org>gt;:
>
>> (I hope the list retains my non-proportional font. Reformat if necessary.)
>>
>> After an interesting discussion with Job Snijders the other day about our
>> respective drafts, I think it would be helpful to analyze the issue of AS
>> path validation further before discussion specific solutions.
>>
>> I'm interested to hear if my assumptions and conclusions are shared.
>>
>> I think we can agree that any AS path that doesn't conform to the
>> valley-free model. A quick refresher: the valley-free model assumes four
>> types of relationships between ASes:
>>
>> customer-provider:  /
>> provider-customer:  \
>> peer-peer:          ^
>> sibling-sibling:    -
>>
>> I've invented the / \ ^ - characters to indicate relationships myself,
>> the idea being that they'll visually show valleys if a path isn't
>> valley-free.
>>
>> You can visualize valley-freeness as the customer ASes at the bottom
>> sending many up the hierarchy, and the money will only flow up, not down.
>> So if you have a "valley" in the relationships between the ASes in a path,
>> someone isn't getting paid and the whole thing doesn't work economically.
>>
>> The model also allows for mutual backup arrangements, where basically two
>> ASes provide transit to each other (also called a sibling relationship).
>> How that works financially is a bit murky, but the interesting thing here
>> is that if nobody implements any policies or filters, you have a network
>> with only sibling relationships.
>>
>> So with these four relationships and the valley-free restriction we
>> should be able model any working real-world relationship between two or
>> more ASes.
>>
>> (We'll ignore the possibility that the relationships between ASes may be
>> different for different address families and/or prefixes for now.)
>>
>> For a formal definition of the valley-free model, read "On inferring
>> autonomous system relationships in the internet", Gao, 2001.
>>
>> I'll state it in the form of the following AS path validation procedure.
>>
>> In addition to / \ ^ - we'll also allow ? to indicate an unknown
>> relationship between two adjacent ASes in the path. And we'll assume the
>> sibling relationship between an AS and itself (i.e., if there is AS path
>> prepending).
>>
>> The steps:
>>
>> 1. Trim from the right (origin) side all \ and - relationships
>> 2. Trim from the left side all / and - relationships
>> 3. If the path is now empty or contains just one ^, the path is
>> valley-free and therefore valid
>> 6. If the path still contains / or \ or contains multiple ^, the path is
>> invalid
>>
>> Here are a few valid paths:
>>
>> A: //\\
>> B: /^\
>> C: ^
>> D: ^\-\
>>
>> So the steps produce:
>>
>>             A       B       C       D
>>             //\\    /^\     ^       ^\-\
>> Step 1      //      /^      ^       ^
>> Step 2              ^       ^       ^
>> Step 3      valid   valid   valid   valid
>>
>> If we look at RFC 7908, the first four types of route leaks are caused by
>> the following relationships:
>>
>> 1: \/
>> 2: ^^
>> 3: ^/
>> 4: \^
>>
>> So the steps produce:
>>
>>             Type 1  Type 2  Type 3  Type 4
>>             \/      ^^      ^/      \^
>> Step 1      \/      ^^      ^/      \^
>> Step 2      \/      ^^      ^/      \^
>> Step 3      \/      ^^      ^/      \^
>> Step 5      invalid invalid invalid invalid
>>
>> Now what if we have unknown relationships in the path?
>>
>> /?^\ could be:
>>
>> //^\    /-^\    /^^\    /\^\
>> valid   valid   invalid invalid
>>
>> /?\ could be:
>>
>> //\     /-\     /^\     /\\
>> valid   valid   valid   valid
>>
>> In other words: if steps 1 and 2 above just leave a ?, then regardless of
>> what the unknown relationship turns out to be, we know the path will be
>> valley-free and valid.
>>
>> So we can now extend the validation steps to consider unknown
>> relationships and see even if we assume a best case scenario, we still end
>> up with an invalid path:
>>
>> 1. Trim from the right (origin) side all \ and - relationships
>> 2. Trim from the left side all / and - relationships
>> 3. If the path is now empty or contains just one ^ or just one ?, the
>> path is valley-free and therefore valid
>> 4. Trim from the right (origin) side all \, - and ? relationships
>> 5. Trim from the left side all /, - and ? relationships
>> 6. If the path still contains / or \ or contains multiple ^, the path is
>> invalid
>> 7. Else the path validity is unknown
>>
>> Now all of the above assumes that the relationship between two ASes is
>> uncontested. But what if the two ASes claim to have different relationships?
>>
>> One approach would be to just assume an unknown relationship ?, so the
>> path will only validate under worst case assumptions.
>>
>> In my opinion, a better approach would be just keep track of claims of a
>> customer-provider relationship from the customer side (where the sibling
>> relationship is simply a mutual customer-provider relationship claim).
>>
>> Overclaiming of the relationship by a customer is relatively
>> unproblematic, because the claimed provider will simply not provide the
>> service with no ill effect. Overclaiming by the provider, on the other
>> hand, could be harmful, the combination of the relationship overclaim and
>> incorrect BGP filters will now create a route leak that our path validation
>> system will declare to have a valid path.
>>
>> There is probably no reason to publish peer-to-peer relationships, as a
>> path with ? where there should be ^ will also validate.
>>
>> One interesting issue is route servers, as deployed by internet
>> exchanges. Typically (universally?) those don't add their AS to the AS
>> path, breaking the BGP specification in the process. In that case, the
>> route server is invisible, so validation will have the same result as with
>> a direct peering relationship.
>>
>> If this behavior is not universal, we should either assume a -
>> relationship for route servers, or define a new type of relationship that
>> will be removed from the valley-free validation process.
>>
>> With all of the above out of the way, we'll have to think about which
>> relationship claims to carry in-band and which out-of-band.
>>
>> _______________________________________________
>> Sidrops mailing list
>> Sidrops@ietf.org
>> https://www.ietf.org/mailman/listinfo/sidrops
>>
>
>
> --
> Best regards,
> Alexander Azimov
>


-- 
Best regards,
Alexander Azimov