Internet Draft J. Kelsey Document: draft-ietf-syslog-sign-01.txt Counterpane Internet Security Expires: December, 2001 June 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This work is a product of the IETF syslog Working Group. More information about this effort may be found at http://www.ietf.org/html.charters/syslog-charter.html Comments about this draft should be directed to the syslog working group at the mailing list of syslog-sec@employees.org. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This document describes syslog-sign, a mechanism for adding origin authentication, message integrity, replay-resistance, message sequencing, and detection of missing messages to syslog. The goal of Kelsey Expires November 2001 [1] Syslog-sign Protocol June 2001 syslog-sign is to provide all these security features in a way that has minimal requirements and minimal impact on existing syslog implementations. It is possible to support syslog-sign and gain some of its security attributes by only changing the behavior of the devices generating syslog messages. Additional security benefits may be realized by some additional processing of the received syslog messages and the syslog-sign messages on the relays and collectors. Table of Contents Status of this Memo...................................................1 Copyright Notice......................................................1 Abstract..............................................................1 1 Introduction........................................................4 1.1 Design Philosophy and Goals.......................................4 1.2 Guide to the Document.............................................5 2 Signature Blocks....................................................5 2.1 How Signature Blocks Work.........................................5 2.2 Signature Groups and PRI Values...................................6 2.3 Signature Block Format and Fields.................................8 2.3.1 Text Block......................................................8 2.3.1.1 Priority......................................................8 2.3.1.2 Timestamp.....................................................9 2.3.1.3 Hostname......................................................9 2.3.1.4 Cookie........................................................9 2.3.1.5 SIG...........................................................9 2.3.2 Base-64 Encoded Binary Block....................................9 2.3.2.1 Version.......................................................9 2.3.2.2 Reboot Session ID............................................10 2.3.2.3 Global Block Counter.........................................11 2.3.2.4 First Message Number.........................................11 2.3.2.5 Count........................................................11 2.3.2.6 Hash Block...................................................11 2.3.2.7 Signature....................................................11 2.4 Notes on Upgrading Versions......................................11 3 Payload and Certificate Blocks.....................................11 3.1 Building the Payload Block.......................................12 3.3. Building the Certificate Block..................................13 3.4 Use of Certificate and Payload Blocks............................14 4 Redundancy and Flexibility.........................................15 4.1 Redundancy.......................................................15 4.1.1 Certificate Blocks.............................................15 4.1.2 Signature Blocks...............................................16 4.2 Flexibility......................................................16 4.3 Short Signature or Certificate Blocks............................17 5 Efficient Verification of Logs.....................................17 5.1. Offline Review of Logs..........................................17 Kelsey Expires November 2001 [2] Syslog-sign Protocol June 2001 5.2. Online Review of Logs...........................................18 6 Security Considerations............................................20 7 Conclusions and Open Issues........................................21 7.1 Initial Version..................................................21 8 Test Values........................................................21 8.1 Generating Signature Blocks......................................22 8.2 Generating Payload and Certificate Blocks........................22 9 Acknowledgements...................................................22 10 Bibliography......................................................22 A Author's Address...................................................22 B Full Copyright Statement...........................................22 Kelsey Expires November 2001 [3] Syslog-sign Protocol June 2001 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. Kelsey Expires November 2001 [4] Syslog-sign Protocol June 2001 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. We 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 us not to try to tackle these issues, which would necessarily involve second-guessing every system administrator who wanted to use the scheme. Using digital signatures instead of symmetric 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, we discuss signature blocks, and the infrastructure that supports them. Next, we discuss the key management tools in syslog-sign, built around payload blocks and certificate blocks. We then discuss redundancy mechanisms in syslog-sign. Next, we discuss efficient verification of logs and log messages, both online and offline. Finally, we 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] Kelsey Expires November 2001 [5] Syslog-sign Protocol June 2001 (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 system administrator 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 system administrator 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 Kelsey Expires November 2001 [6] Syslog-sign Protocol June 2001 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 = 046. 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 certificate 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 = 046. 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 046 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. Kelsey Expires November 2001 [7] Syslog-sign Protocol June 2001 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. The numbers in parentheses are the number of bytes taken up by the binary values inside the Base-64 encoded blob, and the number of characters for other values. a. Text Block (i) "<" (1) (ii) PRI (3) (iii) ">" (1) (iv) Timestamp(15) (v) " " (1) (vi) Hostname (variable) (vii) " " (1) (viii)Cookie (8) (ix) Sig Group (3) b. Base-64 Encoded Binary Block (variable) (i) Version (4) (ii) Reboot Session ID (6) (iii) Global Block Counter (6) (iv) First Message Number (6) (v) Count (2) (vi) Hash Block (variable) (vii) Signature (variable) 2.3.1 Text Block The text block contains information that is not binary-encoded. This is generally the information that relays or the system administrator may need to be able to see "in the clear." Some parts of the text block are required of all syslog messages; others make it easy to distinguish signature and certificate blocks from normal syslog messages. This block must be parsed field by field, using the angle brackets and spaces as delimiters. It is not fixed-length, due to the need to allow PRI, SIG, and hostname fields to vary in length. 2.3.1.1 Priority All syslog messages need a three digit priority and facility code, ranging from 0 to 191 inclusive. This value must be in angle brackets, e.g., <12> or <185>. Signature blocks' priority values are determined by the configuration of syslog-sign, in order to make it as easy as possible to get all syslog messages going to the same final collector to arrive with their signature blocks. In fact, if the syslog installation routes syslog messages based only on their priority+facility code, then the only Kelsey Expires November 2001 [8] Syslog-sign Protocol June 2001 configuration required for syslog-sign is to give each priority+facility code its own signature group. (Syslog-syslog [Lonvick, 2001] requires that syslog messages be routed only based on this code.) 2.3.1.2 Timestamp The timestamp is of the form specified in syslog-syslog [Lonvick, 2001], e.g. "Jan 1 14:33:54" or "Dec 19 02:01:00". The timestamp contains the local time on the device at the time the message is signed. Devices which do not have a clock MUST use the following format: "Jan 1 00:00:00". 2.3.1.3 Hostname The hostname is part of the device's configuration. The device will determine how many messages to include per signature block based mainly on the length of this parameter, so we recommend keeping the hostname parameter relatively short. 2.3.1.4 Cookie The cookie is an eight byte sequence to signal to the verifier that this is a signature block. This sequence is "@#sigSIG", without the quotes. 2.3.1.5 SIG The signature group appears at the end of the text block. It is a one- to-three character string of ASCII digits, between 0 and 191 inclusive. Depending on the device's configuration, this number may be the same as the PRI, or different. 2.3.2 Base-64 Encoded Binary Block The binary fields in the signature block must be encoded in base-64, because syslog messages may only contain printable characters. Again, the fields must be parsed individually, with the first five fields having fixed length, but the hash block's length varying according to how many messages have been signed. 2.3.2.1 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 into three fields, as follows: a. Protocol Version (0-65535) This is encoded as two bytes. The version of the protocol in this document is 1, in binary %b0000000000000001. Version 0 is Kelsey Expires November 2001 [9] Syslog-sign Protocol June 2001 used to represent a local variant of the protocol, used exclusively within a single installation, and with no guarantee of interoperability with other systems. b. Hash Algorithm (0-255) This is encoded as one byte. The following hash algorithms are defined for syslog-sign[FIPS-180-1,1993] (i) SHA-1 = 1 (in binary, %b00000001). Note that hash algorithms with output size less than 160 bits, and hash algorithms known or suspected to be susceptible to collision-finding attacks, MUST NOT be used in syslog-sign. In particular, MD4 and MD5 MUST NOT be used in syslog-sign. At the time of this writing, three new hash functions have been proposed to replace SHA-1, with output sizes of 256, 384, and 512 bits. These hash algorithms have not yet been specified as a new standard, and so are not included here. Version 0 is used to represent a locally-defined hash algorithm, with no promise of interoperability. c. Signature Scheme (0-255) This is encoded as one byte. The only signature scheme currently defined is OpenPGP[Callas, et. al,1998] DSA signatures[FIPS- 186,1994] with p parameter of 1024 bits. This signature scheme is specified as version 1, in binary %b00000001. The full version is a four byte string, encoding the first and second bytes of the protocol version, then the hash version, then the signature version. Thus, in binary, the initial version is %b00000000000000010000000100000001. Some version numbers, and the right mechanism for extending syslog-sign versions, are discussed below. 2.3.2.2 Reboot Session ID The reboot session ID is a 48-bit quantity, which is required to never repeat or decrease in the lifetime of the device. There is no other requirement for how this value is set. It is natural to set this from a timestamp or a reboot counter on the device. Kelsey Expires November 2001 [10] Syslog-sign Protocol June 2001 2.3.2.3 Global Block Counter The global block counter is a 48-bit quantity, and represents the number of messages whose signature blocks had been 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.2.4 First Message Number This is a 48-bit quantity, 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.2.5 Count The count is a 16-bit quantity, the number of message hashes to follow. 2.3.2.6 Hash Block The hash block is a sequence of hash values, their binary strings concatenated to make a long sequence of bytes. The length of the binary hash block (before base-64 encoding) is the length of the hash values from the hash function used, times the count of message hashes specified in the count field. 2.3.2.7 Signature This is a digital signature, encoded in base-64. The binary encoding of the signature is effectively specified by the Version field. 2.4 Notes on Upgrading Versions Note that the format requires that the text block remain unchanged across all future versions. That is, only the base-64 encoded binary block may have fields altered. Also note that the version field MUST remain the first binary field in any future version of the protocol. 3 Payload and Certificate Blocks Key management in syslog-sign is supported by certificate blocks and payload blocks. At session startup, the device Kelsey Expires November 2001 [11] Syslog-sign Protocol June 2001 builds a payload block; there is exactly one payload block built per session. The payload block carries both key-management and session-management information. Certificate blocks are valid syslog messages which carry fragments of the payload block. The collector receives these certificate blocks, and uses them to reassemble the payload block. The payload block's contents can then be cryptographically verified, and its information used. All devices MUST generate a payload block at the start of a session, and this payload block MUST be transmitted to all signature groups by the device, by way of one or more certificate blocks. Certificate blocks SHOULD be sent multiple times, to increase the probability that at least one copy of each certificate block will be received. 3.1 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. Full local timestamp for the device, including year if available, at time reboot session started. This SHOULD be a valid timestamp, but MAY be filled in with ASCII zeros if no internal clock is available. The format of this timestamp is "yyyymmddhhmmss", where yyyy is the four-digit year in ASCII digits, the first mm is a two digit month value (01-12), dd is a two-digit date (01-31), hh is a two-digit hour in military time (00-23), the second mm is a two-digit minute value (00-59), and the ss is a two-digit seconds value (00-59). For example, January 23, 2054 at 8:35:19 AM would be represented as "20540123083519", while February 8, 2002 at 5:15:00 PM would be shown as "20020208171500". A device without an internal clock would use "00000000000000". b. 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 == 046. (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 Kelsey Expires November 2001 [12] Syslog-sign Protocol June 2001 way with no simple relationship to pri values; for all signature/certificate blocks, pri = 046. (iv) '3' -- Signature groups are assigned to ranges of pri values. For each signature/certificate block, pri = largest pri contained within that signature group. c. Highest SIG Value -- a three-character field showing the highest SIG value that will ever be seen on a signature/certificate block. This may range from "000" to "191". d. Key Blob Type, a one-byte field which holds one of the following values: (i) 'C' -- a PKIX certificate (ii) 'N' -- no key information sent; key is predistributed. (iii)'S' -- signed public key e. 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. "<" b. A PRI value, derived and used exactly the same way it will be used for the signature blocks. This may be one to three digits. c. ">" d. A timestamp, as described above for signature blocks. e. " " f. A hostname, as described above for signature blocks. g. " " h. Cookie, an eight byte string, "@#sigCer". Kelsey Expires November 2001 [13] Syslog-sign Protocol June 2001 i. SIG, a one to three-digit character string, as described above for signature blocks. j. A base-64 encoded blob, which encodes the following binary fields: (i) Version, as described above for signature blocks. (ii) RSID, as described above for signature blocks. (iii)Payload length, a four-byte value encoding an unsigned 32-bit integer, whose value is the total payload block's length in bytes. (iv) Index, a 32-bit integer (encoded as four bytes) that specifies where in the payload block this fragment belongs. (v) Fragment Length, a 16-bit integer (encoded as two bytes) that specifies the number of bytes in this certificate block's Fragment field. (vi) Fragment, the raw fragment. (vii)Signature, a digital signature on all the above fields. 3.4 Use of Certificate and Payload Blocks The certificate blocks carry signatures, which will sometimes only be verifiable after the payload block is reconstructed and used. The certificate and payload blocks should be processed as follows: a. Collect all the certificate blocks. Verify that the versions, lengths, indexes, and RSIDs are all valid and internally consistent. b. Rebuild the payload block. c. Verify the parameters of the payload block, and particularly the key blob. d. Extract or verify the key. e. Verify all the certificate blocks' signatures. f. If all verifications were successful, accept the key and session. If any certificate block failed to be verified, then search for redundantly-sent versions of the certificate blocks. Kelsey Expires November 2001 [14] Syslog-sign Protocol June 2001 There are two reasons for putting the signatures on certificate blocks: a. Installations with predistributed keys can simply verify the signatures as the certificate blocks come in. b. Information in the certificate blocks, such as hostname, RSID, etc., needs to be verified cryptographically before it can be trusted. Otherwise, an attacker could send misleading certificate blocks reflecting the use of an old key with a new RSID. 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 MAY send any legal signature or certificate block any number of times. The collector MUST be able to process any legal signature or certificate block, and MUST NOT have its authenticated log output changed by receipt of any number of additional copies of a valid signature or certificate block after the first one. 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 multiple copies of normal syslog messages, here we define some redundancy parameters below which may be useful in controlling redundant transmission from the device to the collector. The collector has no knowledge of these parameters; the device MAY use them, but is not required to. 4.1.1 Certificate Blocks There are three parameters for certificate block redundancy: Kelsey Expires November 2001 [15] Syslog-sign Protocol June 2001 a. certInitialRepeat, the number of times each certificate block should be sent to each signature group before the first message is sent. b. certResendDelay, the maximum time delay in seconds before next redundant sending of the certificate blocks. (Certificate blocks are resent periodically during a long message, so that offline analysis of the logs remains possible even if the initial certificate blocks are not received correctly.) c. certResendCount, maximum number of sent messages to delay before next redundant sending. 4.1.2 Signature Blocks The following parameters define a strategy for redundant signature blocks: a. sigNumberResends, the number of times a signature block is resent. b. sigResendDelay, the maximum time delay in seconds from original sending to next redundant sending. c. sigResendCount, the 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 c. The signing key. d. The RSID. These are fixed per session. A device MUST NOT change these during a session. A collector that sees signature or certificate blocks with any of these things different than the current session MUST check the RSID to see if the blocks come from an earlier or later session. Blocks from an earlier session MUST be ignored and discarded. Blocks from a later session MUST cause the collector to switch to a new session, and to attempt to find the key for the new session. Kelsey Expires November 2001 [16] Syslog-sign Protocol June 2001 When logs are to be verified, the collector MUST have the most recent RSID of a valid session. It MUST NOT accept logs from a session whose RSID is less than or equal to the most recent RSID. It MUST NOT accept a new RSID as valid unless the full payload block from that RSID has been received and verified, and its certificate blocks have also been verified. 4.3 Short Signature or Certificate Blocks There is no requirement for signature or certificate blocks to be any specific length, so long as they are never longer than 1024 bytes. A device MAY vary the length of successive certificate blocks for any reason, a collector or log verification program MUST process these correctly regardless of their length, so long as they are valid blocks. 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 the First Message Kelsey Expires November 2001 [17] Syslog-sign Protocol June 2001 Number field. 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 Kelsey Expires November 2001 [18] Syslog-sign Protocol June 2001 (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. Kelsey Expires November 2001 [19] Syslog-sign Protocol June 2001 6 Security Considerations The following are some important security considerations for using syslog-sign. a. The strength of syslog-sign is totally dependent on the strength of the underlying hash function and digital signature algorithm, and on the quality of their implementation. For this reason, it is critical that new versions of syslog-sign not be added to the standard without a thorough cryptographic review of: (i) The signature scheme (ii) The hash algorithm (iii)Any changes to the protocol (iv) Any possible interactions between protocol steps and versions. New versions and version numbers MUST NOT be added without a review by a competent person appointed by the area directors. b. Local variations (assumed not to be compatible with external systems) are supported by setting the protocol, hash, or signature version to 0x00. This is intended to allow sophisticated users to make use of existing cryptographic infrastructure. Users are warned that making alterations of this kind locally should not be done without competent cryptographic review. c. As with most cryptographic mechanisms, the quality of random number generation available for key and signature generation is a major factor in determining whether this system will be secure. We strongly recommend the use of some well-tested and -reviewed cryptographic random number source. Some recommendations may be found in [RFC1750], and a number of competent designs exist in cryptographic libraries. (In particular, many UNIX systems have a /dev/random interface that meets these requirements.) d. The implementation of syslog-sign which receives and processes logs, online or offline, must be carefully reviewed for programming errors that would allow buffer overruns or similar attacks, as these would allow an attacker to bypass all the cryptographic protection used. e. In particular, certificate blocks and payload blocks have the problem that they are processed extensively before they may be verified. Programs that process these MUST NOT be susceptible to buffer overrun or other program failures when the payload lengths, fragment lengths, or indexes of Kelsey Expires November 2001 [20] Syslog-sign Protocol June 2001 the certificate blocks are inconsistent. f. As processing power, memory, and bandwidth grow cheaper, extended key sizes will become necessary. As of this writing, DSA has a maximum supported parameter sizes of |q|==160, |p|==1024. In the near future, we expect NIST to specify DSA variants with |q| up to 512 bits, and |p| of 4096 or more bits, using a hash function whose output is the same size as |q|. These extensions will change the number of messages per signature block that are possible, and may have a noticeable impact on the ultimate efficiency of the protocol. However, even with |q|==512, we should be able to sign 7 messages per signature block; with a more realistic |q|==256, we should be able to sign 17 messages per signature block. 7 Conclusions and Open Issues In this note, we have described syslog-sign, a mechanism for adding origin authentication, data integrity, message sequencing, and gap and replay detection to syslog over UDP. Syslog-sign does not require moving syslog to TCP, and is intended to minimize the impact of required changes to existing devices, relays, and servers on the network. In addition to meeting these goals, syslog-sign using digital signatures provides storage security, since an attacker who takes over the collector but doesn't know the device's private key cannot alter the saved logs. Note, however, that nothing prevents such an attacker from simply deleting the log messages he finds inconvenient. While those messages will obviously be missing from the log when it is reviewed, there is no way for the reviewer to know whether those messages ever really arrived at the collector. 7.1 Initial Version We have specified the first complete version of syslog-sign as follows: Protocol Version: 1 (this protocol) Hash Function: 1 (SHA1) Signature: 1 (openPGP DSA signatures) The total version value is {0x00, 0x01, 0x01, 0x01} as a sequence of bytes. 8 Test Values The following are some test values generated by the author. Kelsey Expires November 2001 [21] Syslog-sign Protocol June 2001 8.1 Generating Signature Blocks 8.2 Generating Payload and Certificate Blocks 9 Acknowledgements The author wishes to thank Alex Brown, Chris Calabrese, Jon Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin New, Marshall Rose, Bruce Schneier, Holt Sorenson, Rodney Thayer, the many Counterpane Internet Security engineering and operations people who commented on various versions of this proposal, and Counterpane Internet Security and Certicom for their generous support of this work. 10 Bibliography Schneier, _Applied Cryptography_, John Wiley & Sons, 1996. Menezes, van Oorschot, Vanstone, _Handbook of Applied Cryptography_, CRC Press, 1997. FIPS-180-1, "Secure Hash Standard," Federal Information Processing Standards Publication 180-1, U.S. Department of Commerce, 1993. FIPS-186, "Digital Signature Standard," Federal Information Processing Standards Publication 186, U.S. Department of Commerce, 1994. Callas, Donnerhacke, Finney, and Thayer, "OpenPGP Message Format," RFC2440, Nov 1998. Eastlake, Crocker and Schiller, "Randomness Recommendations for Security," RFC1750, Internet Engineering Task Force, Dec 1994. Lonvick, "Syslog Protocol", Internet Draft, draft-ietf-syslog-syslog-06.txt, Feb 2001 A Author's Address John Kelsey Certicom kelsey.j@ix.netcom.com / jkelsey@certicom.com 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 Kelsey Expires November 2001 [22] Syslog-sign Protocol June 2001 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. Kelsey Expires November 2001 [23]