Tamper-Evident Logs
transparency.dev
transparency.dev
Secure logging with syslog-ng Forward integrity and confidentiality of system logs @ FOSDEM 2020[0].
I'm starting to become really suspicious of things being pushed as standards/new approaches/things-that-should-be-rfcs-but-have-a-marketing-budget. As other posts have pointed out, an RFC for this already exists, and all I can see is Google trying to make another gRPC where new engineers hear the term "gRPC" before they hear and/or take the time to understand HTTP/2.
> This document describes a mechanism to add origin authentication, message integrity, replay resistance, message sequencing, and detection of missing messages to the transmitted syslog messages. This specification is intended to be used in conjunction with the work defined in RFC 5424, "The Syslog Protocol".
(Though I admit, I have no idea how I'd even begin to start signing messages with JSON-lines.)
2009-05-03T14:00:39.529966+02:00 host.example.org syslogd 2138 - [ssign VER="0111" RSID="1" SG="0" SPRI="0" GBC="2" FMN="1" CNT="7" HB="K6wzcombEvKJ+UTMcn9bPryAeaU= zrkDcIeaDluypaPCY8WWzwHpPok= zgrWOdpx16ADc7UmckyIFY53icE= XfopJ+S8/hODapiBBCgVQaLqBKg= J67gKMFl/OauTC20ibbydwIlJC8= M5GziVgB6KPY3ERU1HXdSi2vtdw= Wxd/lU7uG/ipEYT9xeqnsfohyH0=" SIGN="AKBbX4J7QkrwuwdbV7Taujk2lvOf8gCgC62We1QYfnrNHz7FzAvdySuMyfM="]
You're trying to re-invent the wheel. Look at the prior art.
> [exampleSDID@32473 iut="3" eventSource="Application" eventID="1011"][examplePriority@32473 class="high"]
Or try out the CLI tool https://github.com/transparencylog/tl#installation
Not meant to be criticism, just feedback, as it would be ideal to have some sort of transparency mechanism in common use.
github.com/arianvp/kpop.sh
I'm happy to see my idea is not novel. That means I was on the right track :P
I don’t understand one part though. Because checking for log integrity is fairly obvious and easy to understand (merkle trees).
However, I don’t see how this creates a log that can’t be tampered with.
If you change a record in a log, you have to change all records following it, in order to preserve integrity of hashes, but if that record has been stored recently, that wouldn’t be terribly hard. So where’s the magic that make this impossible?
With bitcoin the magic is that mining hashes for a transaction block takes a lot of resources and the longest chain always wins.
Here I don’t see anything of this kind.
I'm definitely a layman as far as crypto is concerned, so take the above with a grain of salt. Looking for somebody more knowledgable about the topic to clear my confusion.
EDIT: Looking at https://transparency.dev/verifiable-data-structures/ there's the part `Clients must store a copy of tree head hashes`, so that partly solves the problem I suppose. But aren't the clients (who I understand have to consume all produced records in order to continuously recalculate the root hash) then ripe for tampering?
If it's append only, you should be able to find the old head in the log. Not sure if that is what it's going for though. I'm still a bit confused by this myself.
As you say, Merkle trees are fairly straight-forward, but beyond integrity checking a file they have some other nice properties - as the "operator" of a Merkle tree based log, you can efficiently [O(log N)] convince an observer that: - you've only grown the log by appending new entries since the last time they looked ("consistency proof") - a given entry they hold is indeed included in the log ("inclusion proof")
if you change an entry in the log (or claim something is in the log when it's not) it becomes impossible for you to prove both of those properties (unless you're powerful enough to also break what's called the "second pre-image resistance" of the cryptographic hash you're using).
Note that for these two properties, an observer doesn't need to download or inspect the full contents of the log, just a handful of hashes in the Merkle tree which they can then use to recreate the "tree head hash" you mentioned. These "tree heads" are the state they store and are just a few hundred bytes.
There are generally a few types of log client: - one type is putting things into the log - one type are wanting to use what's stored in the log to make a decision of some kind ("should I trust this site", "should I install this binary", "am I seeing the true history of events", etc.) and they won't trust that data unless they are convinced it is in the log - another can verify the accuracy/validity/goodness of things in the log (e.g. in CT it's the domain owner who is in the unique position of saying "yes, I asked for this cert to be created", for binaries it might be "I'm the authorised creator of these binaries and, yup, that was me" or "I'm a respectable malware scanning company, and this binary doesn't match any known signatures", "I'm an auditor and these transactions are complete and correct", etc. - you can probably think of many more examples!)
In this light, you can think of a tamper-evident log as being a sort of "reliable transport" to connect these different types of clients together, and importantly, where they all can prove to each other (using those light weight tree heads + consistency/inclusion proofs) that they're seeing the same set of data in the log - or, if they can't prove it - they have the cryptographic evidence of operator of the log operator having done something unexpected.
If you have a spare few mins, have a look at the Claimant Model docs here: https://github.com/google/trillian/tree/master/docs/claimant... which talks in a bit more detail about this "transport" idea and the concept of discoverability which it brings.
Hope that's helpful/interesting!
[Disclaimer: I work on CT, Trillian, and a bunch of other related projects.]
Especially this part is enlightening: In this light, you can think of a tamper-evident log as being a sort of "reliable transport" to connect these different types of clients together [...]
As it shows why my observation about possible tampering with clients isn't all that important.
While in theory, anyone publishing public information might find something like this useful, it's not clear there's much demand for it outside DNS. Something like Dolt [2] seems like it would better for publishing public datasets in a way that changes can be tracked?
[1] https://en.wikipedia.org/wiki/Certificate_Transparency [2] https://www.dolthub.com/
The target audience seems to be organizations with strict regulatory requirements who want to prove that data hasn't been tampered with since write. Useful for payment records, storing a log immutable events (patient 23 had an appointment today), stuff like that. The applications aren't endless, but they extend further than just DNS.
Conceptually, maybe not, given the history of Merkle trees and hash chains.
But examples of production code using these ideas are few and far between. That's still valuable.
Certificate transparency itself has been in production for a while. Apparently since 2013 and required for all certificates since 2018, according to Wikipedia.
Depending on how you define it, everyone who publishes source code using git is already using these ideas. It seems they are all Merkle trees?
I would guess this code would be most useful when the logs are pretty big. If you can download the whole dataset (like with git) and you are making manual edits and sending pull requests, then Dolt's approach sounds more user-friendly? You get a change history, and if upstream rebases then you will see it. (I haven't used them; I just read their blog.)
I agree that the presentation is a bit confusing. It feels as though the audience are in directorship/VP roles, but the .dev TLD is usually oriented towards folks in the trenches. I think the idea was to distinguish the general idea (tamper-evident logs) from the specific implementation (Trillian). I already knew about Trillian and found myself unsure as to whether it was about Trillian or not.
> Depending on how you define it, everyone who publishes source code using git is already using these ideas. It seems they are all Merkle trees?
Merkle trees have been around for a smidge over 40 years. I don't think their claim is to have invented a new data structure, but rather that they provide a smooth way to apply Merkle trees to log-structured and map-structured problems.
> If you can download the whole dataset (like with git) and you are making manual edits and sending pull requests, then Dolt's approach sounds more user-friendly? You get a change history, and if upstream rebases then you will see it.
The orientation to logs here suggests that they're not very interested in forking or merging. Added to which, there's no sense in which the subject of discourse is snapshots to which one can apply deltas to emit a successor snapshot.
I believe the idea is to ensure that a particular sequence of events occurred, that it occurred in a particular order, that no entries were inserted, deleted or modified without being detected. In git I believe the closest analogy would be the reflog.
A log tells you what happened. Or really, what events were successfully recorded, which might be different. But it's also common to want to know the result of a sequence of transactions on system state, and to be able to reconstruct that state at any point in time. (For example, there is a debate about when it makes sense to use Kafka as a database.)
So, someone deciding whether to use this might consider whether they just want to publish a tamper-evident log, or whether they are publishing something that looks more like a dataset with a temper-evident change history. A big factor in deciding that will be how large this dataset is likely to be and whether it's feasible and useful for the reader to download a complete copy of it, as we do with git repos.
You also have to consider the criteria for accepting events. This determines what data you need to query before accepting a transaction. The easy case is when all well-formed events are accepted, but for some problems, it makes sense to want more consistency. The reader might want to check consistency too.
The tamper-evident log is useful as an ancillary tool. You can write your keys or perhaps hashed records into the log and then use it later to see if the database has gained unlogged records or has lost logged records. And, if so, where in the sequence the deviation occurs.
I've used dumber versions in the past: hash chain fields on a single table, plus row signature. This approach has the nice property that it's very general and comes with proofs.
Basically, they're pitching using the underlying proven tech from Certificate Transparency (and Go modules) for other similar use cases. To that end, this shouldn't be anything new, beyond documentation / marketing: they want to say this is stable technology.
We're looking in more depth at other use cases, developing a better understanding of which types of problems this might be useful for, and ways to reason about the properties you want/get from using systems like this (e.g. https://github.com/google/trillian/tree/master/docs/claimant...)
[Disclaimer: I work on CT, Trillian, and some other related projects]
unless this new product happens to be run by a company that controls a prominent search ranking algorithm
Pretty graphics and lot of white space for not much meat.
Basically, looks like the command pattern implemented with signed token for every time you read, you must mutate the 'chain' or array of information. Am I close?
It took quite a bit of time to get there.
Command pattern is definitely one pattern we've seen these tamper-evident logs applied to; you can easily imagine a system where, say, config update "commands" are packaged off and written to a TE log, and then workers apply those commands to a system if and only if they are convinced that the commands were properly logged. If the admins/command-workers/auditors etc. can all prove they're looking at the same set of logged commands (which is the property that these tamper-evident logs are intended to provide), then you have a reliable and tamper-evident audit trail of all changes to your system.
There are a bunch of other scenarios we think these things might be useful for too, and we're trying to explore (and help others explore) these and provide mechanisms for reasoning about the properties of such systems.
[Disclaimer: I work on CT, Trillian, and other related projects]
Tip: call it LogOps and engage in an exercise-yard shiv-fight with GitOps folks.
I prefer to think of both as examples of WAL or intent logs. It's a useful pattern and it's nice to have a narrowly-focused tool for it.
I dont particularly agree with an obvious use of a merkle tree being patented in this way - but it is. Probably worthy of further research if you plan to use this.
Put another way: this patent may cover some specific applications of Merkle trees to natural numbers, but doesn't cover all sequential data structures. For most purposes "happened-at" or "happens-before" relations are plenty useful and don't require sequence numbers to establish the relation.
A similar data structure has been proposed as a cryptographic accumulator for the Bitcoin UTXO set: https://eprint.iacr.org/2019/611 (Although in this case, the "log" is not append-only; elements can be deleted.)
They are related, but not quite the same.
"Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something."
https://news.ycombinator.com/newsguidelines.html
You may have a good point, but for it to be a good comment you would need to drop the snark and engage more specifically with the details of the article. The odds, for example, that the authors don't know about or have thought about git are basically zero.
philips: please accept my apologies too. The last thing I want to be is snarky.
I refuse to use Google products for critical infrastructure until they prove they won't kill the product as soon as they lose interest to chase the next shiny trinket or maybe build their 78th chat app
Also, the website format is kinda weird. As I reach the bottom of the page, it looks like this is a promotional site for Trillian. Maybe the confusion comes from here. What is this site really about?