Re: [Sidrops] On validating AS paths

Iljitsch van Beijnum <> Mon, 01 July 2019 13:47 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 54D4A1200B8 for <>; Mon, 1 Jul 2019 06:47:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key) header.b=Ach1D3Tu; dkim=pass (2048-bit key) header.b=E/KFmvPq
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Vh2ZUrShGWPh for <>; Mon, 1 Jul 2019 06:47:28 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 80C53120251 for <>; Mon, 1 Jul 2019 06:47:28 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal []) by mailout.nyi.internal (Postfix) with ESMTP id 93AA321650; Mon, 1 Jul 2019 09:47:27 -0400 (EDT)
Received: from mailfrontend1 ([]) by compute2.internal (MEProxy); Mon, 01 Jul 2019 09:47:27 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; h= from:message-id:content-type:mime-version:subject:date :in-reply-to:cc:to:references; s=fm3; bh=uV1X+qiQL4JkvMDAz3qjLWm aNKDwzstqrJyA1g5ACH4=; b=Ach1D3TuTqNQofmyUoioC7y72vGaCpAghb63PaZ mqGc7gFWniGn/4TbATdWlXk5sW8gZXsYbEbaTkOcKjQfoOHNWR9neprIVHBLt0Oq iIS2YoOcoXxlzrP+gLdbYI7W5GgLml9tGCI40jWDQJykRMtt0mVDz3FFzcxc/DVd RaYTZk0T/HuYCYjuyW2hMDeq2dyFK6eszXyuyS5gHK1dow8LMGC5ERsmvuB710ek 3snvdoEK7H8AHVF+Q1vRefhD5Di79obRDc8taJggq3Ti1LwVVO6DqzeRHM2PXSzS jvyk3Y5yMBXGWLs7I0vQ7zsxYbWxKAqkdsPhtmO7dEz56DA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=uV1X+q iQL4JkvMDAz3qjLWmaNKDwzstqrJyA1g5ACH4=; b=E/KFmvPqHhXEDZjmz6IpDq zWMB3L0rArVnAf/scWtPH+4SL9SkcnBqQGvTMxCzsN0zHUpBUGLKK6XU5ja7Xkt5 G7rEWseOXZurCgguT449EPVqO9QW64Q92GttwxqJtxEMBynibKEw8FIFvzqWiER1 K5WerxUNwfFlERQgsPjsLwhy9R/6ki+riUIH+AwMw9A6lzbh+cFbffxcKn5uUL8Q jkshLn5d30sFpYykiuHC/5sdDBKLyGIXutuid5z48J6mQG1zkxtGAmeTc5LDZIkX OqxKdZnLOYGAybbjdxXr6BN9iLnOBUNhceiX/aUuCXYxjpidc8FrvJhF4k3HFF+g ==
X-ME-Sender: <xms:7w4aXU18oy5cBCIDC6lHiGg1GO_SAz2tY4_jhw9fVagSkqVqDrfIZw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrvdeigdeikecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefhkfgtggfuffgjvfhfofesrgdtmherhhdtvdenucfhrhhomhepkfhljhhithhs tghhuchvrghnuceuvghijhhnuhhmuceoihhljhhithhstghhsehmuhgruggrrdgtohhmqe enucfkphepkeefrdekhedrjedurdelheenucfrrghrrghmpehmrghilhhfrhhomhepihhl jhhithhstghhsehmuhgruggrrdgtohhmnecuvehluhhsthgvrhfuihiivgeptd
X-ME-Proxy: <xmx:7w4aXeGZTPBKs66nZ3IzYx0HZFXZiqDxrp2jK7a3R_UExqxplwAbfQ> <xmx:7w4aXdCKpcXJxrPJF4zGn8FNMKVdrjENieDWIWdvNaxjfgz1Q3NVww> <xmx:7w4aXQPigah5xZtkRKwLuBr3qVgVO4iOD2vmQMTT9Tk74-ZjgcFFBg> <xmx:7w4aXZ8sz0URcNSEFcdfTIL_xohGhjDqE6DPjTlc3TMj8bk5Xln_gw>
Received: from [] ( []) by (Postfix) with ESMTPA id 861AF8006C; Mon, 1 Jul 2019 09:47:26 -0400 (EDT)
From: Iljitsch van Beijnum <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_E5B977E5-C713-43FB-8783-77ACD720CA70"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.8\))
Date: Mon, 1 Jul 2019 15:47:24 +0200
In-Reply-To: <>
To: Alexander Azimov <>
References: <> <>
X-Mailer: Apple Mail (2.3445.104.8)
Archived-At: <>
Subject: Re: [Sidrops] On validating AS paths
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: A list for the SIDR Operations WG <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 01 Jul 2019 13:47:42 -0000

Hi Alexander,

On 26 Jun 2019, at 18:39, Alexander Azimov <> wrote:

> 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.

Yes. Note that in my previous message I was specifically addressing validating the _entire_ path, while ASPA only concerns itself with validating the "up" part of the path, where the only valid relationships are provider-customer and sibling-sibling.

Of course once we can validate the entire path, we can by definition also validate any subset.

> 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.

Yes, this is a valid full path but if you get it from a peer then it's actually \//^\ (from a customer) or ^//^\ (from a peer) so that's not valid.

> 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. 

Basically, a sibling relationship occurs when there is a customer - provider relationship in both directions. (As per Gao/Rexford there is the additional constraint that these relationships have the lowest local preference, but that's probably not relevant for path validation.)

So for the "up" part of the path we can use your algorithm for validation. Then for the "down" part of the path (i.e., the part that your customers see when they get updates from you, not covered in your draft) the same procedure will work as long as we look at customer -> provider relationships rather than provider <- customer relationships. I.e.:

900 800 200 100 i

You care 800. You see a valid 200 \ 100 relationship. You know that 800 ^ 200 because you are 800.

900 sees a valid 900 / 800 relationship. 900 sees 800 ? 200 based on the C2P database as there is no C2P relationship between 800 and 200 in either direction. But as per my previous message, any path with exactly one unknown relationship between a valid up part and a valid down part is still valid so the entire path is valid.

> Take a look at the next example:
> a1 p2p a2 c2c a3 p2c a4 (p2p for peering, c2c for sibling, a4 is checking ASPATH)

Do you mean: a1 ^ a2 - a3 \ a4

Note that you are using the opposite order to how BGP AS paths are normally shown, with the origin on the right. But as valley-freeness doesn't depend on the direction, I'll ignore that here.

a1 ^ a2 - a3 \ a4 = /-^ is a valid path, there are no valleys.

> 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. 

So a2 / a3 but not a2 \ a3 and thus not a2 - a3.

This means the path a1 ^ a2 - a3 \ a4 is actually:

a1 ^ a2 / a3 \ a4

^/\ is not a valid path. So a3 has to register its C2P relationship with a2.

> 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.

In the draft you mention that it's important that the customer can claim the relationship and not the provider. So I would be hesitant to have a S2S relationship record is that would either be too easy to claim (if one sibling can do it) or complex to implement (only valid when both siblings claim the relationship).

> 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: '-\'.

You mean a virtual sibling link? No, we certainly don't want that to be possible.