Tamper-evident audit logs: how they work and how to build one
"Tamper-evident" appears on a lot of logging products. For an audit log it should mean something specific: if someone changes the log, a person who didn't make the change can detect it later. It doesn't mean the change is impossible. That would be tamper-proof, and no log stored on a computer someone controls can promise that.
Detection relies on several separate mechanisms. Each one answers its own question, and a log can have one without the others.
The hash chain
Each record stores the hash of the record before it. Change a record and its hash changes, so the next record's link stops matching. Remove a record from the middle and the link to the next one breaks. Reorder records and both the links and the sequence numbers go wrong.
header 1 <-- prev_hash -- header 2 <-- prev_hash -- header 3 = head
| | |
digest(body 1) digest(body 2) digest(body 3)
The check itself is short. Here's a toy version in Python. It isn't the PALA-1 wire format, only the idea:
import hashlib
def verify(records):
prev = bytes(32) # the first record points at zeros
for r in records:
if r["prev_hash"] != prev:
return None # a link is broken here
if hashlib.sha256(r["body"]).digest() != r["body_digest"]:
return None # the body no longer matches its header
prev = hashlib.sha256(r["header"]).digest()
return prev # the head, to compare with the anchor
A chain answers the question "was anything inside this file altered?" Anyone with the file and the specification can check it, and the check needs no key. In PALA-1 the record bodies can even stay encrypted during the check, because each header carries a digest of its body. That part is explained in how to check an AI log without reading it.
The anchor
A chain has one blind spot. If the last records are deleted, what remains is still a valid chain, only shorter. The same is true when a whole file is swapped for another consistent chain.
To catch that, the latest hash has to be kept somewhere else, such as a separate file, the operating system's keychain or a hardware token. That copy is the anchor. Checking the chain against it answers a second question: "is this the whole log?" An anchor only helps if whoever could rewrite the log can't rewrite the anchor as well. That's why a hardware token is stronger than a file on the same disk.
The witness
The third question is about time. Did this history exist before a certain moment? Nothing inside the log can prove it, because whoever controls the log also controls its clock. Someone outside has to sign a statement.
In Palimpsests that witness can be a SCITT transparency service. Palimpsests registers one signed statement per published head. The statement holds a hash and no record content. The receipt shows that the head existed by the time it was registered, and since a head commits to every record before it, so did those records.
Proofs that travel
Two more tools help when you can't hand over the whole log. An inclusion proof shows that a particular record belongs to a tree whose root you already trust, using a handful of hashes. A consistency proof shows that an older head is a prefix of a newer one, so the log only ever grew. Both use the same construction as Certificate Transparency (RFC 6962 and RFC 9162).
Deletion that explains itself
Logs can't grow forever. Retention rules say how long records stay, and after that they're deleted. In a hash chain, deleting the oldest records leaves a gap at the start, and a gap normally looks like tampering.
Since version 0.13, Palimpsests opens each new segment with a continuation record. It names the previous segment's last hash and the retention period that applied, and it commits to every earlier record. When old segments are removed under that policy, the rest of the log still explains where its beginning went. The standards background for this is in AI logging standards in draft.
How to make an audit log tamper-evident
Put together, the pieces above make a short list for building a tamper-evident audit log. Which items you need depends on what you'll have to prove later:
- give every record a sequence number and the hash of the record before it;
- keep a digest of each record's content in its header, so the log can be checked without being read;
- store the latest hash somewhere the writer can't quietly change, such as a separate file or a hardware token, and check the log against it;
- when you need to show when the log existed, have an outside party sign the head from time to time;
- write retention into the log itself, so deleted segments are declared rather than simply missing;
- publish the format and test it with a verifier someone else wrote.
Other approaches
Hash chains aren't the only way to do this. Signed syslog (RFC 5848) signs batches of messages. The systemd journal can seal its files with forward-secure keys, so an attacker who takes over a machine can't rewrite what was sealed before. Some storage systems simply refuse to change data once it's written. Each of these puts the trust somewhere different: in a signing key, a sealing key or a storage vendor. For any of them it's worth asking who you have to trust, and whether that's the same party you're worried about.
Questions to ask before trusting the claim
- Can someone outside the team check the log with a published specification, without your software?
- Does the check need the decryption key, or can it run without reading the content?
- What does the check report when it has no anchor? It should say completeness wasn't checked.
- Where is the anchor kept, and who can change it?
- What happens to the log when old records are deleted?
- What isn't covered? A tamper-evident log shows the record wasn't changed. It doesn't show the recorded events were true.
Further reading
The ideas here are older than AI agents. Bruce Schneier and John Kelsey described hash-chained audit logs on untrusted machines in "Secure Audit Logs to Support Computer Forensics" (ACM Transactions on Information and System Security, 1999). Scott Crosby and Dan Wallach showed how to make such logs efficient to audit in "Efficient Data Structures for Tamper-Evident Logging" (USENIX Security, 2009). Certificate Transparency put Merkle-tree logs into wide use, specified in RFC 6962 and RFC 9162. Signed syslog is RFC 5848.
The format behind all of this is PALA-1. The reasoning behind its design is in three design principles for verifiable audit logs.