USENIX Association 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’16) 257
tions over different fields of a packet: prefix and keyword
matching, as listed in Table 1. This results in an encrypted
packet that simultaneously supports these middleboxes.
We implemented and evaluated Embark on EC2.
Embark supports the core functionality of a wide-range
of middleboxes as listed in Table 1, and elaborated in
Appendix A. In our evaluation, we showed that Embark
supports a real example for each middlebox category in
Table 1. Further, Embark imposes negligible throughput
overheads at the service provider: for example, a single-
core firewall operating over encrypted data achieves
9.8Gbps, equal to the same firewall over unencrypted
data. Our enterprise gateway can tunnel traffic at 9.6
Gbps on a single core; a single server can easily support
10Gbps for a small-medium enterprise.
2 Overview
In this section, we present an overview of Embark.
2.1 System Architecture
Embark uses the same architecture as APLOMB [54],
a system which redirects an enterprise’s traffic to the
cloud for middlebox processing. Embark augments this
architecture with confidentiality protection.
In the APLOMB setup, there are two parties: the enter-
prise(s) and the service provider or cloud (SP). The enter-
prise runs a gateway (GW) which sends traffic to middle-
boxes (MB) running in the cloud; in practice, this cloud
may be either a public cloud service (such as EC2), or an
ISP-supported service running at a Central Office (CO).
We illustrate the two redirection setups from APLOMB
in Fig. 1. The first setup, in Fig. 1(a), occurs when the
enterprise communicates with an external site: traffic
goes to the cloud and back before it is sent out to the
Internet. It is worth mentioning that APLOMB allows an
optimization that saves on bandwidth and latency relative
to Fig. 1(a): the traffic from SP can go directly to the exter-
nal site and does not have to go back through the gateway.
Embark does not allow this optimization fundamentally:
the traffic from SP is encrypted and cannot be understood
by an external site. Nonetheless, as we demonstrate in §6,
for ISP-based deployments this overhead is negligible.
For traffic within the same enterprise, where the key is
known by two gateways owned by the same company, we
can support the optimization as shown in Fig. 1(b).
We do not delve further into the details and motivation
of APLOMB’s setup, but instead refer the reader to [54].
2.2 Threat Model
Clients adopt cloud services for decreased cost and ease
of management. Providers are known and trusted to
provide good service. However, while clients trust cloud
providers to perform their services correctly, there is an
increasing concern that cloud providers may access or
leak confidential data in the process of providing service.
Reports in the popular press describe companies selling
customer data to marketers [20], disgruntled employees
snooping or exporting data [16], and hackers gaining
access to data on clouds [60, 23]. This type of threat is
referred to as an ‘honest but curious’ or ‘passive’ [33]
attacker: a party who is trusted to handle the data and
deliver service correctly, but who looks at the data, and
steals or exports it. Embark aims to stop these attackers.
Such an attacker differs from the ‘active’ attacker, who
manipulates data or deviates from the protocol it is sup-
posed to run [33]. We consider that such a passive attacker
has gained access to all the data at SP. This includes any
traffic and communication SP receives from the gateway,
any logged information, cloud state, and so on.
We assume that the gateways are managed by the en-
terprise and hence trusted; they do not leak information.
Some middleboxes (such as intrusion or exfiltration
detection) have a threat model of their own about the two
endpoints communicating. For example, intrusion detec-
tion assumes that one of the endpoints could misbehave,
but at most one of them misbehaves [47]. We preserve
these threat models unchanged. These applications rely
on the middlebox to detect attacks in these threat models.
Since we assume the middlebox executes its functions
correctly and Embark preserves the functionality of these
middleboxes, these threat models are irrelevant to the
protocols in Embark, and we will not discuss them again.
2.3 Encryption Overview
To protect privacy, Embark encrypts the traffic passing
through the service provider (SP). Embark encrypts both
the header and the payload of each packet, so that SP does
not see this information. We encrypt headers because
they contain information about the endpoints.
Embark also provides the cloud provider with a set of
encrypted rules. Typically, header policies like firewall
rules are generated by a local network administrator.
Hence, the gateway knows these rules, and these rules
may or may not be hidden from the cloud. DPI and
filtering policies, on the other hand, may be private to
the enterprise (as in exfiltration policies), known by both
parties (as in public blacklists), or known only by the
cloud provider (as in proprietary malware signatures).
We discuss how rules are encrypted, generated and
distributed given these different trust settings in §4.2.
As in Fig. 1, the gateway has a secret key k; in the setup
with two gateways, they share the same secret key. At
setup time, the gateway generates the set of encrypted
rules using k and provides them to SP. Afterwards, the
gateway encrypts all traffic going to the service provider
using Embark’s encryption schemes. The middleboxes at
SP process encrypted traffic, comparing the traffic against
the encrypted rules. After the processing, the middleboxes
will produce encrypted traffic which SP sends back to the