Internet Engineering Task Force Syslog Internet Draft John Kelsey draft-ietf-syslog-auth-00.txt Expires: June 2001 Syslog-Auth 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-auth, an attempt to add origin authentication, message integrity, replay-resistance, message sequencing, and missing message detection to syslog, while continuing to allow the use of UDP for syslog messages. Syslog-auth supports many different setups for syslog devices, relays, and collectors. Syslog-auth should be implemented on all devices, relays, and collectors being used together. 1. Introduction The current syslog protocol sends syslog messages over various unsecured networks, with no mechanisms for ensuring anything about the messages that eventually arrive and are stored. It also provides no mechanisms for storage security. In this note, I describe syslog-auth, a lightweight mechanism for providing authentication of syslog messages sent over an insecure network, between a sender and receiver which share a secret key. The goals of this mechanism are: a. To provide the best over-the-wire security possible between pairs of syslog-auth machines that share a key. This means allowing the receiver to detect alterations, deletions, insertions, and replays in the sequence of syslog-auth messages from a sender in real time if resources permit, and during offline analysis if resources are too tight on the receiver. b. To build in mechanisms to provide some level of storage security for logs generated by syslog-auth machines, when they are stored anywhere but on the machine that generated them. Expires June 2001 [Page 1] Draft Syslog Auth December 2000 c. To build in mechanisms to allow a ``best try'' of providing storage security on syslog-syslog receivers. (That is, on old-style receivers doing nothing but plain old syslog.) d. To NEVER cause a syslog-syslog receiver to crash or drop messages because they're too long, and to NEVER leave syslog-auth data at the end of a message that can't be unambiguously identified as either syslog-auth data or original message text data. e. To combine with reliable delivery mechanisms (e.g., syslog-reliable in RAW mode) to provide even stronger guarantees for both over-the-wire and storage security. 1.1. Resource Requirements Our resource assumptions are as follows: a. The sender's machine may be very limited in its resources. It must have a small amount of persistent storage to keep its shared key with the receiver, and a small amount of RAM which is kept for reasonable lengths of time. It must also be capable of computing a cryptographic hash function over the data it sends out as syslog messages. Senders that lose all their RAM state (e.g., reboot) once per message and have no clock, persistent storage, or reboot counter are not likely to benefit much from this mechanism. b. The receiver's machine is assumed to be much less limited. In general, its problem will be assumed to be keeping up with many senders at once. c. We assume that we have a shared secret key between the sender and receiver. How the key got shared is beyond the scope of this note, but the key did, in fact, get shared. This key includes both raw key data, and some indication of what cryptographic authentication scheme is to be used with that key. d. In this note, I assume no cryptographic mechanisms available except md5. 2. Syslog-Auth Message Format The syslog-auth message format consists of the text of the original syslog message (called the message text from now on), concatenated with an authentication block. This block contains all the information necessary to verify the origin, integrity, and freshness of this message. It may also contain additional useful information. Expires June 2001 [Page 2] Draft Syslog Auth December 2000 2.1. General Formatting Issues A syslog-auth message is intended to go from a syslog-auth enabled sender to a syslog-auth enabled receiver. A receiver that doesn't understand syslog-auth will have no way to use the authentication block, and for very long message texts, won't even see the authentication block. It may be that a sender sends out all messages using syslog-auth. In this case, syslog-auth receivers that share a key with it can make use of the authentication blocks, and old-style syslog receivers will have no harm done by the messages, other than receiving longer messages. All information in syslog-auth is kept in ASCII printable format, and all cryptographic information appears at the end of the syslog message, after the original message text. Cryptographic information is always contained in an "authentication block." A syslog-auth message sent to a syslog-auth receiver may have either one or two authentication blocks. A syslog-auth message sent to an old style receiver may have zero, one, or two authentication blocks. Note that whenever a message is truncated for sending to an old-style receiver, each authentication block is either left intact or entirely deleted. When a new syslog-auth message is generated and sent to a syslog-auth receiver, it will have one authentication block. If the message is forwarded to another syslog-auth receiver, it will end up with both the original authentication block and a block by the forwarder. However many times the message is forwarded, it always keeps its original authentication block and an authentication block from the most recent forwarding machine. As will be discussed below, when a machine forwards a syslog-auth message, it strips off the previous forwarder's block, generates a new authentication block, and appends its new authentication block. The forwarder often borrows some fields from the previous forwarder's block to build its own. The format of a syslog-auth message is thus syslog-auth message = message-text + authentication blocks 2.2. Base 64 Encoding In the following description, we assume base-64 encoding for various fields. This is to be done according to RFC-2045. Expires June 2001 [Page 3] Draft Syslog Auth December 2000 2.3. The Authentication Block Format The authentication block always appears at the end of the syslog-auth message. Its fields always appear in the following order, including optional fields that may not appear at all in most messages. I've listed the range of lengths of these fields using base 64 encoding. a. Transmission MAC Block (Required; 27 bytes) b. Storage MAC Block (Optional; 27 bytes) c. Forwarding Block (Optional; 9 bytes) d. Destination Message Counter (Optional; 8 bytes) e. Global Message Counter (Required; 8 bytes) f. Reboot Session ID (Required; 8 or 16 bytes) g. Flags (Required; 2 bytes) h. Version (Required; 2 bytes) i. Cookie (Required; 8 bytes) Note that the block is intended to be parsed from last field backwards. Also note that the maximum possible length for a single authentication block is 123 bytes. 2.2.1. Transmission MAC Block (27 bytes) The transmission MAC block consists of two parts: the key ID and the MAC. All syslog-auth key IDs are 96 bits wide (encoded as 16 characters in base 64), and are computed by the formula: Key ID = low96(hmac_md5_{K}("KEYID")) All syslog-auth MACs are 64 bits wide (encoded as 11 characters) and are computed by the formula: MAC_{K}(X) = low64(hmac-md5_{K}(X)) In the transmission MAC block, the key ID used is (naturally) that of the key used to generate the MAC. The MAC is computed over the whole message text concatenated with the whole authentication block, exactly as it will appear in the final message except with the transmission MAC field set to eleven characters of ASCII zeros. The purpose of the transmission MAC block is to: a. Identify which key is being used for the receiver. b. Authenticate the contents of the message, as well as its freshness and its position in the sequence of messages being sent by this sender. 2.2.2. Storage MAC Block (27 bytes) The storage MAC block consists of the storage MAC key ID and the storage MAC. The key ID used is (naturally) that of the key used for storage security. The MAC is always computed over the original Expires June 2001 [Page 4] Draft Syslog Auth December 2000 message text concatenated with the first authentication block held by the message, with all MAC fields set to eleven characters of ASCII zeros. Note that this happens even if the storage MAC is being computed by a forwarding machine several hops after the message was generated; the MAC is only computed over that original message and first authentication block, with all its MAC fields set to blocks of ASCII zeros. The purpose of the storage MAC block is to allow the use of a second key for storage security. This is necessary since a syslog-auth receiver with the key to a MAC stored can't use that key to provide any additional storage security. 2.2.3. Forwarding Block (25 bytes) This block is used only when the message is being forwarded, and the sender wishes to inform the receiver of this fact. It has three components: a. Flags (1 byte, encoding 6 bits) numbered 5-0: (i) Secure Path bit (bit 5) -- set if message has traveled over syslog-auth for its whole life. (ii) Replay Resistant bit (bit 4) -- set if every forwarder that has forwarded this message is sure this is not a replayed message. (See the section on forwarding issues to see why this is important.) (iii) Reserved (bits 2-0) -- reserved for later use, MUST be zeros now. b. The IP address of the first syslog-auth sender or forwarder, 128 bits, base-64 encoded as 22 characters. c. The number of times this message has been forwarded, 0-4095, encoded as two base-64 characters. The forwarding block is only used when a message is being forwarded, and it can only appear when it is indicated by the right flag. 2.2.4. Destination Message Counter (8 bytes, base 64 encoded) This is a counter incremented only for messages the sender knows are going to the same destination. It is 48 bits wide in its raw format. 2.2.5. Global Message Counter (8 bytes, base 64 encoded) This is a counter which is incremented and included for each syslog-auth message sent out since its last reboot. It is 48 bits wide in its raw format. Expires June 2001 [Page 5] Draft Syslog Auth December 2000 2.2.6. Reboot Session ID (8-16 bytes, base 64 encoded) The reboot session ID can have one of three sources: a. It can be a fixed value that never changes, though this typically allows no replay resistance. b. It can be generated pseudorandomly, but this means that it needs to be 96 bits long. c. It can be based on something guaranteed always to increase in value, such as the timestamp of the last reboot. It's very important to note that this allows a receiver to immediately detect any replay attempt. This value is always 48 bits long. Its only requirement is that a later reboot session ID MUST always be greater than an earlier reboot session ID. 2.2.7. Flags (2 bytes, base 64 encoded) The flags take up 12 bits in their raw format, and are represented by two base-64 characters. Numbering from 11-0, these are: a. Destination Counter (bit 11): This indicates whether the optional destination message counter is included in this message. A zero bit means there's no desitination message counter. b. Superincreasing Session ID (bit 10): This indicates whether the session ID is guaranteed to always increase over time (so that replayed session IDs can be recognized by the fact that they have lower values than recently seen session IDs), or whether the session ID is pseudorandom. A one bit means the session ID is superincreasing. d. Temporary Reboot Session ID (bit 9): This indicates whether this session ID is a temporary one. This is used when a sender has to wait for its PRNG to become available, or to accumulate the running hash of some limited number of messages, before it can generate a reboot session ID that it overwhelmingly likely to be unique. When this bit is set to one, the reboot session ID MUST be 0. e. Replay Vulnerable (bit 8): This bit indicates whether the replay session ID may be repeated in different sessions. If this bit is set, then the message has no replay protection right now. This may be a temporary situation (e.g., when we're using a temporary reboot session ID) or permanent (e.g., when the sender can't generate any kind of unique session ID). f. Forwarding Block (bit 7): This bit indicates whether the forwarding block is present in this message. Expires June 2001 [Page 6] Draft Syslog Auth December 2000 g. Storage MAC (bit 6): This bit indicates whether the storage MAC is present in this message. h. Old Style Receiver (bit 5): This bit is set when the sender believes it is sending to an old-style receiver. i. Reserved (bits 4-0): These bits must be zero at present, and may be used in the future to indicate new things. 2.2.8. Version (2 bytes, base 64 encoded) The version is twelve bits raw. I don't expect the version to *ever* change, but if it does, then all the other fields may change. The current version is 1. A receiver at version M MAY be able to understand lower versions, but this is not required, since lower versions may be known to be insecure. A receiver below the version of the sender cannot make any use of the syslog-auth authentication block at all. 2.2.9. Cookie (8 bytes) The cookie is an eight character string that occurs at the *end* of the syslog-auth message, signaling that it is a syslog-auth message, rather than an old-style syslog message. There's no special reason to use "authAUTH", and the choice has no security relevance--its purpose is simply to give receivers who must process both old style and syslog-auth messages a simple way to distinguish them, with a very low rate of false identification. Note that falsely identifying an old style message as a syslog-auth message will never cause the receiver to misidentify the message for long, since there won't be a valid MAC for this message. 2.2.10. Length of Messages The longest possible syslog-auth message (including forwarding, as described in detail below) will include a 1024-byte message text, and two 109-byte authentication blocks, and thus a total length of 1133 bytes. A normal syslog-auth message should have about 57 bytes of authentication block when there is no forwarding going on, and 123 bytes with forwarding. 3. Key Management Issues In this document, managing the keys outside the senders, forwarders, and receivers is the responsibility of the user of the system. However, in this section, we discuss: a. Our general philosophy of how keys ought to be managed for this system. Expires June 2001 [Page 7] Draft Syslog Auth December 2000 b. Some ideas of ways that keys may be managed that will scale reasonably well. c. Some tools for managing keys on syslog-auth devices. 3.1. The Basic Scheme: One Key Per Sender/Receiver Pair. This is the cleanest way to manage the keys. Somehow, we distribute a shared key to each sender and receiver, in such a way that each receiver has a different key for each sender it's receiving from, and each sender has a different key for each receiver it's sending to. This has good security properties, since compromise of one sender leads only to the compromise of logs sent by that sender, and compromise of one receiver leads only to the compromise of logs received by that sender. However, we now have the problem of distributing all those keys securely. Consider a set of syslog-auth machines, which are all "owned" by the same entity and communicate with one another. Let's call the entity that owns all these machines the administrator. Also, let's assume that each machine has an IP address, and knows the IP address of all machines it communicates with over syslog-auth. We now have the following trick for simplifying key management: a. The administrator has a master key, K_{master}, which is stored securely somehow. This key could be a passphrase, though it should be a very long one. The key is an hmac-md5 key. b. Each syslog-auth machine has its own device key, K_{device}. This key has to be given to the device by the administrator. The administrator generates a device's key as: K_{device} = hmac-md5_{K_{master}}(Device's IP address). c. Each machine knows the IP addresses of machines it is going to be sending to. The keys of these machines are generated as: K_{sender,receiver} = hmac-md5_{K_{sender}}(receiver's IP address) where K_{sender} is K_{device} for the sender. d. Storage MAC keys are derived as K_{sender,STORAGE} = hmac-md5_{K_{sender}}("STORAGE") e. This reduces the key management problems to: (i) Loading the secret key for a device onto that device securely during installation or change of IP address. (ii) Loading K_{sender,receiver} onto a receiver securely. Expires June 2001 [Page 8] Draft Syslog Auth December 2000 Note that the administrator can always generate any key in the system in this scheme. This means that if the administrator's key is compromised, the whole set of keys have to be changed, and until they are, all syslog-auth security is lost. Similarly, if the administrator's key is lost, the whole system must be rekeyed. If would also be possible to use this kind of a scheme in a network where some devices have variable IP addresses. In this case, we'd give each device a unique serial number, and use the serial number in place of the IP address. So long as "STORAGE" remains an invalid serial number, the scheme will work fine. Along with making the key management simpler, this scheme decreases the memory needed for a single sender who must send to many receivers. The sender can compute the key for each receiver on the fly based on their IP address. 3.2. Some Less Useful Key Management Options There are several alternatives for key managemtent in syslog-auth. Here, I describe three methods that may be useful in some limited environments, but which have major security problems. 3.2.1. One Key per Sender A simpler way to manage keys is simply to give each sender a unique key, and share that key with all receivers that must receive messages from the sender. This is slightly simpler to manage than the scheme described above, but it has a major security problem: If one machine that receives messages from a given sender is compromised, the attacker can alter or make up new messages from that sender to all its other receivers, without being caught by syslog-auth. In this case, each sender that also includes a storage MAC in its messages MUST have a unique storage MAC key, which is not shared by anyone else on the network. 3.2.2. One Key per Receiver Another simple way to manage keys is simply to give each receiver a unique key, and share that key with all senders who will send to a given receiver. This has the same kind of security problem as the above scheme--compromise of one machine sending to a given receiver lets the attacker successfully impersonate all other senders to this receiver. Even worse, if the sender is sending messages to many receivers, then an attacker who compromises that sender will be able to generate fake messages or alter messages in transit from any sender to any of those receivers. In this case, each sender that does storage MACing MUST have its own unique storage MAC key. Expires June 2001 [Page 9] Draft Syslog Auth December 2000 3.2.3. Global Shared Key The simplest method of doing key management is to give all syslog-auth devices under the same administrator the same key. This has the advantage that key management is made very simple, and the disadvantage that compromising a single machine with syslog-auth installed allows an attacker to make up or alter messages to and from all other syslog-auth machines using that key. In this case, each sender that does storage MACing MUST have its own unique storage MAC key. 4. Sending Syslog-Auth Messages 4.1. Overview In this section, we discuss the operations of a syslog-auth sender. We expect the majority of machines implementing syslog-auth to be doing nothing but sending messages out. The requirements for the process of sending messages: a. It must be possible to send messages out properly based only on information the sender has available. b. It must be possible to send messages out with minimal available resources on the sender. c. It must be reasonably computationally cheap to generate and send syslog-auth messages. 4.1.1. Resources The sender MUST have the following resources: a. Shared keys with all its intended syslog-auth receivers. b. RAM in which to store a reboot session ID and a counter. c. The ability to compute MACs and hashes. d. Some way to generate reboot session IDs, which may include: (i) Pseudorandom generation (ii) Superincreasing generation (iii)Fixed session ID Expires June 2001 [Page 10] Draft Syslog Auth December 2000 4.2. Setup and Configuration The sender is told somehow where to send each kind of log message, and is somehow given shared keys to use with any available syslog-auth recipients in its list of machines to send messages to. The mechanisms to do this are generally outside the scope of this note. In the remainder of this section, we will assume the following: a. Any storage MAC keys that are to be used have been loaded onto the sender somehow. b. The sender knows where to send each kind of syslog message, and has shared keys for any of the designated receivers that are equipped to handle syslog-auth messages. 4.3. Reboot Sessions Occasionally, the operations of the sender are disrupted somehow, and it loses the memory of its message counters. We call this event a reboot, though it may or may not correspond to the physical operation of a reboot. Some senders may *never* have a reboot of this kind, while others may reboot several times a day. A reboot session ID must be generated in one of the following ways, with the specified implications for the message flags. a. Superincreasing -- session IDs of 48 bits chosen in a way that guarantees that the session ID will never repeat or decrease in successive reboot sessions. b. Pseudorandom -- session IDs of 96 bits chosen pseudorandomly, and very unlikely to ever repeat in the lifetime of a sender and his key. (If the sender has 2^{32} reboots in its lifetime, the probability of a single collision is about 2^{-33}. If the sender reboots ten times a day for a lifetime of about eighteen years, it will reach 2^{16} reboots in its lifetime, and thus will have a probability of about 2^{-65} of colliding.) c. Fixed -- session IDs that are 96 bits of binary zeros. This kind of session ID is chosen when a pseudorandom session ID hasn't yet been generated, and may be used for some senders that can't generate any variable session ID. 4.3.1. Superincreasing Session IDs The best way to generate reboot session IDs is to guarantee that if we have two IDs, X and Y, and X was generated before Y, then X < Y. This allows the receiver to put reboot session IDs in sequence, and thus to very efficiently determine whether a message with a new session ID is a replay attempt. Expires June 2001 [Page 11] Draft Syslog Auth December 2000 Many devices have an internal clock. Others have some persistent read/write storage in which to store a persistent counter. Still others have a reboot counter available. Any of these can be used to generate superincreasing reboot session IDs. Syslog-auth has no requirement for how these resources (or others) are used to set the reboot session ID. The only requirements are: a. The Superincreasing Session ID flag MUST be set, and the Replay Vulnerable flag MUST be cleared. b. The session ID MUST be 48 bits. c. If there are two session IDs generated at different times, the one generated later MUST be greater than the one generated earlier, when the two session IDs are treated as 48 bit unsigned integers. I don't know whether there will be any devices that use this, but it's legitimate for a system which never "reboots" (that is, never loses track of its message counters) to make use of a permanent fixed session ID, and still set the Superincreasing Session ID flag. This represents a situation in which we have replay resistance despite a fixed reboot session ID. In this case, the reboot session ID can be any fixed value except a block of binary zeros. The messages sent will always satisfy the requirement that no later message will have a smaller reboot session ID. 4.3.2. Pseudorandom Session IDs Senders that do not have access to a clock, persistent storage across reboots, or a reboot counter may have to generate reboot session IDs pseudorandomly. It is legitimate to do this by generating a cryptographically strong 128 bit random number, but I don't expect there to be any sender devices in practice that don't have any of those other things, but which do have a really good RNG or PRNG. I emphasize: C compiler PRNGs MUST NOT be used to generate these reboot session IDs. The standard way I expect for senders to generate reboot session IDs in this case is as follows: a. Initialize the reboot session ID to a fixed 128-bit block of binary zeros. b. Set the Temporary Reboot Session bit and the Replay Vulnerable bit and clear the Superincreasing Session ID bit. c. Decide on a number of messages, N, after which it is overwhelmingly likely that we will have a unique message sequence --that is, that this precise sequence of messages has never been generated from this sender before, and never will again. d. Initialize an md5 hashing context. Expires June 2001 [Page 12] Draft Syslog Auth December 2000 e. For each message sent, feed the message text into the md5 hashing context. If there is an internal clock (e.g., clock ticks since reboot) available on the sender, hash that value in as well. f. After the sender has sent its Nth message, it does the following: (i) Hashes in any additional information that might be unique for this reboot session, such as an internal clock, status flags, etc. (ii) Computes the final hash value from all this information that's been fed into that md5 hashing context. (iii)Sets the reboot session ID to that md5 output value. (iv) Clears the Temporary Reboot Session flag and the Replay Vulnerable flag. (v) Leaves the global message counter and destination counters to increment just as they would for any other message. We don't specify N in this document. However, N MUST be chosen in such a way that the reboot session ID is different for every reboot session. 4.3.3. Temporary Session IDs This is simple enough that there is little to discuss about it. The session ID is set to 96 bits of binary zeros, the Replay Vulnerable flag is set, the Temporary Session ID is set, and the Superincreasing Session ID flag is cleared. 4.4. Building a Syslog-Auth Message The sender builds a Syslog-Auth message one field at a time, in order, as follows: 4.4.1. Cookie (Required; 8 bytes) The cookie value is set to ``authAUTH'' for all authentication blocks. 4.4.2. Version (Required; 2 bytes) The version field is filled in. Note that this field is base-64 encoded, as described above, and so represents a number between 0 and 4095. The current version is version 1. Expires June 2001 [Page 13] Draft Syslog Auth December 2000 4.4.3. Flags (Required; 2 bytes) The flags are set as follows: a. Destination Counter (bit 11): If this sender is including the optional Destination Counter field, then this bit is set, otherwise it is cleared. b. Superincreasing Session ID (bit 10) c. Temporary Reboot Session ID (bit 9) d. Replay Vulnerable (bit 8): These bits are set as indicated earlier in this section, in the discussion of different ways to derive reboot session IDs. e. Forwarding Block (bit 7): For messages being sent (not forwarded), this bit will always be cleared. In the section on forwarding, below, we will discuss cases where this bit is set. f. Storage MAC (bit 6): This bit is set if the sender is including the optional storage MAC block in this message. g. Old Style Receiver (bit 5): This bit is set if the sender believes it is sending to an old-style receiver. h. Reserved (bits 4-0): These bits are all set to zero at present. 4.4.4. Reboot Session ID (Required; 8 or 16 bytes) This value is set as described above. The raw value of the session ID is either 48 or 96 bits; that value is then base 64 encoded. 4.4.5. Global Message Counter (Required; 8 bytes) This value is set to the number of all messages that have been sent so far in this reboot session by this sender. Note that the current reboot session and global message counter on a sender are used for all receivers. It is a 48-bit number that is base-64 encoded as 8 bytes. 4.4.6. Destination Message Counter (Optional; 8 bytes) If this value is included, it is set to the number of messages in this reboot session sent to this receiver so far. It is a 48-bit number that is base-64 encoded into 8 bytes. Expires June 2001 [Page 14] Draft Syslog Auth December 2000 4.4.7. Forwarding Block (Optional; 9 bytes) This field is never included in a message that's just being generated. The format and settings in this field are discussed in the section on forwarding, below. 4.4.8. Storage MAC Block (Optional; 27 bytes) If this field is included, it will carry two subfields: a. A 96-bit key ID, base-64 encoded as 16 bytes. b. A 64-bit MAC, base-64 encoded as 11 bytes. The key ID is a hash of the secret storage MAC key used by this sender. It is computed by taking Key ID = low 96 bits( hmac_md5_{K}("KEYID") ). The MAC is computed as: MAC = hmac-md5_{Key}( message-text, A) where A = the authentication block, with all MAC values set to ASCII "00000000000", but key IDs and all other stuff left unchanged. Note that in forwarded messages, storage MACs are computed using the *original* authentication block. In forwarded non-authenticated messages, no authentication block is included in the MAC. 4.4.9. Transmission MAC Block (Required; 27 bytes) This field also carries two subfields: a. A 96-bit key ID, base-64 encoded as 16 bytes. b. A 64-bit MAC, base-64 encoded as 11 bytes. The key ID is a hash of the MAC key used by this sender when sending to this receiver. It is computed by taking Key ID = low 96 bits( hmac_md5_{K}("KEYID") ). The MAC is computed as: MAC = hmac-md5_{Key}( message-text, A') where A' = the authentication block, with the transmission MAC value set to ASCII "00000000000", but key IDs and all other stuff left unchanged. Note that the storage MAC value will be authenticated by this MAC. Expires June 2001 [Page 15] Draft Syslog Auth December 2000 4.5. Sending to Old-Style Receivers If possible, a sender will know whether it shares a key with a given receiver. If not, it MUST assume that this receiver is an old-style receiver. When a syslog-auth sender is sending to an old-style receiver, it MUST make sure all messages sent are less than or equal to 1024 characters in length. There are only two ways a message may be shortened before being sent off: a. If it has two authentication blocks (e.g., if it's a forwarded message), we can cut off the last one and try to fit the resulting message. b. If that doesn't cut the message down to 1024 or fewer bytes total, we cut off all authentication blocks. This will cause some messages to arrive at their final destinations with no authentication messages, when the last one or more receivers of a message like this are old-style receivers. Note that in no case do we ever leave part of an authentication block. Either the whole authentication block is left, or the whole authentication block is deleted. (The alternative would be to leave random meaningless blobs of bits at the end of long syslog messages, which could not be distinguished from the original message text except by context.) 5. Forwarding Syslog-auth has a mechanism to make it clear when we're dealing with forwarded messages, and what we can guarantee about them cryptographically. These lead to a fairly simple set of mechanisms for handling forwarded messages, which retain important context about these messages. Whenever a syslog-auth message is forwarded, the forwarder appends its own authentication block to the message. To avoid having message keep expanding as they're forwarded, the original sender's authentication block is left untouched, but when an already forwarded message is forwarded again, the previous forwarder's authentication block is stripped off, and replaced with the current forwarder's authentication block. The goal here is to allow future receivers of the message to know exactly what can and cannot be promised about the message. This means: a. Whether the message has been sent and forwarded only through syslog-auth machines, or whether some of the hops the message has traveled have been unauthenticated. b. Whether all the forwarders have been able to implement online replay detection on this message. Expires June 2001 [Page 16] Draft Syslog Auth December 2000 c. The entry point of the message into the chain of one or more syslog-auth forwarders. d. How many hops the message has made so far. All of this is included in the forwarding block, which is contained inside the forwarder's authentication block. A forwarding block MUST be included in the forwarder's authentication block, and MUST NOT be included in the message's original authentication block. Note that when a message is forwarded to an old-style receiver, all its authentication information is treated as just part of the message text. Similarly, when a message is received from an old-style sender or forwarder, the receiver treats the whole message text like nothing but message text; it does not treat it as being a syslog-auth message, even if that message text contains an authentication block! This is necessary, since the receiver will generally have no shared key with the original sender, and so can't trust anything it would find in a previous sender's authentication block. This is the only way a syslog-auth message could end up with more than two authentication blocks. Consider the really weird case where a message goes from a syslog-auth sender to a syslog-auth forwarder to an old-style forwarder, and then to another syslog-auth forwarder. Assuming the original message text is not too long, the last forwarder will receive an unauthenticated message whose text contains two authentication blocks. However, the whole message text will be treated as unauthenticated, and a new authentication block will be appended at the end. It's possible to contrive cases where a very short syslog message is forwarded through alternating syslog-auth and old-style forwarders, and thus ends up with eleven authentication blocks. However, note that this leaves no ambiguity; each authentication block will clearly specify where it came from, and since long messages are never sent to old-style receivers, we will never allow messages to get longer than our maximum syslog-auth length. 5.1. Building the New Authentication Block A forwarder is forwarding messages, using syslog-auth. In this subsection, we describe how the forwarder builds the forwarding block, and thus the authentication blocks, which it uses to forward this message along. We can break the forwarder's task into three cases: Forwarding unauthenticated messages, forwarding authenticated messages that haven't been forwarded before, and forwarding authenticated messages that were forwarded to us. Note that the forwarder must parse, verify, and process authentication blocks just as the receiver must. In the rest of this section, we assume the forwarder has already done everything it would have to do as a receiver, including drawing conclusions about received messages before forwarding them. Expires June 2001 [Page 17] Draft Syslog Auth December 2000 5.2.2. Unauthenticated Message When an unauthenticated message arrives at the forwarder, the whole message text is treated as the original message text for this message. If the sender complies with the syslog standard, this message will be less than 1024 bytes long; if not, the message text is truncated to 1024 bytes before any further processing is done on it. The forwarding block has four fields, and they are set as follows: a. The Secure Path bit, set if the message has traveled over syslog-auth for its whole life. This bit is set to zero, since the message arrived here without any authentication. This is true even if the message was previously forwarded, and has a forwarding block; none of that information can be verified at this forwarder, so it is not relevant or useful. b. Replay Resistant bit, set if every forwarder that has forwarded this message is sure this is not a replayed message. This bit is set to zero, since there's no way to verify that a message arriving unauthenticated isn't a replayed or spoofed message. c. The IP address of the first syslog-auth sender or forwarder in this sequence of forwards. This is filled in with the forwarder's IP address, since this is the first IP address which can actually be known to be correct. d. The number of times this message has been forwarded, 0-4095, encoded as two base-64 characters. This is set to 1, by definition, since this is the first time this particular message text has been forwarded. 5.2.1.1. The Rest of the Authentication Block The rest of the authentication block is set exactly as though this message were being originally sent by the forwarder, with only two exceptions: The Forwarding Block bit in the Flags field is set to one, and the Forwarding Block is included in the authentication block. The whole original message is treated as message text. 5.2.2. Authenticated Messages on First Hop When an authenticated message arrives at the forwarder without a forwarding block, we build its forwarding block as follows: a. The Secure Path bit, set if the message has traveled over syslog-auth for its whole life. This bit is set to one. Expires June 2001 [Page 18] Draft Syslog Auth December 2000 b. Replay Resistant bit, set if every forwarder that has forwarded this message is sure this is not a replayed message. This bit is set to a one if: (i) The Replay Vulnerable bit in the arriving message's authentication block is 0. AND (ii) The forwarder is implementing online replay detection for this kind of message. Otherwise, the bit is cleared. c. The IP address of the first syslog-auth sender or forwarder in this sequence of forwards. This field is set to the IP address of the sender. d. The number of times this message has been forwarded, 0-4095, encoded as two base-64 characters. This is set to 1, by definition. (When the receiver gets this message, it will have been forwarded once.) 5.2.2.1. The Rest of the Authentication Block The rest of the authentication block is set exactly as though this message were being originally sent by the forwarder, with only three exceptions: a. The Forwarding Block bit in the Flags field is set to one. b. The Forwarding Block is included in the authentication block. c. If the forwarder generates a storage MAC, it is done exactly as described in the section on sending syslog-auth messages, above, but the authentication block used is the original message's authentication block, not the one generated by the forwarder. Because forwarders' authentication blocks are stripped off by subsequent forwarders, the storage MAC cannot be based on any part of the forwarder's authentication block. 5.2.3. Authenticated Message, Additional Forwards There is no inherent limit to how many times a message may be forwarded, though syslog-auth supports only allowing a message to be forwarded 4095 times. I don't expect this limit to ever become relevant in practice unless messages are being forwarded in an endless loop. However, syslog-auth forwarders MUST NOT forward a message more than 4095 hops. Expires June 2001 [Page 19] Draft Syslog Auth December 2000 When we forward a message that has already been forwarded to us through syslog-auth, we build a new forwarding block based heavily on the old forwarding block. We do this as follows. Note that we always reference the fields of the last authentication block appended to the message. a. The Secure Path bit, set if the message has traveled over syslog-auth for its whole life. This bit is set to the value of the Secure Path bit in the message we received. b. Replay Resistant bit, set if every forwarder that has forwarded this message is sure this is not a replayed message. If this forwarder is able to guarantee that this message is not being replayed from the previous forwarder (e.g., if it is able to implement online replay detection), and if the previous forwarder set this bit, then the current forwarder sets it. Otherwise, the bit is cleared. c. The IP address of the first syslog-auth sender or forwarder in this sequence of forwards. This value is copied to the new forwarding block unchanged. d. The number of times this message has been forwarded, 0-4095, encoded as two base-64 characters. The forwarder takes this value, increments it by one, and checks to see if the result is greater than 4095. If so, the message MUST NOT be forwarded, but may be stored, discarded, or otherwise processed. Otherwise, the new value is copied into the same field in the new forwarding block. 5.2.3.1. The Rest of the Authentication Block In the case of multiply-forwarded messages, we *replace* the authentication block appended by the previous forwarder with our own. In doing this, we generate an authentication block exactly like we would if we were sending this message ourselves, with three exceptions: a. The Forwarding Block bit in the Flags field is set to one. b. The Forwarding Block is included in our authentication block. c. If there is a Storage MAC field in the authentication block we're replacing, we copy that field into our own authentication block. This is true even in the case that we would normally generate a Storage MAC of our own; in that case, there's simply no room for our Storage MAC, and so it isn't included. Note that when a storage MAC field is computed on a forwarded message, it is computed over only the original message text and the first authentication block; its computation never includes any of the forwarder's authentication block, since that block may be stripped off. The storage MAC is computed exactly as described in the section on sending syslog-auth messages, above, with the authentication block involved being the first authentication block. Expires June 2001 [Page 20] Draft Syslog Auth December 2000 6. Receiver-Side Issues Everything the receiver does with regard to syslog-auth is intended to accomplish the following goals: a. Provide as much real-time information about the logs being received as possible. Whenever possible, we would like to be able to give applications processing these log messages in real time enough information to decide whether this message might be a replay, or whether we can even promise the identity of the sender and the integrity of the message. This is particularly important to allow receivers to resist flooding attacks, by discarding replay-vulnerable messages when the disk is nearly full. b. Provide enough information in the stored logs that a person or program reviewing these logs (i) Has as much information as possible about the log messages stored here, and any missing messages. (ii) Knows unambiguously what can be determined from the log messages stored here about these things. These two goals are the only reason to bother with security for log files in the first place. In this section, we discuss providing online information where possible, and storing auxillary information about a stored log file to aid in offline reviewing of the logs. In the next section, we discuss techniques for using that auxillary information to review stored logs offline. As a rule, message origin and integrity can be detected in real time for all syslog-auth messages, replays can be detected in near real time for some syslog-auth messages by some syslog-auth receivers, and gaps in messages can sometimes be detected offline using one receiver's logs, and in special cases, may be detectable in near real time for some senders and receivers. Even more critical than allowing receivers and reviewers of log messages to detect gaps and replays and such, is making it absolutely clear to a receiver or reviewer (which may be a computer program) what can and can't be determined from available data. 6.1. Description of Steps of Receiver Processing This section discusses the steps of processing a received syslog-auth message: a. Detect the syslog-auth message. b. Parse it into its fields, and verify its integrity. c. Process the fields, drawing conclusions about the status and security of the message. Expires June 2001 [Page 21] Draft Syslog Auth December 2000 d. Apply those conclusions, either through writing them to an auxillary log file, noting them in some other way associated with the log file, or changing some of the flags and fields used in forwarding this message. Note that forwarded messages will generally have two authentication blocks. The last authentication block allows us to verify information from the last forwarder to see the message if it is forwarded, or the original sender if it is not forwarded. In general, we will share a key only with the last forwarder, not with the original sender of a forwarded message. If we share a key with the original sender of a forwarded message, we can check the original authentication block of the message as well as the last authentication block. In general, though, we will only check the last authentication block, since that's the only one we will have the key material for. 6.1.1. Notation We will use the following notation in the rest of this section: M is the syslog message. M[i] is the ith byte in the message. M[-i] is the ith byte from the end of the message. M[i..j] is the string from the ith to the jth byte of M. M[-i..-j] is the string from i characters before the end of the string to j characters before the end of the string. Thus, if M = "Hello, world!", then: M[0] = 'H' M[4] = 'o', M[-1] = '!' M[-5] = 'o'. M[2..4] = "llo," M[-3..-1] = "ld!" Expires June 2001 [Page 22] Draft Syslog Auth December 2000 A is the authentication block data structure, which has fields for all the possible fields in the authentication block. The fields are denoted as follows: A.cookie A.version A.flags A.flags.destinationCounter A.flags.superincreasingSessionID A.flags.temporaryRebootSession A.flags.replayVulnerable A.flags.forwardingBlock A.flags.storageMAC A.flags.oldStyleReceiver A.transmissionMAC A.transmissionMAC.keyID A.transmissionMAC.MAC A.sessionID A.globalCounter A.destinationCounter A.forwardingBlock A.forwardingBlock.flags A.forwardingBlock.flags.securePath A.forwardingBlock.flags.replayResistant A.forwardingBlock.entryPoint A.forwardingBlock.hopCount A.storageMAC A.storageMAC.keyID A.storageMAC.MAC 6.2. Detecting, Parsing and Verifying Before anything else may be done, we must efficiently detect syslog-auth messages, parse them into their constituent fields, and verify their signatures. This is done as follows: 6.2.1. Detecting Syslog-Auth Messages To detect a syslog-auth message, we simply look at the end of the message for the cookie, ``authAUTH''. If the cookie is missing, we assume this is not a syslog-auth message; if it is there, we assume it is a syslog-auth message, but don't make any assumptions that it's a valid one. Expires June 2001 [Page 23] Draft Syslog Auth December 2000 6.2.2. Parsing The next step is parsing the authentication block into its constituent fields. To do this, we must: a. Determine whether this message is long enough to safely process. That means first verifying that it's as long as the minimum length for an authentication block. In what follows, we assume that the receiver takes care never to allow buffer overruns. b. Read the version of the authentication block, and verify that we can understand it. To get the version, we read M[-10..-9], and process it as a base-64 encoded string. The result is put into A.version. If A.version is not any of the versions understood by the receiver, then the message cannot be processed, and must be stored in a log file which is specified not to have been processed or discarded. c. Read the flags of the authentication block, and use those flags to determine what fields will exist and what their size will be. The flags are at M[-12..-11], and are also base 64 encoded. d. Read and store each field from the authentication block for verification and later processing. Based on the specific values of the flags, the right blocks of characters are placed into each field. 6.2.3. Verifying the Authentication Block Before any processing can be done on the contents of these fields, we need to verify that the block and message have arrived intact. To do this, we do the following: a. Check the keyIDs of all keys currently available to the receiver against the A.transmissionMAC.keyID. If there is a match, then use the corresponding key for the following operations. If there is no match, this message must be written to a log file which is specified as not having been processed at all by syslog-auth, or must be discarded. b. Let A' be A with A.transmissionMAC.MAC = "00000000000". c. Compute hmac-md5_{Key}(message-text,A') where , denotes concatenation of strings. Note the use of A', which is A with the transmission MAC field set to a block of ASCII zeros. d. Compare the result of the hmac-md5 computation against A.transmissionMAC.MAC. If the two are equal, then the message has been verified, and processing can contine. If the two are not equal, the message must either be stored in a log file specified as not having been processed, or must be discarded. Expires June 2001 [Page 24] Draft Syslog Auth December 2000 6.3. Drawing Conclusions about Message Security The message flags and receiver configuration, together, determine what fields are in the message, and thus what can be determined about the message. In this subsection, we describe how the receiver will draw conclusions about what can be guaranteed about the messages. 6.3.1. Online Replay Detection The receiver sees a sequence of syslog-auth messages coming from each sender. It needs to be able to detect replay attempts in real time, so that it can't be swamped by replayed messages and have its disk filled up. There are three steps necessary to do this: a. Verify the authentication block and MAC. If that is not valid, discard the message. b. Check to see whether the Replay Vulnerable bit is set; if so, treat this message like an unauthenticated message for purposes of online replay detection. It may still be worthwhile to try to discard accidental replays, but there's no point in spending any time trying to detect intentional ones. c. Otherwise, treat this message as a syslog-auth message with replay resistance. 6.3.1.1. Syslog-auth Messages with Replay Resistance Messages in this category contain the information necessary to *always* detect replays. Whether and how this is done depends on the implementation and resources available. The basic idea is to accept messages arriving slightly out of order, but not to accept messages which have already been seen, or whose reboot session ID indicates a replay. The main difficulty here is with changes of session ID from a sender. When a syslog-auth message arrives with the Replay Vulnerable bit clear, it means that this combination of reboot session ID and global message counter has only been generated and used in a message once. The sender generates these two numbers in such a way that this is somehow assured. 6.3.1.2. The Replay Window A simple way to detect replays is the "replay window." This divides the problem of deciding whether the current message has been seen before into two simpler problems: a. Is this message even in the range of possible non-replayed messages? Expires June 2001 [Page 25] Draft Syslog Auth December 2000 b. If so, is this message in the list of recently-received messages in that range? Whenever a new message arrives, we first check to see if it is automatically disqualified by being outside our allowable range. The allowable range is defined in terms of both session IDs and global message counters, in a way that will be described further below. If the message isn't automatically disqualified, then we check to see whether we've already seen it. If it passes both checks, then it is accepted, the message is added to the list of in-range messages that have recently been received (the "window"), and the range may be adjusted based on this message. Note that the replay window needs to be larger for messages with long forwarding paths, since each hop in the forwarding path can introduce additional delays or re-orderings. A message with the Replay Vulnerable flag not set comes with a promise from the sender: its reboot session ID and global message counter, taken together, are guaranteed to be unique among messages ever sent by this sender. Together, these two fields make up a unique identifier for each message sent by a sender. At any given time, the replay window has zero, one, or two session IDs active. (It would have zero active if the sender hadn't sent a message in a long time; it would have two active if the sender had recently changed session IDs, as it might after a reboot. In nearly all cases, we expect it to have one active reboot session ID.) In the discussion below, we assume there is some number, N, such that we would be very surprised to see a message sent before N other messages that arrived after all of them. When a new message arrives with its Replay Vulnerable flag not set, there are three categories into which we can immediately place it: a. Old -- for example, if it has an active session ID, but a message counter much lower than the highest message counter received for that session ID, then it will be discarded. Similarly, if it has a session ID that's not currently active, but which is determined to be old, then the message is discarded. Note that even if we don't discard messages whose MACs fail, we SHOULD discard messages that are unambigously replayed. b. Current session ID and counter -- in this case, it has a currently active session ID and a counter that's within the range of counter values we're expecting. The session ID and message counter of this message are added to the list of recently-received messages, and the range of messages to be accepted may be updated as a result. c. New session ID -- in this case, a new session ID has occurred, and the new session ID is not known to be a replayed session ID. In this case, a new session ID becomes active in our window. We have to deal with this in various ways, as will be discussed below. Expires June 2001 [Page 26] Draft Syslog Auth December 2000 6.3.1.3. New Session IDs and Discontinuities Because syslog-auth doesn't assume reliable delivery, it is possible to get "discontinuities." A discontinuity is a gap between two blocks of messages, about which the receiver can usually tell nothing except that a block of messages sent between these two blocks was never received. For example, when a message arrives with a new session ID, this implies that the sender has rebooted recently. We will never know whether we saw the last message sent from the old session ID, since there is no later message to show a gap. Further, when a message arrives with a new session ID from a sender that generates those session IDs pseudorandomly, it's impossible to know whether there were other session IDs generated in-between which were never seen. (This could happen if the network between the sender and receiver went down for a long time.) Such situations are noted as discontinuities, and MUST be reported in the authenticated log file. 6.3.1.4. Detecting Replayed Session IDs When the Superincreasing Session ID flag is on, detecting a replayed session ID is easy: we simply check to see if the session ID of the new message is greater than all currently active session IDs, and if not, we reject it. When this flag is off, we must check the list of all session IDs ever sent by this sender since it's been using its current key. This sounds like searching through a long list, but there are two things that make it less demanding than it sounds: a. New session IDs should occur very rarely; very few machines reboot or otherwise lose all context all that often. A message with a new session ID should in practice not arrive from a sender more than a few times a day in the worst case. This means that it's acceptable for the test of a session ID to take a few seconds. It might even be reasonable to set up one machine on a local network to keep track of the pseudorandom session IDs for all the senders. b. The list of previously seen pseudorandom session IDs from a given sender is expected to be pretty small. Suppose in the worst case that we see one new session ID from some sender per hour, and that this sender continues using the same key for five years. The result will be a list of less than 44,000 session IDs. A hash table of 65,536 entries will handle this list efficiently, and the last sixteen bits of the pseudorandom session IDs can be used as the key for the hash table. A syslog server handling many senders will presumably have a lot of disk space; even five years' session IDs for 1000 senders in the worst case will take up only about 64 MB. Despite this, there will be some receivers that cannot do online replay detection for syslog-auth messages with pseudorandom session IDs. This is acceptable. However, the authenticated logs MUST indicate that replay detection isn't done on these session IDs, in the same field that shows discontinuities for new session IDs. Expires June 2001 [Page 27] Draft Syslog Auth December 2000 6.3.1.5. Unauthenticated Messages and Replay-Vulnerable Messages Unauthenticated messages can never be kept from being used to flood a receiver. That means that a receiver that handles unauthentication messages SHOULD take precautions to resist flooding attacks. These include keeping much more storage than is necessary, and keeping separate storage for authenticated and unauthenticated senders, so that an attacker can't fill up the receiver's storage with unauthenticated garbage messages, and thus prevent the receipt of syslog-auth messages. Similar steps SHOULD be taken for syslog-auth messages that are vulnerable to replay, as described above. 6.3.1.6. Syslog-Auth Forwarded Messages Forward messages present a special problem, because even when they're forwarded through syslog-auth, they may not have always been protected by syslog-auth, or some forwarding machine may not have implemented online replay detection. To deal with this, the forwarding block carries a flag (the Replay Resistant bit) which indicates whether the forwarder can guarantee that this message isn't a replay. If a forwarded message arrives at a receiver for storage, and the Replay Resistant bit is not set, the fact that this message (and presumably the whole log file from this sender via this forwarding pattern) is not replay resistant MUST be specified in the log. 6.3.2. Detecting Gaps If the authentication block contains the field A.destinationCounter, then we can detect any gaps in the messages we were sent. The destination counter is incremented by one each time a message is sent to a given destination, so if there are missing destination counter values in the received messages, we know that those messages didn't make it to us. Cryptographic methods can't tell us why the messages didn't arrive (e.g., whether this is due to random packets being dropped or malicious action). If syslog-auth is being used over reliable delivery mechanisms, then gaps in the sequence of received messages is strong evidence of malicious tampering. Note that we can use the replay window mechanism to look for gaps. As each message falls out of the replay window, we can check to see whether it's leaving any gaps more than N messages back, where N is the replay window size. If so, we note the gap. Also note that we don't actually need to note gaps in the auxiliary log; we merely have to note whether or not sufficient information exists in the original log to note gaps, and if so, what information that is. Expires June 2001 [Page 28] Draft Syslog Auth December 2000 6.4. Applying Conclusions Once the receiver has drawn conclusions about what can be guaranteed about a given message cryptographically, it needs to have a way of applying these conclusions. There are three ways this may be done: a. Writing conclusions out as an auxillary log file. b. Using the observations to change flags and such in forwarded messages. c. Using the observations to alter processing based on these messages. 6.4.1. Writing Out Conclusions about Syslog-Auth Messages When the messages are being stored on the receiver, they need to be stored in such a way that a reviewer doesn't need the secret key shared between the sender and receiver to verify a message. For this purpose, we propose an auxillary log file. This log file is related to a given log file, and includes additional information about what can is known from syslog-auth about a given message or range of messages. Entries in this auxillary log file are of the form: a. Key ID, Reboot Session ID (identify the machine and session) b. startGlobalCounter, endGlobalCounter (identify the range of messages; * is valid on either end). c. blob (32-bit encoding of promises being made) d. textDescription ASCII text of the promises being made. The fields are separated by commas. The result is something like 3f48d17787acce4437836b6e,00000348a490,*,*,c1f13839, No replay or gap detection possible online. 9d1eac9bcc3ab07657eb35ee,0000898de7bd,*,000000000048,09dee718, No replay detection possible. 8837174d47328e71937014e2,*,*,091726aa, Session-ID is pseudorandoml cannot be sequenced with other session IDs Expires June 2001 [Page 29] Draft Syslog Auth December 2000 6.4.2. Applying Conclusions in Forwarded Messages The conclusions drawn in subsection 6.3 are also useful when the message in question is being forwarded. Knowledge about replay and gap detection must be passed on to the next receiver, and this can be done by setting appropriate bits in the flags of the authentication block and its forwarding block. In particular, the following flags may be affected: A.flags.replayVulnerable A.forwardingBlock.flags.replayResistant 6.4.3. Applying Conclusions in Online Processing These conclusions may also be of great value for systems doing online processing of log files, e.g., for intrusion detection. Such systems can, for example, discard replayable messages when they're overloaded with other messages, or signal a problem when some authenticated device's messages are showing a suspicious number of missing messages. 7. Reviewing Syslog-Auth Logs Offline We expect that in most applications, people or programs will review logs offline, perhaps hours or days after they have been written. Offline review of logs gives several potential advantages: a. It's possible to postprocess log data, e.g., by putting all of the messages from the same reboot session ID in order of increasing global counter, and thus in order of original transmission. b. It's possible to gather information from other receivers, and thus combine information from the same sender that went to different receivers, or from different senders that ought to be analyzed together. c. Sometimes, an administrator will want to have an additional storage security key which is not available online. This might be used to resist attacks in which someone compromises the receiver machine, and alters logs on it. This section describes offline review of logs received and stored by a syslog-auth receiver, including an auxillary log file. 7.1. Offline Replay Detection Online replay detection is preferable, but offline replay detection is often good enough in practice. Offline replay detection uses exactly the same techniques as online replay detection, but isn't nearly as time critical. Expires June 2001 [Page 30] Draft Syslog Auth December 2000 Offline replay detection uses the same techniques as online replay detection, described above. 7.2. Storage Security Syslog-auth is mainly concerned with ensuring transmission security of log messages--that is, ensuring that they aren't altered on the wire between the sender and receiver. However, someone doing offline analysis of logs may also want to ensure that the logs haven't been tampered with since they've arrived. These two goals are rather distinct. It is important to note: storage security cannot be provided using a key held by the machine on which the logs are to be stored. If that machine isn't compromised, then an attacker can't alter the logs once they've arrived at it. If the machine is compromised, then an attacker can recover the key used, and can alter logs undetectably. 7.3.1. Syslog-Auth Storage MACs Storage MACs are the only way that syslog-auth supports storage security directly. A syslog-auth message may, under normal conditions, contain zero, one, or two storage MACs. The key used for the storage MAC should be known to no online machine except the sender. The storage MAC is intended to be verified offline. The owner of the log uses the storage MAC key, specified by the key ID in the storage MAC block, to verify that the message hasn't changed. There are two important points to consider, here: a. If there is ever a disagreement about authenticity of a message between the receiver and the storage MAC (e.g., a message is stored as a valid message, but its storage MAC is not valid), this implies either a malfunction or a compromise somewhere on the forwarding path of the message, since the storage MAC was added to the machine. b. The storage MAC prevents the receiver, if compromised, from altering stored log messages, but does not prevent it from deleting inconvenient log messages. (This is inevitable, since all that a storage MAC can authenticate is its message, not a sequence of messages that arrived.) Expires June 2001 [Page 31] Draft Syslog Auth December 2000 7.4. Detecting Gaps by Reassembling All Paths of Forwarded Messages Forwarded messages and messages without destination counters can't be checked for meaningful gaps in the message sequence online. (In this context, a meaningful gap is a gap caused by a message being lost or blocked, rather than by the sender having simply sent the message to a different receiver instead of this one.) To check those logs for gaps that represent lost messages, we must reassemble the logs from a given sender, using the logs stored on all the ultimate receivers (possibly at the end of long chains of forwards). We can then find any gaps in global message counters and identify them.8. 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. 9. Bibliography A. Defining the Key ID. The md5 hash function is known to have some weaknesses, particularly in terms of collision resistance. However, it is also believed to be secure when used in the hmac construction, which is hmac_{K}(X) = md5(K xor Pad1,md5(K xor Pad2,X)) This applies the hash twice between the initial use of the key and the output. All our security in this scheme is based on hmac-md5, so far. One nice feature of this is that we can always change the hash function used, e.g., to SHA1 or SHA-256, with no real difficulties in terms of these definitions. Our key IDs and MACs are both based on taking the low-order 64 or 96 bits of the hash value, so changing the output size of the hash should have no impact on them. We use the following formula for Key ID: Key ID = low 96 bits( hmac_md5_{K}("KEYID") ). The reasoning behind this is: a. We are already trusting hmac_md5 with all our security in this scheme, so it introduces no new trust requirements. b. There is no valid syslog-auth message with only the text "KEYID", since it does not include an authentication block. A sender or forwarder who follows the standard will never generate a MAC for such a message. Therefore, we need not worry about someone trying to forge a syslog-auth message using the key ID as a valid MAC, because there's no valid message that could be forged this way. Expires June 2001 [Page 32] Draft Syslog Auth December 2000 c. The key ID is 96 bits based on the following logic: We never expect to see any receiver dealing with more than 2^{32} different senders' keys at once. In fact, we'd be surprised to see even one receiver on earth have to deal with that many senders. For that receiver, however, the probability that a pair of keys will collide is choose(2^{32},2) * 2^{-96} ~= 2^{63} * 2^{-96} = 2^{-33}. This means that in this worst-case environment, the probability that we will get a pair of keys with the same key ID is still astronomically small. Why is this last point important? The software implementing syslog-auth is going to use this key ID to decide which key to use when checking the message's MAC. So if there were ever a pair of keys that had the same key ID, and a given receiver had to deal with both at once, it would almost certainly fail to authenticate messages from one of the two colliding keys. (It's possible to implement this so that it detects unequal keys with colliding key IDs, and deals intelligently with them. But the code to do this will never be used, and so will probably almost never be tested. Even generating a test case for this situation requires a prohibitive amount of processing power (we expect it to take about 2^{48} operations)! So it will never be used, will never be tested, and so it just shouldn't be counted on.) B Author's Address John Kelsey Counterpane Internet Security kelsey.j@ix.netcom.com Expires June 2001 [Page 33] Draft Syslog Auth December 2000 C 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 34]