A SECURE CLOUD BACKUP SYSTEM: with Assured Deletion and Version ControlConference Paper: September 2011
DOI: 10.1109/ICPPW.2011.17  Source: DBLP CITATIONS 70READS485authors, including:
Some of the authors of this publication are also working on these related projects:
Human elephant conflict View project
Encrypted deduplication storage systems View project
Yang Tang
Columbia University
11 PUBLICATIONS   692 CITATIONS   
SEE PROFILE
Patrick P. C. Lee
The Chinese University of Hong Kong
148 PUBLICATIONS   3,211 CITATIONS   
SEE PROFILE
John C.s. Lui
The Chinese University of Hong Kong
427 PUBLICATIONS   9,628 CITATIONS   
SEE PROFILE
All content following this page was uploaded by Patrick P. C. Lee on 27 May 2014.

systems and the related technical issues. In Section III, we
present the threat model and assumptions we make in our
design. In Sections IV and V, we discuss the design and
implementation details of FadeVersion, respectively. In Sec-
tion VI, we evaluate the cost effectiveness and performance
overhead of our system. Sections VII concludes and presents
future work.

Cloud computing is an emerging service model that pro-
vides computation and storage resources on the Internet. One
attractive functionality that cloud computing can offer is cloud
storage. Individuals and enterprises are often required to
remotely archive their data to avoid any information loss in
case there are any hardware/software failures or unforeseen
disasters. Instead of purchasing the needed storage media to
keep data backups, individuals and enterprises can simply
outsource their data backup services to the cloud service
providers, which provide the necessary storage resources to
host the data backups.
While cloud storage is attractive, how to provide security
guarantees for outsourced data becomes a rising concern.
One major security challenge is to provide the property of
assured deletion, i.e., data files are permanently inaccessible
upon requests of deletion. Keeping data backups permanently
is undesirable, as sensitive information may be exposed in
the future because of data breach or erroneous management
of cloud operators. Thus, to avoid liabilities, enterprises and
government agencies usually keep their backups for a finite
number of years and request to delete (or destroy) the backups
afterwards. For example, the US Congress is formulating the
Internet Data Retention legislation in asking ISPs to retain data
for two years [9], while in United Kingdom, companies are
required to retain wages and salary records for six years [24].
Assured deletion aims to provide cloud clients an option
of reliably destroying their data backups upon requests. On
the other hand, cloud providers may replicate multiple copies
of data over the cloud infrastructure for fault-tolerance rea-
sons. Since cloud providers do not publicize their replication
policies, cloud clients do not know how many copies of their
data are on the cloud, or where these copies are located. It
is unclear whether cloud providers can reliably remove all
replicated copies when cloud clients issue requests of deletion
for their outsourced data.
Thus, we are interested in the design of a highly secure
cloud backup system that enables assured deletion for out-
sourced data backups on the cloud, while addressing the im-
portant features for a typical backup application. One such fea-
ture is to enable version control for outsourced data backups,
so that cloud clients can roll-back to extract data from earlier
versions. Typically, each backup version is incrementally built
from the previous version. If the same file appears in multiple
versions, then it is natural to store only one copy of the file and
have the other versions refer to the file copy. However, there
are data dependencies across different versions, and deleting
an old version may make the future versions unrecoverable.
This is one challenge we aim to overcome.
In this paper, we present FadeVersion, a secure cloud backup
system that supports both version control and assured deletion.
FadeVersion allows fine-grained assured deletion, such that
cloud clients can specify particular versions or files on the
cloud to be assuredly deleted, while other versions that share
the common data of the deleted versions or files will remain
unaffected. The main idea of FadeVersion is to use a layered
encryption approach. Suppose that a file F appears in multiple
versions. We first encrypt F with key k, and then encrypt key
k independently with different keys associated with different
versions. Thus, if we remove a key of one version, we can
still recover key k and hence file F in another version.
We implement a proof-of-concept prototype of FadeVersion
that is compatible with today’s cloud storage services. We
extend an open-source cloud backup system Cumulus [23]
and include the assured deletion feature. Using Amazon S3
as the cloud storage backend, we empirically evaluate the
performance of FadeVersion. We also conduct monetary cost
analysis for FadeVersion based on the cost plans of different
cloud providers. We show that the additional overhead of
FadeVersion is justifiable compared to Cumulus, which does
not possess the assured deletion functionality.
The remainder of the paper proceeds as follows. In Sec-
tion II, we provide the necessary background on cloud storage

II. BACKGROUND AND RELATED WORK
There are different ways of achieving assured deletion.
One approach is by secure overwriting [7], in which new
data is written over original data to make the o

described in Section II. Now, if we want to assuredly delete
Version V1, then we can remove the cryptographic key that
encrypts Version V1. However, since Version V2 shares some
files in Version V1, some files in Version V2 also become
inaccessible. In short, assuredly deleting one version may also
affect future versions.
In the second approach, we first pass data backups through
the assured deletion system, followed by the version control
system, as shown in Figure 1(b). First, each backup file is
encrypted with different cryptographic keys by the assured
deletion system. If two identical files are encrypted with
different keys, then their encrypted copies will have different
format. Thus, if we pass these encrypted files through the
version control system, then the version control system cannot
discover any commonality between the encrypted copies and
cannot share identical files across versions.

III. THREAT MODEL AND ASSUMPTIONS
We consider a retrospective attack threat model: an attacker
wants to recover specific files that have been deleted. This type
of attack may occur if there is a security breach in the cloud
data center, or if a subpoena is issued to demand data and
encryption keys. We assume that the attacker is omnipotent,
i.e., it can obtain copies of any encrypted data, as well as keys
on any machines.
Our security goal is to achieve assured deletion of files for
a cloud backup system with version control. We adopt the
cryptographic approach [3], [5], [6], [14], [21], [25], i.e., by
removing the keys that are used to decrypt the data backups
stored on the cloud. We make two assumptions for this
approach. First, the encryption operation is secure, in the sense
that it is computationally infeasible to revert the encrypted
data into the original data without the decryption key. Second,
we assume that the decryption keys are maintained by a key
escrow system that is totally independent of the cloud and can
be fully controlled by cloud clients. If a file is requested to
be assuredly deleted, then we require the associated key be
securely erased [7], which we believe is feasible given that
the size of a key is much smaller compared to a backup file.
In Section IV-F, we discuss in more detail the design of the
key escrow system.
IV. DESIGN OF FADEVERSION
A. Motivation
We argue that existing version-controlled cloud backup sys-
tems (e.g., Cumulus [23]) and assured deletion systems (e.g.,
Vanish [6] and FADE [21]) are incompatible. To elaborate the
issue, we consider a scenario in which we archive data backups
using two independent systems, i.e., a version control system
and an assured deletion system, and explain how they break
certain functionalities.
There are two approaches of deployment. In the first
approach, we first pass data backups through the version
control system, followed by the assured deletion system,
as shown in Figure 1(a). Suppose that Version V1 is first
generated, followed by Version V2. In this case, if there are
some identical file copies in both versions, then Version V2
can keep references to point to the identical file copies in
Version V1 instead of storing redundant file copies. In other
words, Version V2 may depend on some files in Version V1. Now, if we want to assuredly delete
Version V1, then we can remove the cryptographic key that
encrypts Version V1. However, since Version V2 shares some
files in Version V1, some files in Version V2 also become
inaccessible. In short, assuredly deleting one version may also
affect future versions.
In the second approach, we first pass data backups through
the assured deletion system, followed by the version control
system, as shown in Figure 1(b). First, each backup file is
encrypted with different cryptographic keys by the assured
deletion system. If two identical files are encrypted with
different keys, then their encrypted copies will have different
format. Thus, if we pass these encrypted files through the
version control system, then the version control system cannot
discover any commonality between the encrypted copies and
cannot share identical files across versions.

By:pranay kumar reddy

Thanks for joining me!

Good company in a journey makes the way seem shorter. — Izaak Walton