Guys, This is almost done. I still need to fix the references, and may make some other changes. Questions I have for this group: a. Can someone help me with referencing openPGP standards? b. Is there enough detail here? c. Am I leaving any important topics out? d. Am I leaving any important internet draft components out? Thanks, --John ///// Internet Engineering Task Force Syslog Internet Draft Feb 2001 Expires: Aug 2001 Syslog-Sign Protocol STATUS OF THIS MEMO This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress". To view the list Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html ABSTRACT This document describes syslog-sign, a mechanism for adding origin authenticaiton, message integrity, replay-resistance, message sequencing, and detection of missing messages to syslog. The goal of syslog-sign is to provide all these security features in a way that has minimal requirements and minimal impact on an existing setup of syslog devices, relays, and collectors. In particular, it is possible to support syslog-sign by changing only the behavior of the syslog devices, and some software run either online or offline on the collector's stored logs. 1 Introduction Syslog-sign is a protocol for adding origin authentication, message integrity, replay resistance, message sequencing, and detection of missing messages to syslog. A major goal of the protocol is to do all this in a way that can be quickly deployed on existing networks, and that can be implemented mostly using off-the-shelf tools. To this end, a number of basic design decisions were made that determined most of the design: a. All messages sent in this protocol are legal syslog messages. This ensures that relays and collectors can handle the new protocol's traffic without any changes. It also inherits the problems of syslog messages in general: unreliable and out-of-sequence delivery, only printable characters allowed in the message text, and each message limited to 1024 bytes maximum. b. Normal syslog messages are sent unchanged by the protocol, just as they would have been sent by syslog without any enhancements. c. Every N messages, a signature block is sent along as a syslog message. This contains, in effect, a detached signature on the previous N messages. These signature blocks contain additional information to allow them to be put into sequence, and to allow any missing signature blocks to be noticed. d. Because we must keep the logs in the correct sequence even across reboots of the device, we must differentiate different ``sessions'' in which a device is generating log messages and signature blocks. This is done with a ``reboot session ID,'' a 48-bit identifier which is guaranteed never to be reused by a given device. e. To support key and session management, we have a mechanism for sending along a certificate or other information on a per-reboot-session basis. This is done using ``certificate blocks,'' which are also legal syslog messages. 1.1 Design Philosophy and Goals More than anything else, what ultimately drove this design was the decision to use syslog as the transport method for all syslog-sign messages. This requires the use of detached signatures (signature blocks), because there's no other way to add signatures and other information to all messages; some messages would have had to be truncated or fragmented. Using signature blocks appeared the cleanest way to do this. As a side benefit, relatively expensive and large digital signatures can be spread out among N messages at a time, making the whole scheme more efficient. I decided to use syslog as the transport mechanism because altering every syslog message meant changing the software on every relay and collector, and probably dealing with very complicated cases where some relays and collectors could process authenticated messages, while others could not. A previous attempt to design a scheme for doing authenticated syslog messages taught me not to try to tackle these issues, which would necessarily involve second-guessing every sysadmin who wanted to use the scheme. Using digital signatues instead of MACs to authenticate messages makes the key management much simpler (though there's nothing inherent in the syslog-sign design that requires that nobody use symmetric algorithms), and makes the scheme suitable for providing storage security for the logs, as well as transmission security. 1.2 Guide to the Document The rest of this document is organized as follows: First, I discuss signature blocks, and the infrastructure that supports them. Next, I discuss the key management tools in syslog-sign, built around payload blocks and certificate blocks. I then discuss redundancy mechanisms in syslog-sign. Next, I discuss efficient verification of logs and log messages, both online and offline. Finally, I conclude the document with a brief summary and some open questions about the design. 2 Signature Blocks 2.1 How Signature Blocks Work A signature block contains a priority value (required for all syslog messages), some header information (to allow the signature blocks to be put into order on receipt), a sequence of N cryptographic hash values, and a digital signature. Signature Block: a. PRI Value b. Header Information c. List of N hashes: (i) Hash[0] (ii) Hash[1] (iii)Hash[2] ... d. Signature on fields a-c. Consider a device, which is sending log messages to a collector. After every Nth normal log message, it sends an additional message with this format. Again, this is just a syslog message, and so it needs no special treatment by the collector or any intermediate nodes. To generate and send that additional message, (the ``signature block''), the device keeps the cryptographic hash values of the previous N messages sent, and how many messages were sent before these most recently sent N messages. Using that information, the device is able to build the signature block. It digitally signs the block, and sends it along. The collector may process these signature blocks as they arrive, building an authenticated log file on the fly as the pieces arrive. Alternatively, it may store all the log messages in the order they were received, and allow the sysadmin to authenticate the log file when he reviews the logs. In either case, out-of-order messages are put back into order based on the hash values in the signature block. (There are a number of efficient ways to do this.) 2.2 Signature Groups and PRI Values Each signature block contains, in effect, a detached signature on the previously sent N messages. However, a device may send messages that are ultimately routed to many different collectors. If the N messages arrive at one collector, and the signature block at another, then neither collector will be able to verify anything. Similarly, if half of the N messages go to one collector, while the signature block and the other half of the N messages go to the other, there is clearly a problem. The solution to this problem ultimately rests with the sysadmin who uses the system; he must configure any relays and collectors to ensure that messages and their signature blocks arrive at the same place. To make this easier, syslog-sign provides the idea of a ``signature group.'' A signature group identifies a group of messages that are all kept together for signing purposes by the device. A signature block always belongs to exactly one signature group, and it always signs messages belonging only to that signature group. Recall that syslog-sign doesn't alter messages. That means that the signature group of a message doesn't appear anywhere in the message itself. Instead, the device and any intermediate relays use something inside the message to decide where to route it; the device needs to use the same information to decide which signature group a message belongs to. Syslog-sign provides four options for handling signature groups, linking them with PRI values. In all cases, no more than 192 signature groups (0-191) are permitted. In this list, SIG is the signature group, and PRI is the PRI value of the signature and certificate blocks in that signature group. a. '0' -- Only one signature group, SIG = 0, PRI = XXX. The same signature group is used for all certificate and signature blocks, and for all messages. b. '1' -- Each PRI value has its own signature group. Signature and certificate blocks for a given signature group have SIG = PRI for that signature group. c. '2' -- Each signature group contains a range of PRI values. Signature groups are assigned sequentially. A certiticate or signature block for a given signature group have its SIG value, and the highest PRI value in that signature group. (That is, if signature group 2 has PRI values in the range 100-191, then all signature group 2's signature and certificate blocks will have PRI=191, and SIG=2. d. '3' -- Signature groups are not assigned with any simple relationship to PRI values. A certificate or signature block in a given signature group will have that group's SIG value, and PRI = XXX. Note that options (a) and (b) make the SIG value redundant. However, in installations where log messages are forwarded to different collectors based on some complicated criteria (e.g., whether the message text matches some regex), the SIG value gives an easy way for relays to decide where to route signature and certificate blocks. This is necessary, since these blocks almost certainly won't match the regexes. Options (a) and (d) set the PRI value to XXX for all signature and certificate blocks. This is intended to make it easier to process these syslog messages separately from others handled by a relay. One reasonable way to configure some installations is to have only one signature group, send messages to many collectors, but send a copy of each signature and certificate block to each collector. This won't allow any collector to detect gaps in the messages, but it will allow all messages that arrive at each collector to be put into the right order, and to be verified. 2.3 Signature Block Format and Fields The signature block is composed of the following fields. Recall that every field must be printable ASCII, and any binary values are base-64 encoded. a. PRI (3) b. Cookie (8) c. Version (4) d. Reboot Session ID (8) e. Signature Group (3) f. Global Block Counter (8) g. First Message Number (8) h. Count (2) i. Hash Block (??) j. Signature (??) These fields are described below. 2.3.1 Priority The priority field required for all syslog messages. This is set depending on the settings used by the sender, as described below. 2.3.2 Cookie The cookie is an eight byte sequence to signal to the verifier that this is a signature block. This sequence is ``@#sigSIG''. 2.3.3 Version The version specifies what version of the syslog-sign protocol is being used, what hash algorithm is being used, and what signature scheme is being used. This is broken up as follows: a. Protocol Version (0-4095) (2 bytes; base 64 encoded) b. Hash Algorithm (0-63) (1 byte; base 64 encoded) c. Signature Scheme (0-63) (1 byte; base 64 encoded) 2.3.3.1 Current Versions The current version of the protocol is 1. SHA1 is hash algorithm 1, and openPGP DSA is signature scheme 1. 2.3.4 Reboot Session ID The reboot session ID is a 48-bit quantity encoded in base 64 as eight bytes, which is required to never repeat or decrease in the lifetime of the device. 2.3.5 Signature Group This is the SIG identifier, described above. It may take on any value from 0-191 inclusive, and is encoded as two bytes in base 64. 2.3.6 Global Block Counter The global block counter is a 48-bit quantity encoded in base 64 as eight bytes, which is the number of signature blocks sent out by syslog-sign before this one, in this reboot session. Note that this counter crosses signature groups; it allows us to roughly synchronize when two messages were sent, even though they went to different collectors. 2.3.7 First Message Number This is a 48-bit quantity encoded in base 64 as eight bytes, which is the unique message number within this signature group of the first message whose hash appears in this block. (That is, if this signature group has processed 1000 messages so far, and the 1001st message from this signature group is the first one whose hash appears in this signature block, then this field is 1001.) 2.3.8 Count The count is a 6-bit quantity encoded in base 64 as one byte, which is the number of message hashes to follow. 2.3.9 Hash Block The hash block is a block of hashes, each separately encoded in base-64. The size of each hash is determined by the hashing algorithm used, effectively specified by the Version field, but the size MUST NOT be shorter than 160 bits. 2.3.10 Signature This is a digital signature, encoded in base-64. The original encoding of the signature is effectively specified by the Version field. 3 Payload and Certificate Blocks Key management in syslog-sign is supported by certificate blocks and payload blocks. 3.1 Preliminaries: Key Management and Distribution Issues The purpose of certificate blocks is to support key management using public key cryptosystems. All devices send at least one certificate block at the beginning of a new reboot session, carrying useful information about the reboot session. There are three key points to understand about certificate blocks: a. They handle a variable-sized payload, by fragmenting it if necessary, and transmitting the fragments as legal syslog-syslog messages. This payload is built (as described below) at the beginning of a reboot session, and is transmitted in pieces, with each certificate block carrying a piece. Note that there is exactly one payload block per reboot session. b. The certificate blocks are digitally signed. The payload block is not signed by the device, but its authenticity is ensured by the signatures on the certificate blocks. Note that the signature on the certificate blocks may not even be possible to verify without the information in the payload block; in this case the payload block is reconstructed, the key is extracted, and then the certificate blocks are verified. (This is necessary even when the payload block carries a certificate, since some other fields of the payload block aren't otherwise verified.) In practice, I expect that most installations will keep the same public key over long periods of time, so that most of the time, it's easy to verify the signatures on the certificate blocks, and use the payload block to provide other useful per-session information. c. The kind of payload block that is expected is determined by what kind of key material is on the collector that receives it. The device and collector (or offline log viewer) has both some key material (such as a root public key, or predistributed public key), and an acceptable value for the Key Blob Type in the payload block, below. A payload block of the wrong type MUST NOT be accepted by the collector or offline log viewer. 3.2 Building the Payload Block The payload block is built when a new reboot session is started. There is a one-to-one correspondence of reboot sessions to payload blocks. That is, each reboot session has only one payload block, regardless of how many signature groups it may support. The payload block consists of the following: a. Unique identifier of sender; by default, the sender's 128-bit IP address encoded in base-64. b. Full local timestamp for the device, including year if available, at time reboot session started. c. Signature Group Descriptor. This consists of a one-character field specifying how signature groups are assigned. The possibilities are: (i) '0' -- Only one signature group supported. For all signature blocks and certificate blocks, sig == pri == XXX. (ii) '1' -- Each pri value gets its own signature group. For each signature/certificate block, sig == pri. (iii)'2' -- Signature groups are assigned in some way with no simple relationship to pri values; for all signature/certificate blocks, pri = XXX. (iv) '3' -- Signature groups are assigned to ranges of pri values. For each signature/certificate block, pri = largest pri contained within that signature group. d. Highest SIG Value -- a two-byte field base 64 encoded, must be a number between 0 and 191, inclusive. e. Key Blob Type, a one-byte field which holds one of four values: (i) 'C' -- a PKIX certificate (ii) 'K' -- the public key whose corresponding private key is being used to sign these messages. (iii)'N' -- no key information sent; key is predistributed. (iv) 'U' -- installation-specific key exchange information f. The key blob, consisting of the raw key data, if any, base-64 encoded. 3.3. Building the Certificate Block The certificate block must get the payload block to the collector. Since certificates can legitimately be much longer than 1024 bytes, each certificate block carries a piece of the payload block. Note that the device MAY make the certificate blocks of any legal length (that is, any length less than 1024 bytes) which will hold all the required fields. Software that processes certificate blocks MUST deal correctly with blocks of any legal length. The certificate block is built as follows: a. A pri value; this value is chosen to ensure that every signature group will get a full set of certificate blocks. b. Cookie -- an eight byte string, ``@#sigCer''. c. Version -- a 12-bit field encoded in base-64 as two bytes. d. Reboot Session ID -- as above. e. Signature Group -- a 12-bit field encoded in base-64 as two bytes. f. Total Payload Length -- a 32-bit field encoded in base-64 as six bytes. g. Index into Payload -- a 32-bit field encoded in base-64 as six bytes. h. Fragment Length -- a 12-bit field encoded in base-64 as two bytes. i. Payload Fragment -- a fragment of the payload, as specified by the above fields. j. Signature -- a digital signature on fields a-i. 4 Redundancy and Flexibility There is a general rule that determines how redundancy works, and what level of flexibility the device and collector have in message formats: In general, the device is allowed to send signature and certificate blocks multiple times, to send signature and certificate blocks of any legal length, to include fewer hashes in hash blocks, etc. 4.1 Redundancy Syslog messages are sent over unreliable transport, which means that they can be lost in transit. However, signature and certificate blocks must be received by the collector, or many messages may not be able to be verified. Redundancy is provided by sending signature and certificate blocks multiple times; since the collector MUST ignore signature/certificate blocks it has already received and authenticated, the device can in principle change its redundancy level for any reason, without communicating this fact to the collector. Although the device isn't constrained in how it decides to send redundant signature and certificate blocks, or even in whether it decides to send along mutliple copies of normal syslog messages, here I define some redundancy parameters below which may be useful in controlling redundant transmission from the device to the collector. 4.1.1 Certificate Blocks certInitialRepeat = number of times each certificate block should be sent before the first message is sent. certResendDelay = maximum time delay in seconds to delay before next redundant sending. certResendCount = maximum number of sent messages to delay before next redundant sending. 4.1.2 Signature Blocks sigNumberResends = number of times a signature block is resent. sigResendDelay = maximum time delay in seconds from original sending to next redundant sending. sigResendCount = maximum number of sent messages to delay before next redundant sending. 4.2 Flexibility The device may change many things about the makeup of signature and certificate blocks in a given reboot session. The things it cannot change are: a. The version b. The number or arrangements of signature groups It is legitimate for a device to send our short signature blocks, in order to keep the collector able to verify messages quickly. In general, unless something verified by the payload block or cerificate blocks is changed within the reboot session ID, any change is allowed to the signature or certificate blocks during the session. The device may send shorter signature and certificate blocks for 5 Efficient Verification of Logs The logs secured with syslog-sign may either be reviewed online or offline. Online review is somewhat more complicated and computationally expensive, but not prohibitively so. 5.1. Offline Review of Logs When logs are stored by the collector and reviewed later, they can be authenticated offline just before they are to be reviewed. Reviewing these logs offline is simple and relatively cheap in terms of resources used, so long as there is enough space available on the reviewing machine. Here, we will consider that the stored log files have already been separated by sender, reboot session ID, and signature group. This can be done very easily with a script file. We then do the following: a. First, we go through the raw log file, and split its contents into three files. Each message in the raw log file is classified as a normal message, a signature block, or a certificate block. Certificate blocks and signature blocks are stored in their own files. Normal messages are stored in a keyed file, indexed on their hash values. b. We sort the certificate block file by index value, and check to see if we have a set of certificate blocks that can reconstruct the payload block. If so, we reconstruct the payload block, verify any key-identifying information, and then use this to verify the signatures on the certificate blocks we've received. When this is done, we have verified the reboot session and key used for the rest of the process. c. We sort the signature block file by firstMessageNumber. We now create an authenticated log file, which will consist of some header information, and then a sequence of message number, message text pairs. We next go through the signature block file. For each signature block in the file, we do the following: (i) Verify the signature on the block. (ii) For each hashed message in the block: (a) Look up the hash value in the keyed message file. (b) If the message is found, write (message number,message text) to the authenticated log file. (iii)Skip all other signature blocks with the same firstMessageNumber. d. The resulting authenticated log file will contain all messages which have been authenticated, and will indicate (by missing message numbers) all gaps in the authenticated messages. It's pretty easy to see that, assuming sufficient space for building the keyed file, this whole process is linear in the number of messages (generally two seeks, one to write and the other to read, per normal message received), and O(N lg N) in the number of signature blocks. This estimate comes with two caveats: First, the signature blocks will arrive very nearly in sorted order, and so can probably be sorted more cheaply on average than O(N lg N) steps. Second, the signature verification on each signature block will almost certainly be more expensive than the sorting step in practice. We haven't discussed error-recovery, which may be necessary for the certificate blocks. In practice, a very simple error-recovery strategy is probably good enough--if the payload block doesn't come out as valid, then we can just try an alternate instance of each certificate block, if such are available, until we get the payload block right. It's easy for an attacker to flood us with plausible-looking messages, signature blocks, and certificate blocks. 5.2. Online Review of Logs Some processes on the collector machine may need to monitor log messages in something very close to real-time. This can be done with syslog-sign, though it is somewhat more complex than the offline analysis. This is done as follows: a. We have an output queue, into which we write (message number, message text) pairs which have been authenticated. Again, we'll assume we're handling only one signature group, and only one reboot session ID, at any given time. b. We have three data structures: A queue into which (message number, hash of message) pairs is kept in sorted order, a queue into which (arrival sequence, hash of message) is kept in sorted order, and a hash table which stores (message text, count) indexed by hash value. In this file, count may be any number greater than zero; when count ==0, the entry in the hash table is cleared. c. We must receive all the certificate blocks before any other processing can really be done. (This is why they're sent first.) Once that's done, any certificate block that arrives is discarded. d. Whenever a normal message arrives, we add (arrival sequence, hash of message) to our message queue. If our hash table has an entry for the message's hash value, we increment its count by one; otherwise, we create a new entry with count = 1. When the message queue is full, we roll the oldest messages off the queue by taking the last entry in the queue, and using it to index the hash table. If that entry has count==1, we delete the entry in the hash table; otherwise, we decrement its count. We then delete the last entry in the queue. e. Whenever a signature block arrives, we first check to see if the firstMessageNumber value is too old, or if another signature block with that firstMessageNumber has already been received. If so, we discard the signature block unread. Otherwise, we check its signature, and discard it if the signature isn't valid. A signature block contains a sequence of (message number, message hash) pairs. For each pair, we first check to see if the message hash is in the hash table. If so, we write out the (message number, message text) in the authenticated message queue. Otherwise, we write the (message number, message hash) to the message number queue. This generally involves rolling the oldest entry out of this queue: before this is done, that entry's hash value is again searched for in the hash table. If a matching entry is found, the (message number,message text) pair is written out to the authenticated message queue. In either case, the oldest entry is then discarded. f. The result of this is a sequence of messages in the authenticated message queue, each of which has been authenticated, and which are combined with numbers showing their order of original transmission. It's not too hard to see that this whole process is roughly linear in the number of messages, and also in the number of signature blocks received. The process is susceptible to flooding attacks; an attacker can send enough normal messages that the messages roll off their queue before their signature blocks can be processed. 6 Conclusions and Open Issues 7 Acknowledgements The author wishes to thank Alex Brown, Chris Calabrese, Jon Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin New, Marshall Rose, Holt Sorenson, Rodney Thayer, and the many Counterpane Internet Security engineering and operations people who commented on various versions of this proposal. 8 Bibliography Schneier, _Applied Cryptography_, John Wiley & Sons, 1996 Menezes, Vanstone, ... _Handbook of Applied Cryptography_ Lonvick, ``Syslog-Syslog'' New, Rose, ``Syslog-Reliable'' NIST SHA1 spec NIST DSA spec ??? OpenPGP spec ??? HMAC paper ??? HMAC spec for IPSec A Author's Address John Kelsey Counterpane Internet Security [EMAIL PROTECTED] B Full Copyright Statement Copyright (C) The Internet Society (2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
