[Search] [txt|pdf|bibtex] [Tracker] [WG] [Email] [Nits]

Versions: 00                                                            
Internet Engineering Task Force                                   Syslog
Internet Draft                                               John Kelsey
draft-ietf-syslog-auth-00.txt                        Expires:  June 2001

                         Syslog-Auth Protocol


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

     The list of Internet-Draft Shadow Directories can be accessed at


   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

     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

   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

   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

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

        (ii) Loading K_{sender,receiver} onto a receiver

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
   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

   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

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

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

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

   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

   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

   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. 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.


        (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.) 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

   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. 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

   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

   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:


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

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

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. 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. 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

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

Expires June 2001                                              [Page 26]

Draft                      Syslog Auth                     December 2000 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. 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 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. 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

   c.  Using the observations to alter processing based on these

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

                No replay or gap detection possible online.

                No replay detection possible.

                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:


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

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

   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

   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

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

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

Expires June 2001                                              [Page 34]