INVISILINE: Invisible Plausibly-Deniable Storage

INVISILINE: Invisible Plausibly-Deniable Storage

Speakers: Sandeep Kiran Pinjala, PhD Student, Stony Brook University; Bogdan Carbunar, Professor, Florida International University; Anrin Chakraborti, UIC; Radu Sion, Professor, Stony Brook University

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=3vL2o8i5EvM

Overview

In this talk, Sandeep Kiran Pinjala, a PhD student at Stony Brook University, presents "INVISILINE," a novel system for invisible, plausibly-deniable storage. The work, a collaboration with Professors Bogdan Carbunar, Anrin Chakraborti, and Radu Sion, addresses a critical shortcoming of traditional data encryption: its vulnerability to "rubber hose attacks" and legal coercion. While encryption effectively protects data at rest from unauthorized access, it offers no defense when adversaries, such as governments or law enforcement agencies, can compel users to reveal decryption keys. This problem is exacerbated by laws like the UK's RIPA Act, the US's Cloud Act, and Australia's Assistance and Access Act, which empower authorities to demand access to sensitive user data, often under threat of criminal charges.

The core premise of INVISILINE is to provide plausible deniability (PD), a mechanism that allows users to convincingly deny the existence of hidden sensitive data, even under intense scrutiny. Unlike conventional encryption, which merely obscures data, PD aims to make it impossible for an adversary to prove that hidden data exists. INVISILINE takes this concept a step further by introducing "invisibility," ensuring that the very act of using the PD system or the presence of the public data does not raise suspicion. This talk highlights a significant advancement in data privacy, moving beyond mere confidentiality to tackle the complex challenges posed by powerful, coercive adversaries.

The significance of INVISILINE lies in its innovative approach to achieving both plausible deniability and invisibility without requiring modifications to underlying storage media or exposing unusual system artifacts. By integrating hidden data directly into the initialization vectors (IVs) of standard disk encryption, INVISILINE offers a robust defense against sophisticated multi-snapshot adversaries, who might otherwise detect patterns indicating hidden storage. This work is particularly relevant in an era where digital privacy is increasingly under threat from both state-sponsored surveillance and targeted data extraction, providing a crucial tool for individuals and organizations seeking to protect highly sensitive information from forced disclosure.

Background

▶ Watch: Introduction: The problem of data coercion (0:00)

The talk begins by establishing the limitations of traditional encryption. While robust cryptographic algorithms secure data against unauthorized access, they fall short when the adversary can compel the data owner to disclose the decryption keys. This scenario, famously depicted in "rubber hose cryptoanalysis" cartoons, is a tangible threat, as evidenced by real-world instances where governments leverage legal frameworks to force disclosure of digital data from devices like phones and laptops. The speaker emphasizes that mere encryption is insufficient against such "powerful adversaries"; what's needed is a system where users can deny possessing sensitive data altogether.

Plausible deniability (PD) is introduced as the solution. A simple illustration of PD is a one-time pad, where a given ciphertext can plausibly be decrypted to a benign plaintext using one key, while the true, sensitive plaintext is revealed by another. The adversary's model is critical here: they have complete access to the user's device, including installed software and running binaries. The PD system's goal is to ensure that the adversary cannot discern that the user is even using such software. Every observed runtime action must have an alternate, plausible explanation. The adversary is assumed to be computationally bounded, rational (meaning they won't persist if no proof of hidden data is found), and can be either a single-snapshot adversary (capturing device state once) or a multi-snapshot adversary (capturing states at different times to detect patterns). Importantly, the adversary can also question why a user is running PD software.

This leads to the crucial concept of invisible PD systems. Prior PD systems, such as TrueCrypt, a popular disk encryption software with a hidden volume feature, failed the invisibility test. If TrueCrypt was installed on a device, its mere presence could raise suspicion, even if no hidden data existed. An invisible PD system must satisfy two key criteria:

1. Operations on public data should not require the PD software. The user should be able to present benign, public data using standard, non-PD encryption software (e.g., BitLocker for Windows), without raising suspicion.
2. Storing hidden data should not result in any additional metadata or non-standard disk layouts, which could be tell-tale signs for an adversary.

The talk reviews prior PD systems, categorizing them by their resistance to multi-snapshot adversaries and their invisibility. Most existing systems, except for Infuse, fall short on one or both properties. Infuse, while offering both, requires modifications to the Flash Translation Layer (FTL), which is typically proprietary and not exposed by most vendors. This gap highlights the need for a truly invisible, multi-snapshot-resistant PD system without media dependencies – precisely what INVISILINE aims to deliver.

Key Findings

▶ Watch: Limitations of prior PD systems like TrueCrypt (3:20)

INVISILINE is presented as the first invisible plausible deniability system with no media dependencies. Its primary innovation lies in achieving invisibility and multi-snapshot adversary resistance by leveraging the existing structure of standard disk encryption, specifically DM-Crypt in the Linux ecosystem. Instead of creating a separate, detectable hidden volume, INVISILINE cleverly stores hidden data within the initialization vectors (IVs) used for encrypting public data sectors.

The key findings and contributions of INVISILINE are:

1. True Invisibility: INVISILINE ensures that the disk layout and encoding are fully compatible with open-source disk encryption software like DM-Crypt. This means that an adversary examining the disk will only see what appears to be a standard DM-Crypt encrypted volume, with no additional metadata or unusual patterns indicating the presence of hidden data. The operations on public data do not require INVISILINE's specific software, further enhancing deniability.
2. Plausible Deniability through IVs: By embedding hidden data within the IVs of public sectors, any updates to this hidden data can be plausibly explained as changes to the "randomness" used for encrypting public data. Since IVs are designed to be unique and unpredictable for each encryption operation, changes to them are inherently difficult to distinguish from legitimate random generation.
3. Multi-Snapshot Adversary Resistance: A significant challenge for PD systems is resisting adversaries who can take multiple snapshots of a device over time. Such adversaries could compare snapshots to detect changes that are inconsistent with normal system operations or public data updates. INVISILINE addresses this by carefully managing how hidden data is updated and mapped, ensuring that changes to hidden data are always accompanied by plausible public data activity, thus maintaining deniability across multiple observations.
4. No Media Dependencies: Unlike systems like Infuse, INVISILINE does not require any modifications to the underlying storage hardware or its firmware (e.g., the FTL). It operates entirely within the software layer of the operating system, making it broadly compatible and deployable without vendor-specific support.
5. Practical Implementation and Evaluation: The talk details a working prototype implemented by modifying the Linux kernel's DM-Crypt module and the Cryptsetup tool. Performance evaluations demonstrate its feasibility, albeit with trade-offs in throughput for hidden operations, and quantify its storage capacity.

Technical Deep Dive

▶ Watch: Invisiline's position against prior work (5:50)

INVISILINE's architecture builds upon and modifies the widely used Linux disk encryption framework, DM-Crypt, and its integrity counterpart, DM-Integrity. Both are device mapper targets, which are components within the Linux kernel's device mapper framework. This framework allows physical block devices (like hard drives) to be mapped to logical block devices, with each target providing specific functionalities (e.g., DM-Crypt for confidentiality, DM-Integrity for data integrity). These logical devices can be stacked, forming layers of services, with file systems mounted on top. The cryptsetup tool is commonly used to configure DM-Crypt and DM-Integrity.

A key aspect INVISILINE leverages is DM-Crypt's support for multiple IV modes, particularly the random IV mode. In this mode, whenever the file system requests to encrypt a sector, DM-Crypt generates a new, random 16-byte IV. This IV, along with the encrypted sector data, is then passed to the underlying DM-Integrity layer, which stores both the IV and the encrypted data on the physical disk. When data is read, DM-Integrity retrieves the IV and encrypted data, DM-Crypt decrypts it, and the cleartext is returned to the file system.

The standard disk layout under DM-Crypt with DM-Integrity separates physical sectors into data sectors (holding the actual encrypted public data) and metadata sectors (holding the IVs corresponding to the data sectors).

INVISILINE introduces an additional software component, DM-Crypt hidden, which integrates directly into the DM-Crypt module. This module is responsible for managing the hidden data. Crucially, INVISILINE also exposes an additional logical block device, the hidden block device, alongside the standard public block device. This allows users to mount two separate file systems on the same physical block device: one for public data and one for hidden data.

The core mechanism for hiding data is embedding it within the 16-byte IVs of public sectors. Since the IVs are small, a single logical hidden sector (typically 512 bytes) cannot fit into one IV. Given a 16-byte IV, and assuming the entire IV is available for hidden data, it would take 32 IVs (512 / 16 = 32) to store one logical hidden sector. This ratio is termed the storage factor.

However, this setup introduces several challenges that INVISILINE must address to maintain plausible deniability, especially against multi-snapshot adversaries:

1. Hidden Data Non-Interference: If a public sector's IV contains hidden data, and a new public write occurs to that sector, DM-Crypt would generate a new random IV, overwriting the hidden data. INVISILINE must prevent this or manage it.
2. Security Non-Interference: Reusing an IV, even if it contains hidden data, for a new encryption of public data is a bad security practice as it can lead to cryptographic vulnerabilities. INVISILINE ensures that IVs are not reused for public data encryption.
3. Explainable Re-Encryption: If hidden data within an IV is updated, simply updating the IV and re-encrypting the same public data would be suspicious to a multi-snapshot adversary. Such an adversary would observe that the public data hasn't changed, but its IV has, which is inconsistent with normal DM-Crypt behavior (where IVs change only when data changes or is re-encrypted). Therefore, any update to hidden data must be plausibly explained as an update to the public data in the corresponding sector. This means that hidden data updates need to be "piggybacked" on public data writes.

To manage these properties and enable dynamic mapping of logical hidden sectors to physical sectors (since static mapping would be easily detectable by multi-snapshot adversaries), INVISILINE employs several mechanisms:

• Free List: A list that tracks all modified public sectors within a session, identifying where future hidden data can be stored.
• Version Number: Each logical hidden sector has a version number, incremented on every hidden data update, to ensure retrieval of the latest version.
• Public Write Counter (PWC): Associated with hidden data, this counter increments on every public write to the sector whose IV contains the latest hidden data. This helps correlate hidden data updates with plausible public activity.

A critical design choice for mapping logical hidden sectors to physical sectors is the use of a reverse map. Storing a traditional translation table at a fixed offset on disk would be a clear giveaway, as its content would frequently change with hidden data updates. Instead, INVISILINE stores the logical hidden sector number directly along with the hidden data within the IV. During startup, INVISILINE scans all metadata sectors, extracts these logical hidden sector numbers and their corresponding physical sector locations, and builds the translation table in memory. Version numbers are used to ensure only the most current mappings are stored.

This overhead (logical hidden sector number, version number, PWC, etc.) means that not all 16 bytes of the IV can be used for hidden data. Consequently, the storage factor increases from 32 to 52, meaning 52 public sector IVs are needed to store one logical hidden sector.

For single-snapshot adversaries, INVISILINE offers an optimized mode called invis-single. Since these adversaries cannot compare multiple snapshots, the need for dynamic mapping, free lists, and complex translation tables is eliminated. invis-single can statically map logical hidden sectors to physical sectors (e.g., logical hidden sector I maps to physical sectors I*F to (I+1)*F, where F is the storage factor). This simplification results in a reduced storage factor and significantly faster performance compared to the full INVISILINE system.

Demo / Proof of Concept

▶ Watch: Invisiline's core idea: Hiding data in IVs (6:30)

The talk describes a working implementation of INVISILINE and invis-single as a proof of concept. The core changes were made to the Linux kernel 5.19, specifically targeting the DM-Crypt module. Additionally, modifications were made to the Cryptsetup tool to enable the configuration and management of INVISILINE's hidden block device and associated functionalities.

The evaluation environment consisted of a machine with an Intel Core i7 processor, six cores, and 16GB of RAM. Performance metrics were captured using flexible IO tester (FIO), a standard benchmarking tool for disk I/O. The experiments focused on measuring throughput for both sequential and random workloads, comparing INVISILINE and invis-single against vanilla DM-Crypt.

Key performance observations:

• Public Reads: Throughput for public reads with INVISILINE was "almost similar" to that of vanilla DM-Crypt. This is expected, as reading public data does not introduce significant additional overheads for INVISILINE.
• Public Writes: Public writes with INVISILINE were "comparatively slower" than vanilla DM-Crypt. This overhead stems from INVISILINE's need to check if a sector's IV already holds hidden data before generating a new random IV, and to manage the free list and other internal states.
• Hidden Operations: Operations on hidden data were "much slower" than public operations. This is directly attributable to the storage factor of 52, meaning that a single logical hidden sector operation requires interaction with 52 physical public sectors' IVs.
• invis-single Performance: As anticipated, invis-single was "much faster than INVISILINE." This performance gain is due to the simplified architecture, which eliminates the need for dynamic mapping, translation tables, and free lists, making hidden data operations more direct.

In terms of capacity, INVISILINE allows storing approximately 19 GB of hidden data on a 1 TB disk. The source code for INVISILINE is made publicly available, encouraging further research and auditing.

Defensive Implications

▶ Watch: DM-Crypt random IV mode explained (8:10)

INVISILINE presents a significant challenge to conventional digital forensics and defensive strategies. For a defender (e.g., law enforcement, corporate security), the existence of a system like INVISILINE means that the absence of overt signs of hidden data can no longer be taken as proof that no hidden data exists. The very goal of INVISILINE is to make it impossible for an adversary to prove the user is hiding sensitive information, even when they are.

Traditional forensic techniques often rely on:

1. Signature Analysis: Scanning for specific file headers, encryption volume signatures, or known patterns of hidden containers. INVISILINE avoids this by embedding data within standard DM-Crypt IVs, which appear as random bytes.
2. Disk Layout Anomaly Detection: Identifying unusual partitions, unallocated space used for hidden data, or non-standard metadata structures. INVISILINE explicitly maintains a standard DM-Crypt disk layout, with no additional metadata visible on disk.
3. Software Presence Detection: Identifying the installation of known PD software. INVISILINE is designed such that public data operations do not require its presence, and its uninstallation leaves behind a vanilla DM-Crypt setup, making its prior use difficult to prove.
4. Temporal Analysis (for multi-snapshot adversaries): Comparing disk snapshots over time to detect changes inconsistent with known system activity. INVISILINE's sophisticated handling of IVs, version numbers, and public write counters ensures that hidden data updates are always plausibly linked to public data activity, making such temporal analysis ineffective for proving deniability.

The implication for defenders is a shift from seeking to find hidden data to the much more difficult task of attempting to prove its absence. This is a fundamental challenge in computer science and law. In a legal context, if an adversary cannot definitively prove the existence of hidden data, then coercion to reveal keys for an allegedly "hidden" volume becomes moot, or at least significantly harder to enforce.

Defenders need to be aware that relying solely on standard disk encryption or the absence of obvious hidden volumes is insufficient against sophisticated adversaries using systems like INVISILINE. This work highlights the continuous arms race in digital security and privacy, pushing the boundaries of what is forensically detectable. It underscores the need for new investigative techniques that can grapple with the inherent ambiguity introduced by advanced plausible deniability systems, potentially leading to a re-evaluation of legal frameworks that mandate data disclosure without absolute proof of its existence.

Key Takeaways

• Encryption Alone is Insufficient: Traditional data encryption offers no protection against "rubber hose attacks" or legal coercion where users are forced to reveal decryption keys.
• Plausible Deniability (PD) Requires Invisibility: To be effective against sophisticated adversaries (including those who question the mere presence of PD software), a PD system must be "invisible," meaning it does not betray its existence through unusual disk layouts, metadata, or software requirements for public data.
• INVISILINE Achieves Invisible PD without Media Dependencies: It's the first system to offer both multi-snapshot adversary resistance and invisibility without requiring modifications to the Flash Translation Layer (FTL) or other media-specific components.
• Hidden Data is Stored in DM-Crypt IVs: INVISILINE leverages the standard DM-Crypt random IV mode by embedding hidden data within the 16-byte IVs of public data sectors, making it indistinguishable from legitimate randomness.
• Sophisticated Mechanisms for Multi-Snapshot Resistance: To counter adversaries comparing multiple disk snapshots, INVISILINE uses a "reverse map" (storing logical hidden sector numbers in IVs), version numbers, and public write counters, ensuring hidden data updates are always plausibly linked to public data activity.
• Performance Trade-offs Exist, with an Optimized Mode: While full INVISILINE introduces overheads (e.g., 4.5 Mbps throughput for hidden data, 19 GB capacity on a 1 TB disk), invis-single offers a faster, simpler alternative for single-snapshot adversaries.

About the Speaker(s)

The primary speaker for this presentation is Sandeep Kiran Pinjala, a PhD student at Stony Brook University. His work on INVISILINE represents a significant contribution to the field of plausible deniability and data privacy.

He is joined in this research by his collaborators:

• Professor Bogdan Carbunar from Florida International University.
• Anrin Chakraborti from UIC.
• Professor Radu Sion, Sandeep Kiran Pinjala's advisor at Stony Brook University.

Their combined expertise in cryptography, systems security, and privacy research has culminated in the development of INVISILINE, addressing a long-standing challenge in protecting sensitive data from coercive adversaries.