Cryptology ePrint Archive: Report 2013/397

Practical Secure Logging: Seekable Sequential Key Generators

Giorgia Azzurra Marson and Bertram Poettering

Abstract: In computer forensics, log files are indispensable resources that support auditors in identifying and understanding system threats and security breaches. If such logs are recorded locally, i.e., stored on the monitored machine itself, the problem of log authentication arises: if a system intrusion takes place, the intruder might be able to manipulate the log entries and cover her traces. Mechanisms that cryptographically protect collected log messages from manipulation should ideally have two properties: they should be *forward-secure* (the adversary gets no advantage from learning current keys when aiming at forging past log entries), and they should be *seekable* (the auditor can verify the integrity of log entries in any order or access pattern, at virtually no computational cost).

We propose a new cryptographic primitive, a *seekable sequential key generator* (SSKG), that combines these two properties and has direct application in secure logging. We rigorously formalize the required security properties and give a provably-secure construction based on the integer factorization problem. We further optimize the scheme in various ways, preparing it for real-world deployment. As a byproduct, we develop the notion of a *shortcut one-way permutation* (SCP), which might be of independent interest.

Our work is highly relevant in practice. Indeed, our SSKG implementation has become part of the logging service of the systemd system manager, a core component of many modern commercial Linux-based operating systems.

Category / Keywords: secret-key cryptography / secure logging, forward security, seekability, shortcut permutation

Publication Info: A preliminary version of this paper appears in the proceedings of ESORICS 2013. This is the full version.

Date: received 17 Jun 2013

Contact author: bertram poettering at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20130618:091941 (All versions of this report)

Short URL: ia.cr/2013/397

Discussion forum: Show discussion | Start new discussion