Paper 2013/397

Practical Secure Logging: Seekable Sequential Key Generators

Giorgia Azzurra Marson and Bertram Poettering


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. A preliminary version of this paper appears in the proceedings of ESORICS 2013. This is the full version.
secure loggingforward securityseekabilityshortcut permutation
Contact author(s)
bertram poettering @ rhul ac uk
2013-06-18: received
Short URL
Creative Commons Attribution


      author = {Giorgia Azzurra Marson and Bertram Poettering},
      title = {Practical Secure Logging: Seekable Sequential Key Generators},
      howpublished = {Cryptology ePrint Archive, Paper 2013/397},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.