How LogStore Digitial Signatures will Work

One of the next things we are going to implement is true signatures inside LogStore, the file format used by LogTools. Right now, the store is protected by a chain of SHA1 hashes. This means the store is tamper-proof (or tamper-evident, depending on your point of view) it the last hash of the chain has been saved to some external location. Then, it is possible to verify the chain of hashes and also verify that the latest hash is the one that was externally saved.

However, without the “external hash”, it is quite easy for an attacker to just rewrite the log and re-create the hashes. Especially as we have pledged to have the store well documented (security by obscurity is not on our agenda). As such, a hash chain provides only limited protection. It may even provide a false sense of security, if the last hash has not been stored away (attackers will *love* that part of the story).

To make LogStore’s tamper-proofness sound, we are going to implement digital signatures inside the store. This is done by signing some hashes along the chain. You can think of this like a kind of “external hash” inside the LogStore itself. It works the same way digital signatures work for example in PGP and email and thus is considered secure if the signing keys are not compromised (with a compromised key, nothing is secure).

To understand how this is done, let us first define a so-called “log partition”. A log partition is a set of n or fewer log records. It is the smallest object that is being protected by signatures. A log file is made up of one or many partitions (we do not plan to define an upper limit). A new partition is created whenever the LogStore is being opened for writing (even if nothing is written) and is closed when either the store is closed or a pre-configured set of (n) log records has been written. There most probably will be partition start and partition close records. Within at least the closure record, the partition’s last hash is written. It is probable, but not finally decided, if the open record contains the last hash of the previous partition (this would have some advantages in the case of partially tampered-with log stores). The closure record will be digitally signed (using public/private key cryptography). As such, the correctness of the partition closure record can be proven. With that, it is also known that the hash given in the closure record is the last hash used inside the partition. As such, much like with an externally-saved hash value, the hash chain in the partition can be verified.

Keep in mind that the hash chain will not be restarted for a new partition. Still, the previous partition’s last hash will be used to begin the hash chain of the new partition. As such, we can always detect a breach of the whole chain for the whole file. This also means partition closure records contain some redundant information: any one of them can be used to detect a breach of the hash chain in any partition before this closure record. As a side-note, the advantage of including the hash also in the partition open record would be that if a previous partition has been tampered with, we could still, and from the partition alone, verify the correctness of its partition. On the other hand, if the hash is not included inside the open record, we could also obtain it from the closure record immediately in front of it (there is only a subtle difference, and only in cases where that previous closure record has been mangled with – thus the current opinion is that there is not so much value in partition open records).

One may now ask “Why not simply sign each individual message?“. While this for sure is possible, it has considerable overhead, both in processing time as well as storage requirements. First of all, computing a digital signature is performance intense. So one wants to avoid this if high performance is required. From the storage point of view, a digital signature is rather lengthy, the printable form usually longer than a typical syslog or other log message (even Windows Event Log message are often shorter). So it is much more useful to sign only after a minimum number of messages has been processed. Of course, there is a drawback: the hash chain does not proof anything as long as it is not signed. As such the partition size (n) actually is a “vulnerability window” in which log messages can be removed from the file without anybody noticing (except, of course, if the proper closure record can be written). But locally stored data is always vulnerable (this is why with syslog you usually try to send logs off the front-end machine as quickly as possible). If thinking about LogStore as a long-term storage solution for logs that need tamper-proofness (e.g. because they should be used as evidence in court), this problem does not really apply because the log store would usually be created an a specifically protected machine. Or be created as part of a computer forensics investigation, e.g. creating a log of actions taken by the investigator. To care for extreme cases, the partition size can be set to one, in which case actually each message would be digitally signed (but, agreed, with additional overhead of closure records – another point that speaks against open records.)

We hope that you find this information useful. And we also hope that you will speak up if there is something that you don’t like or that we have simply overlooked. As we all know, security is hard to get right and easy to breach by a simple mistake. As such, we would really like to hear your concerns before this is all cast into a wide-spread stable version. Please either use the comment function or email Rainer with your feedback!

Tags:

2 Responses to “How LogStore Digitial Signatures will Work”

  1. Martin says:

    One thought: I think the external hash is one way to prevent/detect a rewriting. Another way is to include a signed timestamp (i.e. from an external timestamp server) into a log partition.

  2. rgerhards says:

    The signed timestamp actually makes a lot of sense. Please also have a look at the comment of on my blog announcement:

    http://blog.gerhards.net/2011/12/feedback-request-for-digitally-signed.html

    I guess this pretty much boils down to the same issue. I will wait for more input, probably until mid-January, and then see what to implement and in which order.