Internet Engineering Task Force Syslog Internet Draft John Kelsey draft-ietf-syslog-sign-00.txt Expires: 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. 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 intended to be an in-band protocol for signing messages within syslog, making no assumptions about any delivery mechanisms. This means that all messages sent along are valid syslog-syslog messages. The messages will be received and stored normally by any syslog collector. However, offline review of the stored logs by a syslog-sign-aware program will allow verification of the logs' origin, integrity, freshness, and completeness. The basic design goals are thus: a. The goal of syslog-sign is offline detection of alterations of the logs. The signatures provide both storage security and transmission security, but we provide no support for any kind of online detection of alterations. (There's nothing saying a collector can't implement such detection online, assuming it can keep up with the workload. But we add nothing to support such online detection.) b. Over the course of a reasonably long session, syslog-sign will transmit the certificate, public key, or key ID on which its signatures are based several times. Expires June 2001 [Page 1] Draft Syslog Sign December 2000 c. Syslog-sign will provide data integrity, data origin authentication, replay detection, and gap detection. It is the responsibility of the users of syslog-sign to ensure that all the logs in a ``signature group'' are sent to the same receiver. (A ``signature group'' is a set of messages signed in the same sequence of signature blocks.) How the administrator sets things up to support this is outside the scope of this document, but if messages from the same signature group are somehow separated during transmission or forwarding, we will generally be unable to authenticate the messages stored by any one collector. d. Because syslog-sign must operate in-band over unreliable delivery mechanisms, there is always some chance that critical information will not make it to the receiver. However, syslog-sign can be configured on the sender side to add redundancy to its messages, to decrease the likelihood that any messages will be impossible to verify. e. Syslog-sign supports multiple signature and hash sizes and schemes. These are encoded in its version field. Larger signatures lead to more bandwidth required by syslog-sign. Syslog-sign even supports symmetric cryptosystems. f. The only awareness of forwarding in syslog-sign is the requirement that a syslog-sign relay (as well as a device) signal some kind of an error if it is required by its forwarding rules to send messages in the same signature group to different recipients. 2. Syslog-Sign Message Formats Syslog-sign uses syslog to transmit its messages. That means that all of its messages have to fit inside legal syslog-syslog messages. This determines most of the design. Syslog-sign processes all syslog messages, but it generates only two kinds of messages of its own: signature blocks and certificate blocks. A signature block contains some header information, a sequence of hashes from recently-sent messages, and a signature of some kind, and a new signature block is sent each time there have been N new messages whose hashes need to be signed and sent out. A certificate block contains some or all of the information needed to uniquely identify the key being used in these signatures. 2.1. Signature Blocks A signature block contains a signature for a sequence of messages sent by syslog-sign. There are several key points that must be understood before the format of the signature block makes any sense: a. In this document, we refer to the normal syslog messages that aren't generated by syslog-sign as ``messages.'' When we discuss processing messages, we never include signature blocks or certificate blocks in this processing. Expires June 2001 [Page 2] Draft Syslog Sign December 2000 b. The sending device divides the set of messages it will ever send into one or more ``signature groups.'' The maximum number of signature groups allowed is 4095. The only requirement for a signature group is that all messages from that signature group must be routed to the same collector. c. Each time the device starts a new logging ``session,'' e.g. because it has rebooted, it must generate a unique reboot session ID. d. Because we must deal with unreliable delivery, we can't assume that all the messages in this sequence arrived. Therefore, we include the hash of each message sent in this sequence in this signature block. When the logs are reviewed, the messages are hashed and their hashes are found in the appropriate signature block. e. Messages are sent along unaltered. However, each message is assigned a unique identifying number within its reboot session and signature group. Each signature block specifies the number of the first message whose hash is included; the numbers of the succeeding messages are defined by their position in the hash block. f. The signature block is sent in-band, and may legitimately be forwarded through old-style syslog machines. Therefore, it must fit within the requirements of a syslog message. That means it is always less than 1024 bytes, and it contains only printable ASCII characters, and in fact, only the 64 characters used in base 64 encoding. 2.1.1. Signature Block Format The signature block consists of the following fields: a. Cookie -- an eight byte sequence to signal to the verifier that this is a signature block. This sequence is ''@#sigSIG''. b. Version -- a 12-bit quantity encoded in base 64 as two bytes, which effectively specifies the hash function, signature mechanism, and other details of the processing of this signature block. c. Session ID -- a 48-bit quantity encoded in base 64 as eight bytes, which is required to never repeat or decrease over multiple reboots of the sender. Expires June 2001 [Page 3] Draft Syslog Sign December 2000 d. Signature Group -- a 12-bit quantity encoded in base 64 as two bytes, which indicates which signature group this message belongs to. (Each raw message belongs to exactly one signature group, and each signature block includes hashes from only one signature group. Messages from the same signature group MUST ultimately be routed to the same collector, and MUST NOT ever be separated in transmission by any device or relay. e. Global Block Counter -- a 48-bit quantity encoded in base 64 as eight bytes, which is the number of signature blocks sent out by syslog-sign in this reboot session. f. First Message Number -- 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. g. Count -- a 6-bit quantity encoded in base 64 as one byte, which is the number of message hashes to follow. h. Message Hashes -- 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. i. Signature -- a digital signature, encoded in base-64. The original encoding of the signature is effectively specified by the Version field. 2.1.2. Variability of Format The format has a certain amount of flexibility. Some of this is determined by the version, and some, by the device generating the messages based on requested level of redundancy in transmission. 2.1.2.1. Versions and Field Sizes The format has some variability, because different signature schemes and hash functions will alter the size of the fields. The following versions are defined right now: 1 = SHA1 and DSA/320 2 = SHA1 and RSA/1024 3 = SHA1 and RSA/2048 [[ I need to reference some specs for all this. --JMK ]] Expires June 2001 [Page 4] Draft Syslog Sign December 2000 2.1.2.2. Redundancy The sending device has a tunable level of redundancy for the signature blocks. If no redundancy is used, then if a signature block is lost, no messages that were signed by that block can be verified. The more redundancy is used, the more signature blocks must be lost before a message cannot be verified. Redundancy is implemented in a simple way: Each message's hash can be included in more than one signature block. If each message's hash is included in two signature blocks, then only when two successive signature blocks from the same signature groups are lost in transit do we end up with messages we can't verify. If each message's hash is included in three signature blocks, then this can happen only when three successive signature blocks from the same signature group are lost in transit. The signature block specifies the message number of the first message whose hash is included in the block. If each signature block contains 40 hashes, and each successive signature block's first message is 20 messages higher than the previous block's, then each message is signed by two blocks. Note that this is totally decided by the sending device, and that any level of redundancy is supported. Similarly, the only requirement about the number of hashes included in each signature block is that it never be less than one, and that it will never be large enough to cause the signature block to go over 1024 bytes in length. (The field cannot support more than 63 message hashes, but in practice, no more than 37 could appear in a 1024-byte message, ignoring the other header fields and the signature block.) In particular, note that it is legal for the sending device to simply include one signature block per message. 2.2. Certificate Blocks The purpose of a certificate block is provide some support for key management in syslog-sign, by allowing the transmission of a certificate and other identifying information from the sending device. The sending device has a certain initial key management blob to send, which may be a PKIX certificate, or a raw public key, or a key fingerprint. In fact, a syslog-sign device doesn't know anything about this payload except what it's told to report about it during device setup. Expires June 2001 [Page 5] Draft Syslog Sign December 2000 There are three key points to understand about certificate blocks: a. The handle a variable-sized payload, by fragmenting it if necessary, and transmitting the fragments as legal syslog-syslog messages. This payload is expected to be a certificate, but the syslog-sign device does no checking of its format or contents. Its goal is simply to make sure that the payload gets sent along with a log of any reasonable length. b. There is an adjustable parameter for required redundancy, just as in the signature blocks. However, the redundancy functions a little differently. c. Each signature group gets sent its own certificate blocks. 2.2.1. Building the Payload Block Note that we build a payload at the time the reboot session starts, and that payload includes a digital signature. The payload block for this reboot session includes: a. Version -- specifying the hash function and signature used; this is the same version identifier as is used in the signature blocks. b. Reboot Session ID -- the same reboot session ID which will be used in the signature blocks c. IP Address of Sender -- the sender's IP address, a 128-bit number base-64 encoded as 22 bytes. d. Key Blob Type -- this one-byte field holds one of four values: (i) 'C' -- a PKIX certificate (ii) 'F' -- a key fingerprint (the hash of the public key using the specified hash algorithm) (iii)'K' -- the public key whose corresponding private key is being used to sign these messages. (iv) 'U' -- user-specific field with no defined meaning in the standard. e. Key Blob -- the raw data, base-64 encoded. f. Signature -- a digital signature on fields a-e, encoded in base-64. 2.2.2. 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. Expires June 2001 [Page 6] Draft Syslog Sign December 2000 The certificate block is built as follows: a. Cookie -- an eight byte string, ``@#sigCer''. b. Version -- a 12-bit field encoded in base-64 as two bytes. c. Signature Group -- a 12-bit field encoded in base-64 as two bytes. d. Total Payload Length -- a 32-bit field encoded in base-64 as six bytes. e. Index into Payload -- a 32-bit field encoded in base-64 as six bytes. f. Fragment Length -- a 12-bit field encoded in base-64 as two bytes. g. Payload Fragment -- a fragment of the payload, as specified by the above fields. 2.2.3. Redundancy Given the 1024-byte limit on syslog messages, a given payload block can be efficiently divided up into some number, P, of certificate blocks. (It is possible that P==1.) The collector must end up with all P of these blocks to be able to verify that this key was in use at the time of this reboot session. The certificate blocks are sent as follows: a. At reboot, we send all P certificate blocks once for each signature group. These are sent as syslog messages, and they are sent before any other syslog messages are sent in this session. b. After this, we resend the certificate blocks occasionally, based on the redundancy parameter R. For each signature group, each time another R messages are sent for that signature group, we send along the next certificate block. Note that this requires that we keep track of which certificate block we're on, for each signature group. If R==0, then we never resend the certificate block. (This would make sense if we were using syslog-sign over syslog-reliable.) 3.0. Offline Review Reviewing the stored logs offline now becomes straightforward. a. Verify that the next reboot session ID is valid, e.g., is larger than the previously seen reboot session IDs. Expires June 2001 [Page 7] Draft Syslog Sign December 2000 b. Go through the log entries with this session ID, and pull out each of the certificate blocks. Reassemble the payload block, and make whatever use of it is desired. c. If more than one signature group appears in the logs, process each group separately as follows. d. For each signature block: (i) Verify the signature at the end of the block. If the signature verifies successfully, then continue processing. (ii) Determine what message numbers we're receiving based on the appropriate fields in the signature block. (iii)For each hash in the hash block, look in the nearby messages for a message with the same hash. If a message is found, then add that message, along with its message number, to the list of verified messages for this session ID and signature group. e. When the processing is done, sort the list of verified messages for this session ID and signature group on the message numbers. Eliminate duplicate message numbers, and the result is a verified log file, complete with gaps in the message numbers where there are gaps in the received messages. 4 Acknowledgements The author wishes to thank Alex Brown, Chris Calabrese, Jon Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin New, Marshall Rose, Holt Sorenson, and the whole bunch of Counterpane engineering and operations people who commented on early or late versions of this proposal. 5 Bibliography A Author's Address John Kelsey Counterpane Internet Security kelsey.j@ix.netcom.com Expires June 2001 [Page 8] Draft Syslog Sign December 2000 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. Expires June 2001 [Page 9]