(Edit: It seems that something like this has already been done by other people.)

This is an idea I've had for a while, I haven't implemented it yet though. This is a solution for the following problems:

The basic idea is this: Log entries are encrypted and signed, and whenever a log entry has been created, the logging process throws away the keys. A trusted administration device has a copy of the keys, so it can download the logs and verify and decrypt them.

Pre-generating and storing all those keys, although doable, would be somewhat ugly. Instead, the keys are generated using repeated hashing: keyi = hasha(keyi-1)
encryptionKeyi = hashb(keyi)
To make a new log entry, you derive encryptionKeyi using the one-way function hashb and use it to encrypt and sign the new log entry using an appropriate symmetric-crypto algorithm. Then you calculate keyi+1 using the one-way function hasha, store it and securely erase encryptionKeyi and keyi. hasha and hashb would in practice probably be the same hash functions with different input prefixes.

To initialize the system, key0 has to be generated, stored on the trusted administration device and fed to the logging process as the initial keyi. Later, on the next connection, the trusted device can download the logs and decrypt and verify them. An attacker can capture the keyi at the time of his intrusion, so he can manipulate the log from then on as he wishes, but he can't manipulate past logs without making the intrusion obvious. Unless an attacker doesn't care about stealth, he won't do that. To prevent the attacker from simply truncating the log and never writing anything to it again until the keys are rotated or so, the trusted device could e.g. verify that its own access is logged.

A problem with this is that, if you want this to work across unexpected power failures, you need to write the new key to disk, erase the old one and force a cache flush whenever a new log entry needs to be committed. Also, the old key must not remain in userspace memory, kernel memory (filesystem caches or so), drive firmware and so on. Another small disadvantage is that you won't have random access to the encrypted log, only linear access, but you would only have to decrypt it once and store the unencrypted copy on the admin device to get around that.

Send comments, improvements, ... to jann+logintegrity@thejh.net, please.