SECURE TRACEROUTE (SECTRACE) Draft 0 December 2002 Carl A. Gunter, Alwyn Goodloe, and Michael McDougall 1 Objective ----------- Security Gateways (SGs) are network elements that aim to protect nodes from unwanted communications. They accomplish this by analyzing packets addressed to the nodes they protect and dropping certain kinds of packets if they might lead to unwanted communications. Secure traceroute (sectrace) is a protocol that discovers SGs and configures IPSec Security Associations (SAs) to enable SGs to do this efficiently and flexibly by classifying packets as authenticated, so that analysis can be better carried out based on packet origin, or unauthenticated, so that analysis must be based on packet shape. 2 Assumptions ------------- There are two general modes in which traffic is analyzed by security gateways. In FILTER mode, packets are reviewed based on their shape. For example, many firewalls filter packets based on port numbers, return addresses (ingress and egress filtering), or protocol-specific flags (SYN filtering). In AUTHENTICATION mode, the packets are reviewed based on some cryptographic authentication criteria such as a Message Authentication Code (MAC). A DUAL MODE SG is one that combines these two modes. For instance, such an SG may place packets into an authenticated tunnel only if they have a certain shape. We will focus on SGs of this kind. We assume that SGs are able to authenticate traffic in an IPSec tunnel and also filter traffic based on various protocol-specific criteria. The aim of an SG is to ensure that a class of what we call INITIATION traffic is routed only if it is authenticated. This class of traffic is contrasted with RESPONSE traffic. The precise definition of INITIATION and RESPONSE traffic determine the low-level protections provided by an SG. We will classify sectrace traffic as initiation or response traffic and assume that it is also possible to classify IPSec negotiation traffic in this way. The functionality of an SG for other protocols depends on this choice; in particular, an SG may classify a TCP SYN as an initiation packet and other TCP packets as responses. It is assumed that routing determines a unique path from source to destination for each pair of nodes. SAs are assumed to be asymmetric; that is, when initiator A negotiates an SA with responder B, then this SA applies only to packets sent by A to B and not to those sent by B to A. Each node is assumed to have a public key certificate and a valid certificate chain from a root key. Each node is also assumed to have a set of root keys it trusts. For simplicity we assume that any request that is authenticated is also authorized: in practice, this could be much more complicated, but much of this complexity is orthogonal to the initial challenge of authentication. With these assumptions, objective of sectrace can be stated more precisely as follows: the protocol uses PKI, routing, and IPSec to ensure that all initiation traffic is efficiently authenticated to its destination and all of the security gateways that must be traversed to reach it. The mechanism of sectrace is similar to that of traceroute. An IP node uses the traceroute protocol to determine the routing path between itself and a chosen destination node. This is accomplished by sending a sequence of messages toward the destination with increasing TTL values and reconstructing the path from ICMP responses generated by exhausted TTLs. Sectrace works by sending a sequence of requests toward a destination and processing responses from SGs that intercept the requests. The protocol establishes an SA ROUTE consisting of a collection of SAs that authenticate packets to SGs. This authentication may be with the originator or with any SG on the routing path so long as the recipient trusts the signature of the authenticating node. 3 Example --------- An example illustrates the basic strategy. Assume the following configuration: C ----- SG1 ----- SG2 ----- S where the dashes indicate the routing path from client node C to server node S. SG1 and SG2 are two security gateways that lie on this path; these nodes aim to protect C and S from unauthenticated initation traffic. The goal is for C to establish a TCP connection to S. To accomplish this, C must gain the approval of SG1, SG2, and S using IPSec authentication based on its certificate and those of SG1 and SG2. Sectrace initiates path setup by sending a sectrace Route Request (RReq) toward S. This is intercepted by SG1, which replies to C with a sectrace Route Reply (RRep) containing a list of root keys it will accept for authentication. C then creates an IPSec SA with SG1 (if it can) and sends a new RReq toward S, via SG1. The new RReq is encapuslated in the SA between C and SG1 established in the previous stage; SG1 decapsulates the RReq and forwards it toward S. This RReq is intercepted by SG2, which responds to it with an RRep. We do not assume that paths are symmetric, so this SRep may or may not pass through SG1, but any SGs that it encounters will allow it to pass back to C. There are three possibilities at this point: (1) SG2 trusts the root of SG1, (2) SG2 trusts the root of C but not SG1, and (3) SG2 trusts neither root. (1) When it receives the RRep from SG2, the client C compares the trusted root information in it to what it received from SG1. If SG2 trusts the root of SG1, then C sends a sectrace Security Association Request (SAReq) to SG1 requesting that SG1 establish an SA with SG2. After this is negotiated by SG1 and SG2, security gateway SG1 sends a positive Security Association Reply (SARep) to C declaring that the necessary SA exists. C then sends another RReq toward S using the SA with SG1; this RReq is then forwarded by SG1 toward S using its SA with SG2. (2) If S2 trusts the root of C but not the root of SG1, then C establishes an SA with SG2 using its SA with SG1. Once this is done, C sends an RReq toward S encapsulated in its (nested) SAs with SG1 and SG2. (3) If neither C nor SG1 have roots that SG2 trusts, then an authenticated path from C to S cannot be established and the protocol terminates unsuccessfully. When S finally receives an RReq from C, it responds with an RRep that indicates the roots it trusts. C uses this to establish an SA with S based on a similar technique to the one used for SG1 and SG2. After C completes its sectrace, there will be three SAs, one for each SG and the server, so that packets sent from the client to the server will always be authenticated at the server and each SG. This SA route can be used to transmit initiation packets from C to S. The sectrace protocol aims to amortize the cost of SA setup across multiple communications, so, when a node receives an SAReq, it checks to see if the requested SA already exists and immediately sends a positive response if it does. SAs are assumed to expire after a period of time. We make no special provision for this; if a communication link is broken by an SA expiration, then sectrace is run again to renew the necessary SA. We assume that SGs have some means of notifying a node that sectrace is needed, but have not specified that here. It would be reasonable to configure SAs so that they are automatically renewed if they are used, with new session keys being created as appropriate. 4 Overview ---------- We split the problem of discovering and configuring an SA route into two parts. First there is a sectrace SIGNALLING protocol that sends a sequence of messages to discover SGs, learn their trust relations, and request that SAs be established to authenticate future communications. Second, there is a sectrace SA SELECTION protocol that determines which SAs to request based on existing SAs and newly-discovered SGs and their trust relations. We describe the signalling protocol assuming the existance of an SA selection protocol and then describe the chosen SA selection protocol. We then provide an extended example of the two protocols on a network with four SGs. We then provide a discussion of tradeoffs and limitations in sectrace and conclude by mentioning some related work. 5 Signalling Protocol --------------------- An instance of the protocol is created for each client/server pair. Only the client maintains state aside from what is needed to establish SAs and the SAD entries that result. Messages are sent via UDP so it is assumed that they include a source and destination. We use a dot notation to indicate information in messages. For instance, RReq.src and RReq.dst are the source and destination attributes of RReq. 5.1 Message Types The signalling protocol involves the following kinds of messages. We indicate fields other than the source and desitination field and whether the message is classified as an initiation or a response. RReq Route Request, initation RRep Route Reply, response RRep.tr List of trusted roots RRep.done Positive or negative SAReq Security Association Request, initiation SAReq.resp Requested responder (The requested initiator is SAReq.dst, the destination node) SARep Security Association Reply, response SARep.resp Requested responder SAReq.done Positive or negative Messages RReq and RRep are said to MATCH if RReq.dst = RRep.src RReq.src = RRep.dst Messages SAReq and SARep are said to MATCH if SAReq.dst = SARep.src SAReq.src = SARep.dst The protocol uses the following timeouts RReqTmt Route Request Timeout SAReqTmt SA Request Timeout Client State RReqTmtCntr RReqTmt Counter: integer SAReqTmtCntr SAReqTmt Counter: integer RRepLst RRep List: list of prior RRep messages OReq Outstanding Request: RReq or SAReq To avoid repetition, the done flag on an RRep is negative unless otherwise indicated. 5.2 Establishing a Security Association A security association is established between an initiator I and a responder R; it is negotiated starting with a message from the former to the latter. For the sectrace protocol an SA consists of an Encapsulated Security Payload (ESP) with null encryption and authentication using a MAC. The SA is established in transport mode and entered into the SA Database (SAD). In sectrace, an SA is established with respect to a server S and the SA is applicable to packets ultimately addressed to S. A packet is ultimately addressed to S if the packet obtained by removing all ESP authentication headers is addressed to S. So, if a packet ultimately addressed to S is processed by I, it will add an ESP header authenticating the packet to R, append a new IP header for R, and dispatch the packet to R. Responder R will remove the new IP header, check and remove the ESP header and trailer, and process the packet. The policy for applicable SAs is stored in the SA Policy Database (SAPD). 5.3 Client Actions Client initiates protocol The client initiates the protocol by sending an RReq toward a server S. When it does so it sets the RReqTmt timeout and sets OReq to be RReq. Client receives RRep If the client receives an RRep message, then it first checks whether it matches the outstanding request OReq. If it does not, then the RRep is ignored. If it does, then the client clears the RReqTmt timer. It inspects the collection of roots in the message and the RRep list to choose an initiator the sectrace SA selection protocol. The client creates an SAReq with the chosen initiator (SAReq.dst) and uses the source of the RRep as the requested responder (SAReq.resp = RRep.src). This SAReq is entered as the outstanding request. The SAReq and RRep messages are added to the list RRepLst of prior RRep messages. If the chosen initiator is the client itself, then the client attempts to establish an SA with the responder (that is, the sender of the RRep message). If this succeeds, and the server is the responder, then the protocol terminates successfully. If it succeeds and the server is not the responder, then the client sets the RReqTmt timeout, sets the counter RReqTmtCntr to zero, sets the outstanding request to RReq, and sends a new RReq toward the server. If the initiator is not the client, then it sends an SAReq to the initiator indicating the desired responder. The client sets the SAReqTmt timeout, sets the SAReqTmtCntr counter to zero, and enters the SAReq as the outstanding request. Client RReqTmt expires If the RReqTmt expires, then the client checks to see if the RReqTmt counter is greater than or equal to three. If it is, the protocol terminates unsuccessfully. Otherwise the RReqTmt counter is incremented, the RReqTmt timeout is reset, and the client resends the outstanding RReq. Client receives SARep If the client receives an SARep message, then it first checks whether it matches the outstanding request OReq. If it does not, then the SARep is ignored. If the SARep is positive and the responder SARep.resp is the server, then the protocol ends successfully. If the SARep is positive and the responder is not the server, then the client sends a new RReq message toward S after setting it as the outstanding request, setting the RReqTmt timeout, and setting the RReqTmt counter to zero. If the SARep is negative, then the protocol ends unsuccessfully. Client SAReqTmt expires If the SAReqTmt expires, then the client checks to see if the SAReqTmt counter is greater than or equal to three. If it is, the protocol terminates unsuccessfully. Otherwise the counter is incremented and the client resends the outstanding SAReq. 5.4 Security Gateway Actions SG receives RReq If the SG receives an authenticated RReq (that is, receives the RReq in an SA), then it routes the RReq on toward its destination using any applicable SAs. If the RReq is unauthenticated, then the SG sends an RRep with its trusted roots toward the RReq sender. It drops the RReq. SG receives RRep If the SG receives a RRep it routes it toward its destination using any applicable SA. SG receives SAReq If an SG recieves an unauthenticated SARep, then it drops it. If an SG receives an authenticated SARep addressed to another node, then it forwards it. If it receives an authenticated SAReq addressed to itself, then it checks to see if it has a policy in the SAPD and SA in the SAD for the server in the request. If it does, then the SG sends a positive SARep to the client. If there is no applicable policy in place already, then the SG attempts to establish an SA with the specified responder. If this is successful, it sends a positive SARep to the sender and updates its SAPD and SAD to indicate that packets for the given server should use the newly established SA. If this is not successful, it sends a negative SARep to the sender. SG receives SARep If the SG receives an RRep it routes it forwards it toward its destination using any applicable SA. SG receives IPSec Negotiation Packets SGs should relay IPSec SA negotiation response packets without authentication. SG receives other packets In general, an SG relays a packet iff it is authenticated or it is a response packet. 5.5 Server Actions Server gets RReq If the server gets an unauthenticated RReq for itself, it sends an RRep with its trusted roots. If it receives an authenticated RRep, it sends an RRep with a positive done flag. 6 Properties of the Protocol ---------------------------- Here are a few properties expected of the protocol. The timeout SAReqTmt never expires when OReq is an RReq. The timeout RReqTmt never expires when OReq is an SAReq. If the client sends an SAReq to a node, then it will arrive there over an authenticated channel. That is, it will be within an SA. RReqTmtCtr and SAReqTmtCtr are never greater than 3. An RReq is never forwarded by an SG unless it is authenticated. In particular, an unauthenticated RReq cannot be used to gather information through an SA. 7 SA Selection -------------- Given a collection of RReqs, a client must select the next SA to request. The sectrace protocol does this by selecting the intermediate initiator that provides the "shortest" SA to the given responder. In general, there is no guarantee that an SA route from the client to the server exists. However, if any such route does exist, then the sectrace protocol will find one. 7.1 Example A node A is TRUSTED by a node B if the root of A is one of the trusted roots of B. If A is trusted by B we write A << B. Consider again the example from Section 3: C ----- SG1 ----- SG2 ----- S For case (1) from Section 3, we have C << SG1 << SG2, so the protocol establishes associations from C to SG1 and from SG1 to SG2. However, in case (2) we have only C << SG1 and C << SG2 so the associations are from C to SG1 and from C to SG2. Let us assume below that SG2 << S. In treating this mathematically, it is helpful to view SAs as determined by a function on an initial segment of the numbers. The example is then rendered as follows: 0 ----- 1 ----- 2 ----- 3 and there is a function f from the non-zero numbers 1,2,3 into the numbers 0,1,2,3 such that, for each n, f(n) is the node that authenticates packets to n. That is, f(n) < n and f(n) << n for each n. In case (1) of the example, we have f(1) = 0, f(2) = 1, f(3) = 2. But in case (2) we have f(1) = 0, f(2) = 0, f(3) = 2. In case (3) of the example, there is no function f that satisfies the criterion that f(n) << n for each n. 7.2 Theory Let N+ denote non-zero numbers and N be the numbers including 0. A trust relation << is a binary predicate on N. To simplify matters, we assume that m << n implies m < n, although this is not important to the formalization. The element 0 corresponds to the client and each number to an SG or the server. For instance, if there are two SGs then we are concerned with trust relations between 0,1,2,3, where 3 is the server and 1,2 are SGs. In general, we need to find a function f: N+ -> N with the following properties: Trusted f(x) << x Encapsulation If x < y then f(y) <= f(x) or x <= f(y) Let us say that a partial function f: N+ -> N is a TRUSTED ENCAPSULATION for n if it is defined on 1,...,n and is an encapsulation on this initial segment of numbers. For a given relation << and number n, there may be no trusted encapsulation for n. We define a partial function fs by induction as follows. Base Case: fs(1) = 0 if 0 << 1, otherwise it is undefined Inductive Case: Assume that fs is defined for 1,...,n and it is a trusted encapsulation on these this initial segment. Let fs(n+1) = the largest value m such that fs restricted to 0,...,n+1 is a trusted encapsulation, if there exists such an m, otherwise let f(n+1) be undefined. If fs is undefined on any of the values 1,...,n, then fs(n+1) is also undefined. fs is the SHORT SA function induced by the relation << Lemma: If f is a trusted encapsulation for n, then fs is a trusted encapsulation for n and f(k) <= fs(k) for each k <= n. Proof: This procedes by induction on n. Suppose that n=1. Then f(1)=0 and fs(1)=0 so there is no problem. Suppose that the lemma holds for n and f is a trusted encapsulation for n+1. In this case f is also a trusted encapsulation for n, so fs is a trusted encapsulation for n and f(k) <= fs(k) for each k <= n. Now, we need to show that fs(n+1) exists and that it is >= f(n+1). Since fs(n+1) is defined to be the largest value such that fs is an trusted encapsulation, given the values of fs on 1,...,n, it suffices to show that fs' is a trusted encapsulation where fs' is equal to fs on 1,...,n and fs'(n+1) = f(n+1). Clearly fs'(n+1) << n+1 since f(n+1) << n+1. Suppose x < y for some x,y < n+1. Then the encapsulation property is satisfied by fs on x,y by induction, and fs equals fs' on these values. Suppose, however, that y=n+1. We need to show that fs'(n+1) <= fs'(x) or x <= fs'(n+1). This is the same as showing that fs'(n+1) > fs'(x) implies x <= fs'(n+1) Suppose fs'(n+1) > fs'(x). Then f(n+1) > fs(x). By induction fs(x) >= f(x), so f(n+1) > f(x). Thus x <= f(n+1) because f is an encapsulation and f(n+1)= fs'(n+1) by definition. Theorem: There exists a trusted encapsulation for n iff fs is a trusted encapsulation for n. Proof: Necessity is obvious and sufficiency is a corollary of the Lemma. 8 Extended Example ------------------ C1 -----| | | C2 ----- SG1 ----- SG2 ----- SG3 ----- SG4 ---- S Assume C1 << SG2,SG4,S C2 << SG1,SG3,S SG1 << SG2 SG3 << SG4,S SG4 << S Intuitively SG1, SG2 are gateways in one autonomous system and SG3,SG4 are gateways in another. The nodes C1 and C2 have relations with gatewasy in each system and are currently situated within the system protected by SG1,SG2. C1 sends an RReq toward S SG2 gets this RReq and sends an RRep to C1 C1 gets this RRep and establishes an SA with SG2 C1 sends an RReq toward S using the SA with SG2 SG2 gets this authenticated RReq and forwards it toward S SG3 gets this RReq from C1 but it is not authenticated SG3 sends an RRep to C1 C1 gets the RRep from SG3 C1 establishes an SA with SG3 C1 sends an RReq toward S using the SAs for SG2 and SG3 SG2 and SG3 receive this RReq and forward it toward S SG4 receives the RReq and responds to C1 with an RRep C1 sends an SAReq to SG3, which establishes an SA with SG4 SG3 sends an SARep to C1 C1 sends an RReq toward S, which is authenticated though SG2, SG3 and SG4 S gets an RReq from C1 and responds with an RRep C1 sends an SAReq to SG4 SG4 gets the SAReq fom C1 and establishes an SA with S SG4 sends an SARep to C1 C1 is now able to send authenticated packets to S The SAs now look like this: C1 ----- SG2 ----- SG3 ----- SG4 ----- S ===== ===== ===== =============== C2 sends an RReq toward S SG1 gets this RReq and sends an RRep to C2 C2 establishes an SA with SG1 C2 sends an RReq toward S SG2 gets this RReq and sends an RRep to C2 C2 sends an SAReq to SG1, which establishes an SA with SG2 and sends an SARep to C2 C2 sends an RReq toward S SG3 gets the RReq from C2 and sends an RRep C2 establishes an SA with SG3 C2 sends an RReq toward S within SAs for SG1 and SG3 SG1 forwards this RReq within an SA between itself and SG2 SG3 receives this RReq and forwards it to SG4 using the SA established by C1 between SG3 and SG4 SG4 forwards this RReq to S using the SA between SG4 and S S sends an RRep with a positive done flag to C2 C2 is now able to send authenticated packets to S C2 ----- SG1 ----- SG2 ----- SG3 ----- SG4 ----- S ===== ===== ===== ===== ========================= Note that the associations SG3 ===== SG4 ===== S were "invisible" to C2 because they had already been established by C1. 9 Issues and Limitations ------------------------ Policy at SGs is based on destination servers. Thus the SAPD needs to find policy for an arriving packet based on its ultimate destination. If a packet has a tunnel header for an SG, this entails searching into the packet to find the ultimate destination. This needs to be supported efficiently by the IPSec policy mechanism on the SGs. Policy could be made more efficient by aggregating destinations. For example, an RRep might include not only a set of roots but also a range of IP addresses "protected" by the given SG. It may be desirable for RRep messages to be signed by SGs. This does not introduce any significant burden on the SG since the signature only needs to be created when roots change. The current protocol is based on trusted roots, but a more likely foundation for the trust relation is delegated authorization. That is, X << Y means that Y is willing to delegate traversal authorization to X. If the trust relation << holds between every pair of nodes, then there is no need for nested tunnels. The current protocol assumes that all nodes will use the same rules for establishing SA routes, namely shortest SAs. Another extreme is to let each node configure longest SAs in which each client authenticates to each SG and the server. Two points are unclear: (1) whether different clients can use different SA selection policies in a practical way and (2) whether it is possible to enforce the use of the same configuration policy on all nodes. One idea is to allow clients to configure policies but prove that this does not cause problems with shared SAs. Another alternative is to cause SGs to set up configurations on the grounds that they are more trusted than client endpoints. There are several ways to do this. For instance, the first SG could do the entire path setup, or each SG could take responsibility for setting up the next SG. The latter approach has the disadvantage of moving lists of roots from one SG to the next, but this is not likely to be a major burden. By contrast, it has the advantage of moving policy configuration of SGs that are close to the server to those SGs themselves; this may reduce the risk of conflicting policy approaches. 10 Related Work --------------- The IETF working group ipsp has a charter describes the need for protocols to discover and configure authentication and authorization through security gateways. Opportunistic encryption has a number of points of commonality with sectrace. The IETF working group midbox is concerned with configuration of network elements that include NAT boxes as well as security gateways like firewalls and monitoring systems like Intrusion Detection Systems (IDSs). Contact Information ------------------- Carl A. Gunter gunter@cis.upenn.edu Alwyn Goodloe goodloe@gradient.cis.upenn.edu Michael McDougall mcdouga@saul.cis.upenn.edu Department of Computer and Information Science University of Pennsylvania 200 South 33rd Street Philadelphia PA 19104