Feistel-based Shuffling for Enhancing Security in LSM Storage Systems

Abstract

Modern Log-Structured Merged-tree (LSM) based key-value stores achieve high performance through sequential writes and structured data organization, but this design implicitly exposes rich side-channel information at the storage layer. Even in the presence of encryption, adversaries can exploit observable artifacts, such as data placement regularity, update propagation, and inter-level transformations, to infer sensitive properties of the underlying workload. These leakages arise not from data content, but from the tight coupling between logical semantics and physical layout. We address this problem by introducing a lightweight, permutation-based obfuscation layer that randomizes data placement while preserving efficient query semantics. Our design leverages a four-round Feistel-based pseudo-random permutation, which provides strong PRP security by the Luby-Rackoff theorem to construct a keyed, invertible mapping without maintaining auxiliary mapping tables, while ensuring that storage-level representations are difficult to correlate with logical data semantics. Rather than applying randomization at a single stage, we embed the permutation mechanism throughout the data life-cycle. We further explore design variants that control the granularity and frequency of permutation to balance security guarantees with system overhead. We implement a C++ prototype and conduct controlled micro-benchmarks to evaluate the performance impact of the proposed mechanism. Results show that key transformation and block-level shuffling introduce less than 1% overhead in average operation latency for insertions, lookups, deletions, and compaction. We further provide a qualitative security analysis showing that the design eliminates key-order preservation and disrupts insertion-order locality in the storage layout. These findings suggest that Feistel-based shuffling is a lightweight and practical complement to existing encryption-based defenses for LSM-based systems.