Clarify meaning of "visited" in DFS target search

[awwad]

Summary

In Section 5 (Detailed Workflows), item 4.5.1 of the spec, the meaning of "visited" should be clarified because an otherwise sensible interpretation can result in an unusual "attack" whereby early delegation confers early right to deny access to a specified role for the purpose of validating any targets included in the early delegation. (It is also prudent for it to be clearer for the purpose of avoiding cycles.)

4.5.1. If this role has been visited before, then skip this role (so that cycles in the delegation graph are avoided). Otherwise, if an application-specific maximum number of roles have been visited, then go to step 5 (so that attackers cannot cause the client to waste excessive bandwidth or time). Otherwise, if this role contains metadata about the desired target, then go to step 5.

Background on Cycle Prevention

When a client seeks target info (hashes, length, etc.) for a given target, it performs a pre-order depth-first traversal of a repository's delegations to find the delegation listing that target info that is trusted to list it (based on delegated paths/patterns), prioritized based on the delegation order.

To avoid clients falling into delegation cycles, a role X must be marked "visited" after that role's list of target info has been searched for the target info and before the recursion proceeds to X's delegations. (Otherwise, X->X, X->Y->X, etc. result in a cycle.) It is not made clear when a role is to be marked "visited", however, and this ambiguity can lead to a further issue beyond delegation cycles.

Particulars: unusual "attack"

The cycle prevention constraint in the preorder depth-first search algorithm says not to visit a role that has already been visited; however, if a role is deemed "visited" as soon as it has been obtained and before it has been validated (which is a place implementers might be tempted to put this for performance reasons), then an attack is possible:

Suppose some role "T" delegates some target "target" to some roles "R1" and "R2", in that order.

Suppose R1 and R2 both delegate to R3. R1 can prevent R2 from trusting R3 (for any target for which R1 has earlier delegation) by "delegating" to R3 with an expected list of keys that is impossible to satisfy (by e.g. requiring a fake or thrown away key. This denial can cover all possible targets in a delegated space (instead of requiring targets to be specified individually). R1, being an earlier delegation, is allowed to specify targets and thereby prevent R2 from specifying those targets. In this "attack", however, R1 can prevent R2 from trusting arbitrary roles. This is undesirable, though the security impact is likely not noteworthy (since in principle, R1 has the right to deny later delegations from specifying targets by simply listing them).

Solution

This can be solved by defining what a visit entails in item 4.5.1 of Section 5 of the spec. To avoid cycles, a role X must be marked "visited" before the recursion proceeds to X's delegations. Further, if we want to avoid this "attack", role X must be marked "visited" only after the X role file is validated (and still before recursion proceeds to X's delegations).