Integrity checking in cryptographic file systems with constant trusted storage
Alina Oprea, Michael K. Reiter · 2007
In this paper we propose two new constructions for pro-tecting the integrity of files in cryptographic file systems. Our constructions are designed to exploit two charac-teristics of many file-system workloads, namely low en-tropy of file contents and high sequentiality of file block writes. At the same time, our approaches maintain the best features of the most commonly used algorithm to-day (Merkle trees), including defense against replay of stale (previously overwritten) blocks and a small, con-stant amount of trusted storage per file. Via implementa-tions in the EncFS cryptographic file system, we evalu-ate the performance and storage requirements of our new constructions compared to those of Merkle trees. We conclude with guidelines for choosing the best integrity algorithm depending on typical application workload. 1