journald log hash chaining is broken

I promised to dig into some of the details of the journald announcement. One of the most hyped features is log hash chaining. Lennart describes this in his paper as follows (highlighting by me):

The Internet is a dangerous place. Break-ins on high-profile web sites have become very common. After a successful break-in the attacker usually attempts to hide his traces by editing the log files. Such manipulations are hard to detect with classic syslog: since the files are plain text files no cryptographic authentication is done, and changes are not tracked. Inspired by git, in the journal all entries are cryptographically hashed along with the hash of the previous entry in the file. This results in a chain of entries, where each entry authenticates all previous ones. If the top-most hash is regularly saved to a secure write-only location, the full chain is authenticated by it. Manipulations by the attacker can hence easily be detected.

For a moment, let’s assume he really means what he writes (I somewhat doubt that…). Then this is vaporware. You don’t get anything by providing a hash chain by itself. Let’s assume you have a log of 2,000 records. Now an attacker wants to remove record number 1,001 to 1,010. All he needs to do is seek to the proper location inside the (binary) file, and remove these 10 records, regenerating the hashes for record 1,011 to 2,000. Now let’s assume that you saved your initial hash to write only memory. First thing is that it probably is complicated to read the hash off from an unreadable location (write-only medium, mhhh ;)). Assuming you manage that, you can verify the whole log of now 1,990 records. You will not detect the missing records because the chain as such is perfectly well. This, by the way, is the main reason why I have not (yet) implemented such a simplistic method inside rsyslog.

This approach is “data sheet cryptography” at best. To do it right, you need some crypto experts. Bruce Schneier and John Kelsy have written a non-nonsene paper on securing computer audit logs (often called “Counterpane Paper”) in 1999. Note that John Kelsy and others have also written RFC5848, which describes how to securely sign syslog messages. This RFC went through numerous revisions and took a couple of years to complete. An interesting fact is that Albert Mietus reported the first implementation of syslog-sign (as RFC5848 was called these days) on EuroBSDCon in 2002! In his presentation “Securing Syslog on FreeBSD” he nicely describes what needs to be done.

I have not yet implemented this method in rsyslog because it has some serious issues when used in larger environments. When CEE discussed about signature chaining (note the difference to hash chaining!), I wrote a small paper about the issues with log signature chaining and remote logging. As I describe there, RFC5848 addresses only the less complex issues. This is not a failure of it’s authors, which for sure are real crypto experts – and me not. This is rooted in the fact that this is a very complex problem and a real good answer is still not known. As you can see, this is not something you can solve in with a few hours (or even days) of hacking.

Let me close with a quote from the journald paper: “The Internet is a dangerous place.”. And, indeed, it is. The most dangerous thing in my experience is a false sense of security. I guess black hats will *absolutely love* journald and its crypto stuff ;)

Update: Lennart’s non standard (for the logging comminity) use of the term top vs. bottom caused some confusion. Please be sure to read the comments attached to this posting. I probably need to blog about the issue again, but right now there are so many things going on. Again, read the comments, they have all information.