SPAO Improvements / Clarifications

[mlegner]

I would like to discuss several points about the "SCION Packet Authenticator Option" (SPAO), which was recently introduced in #4014 . I am happy to create specific PRs for these points but wanted to get your opinion first, in particular @matzf, @oncilla, @shitz.

Include Address Types and Lengths in Pseudo Header

The fields DT, DL, ST, and SL are important to properly process the addresses and as such should be part of the pseudo header.
Consequently, they would also be part of the SPAO input.

Unfortunately, this would constitute a breaking change as it changes the computation of transport-layer checksums.

Bottom-line suggestion: Add DT, DL, ST, and SL to the pseudo header.

Include Common Header and Path Header in SPAO

The SPAO could also protect other immutable fields of the common header.

In addition, it would also be desirable to authenticate the (immutable parts of the) path header. This would provide a weak form of path validation (i.e., no router on the path modified the path header).

This requires path-type-specific processing of the SPAO as the different path types could have different immutable fields.

It would also be possible (but could come with substantial overhead in particular for routers) to "predict" the values for the mutable fields (HF and INF pointers, SegIDs) at the destination and include them.

Bottom-line suggestion: Include all immutable fields of the common header and path header in the input to the SPAO.

Identify Keys in SPAO

There is currently no mechanism to identify the keys used to compute the authenticator. In case of DRKey, this is determined from the context in most cases, especially as there is normally a "fast side" and a "slow side"; for example, a router creating an SCMP message always uses a key of the form router -> host and a DNS server always uses server -> client. However, this implicit key identification has several downsides in my opinion:

• Identifying the key requires looking at the payload (SCMP or UDP+DNS) to even determine the protocol.
• In some cases, it may be difficult or even impossible to identify the correct key. For example, when authenticating end-host communication, there is no natural fast side; both sender and receiver are normal end hosts. Even if we use the convention, that we use the key receiver -> sender for an initial packet, it would make sense to use the same key also for the reply to avoid having to query the CS. Then it would become quite complicated to determine which key to use and potentially require stateful processing.

Explicitly identifying the key might also have additional benefits besides identifying the protocol and directionality (in case of DRKey). For example, it would in principle be possible to use SVs with overlapping validity periods, which could be differentiated based on this field.

The ideal size of this field depends a bit on how we decide to encode protocols in DRKey (see also #4039). Still, a size of 4 bytes (like the SPI in IPsec) should be good enough for most cases.

Bottom-line suggestion: Add a field KeyID to SPAO (similar to the SPI in IPsec).

Add Time Stamp

To be able to use the SPAO with systems like Lightning Filter, we would need an additional time stamp that would be included in the authenticator input. This serves several purposes:

• Uniquely identify packets (or help with uniqueness) to identify duplicates and thus prevent replay attacks.
• Identify and discard old packets to make duplicate detection practical.

The size depends on whether or not this alone should be able to uniquely identify packets and how it is encoded.

Bottom-line suggestion: Add a timestamp to the SPAO.

Suggestion for Algorithm: Hash+MAC

In the context of Lightning Filter, we have suggested explicitly including the payload hash in the header and verifying the packet in two steps:

1. Source authentication: Calculate the MAC using the payload hash in the header and other header fields as input. If this is unsuccessful, drop the packet directly.
2. Packet authentication: Calculate the hash of the payload and check that it is equal to the value stored in the header.

This has the advantage that long attack packets can be processed much faster as only a handful of block-cipher operations are necessary instead of having to MAC the complete packet.

Bottom-line suggestion: Define an algorithm "SHA256-AES-CMAC" for which the authenticator contains the SHA256 of the payload and the AES-CMAC of header fields plus the hash.

[matzf]

Thanks for starting this discussion and writing this up!

Include Address Types and Lengths in Pseudo Header

Add DT, DL, ST, and SL to the pseudo header.

👍

Include Common Header and Path Header in SPAO

It would also be possible (but could come with substantial overhead in particular for routers) to "predict" the values for the mutable fields (HF and INF pointers, SegIDs) at the destination and include them.

This might not actually be possible in general when reversing the path (e.g. when creating SCMP error replies) as the dataplane path does not contain information about which hop field corresponds to the source AS (it does not strictly need to be at the end of the path).

Include all immutable fields of the common header and path header in the input to the SPAO.

👍

This makes sense to me and I can't think of any good reason not to do this. But I have to admit that I don't really know which additional security properties that this can achieve.

Identify Keys in SPAO

For example, it would in principle be possible to use SVs with overlapping validity periods, which could be differentiated based on this field.

Nice.

Add a field KeyID to SPAO (similar to the SPI in IPsec).

Unsure.

My reservation here is that I believe that in most cases DRKey will require the application specific processing anyway, to ensure that the correct, expected key was specified. It seems like it would be tempting to generalize the processing and fetch keys based on the information in a KeyID field, which could potentially become a vulnerability.

Add Time Stamp

Generally, I'm in favor of this.

The accuracy requirements for this seem to be quite different for the two use cases that we have:

• for lightning filter, the timestamp should ideally be unique (no two packets with same timestamp) and detect high volume replays very rapidly (very accurate time synchronisation and narrow range of valid timestamps)
• for SCMP, this should allow detecting replays of error messages long after the error occurred (low time synchronisation accuracy, range of valid timestamps would be tens of seconds or minutes).

We could use nanosecond granularity within the validity period of a SCION Path, i.e. relative to the (earliest) InfoField timestamp with ~44 bits (6 bytes). I think this would cover both use cases and 6 bytes may just be acceptable.
(Note: with microsecond granularity, it would be about 34 bits and so just over 4 bytes; using a ~4 microsecond granularity to make it fit, or a 5 bytes timestamp both seem like an odd choice)

Suggestion for Algorithm: Hash+MAC

Define an algorithm "SHA256-AES-CMAC" for which the authenticator contains the SHA256 of the payload and the AES-CMAC of header fields plus the hash.

👍

In this case, the MAC is computed over a short input with fixed length (or If we add the path header, the input length is still at least known in advance). The CMAC subkey derivation might add a noticable overhead here. Perhaps we could use a simpler CBC-MAC scheme, with a length prefix if necessary (maybe path meta header suffices).

[mlegner]

Thanks for the feedback!

Include Common Header and Path Header in SPAO

It would also be possible (but could come with substantial overhead in particular for routers) to "predict" the values for the mutable fields (HF and INF pointers, SegIDs) at the destination and include them.

This might not actually be possible in general when reversing the path (e.g. when creating SCMP error replies) as the dataplane path does not contain information about which hop field corresponds to the source AS (it does not strictly need to be at the end of the path).

Hmm... That could happen but is not consistent with the SCION protocol, is it? That means, such a packet is either the result of an error/mistake/bug or an attack. So I don't think we should take this into account.

Identify Keys in SPAO

Add a field KeyID to SPAO (similar to the SPI in IPsec).

Unsure.

My reservation here is that I believe that in most cases DRKey will require the application specific processing anyway, to ensure that the correct, expected key was specified. It seems like it would be tempting to generalize the processing and fetch keys based on the information in a KeyID field, which could potentially become a vulnerability.

Yes, that could be a problem in some cases. But in case the key is already available (through derivation or in cache), it might speed up processing and would allow for some parallelization (i.e., perform crypto checks at the same time as checking whether the KeyID is set "correctly").

Add Time Stamp

Generally, I'm in favor of this.

The accuracy requirements for this seem to be quite different for the two use cases that we have:

* for lightning filter, the timestamp should ideally be unique (no two packets with same timestamp) and detect high volume replays very rapidly (very accurate time synchronisation and narrow range of valid timestamps)

* for SCMP, this should allow detecting replays of error messages long after the error occurred (low time synchronisation accuracy, range of valid timestamps would be tens of seconds or minutes).

We could use nanosecond granularity within the validity period of a SCION Path, i.e. relative to the (earliest) InfoField timestamp with ~44 bits (6 bytes). I think this would cover both use cases and 6 bytes may just be acceptable.
(Note: with microsecond granularity, it would be about 34 bits and so just over 4 bytes; using a ~4 microsecond granularity to make it fit, or a 5 bytes timestamp both seem like an odd choice)

That makes sense to me.

Suggestion for Algorithm: Hash+MAC

Define an algorithm "SHA256-AES-CMAC" for which the authenticator contains the SHA256 of the payload and the AES-CMAC of header fields plus the hash.

+1

In this case, the MAC is computed over a short input with fixed length (or If we add the path header, the input length is still at least known in advance). The CMAC subkey derivation might add a noticable overhead here. Perhaps we could use a simpler CBC-MAC scheme, with a length prefix if necessary (maybe path meta header suffices).

Agreed. Actually, I wanted to suggest CBC-MAC anyway, don't really know why I wrote CMAC... 😄

[matzf]

All clear. I'm ok with the KeyID despite may vague uneasiness about it :)

Most points are fairly clear and at least the two of us seem to agree. :) Perhaps we can discuss the details of how this KeyID should be used and encoded, and then I'd proceed to incorporate these changes into the specification and implementation of the SPAO.

Identify Keys in SPAO

• Do we need to add a way to distinguish different kinds of key identifiers? That is, should this mechanism be able to potentially identify other things than DRKey keys, e.g. IPSec-style security associations?
  If so, how many different kinds should we expect (i.e. how many bits do we need to encode this)?
• How should we encode the DRKey key identifier? As mentioned above, this depends on outcome of DRKey #4039, but here's a preliminary proposal:

  • protocol identifier: 16 bits

  • type: AS-host or host-host, 1 bit

    I think neither the level-1 key AS-AS key nor the (new) intermediate derivation key host-AS need to be representable.

  • direction: receiver-derives-sender-fetches or sender-derives-receiver-fetches, 1 bit

  • epoch: assuming that the grace periods for epochs is such that at any time at most two keys can be active, a single bit suffices to distinguish between the older/newer epoch (active at the time of the included timestamp).

    Such a scheme would force a node to use an active key (assuming it includes the true timestamp); if the epoch is identified by some absolute identifier, it would be possible to keep using keys after the epoch has expired. Assuming that the grace periods are chosen sensibly and requests always use the newest available key, it should still be possible to always keep using the same key to authenticate request/response packets.

[mlegner]

@matzf Thanks for the suggestions for the KeyID. I don't really have an answer to the question about what types of keys we need to be able to encode beyond DRKeys.
Concerning DRKey, your suggestion makes sense to me.

A separate point that I just remembered is the problem of NAT with DRKey. In the PISKES paper, we argued to not include the addresses in the MAC input as those might change due to NAT. Instead, the addresses simply allow to identify and compute the correct key and thus do not need to also be part of the MAC input.

I think, from a security perspective it's ok to drop the addresses from the MAC input as long as they are part of the key derivation. However, I'm generally not sure how SCION interacts with NAT. For example, would the NAT device replace the address in both the SCION header and the header of the encapsulating IP packet?

What is your opinion on this? Maybe we need to open a separate issue for this...

[matzf]

I don't really have an answer to the question about what types of keys we need to be able to encode beyond DRKeys.

Ok, to make a somewhat arbitrary choice then; with the field lengths discussed above, we seem to have one byte left to get good alignment, so maybe we can just use this (or partially and reserve some of the bits). The fields we have are:

• key id: 4 bytes (only 19 bits for DRKey as discussed above, 4 bytes for IPsec style SPI)
• timestamp: 6 bytes
• algorithm: 1 byte

Using a 4 n + 2 alignment (which is good because it requires no padding if it's the first option), we can arrange these as follows:

    +-+-+
    |T|L|    // OptType, OptDataLen
+-+-+-+-+
| KeyID |
+-+-+-+-+
| Time ..
+-+-+-+-+
 .. |A|X|   // Algorithm type, X: key identifier type
+-+-+-+-+

It's maybe a tad unnatural to put this X field after the KeyID, but this way we seem to be able to nicely row-align the key ID and timestamp fields.

A separate point that I just remembered is the problem of NAT with DRKey. In the PISKES paper, we argued to not include the addresses in the MAC input as those might change due to NAT. Instead, the addresses simply allow to identify and compute the correct key and thus do not need to also be part of the MAC input.

That's a fair point. This would be a special case for DRKey though, and the behavior would have to depend on the DRKey key type / direction being used, as not both host addresses are used to identify e.g. AS-to-host keys.
Other than the additional complexity, I cannot see a down side to this. And whether it would be useful, I don't know either -- somehow, NAT and authentication together doesn't feel quite right.

[mlegner]

@matzf Your suggestion makes sense to me. In terms of the layout of the different fields and how they impact the processing, I cannot really comment.

A separate point that I just remembered is the problem of NAT with DRKey. In the PISKES paper, we argued to not include the addresses in the MAC input as those might change due to NAT. Instead, the addresses simply allow to identify and compute the correct key and thus do not need to also be part of the MAC input.

That's a fair point. This would be a special case for DRKey though, and the behavior would have to depend on the DRKey key type / direction being used, as not both host addresses are used to identify e.g. AS-to-host keys.
Other than the additional complexity, I cannot see a down side to this. And whether it would be useful, I don't know either -- somehow, NAT and authentication together doesn't feel quite right.

Indeed, I think we need to consider NAT a bit more generally. For example, it's not even straight-forward to use existing NAT implementations with SCION as the NAT device would have to adjust addresses in both the SCION header and the (encapsulating) IP packet... Maybe it would be good to completely disallow NAT for SCION packets (it would still work for IP packets that go through a SIG after the NAT), then we also don't have that issue with the SPAO. What do you think, @shitz?

[matzf]

Indeed, I think we need to consider NAT a bit more generally. For example, it's not even straight-forward to use existing NAT implementations with SCION as the NAT device would have to adjust addresses in both the SCION header and the (encapsulating) IP packet

I think it's only odd if you're thinking of an IP NAT device. A device doing NAT for SCION traffic would only care about the SCION packet; it adjusts the addresses in the SCION header and sends the packet out, not caring much about the addresses set in the encapsulating underlay layers -- in an IP-based NAT, we probably wouldn't care much about ethernet addresses either.
Also, the NAT device would probably also meddle with the transport protocols (read or change ports) -- for this, the device needs to understand the SCION header much more than for just changing the address header.

A bit far fetched maybe, but I believe a SCION NAT could have its place e.g. when a network wants needs to be part of multiple SCION ASes that use incompatible internal addressing.

Anyway, my concern is less about NAT in general but about authentication and NAT; effectively the authentication is there to forbid somebody from messing with the address headers. So it seems acceptable if a NAT would need to do something weird to make this work (like recomputing the MAC with a different weird key).

[mlegner]

I'm thinking about a standard NAT use case in the current Internet ecosystem: Consider a host in a home network with private RFC 1918 address space, where the home router performs NAT. The problem I'm struggling with is: How can this host send SCION traffic directly when it is not an AS itself but simply an end host in the AS of its ISP? This is a deployment problem in the short/intermediate term as long as home routers don't understand SCION.

In this case, the host constructs SCION packets, encapsulates them in UDP+IP, and sends them to the border router. Unfortunately, the home router only adjusts address and port in the outer headers but not in the SCION header (as it is not even aware of SCION) or an inner transport header. Thus, the SCION header contains a private address and, when a reply packet comes in, the border router wouldn't know what to do with it.

There are several ways to resolve this:

• Disallow "standard" NAT with SCION and only support addresses for end hosts that are routable for a border router.
• The host knows the gateway's public IP address and writes this into the SCION header.
• Upgrade NAT devices to modify also the SCION header.

In the second and third case, the host could also obtain DRKeys for the public IP address to authenticate packets, although this deteriorates security properties in case many hosts are behind the NAT device.

[marcfrei]

In a recent discussion concerns about the choice of SHA-1 as the hash function in the SPAO variant with algorithm identifier SHA1-AES-CBC came up. It's not technical aspects that triggered the discussion but the fact that parts of the wider networking and crypto community will not accept this as a matter of principle.

So the question is whether we want to replace SHA-1 by a more modern hash function that can be safely truncated to 20 bytes. An additional criterion for the new hash function would be good support for hardware acceleration in today's processor architectures.

[matzf]

Thanks for raising this here, @marcfrei. I don't really recall why we defined the algorithm as SHA1 in the first place, as the discussion in this issue only referred to SHA256. Probably it was just that the 160bits/20bytes of SHA1 neatly fit the "budget" available for a two block input to the AES-CBC-MAC.

After a bit of a discussion via email, it seems there are two main options:

• Replace SHA1 with a different hash function suitably truncated to 160 bits. Sensible options are SHA-2, SHA-3 or BLAKE-3.

• Use a MAC instead of a hash function. We can use a MAC here because we have a shared key anyway.

  The sender computes two MACs;

  • the "full" MAC over the entire packet including payload. This is identical to the AES-CMAC algorithm type.
  • the "fast" MAC, covering only the metadata, addresses and the "full" MAC. This is analogous to the MAC that is now computed in the SHA1-AES-CBC algorithm type.

Using the MAC scheme instead of a hash offers a few practical advantages;

• We only need to worry about a single crypto primitive, AES, albeit in two slightly different forms, AES-CMAC for the "full" MAC and AES-CBC-MAC for the "fast" MAC.
• The "full" MAC can be identical to the AES-CMAC algorithm, so the logic can be shared
• The receiver only needs to check the "full" MAC -- with the current hash-based scheme, it needs to check both the hash and the "fast" MAC covering the hash. Only middle boxes like Lightning Filter would explicitly check the "fast" MAC.
• The performance of this should be roughly in the same ballpark as the hash-based scheme (perhaps with the exception of BLAKE-3).

Unless there are some disadvantages that we've overlooked, this double MAC scheme seems ideal. I'll wait a bit for further feedback, and if there are no negative votes I'll replace SHA1-AES-CBC in the documentation.

[matzf]

One other issue with the current design of the SPAO was raised by @fstreun; the timestamp is defined to be relative to the timestamp in the SCION path. This does not work for AS-local traffic, which uses the "Empty" path type.
As I remember it, this restriction was an oversight, not an intentional design choice.

The suggestion made by @fstreun was to change the timestamp to be relative to the DRKey epoch.

• a clever insight is that this even obviates the need for the E "Epoch" bit in the DRKey SPI -- a timestamp can only refer to one of the active epochs (provided the grace period is not longer than an entire epoch).
• this clearly only makes sense for SPIs based on DRKey.
  Perhaps a way to address this would be to "formally" combine the Timestamp/Sequence Number fields and define the timestamp part only for the DRKey case; the purpose of the timestamp field is to allow rejection of old replayed packets with valid MACs. This only really makes sense in a setting like DRKey where a middle box is able to verify the MAC but does not want to keep state about all the sequence numbers used.
• the granularity of the timestamp is currently chosen to represent values in the validity range of SCION paths. This would have to be adapted to fit DRKey Epochs.
  These DRKey Epochs do not currently have a defined upper bound, which we'd need to define. Just for illustration, with the same 24-bit timestamp that we currently have, a granularity of around 100ms would cover a maximum epoch length of ~19 days and this would still seem to be sufficient for the detection of "old" packets.

As far as I'm aware, there are no implementations of the SPAO in practical use, so we still have a chance to fix this.
As above, I'll wait for some feedback but otherwise I'll adjust the SPAO specifications according to @fstreun proposal.

[marcfrei]

Thanks, @matzf! Regarding the proposed "MAC scheme":

What would '"full" MAC over the entire packet including payload' mean precisely?

• Would it be (2.), (4.), and (5.) as in the definition for the data to be hashed in SHA1-AES-CBC [0]?
• Or would it be (1.), (2.), (3.), (4.), and (5.) as defined in Authenticated Data [1].

[0] https://docs.scion.org/en/latest/protocols/authenticator-option.html#sha1-aes-cbc
[1] https://docs.scion.org/en/latest/protocols/authenticator-option.html#authenticated-data

[matzf]

I meant the latter, (1.), (2.), (3.), (4.), and (5.).

[marcfrei]

I like the overall simplification that switching to the MAC scheme would bring.

To evaluate the performance implications in scenarios like Hercules protected by Lightning Filter where authenticators have to be computed for every outgoing packet at as close as possible to line rate, it would probably make sense to schedule a short experiment comparing the MAC scheme with one or more of the hash function based approaches. What do you think?

[JordiSubira]

Thanks for the discussion @matzf @marcfrei.

a clever insight is that this even obviates the need for the E "Epoch" bit in the DRKey SPI -- a timestamp can only refer to one of the active epochs (provided the grace period is not longer than an entire epoch).

By obviates, do you mean that the E flag is not relevant anymore? I'm probably missing something but according to https://scion.docs.anapaya.net/en/latest/cryptography/drkey.html#grace-period at a given point in time we can admit two keys as valid, i.e. a spell in which two epochs validity overlap. Thus, even if the timestamp is relative to the current epoch, usage of the previous epoch key in the validity period could be acceptable and also conveyed, right?

In general, I like this double-MAC approach. I second @marcfrei's suggestion regarding the experiments in the LF sender side, to confirm that performance is similar in both cases, although assuming it seems also reasonable.

[fstreun]

By obviates, do you mean that the E flag is not relevant anymore? I'm probably missing something but according to https://scion.docs.anapaya.net/en/latest/cryptography/drkey.html#grace-period at a given point in time we can admit two keys as valid, i.e. a spell in which two epochs validity overlap. Thus, even if the timestamp is relative to the current epoch, usage of the previous epoch key in the validity period could be acceptable and also conveyed, right?

Yes, it is still possible that two keys are valid during the transition period. With a timestamp relative to the key validity start time, it is obvious which of the two keys was used.
If the relative timestamp is small, then the newer key was used. If the relative timestamp is large (approximately the epoch's duration), then the old key was used.

[JordiSubira]

With a timestamp relative to the key validity start time, it is obvious which of the two keys was used.
If the relative timestamp is small, then the newer key was used. If the relative timestamp is large (approximately the epoch's duration), then the old key was used.

Indeed, this could work. One possible approach is to consider to remove/leave out the E flag if the timestamp value ranges between [0, epoch_duration + grace_period], where (epoch_duration, epoch_duration + grace_period] correspond to older key usage.

[matzf]

Closed by #4300, #4366.