Sensitive information is present on our phones, disks, watches and computers. Its protection is essential. Plausible deniability of stored data allows individuals to deny that their device contains a piece of sensitive information. This constitutes a key tool in the fight against oppressive governments and censorship. Unfortunately, existing solutions, such as the now defunct TrueCrypt [5], can defend only against an adversary that can access a user's device at most once ("single-snapshot adversary"). Recent solutions have traded significant performance overheads for the ability to handle more powerful adversaries able to access the device at multiple points in time ("multi-snapshot adversary"). In this paper we show that this sacrifice is not necessary. We introduce and build DataLair 1 , a practical plausible deniability mechanism. When compared with existing approaches, DataLair is two orders of magnitude faster for public data accesses, and 5 times faster for hidden data accesses. An important component in DataLair is a new write-only ORAM construction which improves on the complexity of the state of the art write-only ORAM by a factor of O(logN ), where N denotes the underlying storage disk size. Plausible deniability (PD) was first proposed in relation to deniable encryption [8] . Deniable encryption uses cryptographic techniques to allow decrypting the same ciphertext to different plaintexts. Filesystem Level PD. For storage devices, Anderson et al. first explored the idea of steganographic filesystems and proposed two solutions for hiding data in [6] . The first solution is to use a set of cover files and their linear combinations to reconstruct hidden files. The ability to correctly compute the linear combination required to reconstruct a file was based on the knowledge of a user-defined password. The second solution was to use a hash based scheme for storing files at locations determined by the hash of the filename. This requires storing multiple copies of the same file at different locations to prevent data loss. Macdonald and Kahn [14] designed and implemented an optimized steganographic filesystem for Linux, that is derived from the second solution proposed in [6] . Pang et al. [17] further improved on the previous constructions by avoiding hash collisions and more efficient storage. The solutions based on steganographic filesystem only defend against a single-snapshot adversary. Han et al. [11] designed a steganographic filesystem that allows multiple users to share the same hidden file. Further, runtime relocation of data ensures deniability against an adversary with multiple snapshots. However, the solution does not scale well to practical scenarios as deniability is attributed to joint-ownership of sensitive data. Defy [18] is a log structured file system for flash devices that offers PD using secure deletion. Although, Defy protects against a multi-snapshot adversary, it does so by storing all filesystem related metadata in the memory, which does not scale well for memory constrained systems with large external storage devices. Block device level PD. At device-level, disk encryption tools such as Truecrypt [5] and Rubberhose [4] provide deniability but cannot protect against a multisnapshot adversary. Mobiflage [20] also provides PD for mobile devices against a single-snapshot adversary. Blass et al. [7] were the first to deal with deniability against a multi-snapshot adversary at device level. The solution in [7] deploys a write-only ORAM for mapping data from logical volumes to an underlying storage device and hiding access patterns for hidden data within reads to non-hidden (public) data.
Chakraborti et al. REF use writes to public data to hide accesses to hidden data based on another write-only ORAM that does not need recursive maps.
DataLair: Efficient Block Storage with Plausible Deniability against Multi-Snapshot Adversaries
Proceedings on Privacy Enhancing Technologies
Computer Science