chap_background.tex

\chapter{Background}
\label{chap:background}

The work presented in this document builds on a number of established
topics related to computing, privacy, and security. This chapter
touches on the fundamentals of such work. Chapter~\ref{chap:related}
touches on more directly related work.

\section{Cryptography}
\label{chap:background:crypto}

Many of the topics discussed in this dissertation leverage
cryptographic primitives as the basis of various security and privacy
guarantees. Cryptography represents a security primitive that does not
rely on trusting specific people, platforms, or systems in order to
securely function. Instead, it requires trust in only one thing: the
underlying math. This has led to the proliferation of cryptography as
the primitive on which many security and privacy enhancing features
are built.

\subsection{Symmetric Cryptography}

Modern cryptographic systems come in two flavors: symmetric
cryptography and asymmetric cryptography. Symmetric cryptography
algorithms function on the principle that a single ``key'' is used for
both halves of each cryptographic operation (e.g. encryption and
decryption). Asymmetric algorithms (discussed in the next section)
overcome this limitation.

The core symmetric cryptography operation is symmetric
encryption. Symmetric encryption algorithms use a single key to both
encrypt and decrypt a message. This message, once encrypted, can not
be deciphered without access to the associated secret key (or to
insurmountably large amounts of computing power). This key must be
securely stored, or if shared, securely exchanged between
parties. Anyone with the key can decrypt the corresponding ciphertext
the key was used to create; anyone without can not. The security of a
symmetric encryption cipher tends to be proportional to the length of
the encryption key; the longer the key, the more secure the data
encrypted with it is. Common symmetric encryption algorithms include
block ciphers such as AES~\cite{nist2001} and
TwoFish~\cite{schneier1998} as well as stream ciphers such as (the now
deprecated) RC4~\cite{rc4-source}. Many block ciphers can also be used
as stream ciphers by leveraging operation modes such as CTR and
OFB~\cite{schneier2010crypto}.

In addition to encryption and decryption, symmetric cryptography
algorithms can also be used to provide secure message integrity and
authenticity verification. Such algorithms leverage a secret
authentication key to generate a message authentication code (MAC)
across a given piece of data. This MAC can then be sent to another
user along with the data over which it was generated. Any holder of
the authentication key who receives said data can recompute the MAC
value independently, comparing their computed value to the one that
was sent and verifying the authenticity and integrity of the
associated data in the process. In this manner, users who share a
symmetric authentication key can ensure that the data they send to
each other is not tampered with in transit and that it comes from
another holder of the required key. MAC algorithms can be built from
existing hash functions using mechanisms such as
HMAC~\cite{krawczyk1997} (e.g. HMAC-SHA-256~\cite{kelly2007}) or from
existing symmetric block ciphers using mechanisms such as
CMAC~\cite{black2005, dworkin2005} (e.g. AES-CMAC~\cite{song2006}). In
most situations, both encryption and authentication are used in tandem
to form a secure channel capable of communicating data that is
indecipherable to outsiders and over which any data tampering can be
detected.

While symmetric cryptography algorithms are useful in situations where
a single actor will be both encrypting and decrypting a piece of data
(and thus can hold the required key personally), they pose a major
challenge in situations where multiple parties wish to communicate or
exchange data securely. In such situations, the parties must find a
way to securely communicate the required symmetric encryption and
authentication keys out-of-band. In the absence of additional
cryptographic methods, the only real way to securely communicate such
keys while avoiding both eavesdroppers and interlopers is to meet in
person and generate or exchange keys manually. This task is tedious
and impractical for all but the simplest of situations, especially
given the modern digital communication landscape where multiple actors
may be continents apart. The challenges of securely bootstrapping
symmetric cryptography systems led researchers to seek a better method
for secure data exchange in the absence of an inherently secure
communication channel.

\subsection{Asymmetric Cryptography}

The major breakthrough in solving this challenge came in 1976 when
Diffie and Hellman proposed several novel cryptographic constructs,
including a system for multiple parties to negotiate a symmetric
encryption key across an insecure
channel~\cite{diffie1976}.\footnote{Such methods were actually
  independently developed by the GCHQ (the British signal-intelligence
  counterpart to the U.S. National Security Agency) in the early 1970s
  prior to the publication of Diffie and Hellman's research, but this
  work was classified and remained a secret until the late
  1990s~\cite{singh1999}.}These concepts paved the way for the
development of asymmetric cryptography (i.e. public-key cryptography):
a cryptography system in which one key is used for encryption while a
second related key is used for decryption. When properly designed, it
is computationally infeasible to derive one of these keys from the
other, allowing a user to publish one of their keys for public
consumption while keeping the corresponding key private. A member of
the public can then use a user's public key to encrypt a message that
only the holder of the corresponding private key will be able to
decrypt. If all members of the public maintain such public/private key
pairs, it becomes possible for any user to send any other user a
message that only the recipient can read without requiring an
in-person meeting or similar out-of-band secure communication channel.

Asymmetric cryptography relies on the existence of ``trapdoor''
functions. These functions can be quickly solved in one direction, but
are computationally difficult to reverse without knowledge of a secret
piece of information (e.g. the key). Factoring large numbers is a
classic example of a trapdoor function (and the method on which many
modern public key encryption systems are based). Factoring large
numbers is computationally difficult in cases where some piece of
secret information (e.g. one of the factors) is not known. Other
systems rely on the computation of discrete logarithms across elliptic
curves (ECC cryptography)~\cite{koblitz1987, miller1986}, computations
across lattices~\cite{ajtai1996},\footnote{Lattice-based encryption
  schemes are believed to be resistant to (currently theoretical)
  quantum-based attacks that are successful at breaking more
  traditional factoring and ECC-based schemes.}and beyond.

While Diffie and Hellman proposed a theoretical implementation of a
public key cryptography system, the first practical public key
cryptography system came a few years later with the publication of the
RSA~\cite{rivest1978} algorithm. Diffie and Hellman's joint key
negotiation scheme, however, remains a critical component of
asymmetric cryptography systems today -- especially those that employ
``forward secrecy''.\footnote{Forward secrecy is a property of secure
  communication that ensures that the short-term sessions keys used to
  protect individual messages can not be derived from any long-term
  authentication or encryption keys. In short, it guarantees that
  prior messages can not be decrypted should an adversary manage to
  compromise a long-term user key at some point in the future. Such
  systems are commonly implemented by decoupling short-term session
  keys from long-term authentication keys, using systems such as
  Diffie-Hellman key derivation to generate the former while relying
  on the latter for the prevention of Man-in-the-Middle attacks during
  the initial setup process.}Both asymmetric cryptography schemes such
as RSA and secure negotiation schemes such as Diffie-Hellman can be
used to bootstrap secure communications across an insecure channel by
allowing two parties to derive or exchange a mutual secret
(e.g. session key) that can then be used to facilitate further secure
communication using a symmetric encryption and authentication
algorithm. Symmetric algorithms tend to be more performant (and for a
given key length, more secure) than asymmetric algorithms, making such
split-type cryptography systems desirable.

Asymmetric encryption can be used to build the two additional core
cryptography primitives: cryptographic verification and cryptographic
authentication. Cryptographic verification (also called a
cryptographic ``signature'') is essentially the reverse of asymmetric
encryption; instead of a member of the public using another party's
public key to encrypt a message that only the target party can read,
they instead use their own private key to encrypt a message that the
public can then decrypt using the signers public key. Since only the
owner of a given key-pair should have access to the private key
necessary to generate such a message, the owner can ``prove'' to the
public that a given message comes from them. Similar to symmetric MAC
systems, asymmetric signatures can also be used to verify that signed
data has not been altered in transit. Any alteration would result in a
verification failure when a member of the public decrypts the message
signature - making such alterations detectable by the public at large.

Just as asymmetric encryption gives rise to secure signature
algorithms, secure signature algorithms give rise to secure
authentication systems. If a user generates a signed message saying
``I am John'' and sends it to an authentication server, the server can
verify that the message signature is valid using John's public key,
authenticating John in the process. The server need only have a list
of public keys for each approved user. It can then leverage the
assertion that only the intended user has access to the private key
corresponding to each approved public key, and is thus the only one
capable of generating a signed message from that user, as the basis of
user authentication.

Such systems can be further layered and generalized to build
cryptographically secure hierarchical assertion systems attesting to
the veracity of a range of data. Such public-key infrastructure (PKI)
systems allow the public to extrapolate their trust of a core set of
actors (i.e. Certificate Authorities, or CAs) to the any party for
which such actors are willing to certify specific facts. For example,
a server can trust a specific CA to manually verify the identities of
various users (e.g. by having them visit their office and present a
photo ID). This CA can then cryptographically sign a combination of
their declaration attesting to the identity of each user and a copy of
the user's public key. This signed combination of metadata and public
key forms a user ``certificate'' that can be presented to various
parties. These parties can then use their knowledge of the trusted
CA's public key to verify the identity attestation attached to the
user certificate -- allowing them trust that the user is who they
claim to be. This user can then use their ability to prove they (and
only they) control a private key corresponding to their certificate to
authenticate to a service. The x509 PKI standard is an example of such
a PKI system~\cite{rfc5280}. The x509 system is widely used to prove
the validity of domain name ownership on the Internet via
\texttt{HTTPS}).

\subsection{Secret Sharing}

Beyond the creation of public key cryptography, one of the other major
cryptographic breakthroughs of the last fifty years was the invention
of unconditionally secure secret sharing schemes. In particular, Adi
Shamir (the `S' from ``RSA'') proposed a practical and robust secret
sharing scheme in 1979~\cite{shamir1979}. Secret sharing is a method
for splitting a block of information up into two or more pieces such
that holders of any subset of the pieces can not infer any information
about the original block as a whole. Shamir Secret Sharing allows a
user to divide a block of $d$ data into $n$ pieces of which $k$ or
more pieces can be used to recompute the original value of $d$. A user
with fewer than $k$ pieces, however, has no more information about the
value of $d$ than a user with no pieces. Such ``$n$ choose $k$''
threshold systems provide a useful method for distributing information
amongst multiple parties in situations where no single party can be
fully trusted. These systems can also be used to provide redundancy by
selecting $n$ to be greater than $k$.\footnote{Not unlike RAID systems
  can be used to provide redundancy across multiple
  disks~\cite{patterson1988}.}

Shamir Secret Sharing, unlike other cryptography techniques, does not
rely on computational complexity as the basis of its
security. Instead, it is unconditionally secure based on information
theory principles. Thus, unlike computationally secure systems such as
RSA, Shamir Secret Sharing can not be broken regardless of the amount
of computational power one posses.\footnote{ I.e., computationally
  secure systems are potentially breakable if an adversary is afforded
  enough computing power or the ability to solve certain classes of
  computationally difficult problems quickly (e.g. via new technology
  such a quantum computers). Unconditionally secure systems remain
  unbreakable even to an adversary with unlimited computational power
  or newfangled computing capabilities.}

Shamir Secret Sharing functions on the basis of defining a polynomial
of degree $k-1$ over a finite field with the $d$ data encoded as the
first order-zero term. $n$ points are then selected from this
polynomial and distributed to the participants. Since $k$ points (but
no fewer) will uniquely identify the original polynomial, at least $k$
users must combine their pieces in order to re-compute $d$.

Shamir Secret Sharing (and related ``$n$ choose $k$'' systems) are
useful in a wide range of situations where one needs to distribute
trust across multiple entities. In particular, secret sharing
techniques are leveraged in some cryptographically-based access
control systems like that described in~\cite{goyal2006}.

\section{Usability}
\label{chap:background:usability}

Strong cryptography provides the basis for many of the secure systems
we build today. Unfortunately, strong cryptography has a rather
checkered history when it comes to the usability of secure
cryptographic systems.\footnote{Usability issues are not limited
  merely to cryptographic systems. Many computing systems struggle
  with balancing security and usability~\cite{furnell2006,
    ibrahim2010}.}Since most cryptographic systems merely reduce the
security of a system to the security of the cryptographic keys
protecting a system, how one manages such keys is of the utmost
importance. Manual key management, the defacto key management
standard for most cryptographic systems, tends to be extremely
challenging for the average user to execute properly. These usability
challenges often lead to security failures that have little to do with
the quality of the cryptography itself.

The poster child of the ``cryptographic system are largely unusable''
school of thought is a system for encrypting and cryptographically
signing email messages known as PGP~\cite{callas2007}. PGP (and its
open-source implementation - GnuPG/GPG~\cite{gnupg}) is one of the
longest running cryptographic security projects. It is also known to
have major usability issues, making it largely incomprehensible to all
but the most highly trained users~\cite{whitten1999}. These challenge
are largely related to the average user's inability to properly manage
the various cryptographic keys required for the proper use of
PGP~\cite{green-challenge}. This has led multiple parties to call for
the retirement of PGP~\cite{green-pgp} and/or to suggest
alternatives~\cite{borisov2004, mailpile, openwhisper,
  google-endtoend}. It remains to be seen if any of the proposed
alternatives will be able to provide (or improve upon) the level of
security offered by PGP while avoiding the usability pitfalls
leveraging PGP traditionally entails.

Similar challenges have been observed with other end user
cryptographic systems, ranging from secure storage devices to various
communication mediums~\cite{sweikata2009}. In all cases, properly
obtaining, storing, and controlling access to cryptographic keys and
related cryptographic secrets tends to be a task for which the typical
user is ill-suited. Thus, while cryptographic systems like
S/MIME~\cite{ramsdell-rfc5751} have seen limited success in the
enterprise where a central authority and staff can handle all key
management duties, they have largely failed for individual computer
users.

Even cryptographic systems that largely avoid burdening the user with
key-management responsibilities are subject to numerous usability
challenges. For example, take systems such as
Tor~\cite{dingledine2004} which are designed to allow users to
anonymously browse the Internet or otherwise utilize network resources
without leaking their identity. Securely using these systems, while
important for subverting censorship and authoritarian regimes, entails
overcoming numerous usability challenges. Most of these challenges are
related to the fact that all secure systems make assumptions about the
manner in which they will be used. If these assumptions violated, the
security of the system is unlikely to hold. While such assumptions are
necessary in order to make implementing secure systems possible, they
do not always align well with the manner in which users might use the
given system. When assumptions fail to align with user expectations,
security failures result. Tor has been subject to several notable
security failings related to mismatches between user behavior and
usage limits and assumptions. For example, a Tor user who logs into a
site on which they have a known user account (e.g. Facebook or Gmail)
while connected to the Tor network risks unmasking themselves not
through any failings of Tor itself, but through the voluntary
self-identification that occurs when they enter their username on such
a site~\cite{goodin-dreadpirate}.

How best to build systems that are both cryptographically secure and
easy to use remains an open and pressing question; a question to which
this document attempts to provide an answer.

\section{Storage}
\label{chap:background:storage}

Data storage has long been one of the core use cases of the digital
age. And the amount of data we generate, process, and store is greater
now than ever before. The need to store large amounts of data has also
entailed the need to control access to such data. Digital data storage
and access control techniques have morphed and changed over the last
50 years, and many of these changes have bearing on the work presented
in this document.

Lacking robust encryption, verification, and access control
primitives, early storage and file system technologies often simply
neglected data security. The rise of multi-user operating systems like
Unix mandated the creation of basic file-system access control
schemes. The traditional Unix file access control and permissioning
scheme grew out of such early multi-user computing systems as part of
the virtual file system (VFS) abstraction~\cite{linux-vfs}. The Unix
access control system, however, has a number of limitations: it
supports only a single, basic access control model (owner, group, and
other; R/W/E permissions), it requires a trusted system for
enforcement (i.e. the OS kernel), and it is strongly coupled to a
specific local system. Systems like NFS attempt to extend Unix file
security semantics beyond the local machine allowing remote sharing of
files, but even these systems are limited to singular administrative
domains and trusted systems.

The Windows NT file system access control model (implemented via the
NTFS file system) extends the flexibility of the traditional Unix
model by adding support for more expressive access control lists
(ACLs). ACLs allow the control of additional permissions (e.g. delete,
create directory, etc) as well as more expressive user-to-permission
mappings beyond the basic owner/group/other Unix model. Furthermore,
the Windows NT model has the ability to delegate user authentication
to a local Domain Controller (DC) capable of centrally managing all
users from a single location. This expands the ability to control file
access beyond the users associated with the local system to the users
associated with an entire administrative domain. Yet this system still
has many of the same limitations as the Unix model: the requirement
for a trusted system for enforcement and the tight coupling to the
local administrative domain.

The rise of the Internet as a reliable and high speed system for
connecting multiple machines across the world, as well as the move
toward cloud computing models where computational resources are
outsourced to dedicated providers, have increased the demand for
secure storage systems capable of spanning multiple systems and
domains. In order to overcome the limitations posed by traditional
file system security models and accommodate modern multi-user,
multi-system use cases, researchers have proposed a number of newer
file storage systems. These systems try to address one or more of the
limitations mentioned above. Some of them employ cryptographic
security models to overcome the need for a trusted enforcement
system. Others are designed to extend access control semantics beyond
the local machine to large networks or even the global internet. Still
others explore the use of novel access control models more expressive
than Unix permissions or Windows NT ACLs. Many systems combine more
than one of these approaches to build a fully featured next-generation
storage system.

Kher~\cite{kher2005} presents a survey of the security models of
various data storage systems, sorting such systems into basic
networked file systems, single-user cryptographic file systems, and
multi-user cryptographic file systems. As previously mentioned, basic
networked file systems rely on trusted systems and administrators for
the enforcement of security rules. Examples of such systems include
the Sun Network File System (NFS)~\cite{sandberg1985}, the Andrew File
Systems (AFS)~\cite{howard1988}, and the Common Internet File System
(CIFS/SMB)~\cite{microsoft-smb2}. All of these systems are designed
for use within local administrative domains and do not scale well to
global, loosely-coupled distributed systems. To deal with the
scalability issues, researchers have built systems like
SFS~\cite{mazieres1999} or OceanStore~\cite{kubiatowicz2000} which aim
to reduce the administrative burden of large scale distributed file
systems.

All of these systems, however, rely on some degree of system,
administrative, or third party trust. In order to accommodate
situations where users do not wish to place trust on the underlying
system or remote servers, there exist a handful of cryptographically
secure file systems. The best of these systems offer end-to-end
cryptography, meaning that data is encrypted and decrypted on the
client side and the server never has access to the unencrypted data.
Systems like the Cryptographic File Systems (CFS)~\cite{blaze1993} or
eCryptFS~\cite{ecryptfs} provide basic single-user end-to-end file
encryption when coupled with traditional network file systems such as
NFS. While end-to-end encryption is a powerful security model for
enabling secure storage atop untrusted systems, it does pose
challenges with respect to multi-user, multi-device use
cases~\cite{miltchev2008}. These challenges arise from the requirement
that all clients have access to private cryptographic credentials in
order to effectively read or write files. In order to support both
end-to-end encryption and multi-user scenarios, researchers have
proposed multi-user cryptographic storage systems like
SiRiUS~\cite{goh2003}, cepheus~\cite{fu1998}, and
Plutus~\cite{kallahalla2003}.

Beyond traditional local and networked file systems, many users have
turned to cloud-backed storage technologies. System like
Dropbox~\cite{dropbox} or Google Drive~\cite{google-drive} offer
mechanisms for storing arbitrary files on third party cloud
servers. Such files can either be accessed via a web browser or synced
to a local machine via various client-side utilities. Other cloud
services forgo the traditional file storage model all together in
favor of various object storage abstractions. Amazon's
S3~\cite{amazon-s3} and Ceph~\cite{ceph} are examples of such
systems. These systems can either be used for raw key:object data
storage or as a block-oriented backing store for higher level file
storage abstractions such as Dropbox or Google Drive. Systems like
Dropbox, Google Drive, or Amazon S3 all rely on a centralized, trusted
third party storage provider for ``secure'' operation. To overcome
this requirement, distributed systems such as
Tahoe-LAFS~\cite{wilcox-o'hearn2008} propose an alternate model where
trust in any single system is reduced and storage is spread across a
variety of third party providers.

\section{Access Control}
\label{chap:background:ac}

Over the years, computing systems have deployed a range of access
control techniques. All of these techniques share a common goal --
controlling access to a specific system, resource, or piece of
data. Most access control models have two key components:
authentication and authorization.  Authentication is used to establish
the identity of an actor. Authorization then leverages this
identification as the basis of granting or denying specific
permissions to the actor.

Computer-based access control systems have been with us since the
earliest multi-user (e.g. time-sharing) operating systems became
popular in the 1970s and 1980s~\cite{saltzer1974}. Early access
control systems were primarily focused around the Unix model of access
control: users, groups, and read/write/execute file-level
permissions. Authentication in these early systems was generally
limited to username:password combinations, the mechanisms of which
were hard coded into the \texttt{login} program. Later, more flexible
pluggable authentication systems such as PAM were
created~\cite{samar1996, linux-pam, openpam}. In such Unix-like access
control systems, each user is a member of one or more groups and each
file has an owner and a group. The three file permissions (read,
write, and execute) are granted on the basis of a user's relationship
to a given file. Either the user is the file's owner, the user is a
member of the file's group, or the user is neither of these
things. This model is flexible enough to support many use cases, and
continues to be used today as the core access control model in many
Unix-like operating systems (e.g. BSD, Linux, OSX, etc).

Access Control List (ACL) schemes were originally proposed in systems
such as Multics~\cite{saltzer1974} and later popularized by systems
such as VMS and Windows NT. ACLs extend the permission model beyond
the basic Unix file permissions to include a wider range of file
(e.g. read, write, delete, create, etc) and system-level
(e.g. shutdown, connect to network, etc) permissions. ACLs are
associated with specific system objects (e.g. files, folders, OS
subsystems, etc) and map a user or group to a list of permissions that
user or group possess. They generalize the Unix access control model
to accommodate a wider range of permissions and mappings between
permissions and actors. ACL-based systems have been integrated into
many modern Unix-like operating systems as an optional extension
beyond the tradition Unix permissioning scheme.

Existing access control schemes are often grouped into one of two
classes: Mandatory Access Control (MAC) systems or Discretionary
Access Control (DAC) Systems. While the lines between these two
approaches are occasionally blurred, the basic difference between them
lies in which actors within a system have the ability to grant/extend
permissions to other actors. In MAC systems, all permissions are set
by the system administrator and users have no ability to change these
permissions themselves or to transfer permissions to other users. DAC
systems, in contrast, give users the ability to set their own
permissions on objects they own or create, and to transfer these
permissions to other users. Traditional Unix access control systems as
well as ACL access control systems can generally be used in either MAC
or DAC based systems. MAC systems are generally preferred in high
security environments where centralized management models are common
and to tighter control over data is desirable. DAC systems are more
common in general purpose systems where the extra flexibility they
offer reduces the administrative burden. Most Unix-like systems are
DAC systems by design, but extensions
(e.g. SELinux~\cite{loscocco2001}) can be used to add MAC properties
to these systems.

Many of the early access control systems pose a host of manageability
challenges. How do you coordinate the permissions of thousands of
users across millions of objects? How do you revoke permissions for a
defunct user? Or add a new user?  Role-Based Access Control
Models~\cite{sandhu1996} arose to cope with many of these challenges.
Role-Based Access Control (RBAC) inserts an additional layer of
indirection between users and permissions. In an RBAC system, users
are assigned to one or more roles. Each role is then assigned one or
more permissions. This model simplifies management by separating
permission assignment from specific users. RBAC permissions are
assigned on the basis of specific positions or duties within an
organization and mapped to specific roles. Users are then assigned to
these roles on the basis of whether or not they hold a specific
positions or are required to perform a specific duty. Thus, adding or
removing users does not require any modification to permission
mappings, only role mappings. Likewise, adding or removing permissions
does not require modifying user mappings, only role mappings.

Many authentication systems strive to provide mechanisms to allow a
user to authenticate to multiple system using a single account.
``Single-sign-on'' (SSO) systems such as Kerberos~\cite{neuman1994,
  kohl1994} aim to unburden users by allowing the use of a single
account across multiple machines. Similarly, SSO systems aim to
unburden administrators by allowing the centralized management of user
accounts. A more recent variant of this idea has been toward the use
of dedicated ``identify providers'' who provide federated
authentication to a suite of third party services. This ``federated
identity management'' (FIM) arrangement allows one entity to delegate
the authentication of users to a separate entity, often for the
purpose of allowing a user to leverage their existing account with one
service provider to authenticate to a separate service
provider. System such as Shibboleth~\cite{leandro2012},
SAML~\cite{SAML}, and OAuth~\cite{oauth} provide frameworks for
performing delegation. Other systems leverage these frameworks to
provide additional security guarantees~\cite{bhargava2011}. Like more
traditional SSO system, FIM systems aim to increase usability and
security by reducing the number of accounts a user must maintain,
encouraging the use of stronger passwords (or non-password based
authentication mechanism) in the process.

\section{The Cloud}
\label{chap:background:cloud}

The previous ten years have seen a major shift in the manner in which
users and developers obtain various computing resources. Gone are the
days where one must purchase their own hardware or operate their own
computing systems. Instead, numerous companies are more than happy to
sell you any computing service you require for a pre-established,
time-metered rate. This ``Cloud'' computing model significantly lowers
the barrier to entry to those needing to leverage compute resources,
increasing the availability of such services and driving a vast shift
in the way we use the Internet, store our data, obtain our
entertainment, interact with our friends, and more.

\subsection{Benefits}

Cloud service providers like Amazon, Google, Microsoft, Rackspace, and
IBM sell over \$150 billion in cloud services
annually~\cite{flood2013}. The rapid rise of the cloud computing model
is supported by a number of desirable qualities the cloud can provide
more effectively than traditional self-hosted computing
systems. Namely:

\begin{packed_desc}
\item[OPEX vs CAPEX] \hfill \\ Using cloud-based compute services
  allows companies to shift what are traditionally one-time, up-front
  capital expenditures (CAPEX, e.g. large arrays of servers) to
  regular operational expenditures (OPEX, e.g. a monthly subscription
  fee). This fact gives rise to a number of potential
  benefits. Whereas spinning up traditional compute infrastructure
  requires a large initial investment, cloud compute infrastructure
  can be purchased for as low as a few dollars each month. This
  drastically lowers the barrier of entry to those requiring such
  services by eliminating any large up-front costs. Furthermore,
  moving to the cloud makes compute infrastructure a regular,
  predictable expense, easily accounted for when planning
  budgets. Finally, operational expenditures are often more easily
  justified at many organizations without requiring major internal
  review processes, allowing those that purchase compute services via
  the cloud to retain more direct control over how, when, and what
  they purchase. All of these factors interact to make the OPEX cloud
  model a more desirable purchasing model than the traditional CAPEX
  model.
\item[Flexibility] \hfill \\ The ``pay-for-what-you-need'' cloud
  purchasing model is also far more flexible than the traditional
  in-house computing model. While the traditional model requires
  buyers to accurately predict their future compute requirements
  before making the initial purchase, the cloud allows users to scale
  infrastructure as required and without any real need for accurate
  forward demand prediction. This makes it far simpler to start a
  small project and grow it into a larger project without requiring
  any large up-front cost or guesswork. Likewise, if a project fails
  to gain traction, it can be efficiently spun down and no one is left
  holding a bunch of expensive, but no longer useful, hardware.
\item[Efficiency] \hfill \\ The cloud models offers efficiencies of
  scale not available to traditional in-house compute users. At the
  macro-level, it is rare for end user facing systems to require
  constant load throughout the day. Instead, services tend to see peak
  usage at certain times each day related to the diurnal cycles of
  their users. Large international cloud service providers can
  leverage this fact in ways individual hardware operators can not. In
  particular, such providers can ensure their underlying hardware is
  uniformly loaded 24/7/365 by spreading the workloads of a diversity
  of global tenants across their infrastructure. After all, it is
  always 5:00 PM somewhere. This allows large cloud services providers
  to operate their systems at a steady capacity, avoiding the need to
  oversize systems to account for short-lived peak loads. At the
  micro-level, cloud providers are generally able to colocate a large
  number of compute systems in a single data center, allowing them to
  optimize cooling, power, network, and other resources in manners not
  available to smaller in-house server farms. On the power and cooling
  front, it is not uncommon to see cloud data centers that are over
  $90\%$ efficient -- a PUE\footnote{Power Usage Effectiveness: The
    ratio of total consumed power to useful IT power.}of
  $\approx1.1$~\cite{google-efficiency}. On the networking front, such
  colocation allows for higher speed, lower energy, data transfers
  between machines. The net result of all these efficiency gains is
  that cloud providers can generally offer compute resources with
  better performance and lower costs than in-house data center
  deployments.
\end{packed_desc}

\subsection{Service Classes}

Modern cloud systems come in a range of classes. These classes
generally divide up cloud services based on the level of abstraction
they provide. The common cloud service classes include:

\begin{packed_desc}
\item[IaaS:] ``Infrastructure as a Service'' systems are the lowest
  level of cloud services. In an IaaS environment, the user is
  provided with remote access to a raw ``computer'' -- generally a
  virtual machine with a pre-installed operating system -- atop of which
  they may build and implement their own services. This class of cloud
  services represents the most direct replacement for the traditional
  in-house compute model where a user would start with a raw physical
  machine and build up from there. Amazon EC2~\cite{amazon-ec2} and
  Google Compute Engine~\cite{google-compute} are both examples of IaaS
  services.
\item[PaaS:] One step up the stack are ``Platform as a Service''
  offerings. PaaS systems provide the end user with an environment
  capable of running their code, but abstract away a lot of the lower
  level details of setting up and managing a full OS and virtual
  machine. This allows users to trade flexibility for simplicity and
  ease of use. Google App Engine~\cite{google-appengine} and
  Heroku~\cite{heroku} are examples of PaaS offerings.
\item[SaaS:] ``Software as a Service'' sits at the top of the cloud
  service stack. This class of service is most generally what consumer
  end users are referring to when they talk about the ``cloud''. SaaS
  offerings represent fully-fledged services that provide some form of
  functionality directly to an end user. Examples of SaaS systems
  include Dropbox~\cite{dropbox}, Gmail~\cite{google-gmail}, and
  Facebook~\cite{facebook}.
\end{packed_desc}

It is not uncommon for one layer of cloud services to be built atop a
lower layer. E.g., an SaaS system might be built atop a PaaS system,
itself built atop an IaaS system. Furthermore, the ``...aaS'' inherent
in the names of each of these layers reflects another cloud trend: the
popularity of service oriented architectures
(SOA)~\cite{valipour2009}. Service oriented architectures abstract a
set of useful actions into a service that can be consumed by users.
SOA systems encourage the standardization and commoditization of a
wide range of useful computing tasks. This allows developers of new
services to lean heavily on existing services -- adding only the
specific new functionality they need without having to build the
supporting infrastructure from scratch. The end result is yet another
mechanisms for accelerating the rate of advancement when building
systems and services atop the cloud.

\subsection{Enabling Technologies}

It is also important to note the technologies underlying the shift
toward cloud-backed computing infrastructure. In particular, several
core advances have enabled the modern cloud as we know it. These
include:

\begin{packed_desc}
\item[Commoditization of Hardware] \hfill \\ The cloud, by and large,
  is built using cheap, off-the-shelf commodity hardware. High-end,
  specialty hardware is rare to find in most cloud data
  centers. Instead, Google, Amazon, and others leverage more or less
  the same computing components used in most consumer hardware, but in
  much larger numbers. Cloud providers have discovered that it is more
  cost effective to utilize cheap consumer parts and simply design
  systems to cope with the higher rates of failure such parts exhibit
  than it is to buy high-end parts with lower failure rates but
  disproportionately larger costs~\cite{atwood2007}. This shift has
  made hardware an easily replaceable and interchangeable commodity in
  modern data center design, lowering the cost and barriers to entry
  involved in constructing and maintaining data centers.
\item[Virtualization] \hfill \\ Virtualization, the ability to
  simulate one or more ``virtual computers'' running atop a single
  physical computer, is not a new concept~\cite{goldberg1974}. But the
  previous 10 to 20 years have seen the use of virtualization become a
  commonplace occurrence, well supported by commodity hardware and
  software alike. Virtualization has made it simple and cost effective
  for cloud-providers to offer their services, slicing discrete
  physical systems between many paying users. Virtualization also
  allows providers to separate tenants from any single piece of
  hardware, allowing providers to migrate tenants between physical
  systems in order to meet up-time and load balancing goals without
  the user ever being aware of a change.
\item[Free and Open Source Software (and Hardware)] \hfill \\ The rise
  of Linux and related Free and Open Source Software (FOSS) systems
  has closely tracked the rise of the cloud. This is no
  coincidence. FOSS systems allow users to quickly and cheaply deploy
  a range of applications without having to worry about licensing
  specialty high-cost software, vendor lock-in, or any number of other
  barriers to deployment mobility. While the cloud provided cheap,
  commodity (often virtual) hardware, FOSS provides cheap, commodity
  software to make such hardware do useful things. Furthermore, many
  cloud providers have combined the ubiquity of commodity hardware
  with the ethos of FOSS to create open-hardware ecosystems -- making
  it a lot simpler for service providers to build and deploy
  cloud-optimized computing hardware~\cite{opencompute}.
\end{packed_desc}

The success of the cloud is not due to any singular new idea or
major breakthrough in computing. Instead, it represents the confluence
of a number of discrete technologies, business cases, and user demands
at a mutually beneficial moment in time. In doing so, these events
have fundamentally shifted the way developers and end users alike
consume and interact with the available computing systems of the
21\textsuperscript{st} century.

%%  LocalWords: SSaaS SSP Lenovo SSPs IaaS Diffie Hellman's Adi VFS
%%  LocalWords: Shamir NTFS AFS CIFS SMB SFS OceanStore CFS SiRiUS
%%  LocalWords: Plutus ACL LAFS Rackspace CAPEX OPEX PUE de colocate
%%  LocalWords: PaaS Heroku SaaS aaS FOSS TwoFish OFB HMAC SHA CMAC
%%  LocalWords: GCHQ cepheus DAC SELinux RBAC eCryptFS Ceph ECC CA's
%%  LocalWords: CAs HTTPS et al SSO FIM Kher