Space-Efficient Block Storage Integrity
We present new methods to provide block-level integrity in encrypted storage systems, i.e., so that a client will detect the modification of data blocks by an untrusted storage server. We present cryptographic definitions for this setting, and develop solutions that change neither the block size nor the number of sectors accessed, an important consideration for modern storage systems. In order to achieve this, a trusted client component maintains state with which it can authenticate blocks returned by the storage server, and we explore techniques for minimizing the size of this state. We demonstrate a scheme that provably implements basic block integrity (informally, that any block accepted was previously written), that exhibits a tradeoff between the level of security and the additional client's storage overhead, and that in empirical evaluations requires an average of only 0.01 bytes per 1024-byte block. We extend this to a scheme that implements integrity resistant to replay attacks (informally, that any block accepted was the last block written to that address) using only 1.82 bytes per block, on average, in our one-month long empirical tests.
