Pre-capability(routers ≤(4-t3)xN timestamp(8 bits) hash(src IP, dest IP, time, secret)(56 bits) Capability(hosts) ts t1 ash(pre-capability, N, T)(56 bits) Figure 3: Format of capabilities. Figure 4: Bound on the bytes of a capability with caching. 3.4 Unforgeable Capabilities whose requests were granted would be able to ar- strap mechanism and policy, we turn our destination until their capabilities expire. This attention to the form of capabilities themselves. Our key require low even a very small rate of false authorizations ment is that an attacker can neither forge a capability, nor make use to deny service. This argues for a very short expiration period, yet of a capability that they steal or transfer from another party. We otocol dynamics such as TCP timeouts place a lower bound on also need capabilities to expire what is reasonable work path, including source and destination IP addresses, at a spe- grant the right to send up to bytes along a path within the next T cific time. Each router that forwards a request packet generates its wn pre-capability and attaches it to the packet. This pre-capability of data as well as the period of validity. The form of these ca- is shown in Figure 3. It consists of a local router timestamp and a pabilities is shown in Figure 3. The destination converts the pre- ryptographic hash of that timestamp plus the source and destina- capabilities it receives from routers to full capabilities by hashing tion IP addresses and a slowly-changing secret known only to th them with n and T. each destination can choose n and T router. Observe that each router can verify for itself that a pur limits) for each request, using any method from simple defaults to ported pre-capability attached to a packet is valid by re-computing models of prior behavior. It is these full capabilities, along with M the hash, since the router knows all of the inputs, but it is crypto and T, that are returned to authorize the sender. For longer flows, graphically hard for other parties to forge the pre-capability with the sender should renew these capabilities before they reach their out knowing the router secret. Each router changes its secret at limits twice the rate of the timestamp rollover, and only uses the current With this scheme, routers verify their portion of the capabilities by C-computing the hashes much as before, except that now two or the previous secret to validate capability. This ensures that a hashes are required instead of one. The routers now perform two pre-capability expires within at most the timestamp rollover period nd each pre-capability is valid for about the same time period re- further checks, one for N and one for T. First, routers check that gardless of when it is issued. The high-order bit of the timestamp their local time is no greater than the router timestamp plus t to ensure ot exp ired. This requires that T ndicates whether the current or the previous router secret should be at most one half of the largest router timestamp so that two time be used for validation. This trick allows a router to try only one values can be unambiguously compared under a modulo clock. The ecret even if the router changed its secret right after issuing a pre replay of very old capabilities for which the local router clock has The destination thus receives an ordered list of pre-capabilities wrapped are handled as before by periodically changing the router that corresponds to a specific network path with fixed source and secret. Second, routers check that the capability will not be used destination IP endpoints. It is this correspondence that prevents for more than N bytes. This check is conceptually simple, but an attacker from successfully using capabilities issued to another and raises the concern that attackers may exhaust arty: it cannot generally arrange to send packets with a specific router state. We deal with this concern next source and destination IP address through a specific sequence of 3.6 Bounded router state routers unless it is co-located with the source. In the latter case. the attacker is indistinguishable from the source as far as the network We wish to ensure that attackers cannot exhaust router mem is concerned, and shares its fate in the same manner as for requests ory to bypass capability limits. This is especially a concern given (And other, more devastating attacks are possible if local security that we are counting the bytes sent with a capability and colluding breached. Thus we reduce remote exploitation to the problem of local security If the destination wishes to authorize the request, it returns an To handle this problem, we design an algorithm that bounds the ordered list of capabilities to the sender via a packet sent in the tes sent using a capability while using only a fixed amount of reverse direction. Conceptually, the pre-capabilities we have de router state no matter how attackers behave. In the worst case. a scribed could directly serve as these capabilities. However, we pro- capability may be used to send 2N bytes in T seconds. The same cess them further to provide greater control, as is described next capability will still be precisely limited to n bytes if there is no memory pressu 3.5 Fine-Grained Capabilities The high level idea of the algorithm is to make a router ke ep only for flows(a flow is defined on a sender to a destination basis. Even effective policies will sometimes make the wrong decision with valid capabilities that send faster than N/T. The router does and the receiver will authorize traffic that ultimately is not wanted For example, with our blacklist server policy an attacker will be not need to keep state for other authorized fows because they will authorized at least once, and with our client policy the server that 2An alternative would be to build rapid capability revocation.We a client accesses may prove to be malicious. If authorizations were believe this to be a less tractable problemPre-capability (routers) timestamp (8 bits) hash(src IP, dest IP, time, secret) (56 bits) Capability (hosts) timestamp (8 bits) hash(pre-capability, N, T) (56 bits) Figure 3: Format of capabilities. 3.4 Unforgeable Capabilities Having provided a bootstrap mechanism and policy, we turn our attention to the form of capabilities themselves. Our key require￾ment is that an attacker can neither forge a capability, nor make use of a capability that they steal or transfer from another party. We also need capabilities to expire. We use cryptography to bind each capability to a specific net￾work path, including source and destination IP addresses, at a spe￾cific time. Each router that forwards a request packet generates its own pre-capability and attaches it to the packet. This pre-capability is shown in Figure 3. It consists of a local router timestamp and a cryptographic hash of that timestamp plus the source and destina￾tion IP addresses and a slowly-changing secret known only to the router. Observe that each router can verify for itself that a pur￾ported pre-capability attached to a packet is valid by re-computing the hash, since the router knows all of the inputs, but it is crypto￾graphically hard for other parties to forge the pre-capability with￾out knowing the router secret. Each router changes its secret at twice the rate of the timestamp rollover, and only uses the current or the previous secret to validate capability. This ensures that a pre-capability expires within at most the timestamp rollover period, and each pre-capability is valid for about the same time period re￾gardless of when it is issued. The high-order bit of the timestamp indicates whether the current or the previous router secret should be used for validation. This trick allows a router to try only one secret even if the router changed its secret right after issuing a pre￾capability. The destination thus receives an ordered list of pre-capabilities that corresponds to a specific network path with fixed source and destination IP endpoints. It is this correspondence that prevents an attacker from successfully using capabilities issued to another party: it cannot generally arrange to send packets with a specific source and destination IP address through a specific sequence of routers unless it is co-located with the source. In the latter case, the attacker is indistinguishable from the source as far as the network is concerned, and shares its fate in the same manner as for requests. (And other, more devastating attacks are possible if local security is breached.) Thus we reduce remote exploitation to the problem of local security. If the destination wishes to authorize the request, it returns an ordered list of capabilities to the sender via a packet sent in the reverse direction. Conceptually, the pre-capabilities we have de￾scribed could directly serve as these capabilities. However, we pro￾cess them further to provide greater control, as is described next. 3.5 Fine-Grained Capabilities Even effective policies will sometimes make the wrong decision and the receiver will authorize traffic that ultimately is not wanted. For example, with our blacklist server policy an attacker will be authorized at least once, and with our client policy the server that a client accesses may prove to be malicious. If authorizations were ts
(t2 -t1 ) x N t1 t4 ts+T t2 ttl time t3
(t4 -t3 ) x N
N Figure 4: Bound on the bytes of a capability with caching. binary, attackers whose requests were granted would be able to ar￾bitrarily flood the destination until their capabilities expire. This problem would allow even a very small rate of false authorizations to deny service. This argues for a very short expiration period, yet protocol dynamics such as TCP timeouts place a lower bound on what is reasonable. To tackle this problem, we design fine-grained capabilities that grant the right to send up to N bytes along a path within the next T seconds, e.g., 100KB in 10 seconds2 . That is, we limit the amount of data as well as the period of validity. The form of these ca￾pabilities is shown in Figure 3. The destination converts the pre￾capabilities it receives from routers to full capabilities by hashing them with N and T. Each destination can choose N and T (within limits) for each request, using any method from simple defaults to models of prior behavior. It is these full capabilities, along with N and T, that are returned to authorize the sender. For longer flows, the sender should renew these capabilities before they reach their limits. With this scheme, routers verify their portion of the capabilities by re-computing the hashes much as before, except that now two hashes are required instead of one. The routers now perform two further checks, one for N and one for T. First, routers check that their local time is no greater than the router timestamp plus T to ensure that the capability has not expired. This requires that T be at most one half of the largest router timestamp so that two time values can be unambiguously compared under a modulo clock. The replay of very old capabilities for which the local router clock has wrapped are handled as before by periodically changing the router secret. Second, routers check that the capability will not be used for more than N bytes. This check is conceptually simple, but it requires state and raises the concern that attackers may exhaust router state. We deal with this concern next. 3.6 Bounded Router State We wish to ensure that attackers cannot exhaust router mem￾ory to bypass capability limits. This is especially a concern given that we are counting the bytes sent with a capability and colluding attackers may create many authorized connections across a target link. To handle this problem, we design an algorithm that bounds the bytes sent using a capability while using only a fixed amount of router state no matter how attackers behave. In the worst case, a capability may be used to send 2N bytes in T seconds. The same capability will still be precisely limited to N bytes if there is no memory pressure. The high level idea of the algorithm is to make a router keep state only for flows (a flow is defined on a sender to a destination basis.) with valid capabilities that send faster than N/T. The router does not need to keep state for other authorized flows because they will 2An alternative would be to build rapid capability revocation. We believe this to be a less tractable problem. 244