rsyslog’s first signature provider: why Guardtime?

The new has already spread: rsyslog 7.3 is the first version that natively supports log signatures, and does so via a newly introduced open signature provider interface. A lot of my followers quickly realized that and begun to play with it. To make sense of the provider interface, one obviously also needs a signature provider. I selected the keyless signature infrastructure (KSI), which is being engineered by the OpenKSI group. Quickly, I was asked what were the compelling reasons to provide the first signature provider for this technology.

So rather than writing many mails, I thought I blog about the reason ;)

We need to dig a little back in history to understand the decision. I looked at log signature a long time ago, I think my interest started around 2001 or 2002, as part of the IETF syslog standardization efforts. I have to admit that at this time there was very limited public interest in signed logs, even though without signatures it is somewhat hard to prove the correctness of log records. Still, many folks successfully argued that they could proof their process was secure, and that proof seemed to be sufficient, at least at that time.

A core problem with log record signatures is that a single log record is relatively small, typically between 60 bytes and 2k, with typical Linux logs being between 60 and 120 bytes. This makes it almost impossible to sign a single log record, as the signature itself is much larger. Also, while a per-record signature can proof the validity of the log record, it cannot proof that the log file as such is complete. This second problem can be solved by a method that is called “log chaining“, where each of the log records is hashed and the previous hash is also used as input for hashing the current record. That way, removing or inserting a log record will break the hash chain, and so tampering can be detected (of course, tampering within a log record can also be easily detected, as it obviously will invalidate the chain as well).

This method is actually not brand new technology but ages old. While it sounds perfect, there are some subtle issues when it comes to logging. First and foremost, we have a problem when the machine that stores the log data itself is being compromised. For the method to work, that machine must both create the hashes and sign them. To do so, it must have knowledge of the secrets being used in that process. Now remember from your crypto education that any secrets-based crypto system (even PKI) is only secure as long as the secrets have not been compromised. Unfortunately, if the loghost itself has been compromised, that precondition does not hold any longer. If someone got root-level access, he or she also has access to the secrets (otherwise the signature process could also not access them, right?).

You may now try as hard as you like, but if everything is kept on the local machine, a successful attacker can always tamper the logs and re-hash and re-sign them. You can only win some advantage if you ship part of the integrity proof off the local system – as long as you assume that not all of the final destinations are compromised (usually a fair assumption, but sometimes questionable if everything is within the same administrative domain).

The traditional approach in logging is that log records are being shipped off the machine. In IETF efforts we concentrated on that process and on the ability to sign records right at the originator. This ultimately resulted in RFC 5848, “signed syslog messages”, which provides the necessary plumbing to do that. A bit later, at Mitre’s CEE effort, we faced the same problem and discussed a similar solution. Unfortunately, there is a problem with that approach: in the real-world, in larger enterprises, we usually do not have a single log stream, where each record is forwarded to some final destinations. Almost always, interim relays filter messages, discard some (e.g. noise events) and transform others. The end result is that a verification of the log stream residing at the central loghost will always fail. Note that this is not caused by failure in the crypto method used – it’s a result of operational needs and typical deployments. Those interested in the fine details may have a look at the log hash chaining paper I wrote as an aid during CEE discussions. In that paper, I proposed as an alternative method that just the central log host signs the records. Of course, this still had the problem of central host compromise.

Let me sum up the concerns on log signatures:

  • signing single log records is practically impossible
  • relay chains make it exceptionally hard to sign at the log originator and verify at the central log store destination
  • any signature mechanism based on locally-stored secrets can be broken by a sufficiently well-done attack.

These were essentially the points that made me stay away from doing log signatures at all. As I had explained multiple times in the past, that would just create a false sense of security.

The state of all the changed a bit after the systemd journal was pushed into existence with the promise that it would provide strong log integrity features and even prevent attacks. There was a lot of vaporware associated with that announcement, but it was very interesting to see how many people really got excited about it. While I clearly described at that time how easy the system was to break, people begun to praise it so much that I quickly developed LogTools, which provided exactly the same thing. The core problem was that both of them were just basic log hash chains, and offered a serious amount of false sense of security (but people seemed to feel pampered by that…).

My initial plan was to tightly integrate the LogTools technology into rsyslog, but my seriousness and my concerns about such a bad security took over and I (thankfully) hesitated to actually do that.

At this point of the writing credits are due to the systemd journal folks: they have upgraded their system to a much more secure method, which they call forward secure sealing. I haven’t analyzed it in depth yet, but it sounds like it provides good features. It’s a very new method, though, and security folks for a good reason tend to stick to proven methods if there is no very strong argument to avoid them (after all, crypto is extremely hard, and new methods require a lot of peer review, as do new implementations).

That was the state of affairs at the end of last year. Thankfully I was approached by an engineer from Guardtime, a company that I learned is deeply involved in the OpenKSI approach.  He told me about the technology and asked if I would be interested in providing signatures directly in rsyslog. They seemed to have some experience with signing log files and had some instructions and tools available on their web site as well as obviously some folks who actually used that.

I have to admit that I wasn’t too excited at that time and very busy with other projects. Anyhow, after the Fedora Developer Conference in February 2013 I took the time to have a somewhat deeper look at the technology – and it looked very interesting. It uses log chains, but in a smart way. Instead of using simple chains, it uses so-called Merkle trees, a data structure that was originally designed for the purpose of signing many documents very efficiently. They were invented back in the 1970’s and are obviously a quite proven technology. An interesting fact about the way Merkle trees are used in the OpenKSI approach is that they permit to extract a subset of log information and still prove that this information is valid. This is a very interesting property when you need to present logs as evidence to the court but do not want to disclose unrelated log entries.

While all of this is interesting, the key feature that attract my interest is the “keyless” inside the KSI name. If there is no key, an attacker can obviously not compromise it. But how will signing without a key work? I admit that at first I had a hard time understanding that, but the folks at Guardtime were very helpful in explaining how it works (and had a lot of patience with me ;)). Let me try to explain in a nutshell (and with a lot of inaccuracies):

The base idea goes back to the Merkle tree, but we can go even more basic and think of a simple hash chain. Remember that each hash is depending on its predecessor and the actual data to be hashed. If you now create a kind of global hash chain where you submit everything you ever need to “sign”, this can form a chain in itself. Now say you have a document (or log) x that you want to sign. You submit x to the chaining process and receive back a hash value h. Now you store that h, and use it as a signature, a proof of integrity of x. Now assume that there is a way that you give out x and h and someone can verify that x participated in the computation of the “global” log chain. If so, and if x’s hash stil matches the value that was used to generate h, than x is obviously untampered. If we further assume that there is a fixed schedule on which some “anchor hashes” are being produced, and assume that we can track to which such anchor hash h belongs to, we can even deduce at what time x was signed. In essence, this is what Guardtime does. They operate the server infrastructure that does this hashing and timestmaping. The key hashes are generated once a second, so each signature can be tracked very precisely to the time it was generated. This is called “linked timestamping” and for a much better description than I have given just follow that link ;)

The key property from my PoV is that with this method, no secrets are required to sign log records. And if there is no secret, an attacker can obviously not take advantage of the secret to hide his tracks. So this method actually provides a very good integrity proof and does not create a false sense of security. This removed a major obstacle that always made me not like to implement log signatures.

The alert reader may now ask: “Doesn’t that sound too good?  Isn’t there a loophole?“. Of course, and as always in security, one can try to circumvent the mechanism. A very obvious attack is that an attacker may still go ahead and modify the log chain, re-hash it, and re-submit it to the signature process. My implementation inside rsyslog already makes this “a bit” hard to do because we keep log chains across multiple log files and the tooling notifies users if a chain is re-started for some reason (there are some valid reasons). But the main answer against these types of attacks is that when a re-hashing happens, the new signature will bear a different timestamp. As such, if comparing the signature’s timestamp and the log record timestamps, tampering can be indicated. In any case, I am sure we will see good questions and suggestions on how to improve my code. What makes me feel about the method itself is that it

  • bases on well-known and proven technology (with the Merkle tree being one foundation)
  • is in practical use for quite some while
  • ample of academic papers exist on it
  • there is a vital community driving it forward and enhancing the technology

So everything looks very solid and this is what triggered my decision to finally implement log signature directly into the rsyslog core. And to do it right, I did not create a KSI-specific interface but rather modeled a generic signature provider interface inside rsyslog. So if for whatever reason you don’t like the KSI approach, there is a facility inside rsyslog that can be used to easily implement other signature providers. Due to the reasoning given above, however, I have “just” implemented the KSI one for now.

As a side-note, please let me say that the Guardtime folks were very easy to work with and very cooperative, especially when I asked my initial though and very skeptic questions. They also are very open (lot’s of their tooling is open source) and … smart ;) During the project, our work relationship grew very much and the even managed to get me in direct contact with Ahto Buldas, who is a key inventor behind that technology (and a very impressive guy!). I am looking forward to continue to work with them in the future. In April 2013 they invited me to their Estonian office, where we had three days to discuss things like the network-signature problem (with relays discarding logs) and related problems like multi-tenancy and centralized virtual machine logging. These were very good discussions and some cool technology is probably coming out of them. I am tempted to write a bit more about these topics (as far as they have been tackled so far), but this posting is already rather long, so let’s save this for another one ;)

Which data does the Guardtime signature provider transfer to external parties?

With the interest in privacy concerns currently having a “PRISM-induced high”, I wanted to elaborate a little bit about what rsyslog’s Guardtime signature provider actually transmits to the signature authority.

This is a condensed post of what the provider does, highlighting the main points. If you are really concerned, remember that everything is open source. So you are invited to read the actual signature provider source, all of which is available at the rsyslog git.

The most interesting question first: the provider does only send a top-level hash to the signature authority. No actual log record will ever be sent or otherwise disclosed.

The way this works is that the provider creates a “smart” log signature chain. Actually, it is not a simple chain but rather a Merkle Tree (that’s why I call it “smart”).

When a log file is opened, the provider checks the signature status file if the file already contains some signed records and, if so, picks up the last hash. Then, hashing is initialized. For each record being written, both the previous hash and the current record are concatenated, hashed and the Merkle tree is updated. The actual signature is written when it is “time to do so”. And “time to do so” is when the file either needs to be closed (e.g. rsyslogd shutdown, eviction from dynafile cache) or the configured max block size is reached. In that case, the “last” hash (actually the root of the local Merkle tree) is sent to the signature authority for signing. This is the only data item ever sent out remotely. The signature authority replies with a signature for that hash, and the signature is stored.

Now let’s refresh you crypto know-how with the fact that a cryptographic hash function is necessarily a one-way function. That means there is no way to deduce from the hash what the original data is (except, of course, for brute-force attacks, what is a well-known fact and easily circumvented by using sufficiently large hash sizes). So even with the “last” hash being known by the authority, there is no way to know or even guess what the actual log records look like.

The bottom line is that all processing of the actual log records is done on the local rsyslog machine. You’ll even notice that by a slight (up to 30% depending on settings) increase in CPU use of the local machine. This is the actual hashing taking place.

Do you know wonder why log signatures can still be verified and trusted even if under attack. The answer is relatively straightforward, but requires some “cryptographer thinking”: It is impossible to alter the “last” hash, and that last hash has been signed (and timestamped!). So if you try to re-hash, that last hash would change. If you now verify, hashes do not match. You may think of this systems as multiple distributed Merkle trees in action, where the lowest-level Merkle tree is generated by the local rsyslog, and its top-level hash being provided to the external upper part of the tree (where it actually goes into the bottom-level computation). But I think now I involved myself (and you) too much into details…

Some more details on how the signing happens can also be found in my LinuxTag 2013 presentation (see slide 24 and following) and the accompanying paper.

Joining the Guardtime Technical Advisory Board

I just wanted to let everyone know that I will be joining the Guardtime technical advisory board. The board’s prime mission is to make sure that Guardtime implements technology that users need.

While implementing the rsyslog log signature interface and it’s first signature provider, I worked very closely and productive with the Guardtime folks. Over time, we exchanged more and more ideas and the whole thing culminated when I visited their office in Tallinn, Estonia where we had even better discussions and hacking sessions.

Guardtime seems to have enjoyed this work as well, and so I was recently asked if I would like to join their to-be-formed technical advisory board (TAB). At first, I was a bit hesitant because I wondered if there is any collision of interest between being on the Guardtime  TAB and driving rsyslog forward. So I talked a bit with the Guardtime folks clarifying my position. As it turns out, the whole point of the TAB is to assemble experts from different fields and let them discuss and provide information on what end-users really need. The rationale is very obvious: Guardtime as a company can only succeed if they provide what the market really needs. There is no point in trying the market to pick up some product or technology that has no real value. Too many companies tried that in the past and failed miserably. So, in that sense, I can act as the logging user’s agent inside the TAB and help push Guardtime in a direction that really is of value for logging. As I already think their current technology is a really good fit for what we need in logging, this is an exciting opportunity.

I also admit that it is very appealing that I will get ready access to Guardtime’s team of qualified cryptographers (including chief scientist Atho Buldas, who helped building the Estonian national PKI), which is a really big win in regard to secure cryptography in rsyslog. I never before had the chance to work with such top-notch crypto people. In fact, they already provided feedback on the non-Guardtime encryption bits in rsyslog and I am sure that working closer with them will help us getting very solid cryptography into rsyslog. If in doubt, just look at the rsyslog git tree and commit history about when all this new crypto stuff got in :-)

As a side-note, I am also talking with some other party about a custom module using a HMAC based tamper proof system for log records. While this is not as strong as the Gurdtime signature provider, there are obviously some use cases for it as well. If that project materializes, it will of course be merged into the main rsyslog git tree. So, for the concerned, rsyslog will definitely not get a Guardtime bias. After all, my main interest is driving rsyslog forward and, again, you can do that against what “the market” demands.

One of the things I discussed with the Guardtime cryptographers while I was in Tallinn was about how we could extend log integrity proof to a full network relay case, where relays even drop messages. This is a very hard and yet unsolved problem (for details see my paper on log signing in the relay case). While we got no ready solution from the initial discussion, we had some very promising ideas. This for sure is nothing we’ll see within the next quarter or so, but I am happy I now have the opportunity to discuss this and other hard problems with the knowledgeable (and very friendly, btw ;)) folks from Guardtime.

So for me getting on the TAB I think is a win-win-win situation for rsyslog, it’s user base and of course also Guardtime. Hope a lot of good stuff will come out of it.

What is a rsyslog signature provider?

Some folks asked what a (rsyslog) signature provider is. In essence, it is just a piece of software written to a specific interface.

There are little functional requirements for signature providers. Most obviously, we expect that it will provide some useful way to sign logs, what means it should be able to provide an integrity proof of either a complete log file or even some log records some time after the logs are recorded.

There is no “official signature provider spec” available. As usual in open source, the provider interface is well defined inside its actual source header file. Take a look for example at rsyslog’s git to see the definition.

If you look at that code, the interface is fairly simple. The primary entry points a programmer needs to define are

  • OnFileOpen
  • OnRecordWrite
  • OnFileClose

As the names imply, they are called whenever a log file is opened, written to, and closed. Again, what the provider does at these events is up to the provider.

The initial provider that ships directly with rsyslog is using a secure remote signing service provided by Guardtime.  There are various reasons why I selected this provider, and I elaborated at length on them in my blog posting on why I selected Guardtime as first rsyslog signature provider. In a nutshell, it is a method that does not rely on local secrets and as such can not be circumvented (again: details in my other posting). Obviously, Guardtime offers paid services, but they also operate free services for everyone to use (a key point when I evaluated that technology).

If you have privacy concerns about the Guardtime provider, you may want to read my blog posting on just that question.

Note that signature provider implementations can use the above entry points in any way they like. For example, the may ignore file open and close and do all work in record write. So this small interface is highly flexible. If you look at the full interface description, you’ll also see some more events which primarily provide housekeeping functionality. If you intend to write your own signature provider, I suggest to start with a copy of the guardtime provider and change it according to your needs. That way, you have a great example of how the housekeeping calls are handled.