Crypto-Erasure in Hash-Linked Audit Logs: Guarantees and Their Limits

#Abstract

An append-only hash-linked audit log and a statutory right to erasure are incompatible in their naive forms. This report describes resolving the conflict by encrypting personal data under per-subject keys held outside the log, so that destroying a key renders the plaintext unrecoverable while the chain continues to verify. The resulting guarantee is bounded by three conditions, each of which is stated, and one of which cannot be enforced by the library at all. No formal adversary model is given.

#Why the log is chained

An audit log an administrator can modify is not evidence. Where the credentials that perform an action can also remove its record, the log answers no question of interest.

Linking each entry to its predecessor by a cryptographic hash makes modification detectable. The technique originates in digital timestamping [1] and in hash tree constructions [2], and secure audit log designs have addressed a compromising adversary directly [3].

The property obtained is detection rather than prevention. Nothing prevents a party with storage access from writing to storage. What changes is that concealment requires rewriting every subsequent entry and any externally published chain head.

#The conflict

The right to erasure entitles a data subject to have personal data concerning them removed [4]. The log's design property is that nothing is removed. These cannot both hold over the same bytes.

#Construction

Personal data within an entry is encrypted under a key associated with that data subject. The entry stored in the log is ciphertext, and the key is held in separate storage with its own access control.

Because the hash covers the ciphertext rather than the plaintext, destroying the key leaves every hash unchanged and the chain verifiable end to end, while the plaintext becomes unrecoverable by any party including the operator.

The key is deleted, not the record. The trail retains its integrity and the data subject obtains an outcome that is, in practice, indistinguishable from deletion.

#What an external verifier can check

Tamper evidence is only worth something if somebody outside the operator can act on it, and a chain that only the operator verifies proves nothing to anyone else, since the operator could recompute it after a rewrite. Three things are therefore needed beyond the chain itself.

The chain head is published periodically to a location the operator cannot retroactively alter. Once a head is published, every entry preceding it is fixed, because changing any of them changes that head. This is the same reasoning that underpins timestamping [1] and is what turns an internal integrity check into an external commitment.

The verifier needs the entry format and the hash algorithm identifier, both of which are in the entry rather than in documentation, so that verification does not depend on the operator's cooperation beyond handing over the log.

And the verifier must be able to check a chain containing entries whose keys have been destroyed. This falls out of the construction rather than needing anything extra: the hash covers ciphertext, and an erased entry's ciphertext is still present and still hashes to the same value. A verifier can confirm the log is intact without being able to read the personal data in it, which is the property that makes the scheme usable at all, since otherwise verification and erasure would be in conflict for the same reason the original problem was.

What no verifier can check is completeness. The chain proves that the entries present have not been altered. It does not prove that an action which should have produced an entry did produce one, because an action never logged leaves no gap. That is a limitation of the technique rather than of this implementation, and it means the log answers "was this record changed" and not "is this record of everything".

#Three bounding conditions

Key destruction must be complete. The entire guarantee rests on the key being irrecoverable everywhere it existed, including backups of the key store, which is precisely where keys survive unnoticed. Sanitisation guidance exists because deleted and unrecoverable are distinct states [5]. A library can guarantee its own behaviour and cannot guarantee that an operator's key management system lacks a soft-delete window, which makes this the weakest link and one outside the system's control.

Metadata remains in the clear. Timestamps, actor identifiers, resource types and action names must remain readable, because a log that cannot be queried serves no purpose. The fact that a subject performed an action at a time therefore survives erasure. Whether that residue is itself personal data depends on the data and is a legal determination rather than a technical one.

Hash algorithms have finite lifetimes. A chain constructed today may require verification decades hence. The format carries an algorithm identifier permitting a successor chain, and the earlier segment remains verifiable only under its original algorithm.

#Key lifecycle

The construction relocates the hard problem into key management, so the key lifecycle deserves stating rather than being left as an exercise. Four transitions matter.

Derivation. A subject key is derived on first write concerning that subject, not provisioned in advance, since provisioning in advance requires knowing the subject population and the population is what the log is discovering.

Rotation. Rotating a subject key requires re-encrypting that subject's entries, which changes their ciphertext and therefore breaks every subsequent hash. The implementation does not rotate subject keys for this reason. Rotation is available only through the algorithm-successor mechanism described above, which starts a new chain segment. This is a real constraint and it runs against ordinary key management practice [6], where long-lived keys are exactly what one avoids.

Destruction. Erasure destroys the subject key. The operation must reach every copy, which is the first bounding condition and is discussed above.

Escrow, deliberately absent. No recovery mechanism exists for a destroyed subject key. An escrow would make erasure reversible, which would defeat the purpose, and the absence means an accidental destruction is unrecoverable. That risk is accepted rather than mitigated, and it should be stated to operators plainly, because a key management system with no recovery path is unusual enough that people assume one exists.

#Threat model, stated informally

No formal adversary model is given, and it would be better if one were. What follows is the informal model the design was built against, offered so that its gaps are visible rather than implied.

The adversary of interest is an insider with administrative access to the application and to the log storage, who has performed an action and wishes to conceal it. Against that adversary the construction is effective: concealment requires rewriting every subsequent entry, and any published chain head that covers the entry makes the rewrite detectable by anyone holding that head.

The adversary the construction does not resist is one with unified control of both the log storage and the key store, before publication of a covering head. Such a party can rewrite the chain and recompute it, and nothing internal to the system distinguishes the result from an honest log. The separation of the two stores is therefore not a defence in depth measure but a load-bearing assumption, and a deployment that puts both under the same credentials has the mechanism without the property.

A third case is a party who has already read the plaintext before erasure. Erasure destroys the key, not the reader's memory or their copy. This is inherent to erasure of any kind, and it is worth stating because "unrecoverable by any party including the operator" is true of the log and not of the world.

What a formal treatment would add is a precise statement of the forward integrity property, in the sense that entries written before a compromise remain trustworthy after it [7], and a proof that the erasure operation preserves it. That has not been done here.

#Related constructions

Tamper-evident logging has a substantial literature. Designs addressing an adversary who compromises the logging machine itself are the direct ancestor of this work [3], and history-tree structures give efficient membership and consistency proofs rather than requiring a verifier to walk the whole chain [8]. Certificate Transparency is the same idea deployed at scale, with public logs, published heads and independent auditors [9], and its operational lesson is the one taken here: the value comes from the head being published somewhere the operator does not control.

The construction is far simpler than any of these. It uses a linear chain rather than a tree, so verification is linear in log length and there are no compact consistency proofs. For a per-tenant audit log of moderate size this is adequate and the simplicity is worth more than the asymptotics. For a log intended to be audited frequently by many parties it would not be, and a history tree would be the right structure.

On the erasure side, crypto-shredding is one of several techniques surveyed under secure deletion, and the survey's framing is useful: the guarantee always reduces to an assumption about what the adversary can reach [10]. Assured delete schemes that make deletion a property of key availability rather than of storage predate this application by some years [11]. Nothing here is novel as a cryptographic technique. The contribution, such as it is, lies in the specific composition with a chained audit log and in stating precisely which properties survive the composition.

#Design constraint that makes reporting possible

Entries have a fixed shape: actor, action, resource, outcome, scope and timestamp. Every subsequent request to add a free-form field has been declined. Economy of mechanism is the relevant principle [12], and the practical consequence is that a compliance report is a query rather than a text-mining exercise.

#An unanticipated effect

Once engineers trusted that the log could not have been silently modified, they began consulting it during incidents rather than reconstructing sequences from application logs. The log's value in ordinary operation exceeded its value at audit, which was not the reason it was built.

#Limitations

No formal adversary model is given, as set out above. The informal model names the assumption the construction depends on and does not prove anything about it.

Per-subject keys imply a key per subject, and the operational cost of that at scale, including the enumeration required to erase, is not evaluated here. Systems with very large subject populations may find the key management cost dominant, and no measurement is offered either way. The inability to rotate subject keys compounds this, since it means key lifetime equals log retention.

The residual metadata question is left to a legal determination and is treated here as though that determination were straightforward. It is not. Whether a record showing that a particular actor performed a particular action at a particular time constitutes personal data concerning that actor is exactly the sort of question on which reasonable authorities differ, and a technical design that depends on the answer should say so rather than treating it as somebody else's problem. The practical hedge, which this implementation does not take, would be to make actor identifiers themselves subject-keyed, at the cost of making the log unqueryable by actor without key access.

Finally, no measurement of verification cost is reported. A linear chain over a log of any size is verified by reading all of it, and how that behaves for a multi-year log has not been established.