Overlapping ISDs

[matzf]

Background

SCION ASes can be present in multiple ISDs simultaneously. This is an important feature for (existing and envisioned) real world SCION topologies. We could have, for instance, ISDs organized into different "verticals" (like finance, education, health industry etc). The same ISPs may be operating in the different ISDs, and use the same underlying network infrastructure for the transit traffic of their customers.

Current situation

There is no secure way to determine whether the same AS identifier in different ISDs refers to the same entity; an imposter in a rogue ISD could be (ab-)using the same AS identifier. For all practical purposes, we must considered the different occurrences of the AS as entirely separate ASes that just happen to share the same AS identifier.

To run an AS that is present in multiple ISDs, an operator runs multiple independent ASes on the same internal network infrastructure, linked in a cluster of core-links (or peering-links, for non-core transit ASes).
Paths between the different ISDs need explicit hops containing these core- or peering-links.
Neighboring ASes need to operate separate links for each ISD that they are part of.

Problems

This has the following main disadvantages:

• path length overhead; the hop from an AS to its twin requires a core-segment or a peering link and so add two additional hop fields in the path which need to be processed by two more border routers. Border router implementation could also explicitly handle this special case and process all hop fields in one go, at the cost of significantly increased complexity.
• setup complexity; the AS-local topology and beaconing policy must be chosen very carefully to avoid degrading performance related to the ISD crossing.
• lack of transparency
• beaconing overhead; for core ASes, the beaconing treats paths to the AS in each ISD separately, which will lead to many practically identical paths being discovered.
• no way to discover or address occurrences of an AS in different ISDs.
  For a given ISD-AS destination address, no policy-compliant paths (e.g. paths restricted to certain ISDs) may exist, while policy-compliant paths do exist to the occurrence of the same AS in a different ISD. It may be necessary to explicitly try out multiple ISD-AS combinations. There is currently no mechanism to determine in which ISDs to (also) lookup an AS.

Proposal

The general idea (or goal) is to add information somewhere, so that we can securely add crossovers between up-, core- and down- segments at occurrences of an AS in different ISDs. The underlying assumption is that the hop fields are compatible between the occurrences of the AS in different ISDs. Practically, this means that the interface numbering and hop validation keys are shared.

In all proposed variants, the router implementations need only relatively small tweaks to handle multiple ISDs in the configuration of the local topology information.

Variant 1: virtual hops

Extend the AS entry of path segments (ASEntrySignedBody) with a field listing the (claimed) other ISDs that the AS is present in (repeated uint16 other_isds).
During path segment combination, we allow a direct cross-ISD shortcut between two segments in an AS if the corresponding ASEntries' other_isds mutually include the respective other ISD.
Both AS entries are verified with the AS certificate chains in both ISDs. If we find mutually agreeing entries, we can trust that both occurrences of the AS represent the same entity. This is very similar in spirit to how the peering links are represented in the beacons. We can think of the other_isds list as "virtual" peering hops to the twin AS.

As described above, so far this only works if we have two segments, i.e. up-core, core-down, or up-down segment combinations.
We need an additional mechanism to also allow ISD-crossing in the core AS at the end of an up-segment. This is particularly important, as contacting this core AS is necessary to fetch down-segments in the destination ISD.
To address this, we define "virtual core segments"; these are created by a modified core beaconing process between occurrences of the same AS in different ISD. These path segments consist of two AS entries (with the same AS identifier, but in different ISDs) without hop information (ASEntrySignedBody.hop_entry omitted).
These virtual segments are registered and fetched like ordinary core segments. During path segment combination, the virtual core segment signals that a crossover is allowed (no hop fields added).

The non-core beaconing process remains unchanged, i.e. the beaconing process in the different ISDs remain entirely independent. Implementations can run independent control services for the different ISDs. The core-beaconing process only needs small adaptations to create the virtual core segments.
This scheme can also be made to work if an AS occurs in different ISDs with different roles, i.e. if it is a core AS in one ISD but non-core in a different ISD. Furthermore, the virtual core segments idea can also be extended to allow "joint" core-beaconing of the occurrences of an AS in different ISDs (joint: one path segment includes all the occurrences of an AS), which can be a significant improvement for the scalability of core-beaconing.

Variant 2: other ISDs in AS certificates

Extend the AS certificate with a field listing the (claimed) other ISDs that the AS is present in (represented, roughly, as otherISDs SEQUENCE OF INTEGER). When two certificate chains on the same subject AS mutually include the respective other ISD, we can trust that both occurrences of the AS represent the same entity.
During path segment combination, we allow direct ISD-crossing at an AS if the corresponding AS certificates' otherISDs mutually include the respective other ISD.

This mechanism covers all relevant cases of ISD-crossing during path segment combination (in contrast to variant 1 where two combined mechanisms are required).
The beaconing process remains entirely unchanged. This variant does not allow joint (core-) beaconing.

Compared to variant 1, variant 2 keeps the (relatively small) size overhead in the AS certificates instead of in the beacons. As the certificates are less numerous and longer-lived, this may result in slightly lower overhead for the overall control plane traffic.
This longer lifetime of the information also allows to keep cached information about the ISDs in which an AS is known to be present.

Variant 3: multiple signatures on beacons

Combine the beaconing processes of the overlapping ISDs. The isd_as uint64 identifier in AS entries (ASEntrySignedBody) is replaced with a list of ISDs and an AS identifier (repeated uint16 isds; uint64 as). The AS entry is then signed with the key for each ISD -- this requires that the control service has access to the AS crypto for all ISDs, or a distributed system for signing among the different control services of the AS.
In non-core beaconing, beacons are propagated down to a child AS if the set of ISDs overlaps (non-empty intersection) with the set of ISDs of the core-AS originating the beacon.

During path segment combination, we attempt to verify the individual signatures of an AS entry. The set of ISDs for which the signature was successfully validated, together with the AS identifier, defines the graph node for this AS entry. Shortcuts / segment cross-over are allowed for all segments across this graph node.

Note: with the multiple signatures backed by different certificate chains on each AS entry, the rules on path segment lifetime needs to be decoupled from certificate expiration -- if the certificate renewal schedules are unfavorably (mis-)aligned, the intersection of the certificate lifetimes could be overly restrictive for useful path segment lifetimes. See #4286 (comment).

Compared to variants 1 and 2, the additional signatures leads to a considerable size overhead of the individual beacons. At the same time, the number of beacons/path segments is reduced due to the combined beaconing process. The numbers don't cancel out exactly, as ASes add signatures also for ISDs of which the originating core AS.

As in variant 1, the "joint" core-beaconing can significantly improve the scalability of the core-beaconing process.
While variant 3 is conceptually relatively straight forward, it is clearly the variant with the biggest change compared to the current architecture.

Update (June '23): Removed this variant as it's seems like the least likely contender and blocks moving forward with #4286.

---

My personal preference is variant 2. It doesn't solve everything. but it's really simple.

[JordiSubira]

Thank you for writing this down!

In general, I also lean towards alternative 2, for the simplicity and small overhead compared to the other ones. In principle, I guess the AS membership to ISDs is not expected to be frequently updated.

I'm just wondering the implications of this information being on the certificate. Some questions on the top of my head (which might not be really relevant):

• Must the issuer CA verify that the subject AS actually belongs to the given ISDs?
• Does the fact that we need to convey the membership to remote ISDs to the issuer CA constraints operation in some way (e.g., CA deciding not to sign certificates containing certain otherISDs)?
• I'm not sure how the AS numbers allocation/governance is expected to be carried out (mainly if we can expect that AS numbers will be unique across multiple ISDs), but: Could we have instead of otherISDs, some array containing the IA number in remoteISD, e.g., IAinRemoteISDs, that being a list of the tuple (ISD,AS).

[matzf]

Thanks for the feedback, these are excellent points!

• Must the issuer CA verify that the subject AS actually belongs to the given ISDs?
• Does the fact that we need to convey the membership to remote ISDs to the issuer CA constraints operation in some way (e.g., CA deciding not to sign certificates containing certain otherISDs)?

The idea was that otherISDs is an unverified claim of the AS and that the CA does not verify this. It couldn't perform such a verification without relying on information in the other ISDs, which would violate the autonomy of the ISD's CPPKI and create tricky bootstrapping inter-dependencies.

There is, however, a potential risk that a CA would refuse to sign certificates with particular ISDs in this list. Ideally, this otherISDs would not be a part of the AS certificate, but let's say an amendment to it, signed with the AS key. I don't know whether there is any suitable mechanism for this.

• I'm not sure how the AS numbers allocation/governance is expected to be carried out (mainly if we can expect that AS numbers will be unique across multiple ISDs), but: Could we have instead of otherISDs, some array containing the IA number in remoteISD, e.g., IAinRemoteISDs, that being a list of the tuple (ISD,AS).

The underlying assumption is that AS numbers are assigned globally, i.e. not scoped to ISDs. Recall that the (BGP-)ASNs are implicitly also SCION AS numbers; I imagine that the allocation of the wider range of SCION AS numbers will work analogously.

Technically, a more general "alias" list would work just the same, but I don't think it would be more useful. I can't think of a good reason why an AS would be operated under different AS identifiers in different ISDs -- the only thing that comes to mind is that the CAs could have specific rules for AS identifiers, and perhaps it's best to not open this can of worms. Restricting to the same AS identifier in different ISDs would seem to keep the system transparent.

[JordiSubira]

There is, however, a potential risk that a CA would refuse to sign certificates with particular ISDs in this list. Ideally, this otherISDs would not be a part of the AS certificate, but let's say an amendment to it, signed with the AS key. I don't know whether there is any suitable mechanism for this.

Yes, I do not know if there's any mechanism to encode/distribute this information. At the end, it will become a piece of information signed with a public key, it could even be a independent request/response between Certificate Servers or just added it to the Certificate request responses as optional part in the message.

The rest makes absolute sense and I a agree on the approach to tackle those points.

[benthor]

(Just putting my own re-invention of the wheel from today's SCIONLab presentation on record here)

[benthor]

There is no secure way to determine whether the same AS identifier in different ISDs refers to the same entity; an imposter in a rogue ISD could be (ab-)using the same AS identifier. For all practical purposes, we must considered the different occurrences of the AS as entirely separate ASes that just happen to share the same AS identifier.

I agree in principle. But I think the mere presence of a peering link that is configured between the same ASNs in different ISDs should be a pretty strong (sufficient?) indicator that they represent the same organization. You can not unilaterally configure such a link after all and if you, as a network operator, have the tiniest bit of doubt that the remote side indeed represents your organization in the other ISD, then don't peer with them.

Maybe I'm missing something, but can't we just delegate the responsibility of determining whether the same ASN in two different ISDs represents the same organization to those who are actually operating the AS?

EDIT: Looking at this again, variant 2 seems to also be based on this insight. +1 for variant 2 (if I even get a vote)

[matzf]

Closing this for lack of interest. I still think the design makes sense, especially variant 2.

In the meantime, I have learned that this idea had been part of the original plan when introducing the globally unique AS numbers: #1451, in particular #1451 (comment).
Side note: this overlapping ISD mechanism should not have been used as motivation to introduce globally unique AS numbers. This same mechanism could have been made to work with ISD-scoped AS numbers. As Jordi also observed in his comment above, announcing a list of alias ISD-AS would work just the same as the otherISDs list. In hindsight, the wide and globally unique AS numbers seemed to have caused a bunch of trouble, and no real benefit (but that's not the topic here).

Also related: #2886 (also abandoned due to lack of interest).