protocol: segment ID is narrow

[matzf]

Background

The segment ID of the SCION path's info field is used to chain the hop field MACs.
The hop field MAC for the $i$'th hop of a path segment is computed as

hops[i].MAC = checksum(
    key, 
    // info field
    timestamp,
    // chained MACs
    segID XOR hops[0].MAC[:2] XOR hops[1].MAC[:2] XOR ... XOR hops[i-1].MAC[:2],
    // hop field data
    ingress, egress, exp time
)

See the documentation on Hop Field MAC computation for more details.
Some background on this can also be found in this document describing the (at the time) new SCION header: SCION_Header_Redesign.v2019-11-05.pdf

One of the purposes of this aggregated segment ID and preceding hop field MACs is prevent path splicing. Path splicing means fabricating new, illegitimate path segments from fragments of legitimate path segments.

Example:

Notation: AS identifiers are capitals letters A-F, interface identifiers are lower case letter pairs "xy" denoting an interface in AS X connecting to AS Y.

Path splicing is prevented in SCION paths by the segment ID and MAC chaining mechanism. If a hop field is inserted into a different path segment than it was created for, the XOR-aggregation of segment ID and preceding hop field MACs will be different, and the MAC validation will fail.
That is, unless there is a per-chance collision of the 16-bit segment ID.

Probability for Segment ID Collisions

Multiple path segments are "candidates" for a path splicing attack if they share the ingress interface and have the same timestamp (as this is explicitly also covered by the MAC). If such a candidate set is large enough, the probability of collisions among the 16 bit segment ID grows substantially ("birthday paradox"). E.g. for a candidate set of 200 paths, the probability for at least one collision is ~25%.

Assuming that timestamps are unique, just for the moment, path segments that are candidates for path splicing can occur in core beaconing if a segment "diverges" and than "converges" back:

As we limit the number of propagated path segments with the same origin AS, the "candidate set" here is typically only 5 segments. The probability of collision is merely 0.015% (0.00015).
This seemingly low probability is, however, compounded over time as there is a new chance at each beaconing interval. At a beacon interval of 5 minutes, this results in roughly 4% chance of a collision in a day (1 - (1-0.00015)^(24*12)), or about 70% in a month.

This is the chance for a collision for segments with one specific origin, at one specific "splicing point". An attacker may be looking at possible splicing candidates all over the network. Possibly not all of these may be useful to the attacker, but lets just assume an attacker wants to splice a path just for the sake of it.
Again, this compounds probabilities of some opportune collision occurring somewhere; in a network with N ASes, connected so there are at least 5 different paths between any two ASes, this gives us a chance of 1 - (1-0.00015)^(N*(N-1)*5) of at least one collision somewhere during each beaconing interval. That's about 25% with 10 ASes, and already close to 100% with 100 ASes.

Returning to the timestamp; this has granularity of seconds. With a beaconing frequency of 5 minutes, there are only 300 possible timestamp value during each interval. In core beaconing, for each core-link two beacons originated during each interval (one from each AS connected by the link). The probability of segments being originated at the same time is almost 1 in a network with merely 30 core links!
I don't know how to model this precisely, but it appears to me that this high chance of some collisions among the timestamp might significantly increase the "typical" set of compatible path segments among which a segment ID collision will lead to an opportunity for path splicing.

Discussion

These collision probabilities seem rather high, the segment ID field is too narrow to give us a good safety margin against path splicing.

It should be noted that path splicing attacks, while not entirely benign, do not affect the routing of legitimate packets; the most convincing attack scenario seems to be an attempt to create a routing loop. A successful splice of two path segment fragments can create a path that traverses some links twice. More looping can be done by splicing more fragments into the same path, but the probabilities of multiple simultaneous opportune collisions seem to vanish quickly.
Such a loopy path can be used as amplification factor when attempting to overload a link/router.

It's not clear to me if this attack scenario is at all relevant.
The main reason I'm writing this up is that I was not previously aware that the defense mechanism against path splicing is effectively probabilistic.

Creating routing loops by splicing

To illustrate how splicing can be used to create routing loops with core path segments, here's an example of how two valid core path segments could be spliced into invalid paths. If the segment IDs collide in one suitable location, a path can be made to traverse a link twice.
In the much more improbable case that the segment IDs collide at two suitable places, a loop bounded only by the max path size could be created.

Solutions?

There are 8 reserved bits right next to the segment ID in the info field. The segment ID could thus easily be extended to 24 bits. The processing rules would only need to be updated slightly, so that the hop field chaining would now aggregate 24 bits of the MAC instead of 16.
Unfortunately, there does not seem to be a an easy way to introduce such a change. Control services, routers and end hosts all need to process this information, and would need to be changed.

Extending the segment ID to 24 bits could increase the safety margin a bit, but for large networks, collisions will still occur eventually.
I don't know how wide the segment ID field would need to be in order to consider this quite safe.