You are looking at a specific version 20190520:125105 of this paper. See the latest version.

Paper 2019/506

Forward Integrity and Crash Recovery for Secure Logs

Erik-Oliver Blass and Guevara Noubir

Abstract

Logging is a key mechanism in the security of computer systems. Beyond supporting important forward security properties, it is critical that logging withstands both failures and intentional tampering to prevent subtle attacks leaving the system in an inconsistent state with inconclusive evidence. We propose new techniques combining forward integrity with crash recovery for secure data storage. Our main contribution is a new coding scheme resolving unique design constraints such as forward integrity and most importantly a {single-pass, constant number} of operations per encoding. Our idea is to add a new log item by XORing it to forward-securely selected $k$ cells of a table. If up to a certain threshold of cells is modified by the adversary, or lost due to a crash, we still guarantee the recovery of all stored log items. We instantiate our scheme into an abstract data structure which allows to either detect adversarial modifications to log items or treat modifications like data loss in a system crash. The data structure can recover lost log items, thereby effectively reverting adversarial modifications. The key advantage of this setup is its efficiency: we use spectral graph theory techniques to prove that $k$ is {constant} in the number $n$ of all log items ever stored and small in practice, e.g., $k=5$. Moreover, we prove that to cope with up to $\sqrt{n}$ lost log items, storage expansion is asymptotically constant in $n$ and small in practice. For $k=5$, the total size of the table is only $12\%$ more than the simple concatenation of all $n$ items.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
erik-oliver blass @ airbus com
History
2024-01-17: last of 4 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/506
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.