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

                         Syslog-Sign 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-sign, a mechanism for adding
   origin authenticaiton, message integrity, replay-resistance,
   message sequencing, and detection of missing messages to
   syslog.  The goal of syslog-sign is to provide all these
   security features in a way that has minimal requirements and
   minimal impact on an existing setup of syslog devices,
   relays, and collectors.  In particular, it is possible to
   support syslog-sign by changing only the behavior of the
   syslog devices, and some software run either online or
   offline on the collector's stored logs.

1. Introduction

   Syslog-sign is intended to be an in-band protocol for
   signing messages within syslog, making no assumptions about
   any delivery mechanisms.  This means that all messages sent
   along are valid syslog-syslog messages.  The messages will
   be received and stored normally by any syslog collector.
   However, offline review of the stored logs by a
   syslog-sign-aware program will allow verification of the
   logs' origin, integrity, freshness, and completeness.

   The basic design goals are thus:

   a.  The goal of syslog-sign is offline detection of
       alterations of the logs.  The signatures provide both
       storage security and transmission security, but we provide
       no support for any kind of online detection of alterations.
       (There's nothing saying a collector can't implement such
       detection online, assuming it can keep up with the workload.
       But we add nothing to support such online detection.)

   b.  Over the course of a reasonably long session,
       syslog-sign will transmit the certificate, public key, or
       key ID on which its signatures are based several times.

Expires June 2001                                               [Page 1]

Draft                      Syslog Sign                     December 2000

   c.  Syslog-sign will provide data integrity, data origin
       authentication, replay detection, and gap detection.  It is
       the responsibility of the users of syslog-sign to ensure
       that all the logs in a ``signature group'' are sent to the
       same receiver.  (A ``signature group'' is a set of messages
       signed in the same sequence of signature blocks.)  How the
       administrator sets things up to support this is outside the
       scope of this document, but if messages from the same
       signature group are somehow separated during transmission or
       forwarding, we will generally be unable to authenticate the
       messages stored by any one collector.

   d.  Because syslog-sign must operate in-band over unreliable
       delivery mechanisms, there is always some chance that
       critical information will not make it to the receiver.
       However, syslog-sign can be configured on the sender side to
       add redundancy to its messages, to decrease the likelihood
       that any messages will be impossible to verify.

   e.  Syslog-sign supports multiple signature and hash sizes
       and schemes.  These are encoded in its version field.  Larger
       signatures lead to more bandwidth required by syslog-sign.
       Syslog-sign even supports symmetric cryptosystems.

   f.  The only awareness of forwarding in syslog-sign is the
       requirement that a syslog-sign relay (as well as a device)
       signal some kind of an error if it is required by its
       forwarding rules to send messages in the same signature
       group to different recipients.

2. Syslog-Sign Message Formats

   Syslog-sign uses syslog to transmit its messages.  That
   means that all of its messages have to fit inside legal
   syslog-syslog messages.  This determines most of the design.

   Syslog-sign processes all syslog messages, but it generates
   only two kinds of messages of its own: signature blocks and
   certificate blocks.  A signature block contains some header
   information, a sequence of hashes from recently-sent
   messages, and a signature of some kind, and a new signature
   block is sent each time there have been N new messages whose
   hashes need to be signed and sent out.  A certificate block
   contains some or all of the information needed to uniquely
   identify the key being used in these signatures.

2.1. Signature Blocks
   A signature block contains a signature for a sequence of
   messages sent by syslog-sign.  There are several key points
   that must be understood before the format of the signature
   block makes any sense:

   a.  In this document, we refer to the normal syslog messages
       that aren't generated by syslog-sign as ``messages.''  When
       we discuss processing messages, we never include signature
       blocks or certificate blocks in this processing.

Expires June 2001                                               [Page 2]

Draft                      Syslog Sign                     December 2000

   b.  The sending device divides the set of messages it will
       ever send into one or more ``signature groups.''  The
       maximum number of signature groups allowed is 4095.  The
       only requirement for a signature group is that all messages
       from that signature group must be routed to the same

   c.  Each time the device starts a new logging ``session,''
       e.g. because it has rebooted, it must generate a unique
       reboot session ID.

   d.  Because we must deal with unreliable delivery, we can't
       assume that all the messages in this sequence arrived.
       Therefore, we include the hash of each message sent in this
       sequence in this signature block.  When the logs are
       reviewed, the messages are hashed and their hashes are found
       in the appropriate signature block.

   e.  Messages are sent along unaltered.  However, each
       message is assigned a unique identifying number within its
       reboot session and signature group.  Each signature block
       specifies the number of the first message whose hash is
       included; the numbers of the succeeding messages are defined
       by their position in the hash block.

   f.  The signature block is sent in-band, and may
       legitimately be forwarded through old-style syslog machines.
       Therefore, it must fit within the requirements of a syslog
       message.  That means it is always less than 1024 bytes, and
       it contains only printable ASCII characters, and in fact,
       only the 64 characters used in base 64 encoding.

2.1.1. Signature Block Format

   The signature block consists of the following fields:

   a.  Cookie -- an eight byte sequence to signal to the
       verifier that this is a signature block.  This sequence is

   b.  Version -- a 12-bit quantity encoded in base 64 as two
       bytes, which effectively specifies the hash function,
       signature mechanism, and other details of the processing of
       this signature block.

   c.  Session ID -- a 48-bit quantity encoded in base 64 as
       eight bytes, which is required to never repeat or decrease
       over multiple reboots of the sender.

Expires June 2001                                               [Page 3]

Draft                      Syslog Sign                     December 2000

   d.  Signature Group -- a 12-bit quantity encoded in base 64
       as two bytes, which indicates which signature group this
       message belongs to.  (Each raw message belongs to exactly
       one signature group, and each signature block includes
       hashes from only one signature group.  Messages from the
       same signature group MUST ultimately be routed to the same
       collector, and MUST NOT ever be separated in transmission by
       any device or relay.

   e.  Global Block Counter -- a 48-bit quantity encoded in
       base 64 as eight bytes, which is the number of signature
       blocks sent out by syslog-sign in this reboot session.

   f.  First Message Number -- a 48-bit quantity encoded in
       base 64 as eight bytes, which is the unique message number
       within this signature group of the first message whose hash
       appears in this block.  (That is, if this signature group
       has processed 1000 messages so far, and the 1001st message
       from this signature group is the first one whose hash
       appears in this signature block, then this field is 1001.

   g.  Count -- a 6-bit quantity encoded in base 64 as one
       byte, which is the number of message hashes to follow.

   h.  Message Hashes -- a block of hashes, each separately
       encoded in base-64.  The size of each hash is determined by
       the hashing algorithm used, effectively specified by the
       Version field, but the size MUST NOT be shorter than 160

   i.  Signature -- a digital signature, encoded in base-64.
       The original encoding of the signature is effectively
       specified by the Version field.

2.1.2. Variability of Format

   The format has a certain amount of flexibility.  Some of
   this is determined by the version, and some, by the device
   generating the messages based on requested level of
   redundancy in transmission. Versions and Field Sizes

   The format has some variability, because different signature
   schemes and hash functions will alter the size of the
   fields.  The following versions are defined right now:

   1 = SHA1 and DSA/320

   2 = SHA1 and RSA/1024

   3 = SHA1 and RSA/2048

   [[ I need to reference some specs for all this. --JMK ]]

Expires June 2001                                               [Page 4]

Draft                      Syslog Sign                     December 2000 Redundancy

   The sending device has a tunable level of redundancy for the
   signature blocks.  If no redundancy is used, then if a
   signature block is lost, no messages that were signed by
   that block can be verified.  The more redundancy is used,
   the more signature blocks must be lost before a message
   cannot be verified.

   Redundancy is implemented in a simple way:  Each message's
   hash can be included in more than one signature block.  If
   each message's hash is included in two signature blocks,
   then only when two successive signature blocks from the same
   signature groups are lost in transit do we end up with
   messages we can't verify.  If each message's hash is
   included in three signature blocks, then this can happen
   only when three successive signature blocks from the same
   signature group are lost in transit.

   The signature block specifies the message number of the
   first message whose hash is included in the block.  If each
   signature block contains 40 hashes, and each successive
   signature block's first message is 20 messages higher than
   the previous block's, then each message is signed by two

   Note that this is totally decided by the sending device, and
   that any level of redundancy is supported.  Similarly, the
   only requirement about the number of hashes included in each
   signature block is that it never be less than one, and that
   it will never be large enough to cause the signature block
   to go over 1024 bytes in length.  (The field cannot support
   more than 63 message hashes, but in practice, no more than
   37 could appear in a 1024-byte message, ignoring the other
   header fields and the signature block.)

   In particular, note that it is legal for the sending device
   to simply include one signature block per message.

2.2. Certificate Blocks

   The purpose of a certificate block is provide some support
   for key management in syslog-sign, by allowing the
   transmission of a certificate and other identifying
   information from the sending device.  The sending device has
   a certain initial key management blob to send, which may be
   a PKIX certificate, or a raw public key, or a key
   fingerprint.  In fact, a syslog-sign device doesn't know
   anything about this payload except what it's told to report
   about it during device setup.

Expires June 2001                                               [Page 5]

Draft                      Syslog Sign                     December 2000

   There are three key points to understand about certificate blocks:

   a.  The handle a variable-sized payload, by fragmenting it
       if necessary, and transmitting the fragments as legal
       syslog-syslog messages.  This payload is expected to be a
       certificate, but the syslog-sign device does no checking of
       its format or contents.  Its goal is simply to make sure
       that the payload gets sent along with a log of any
       reasonable length.

   b.  There is an adjustable parameter for required
       redundancy, just as in the signature blocks.  However, the
       redundancy functions a little differently.

   c.  Each signature group gets sent its own certificate blocks.

2.2.1. Building the Payload Block

   Note that we build a payload at the time the reboot
   session starts, and that payload includes a digital
   signature.  The payload block for this reboot session

   a.  Version -- specifying the hash function and signature
       used; this is the same version identifier as is used in the
       signature blocks.

   b.  Reboot Session ID -- the same reboot session ID which
       will be used in the signature blocks

   c.  IP Address of Sender -- the sender's IP address, a
       128-bit number base-64 encoded as 22 bytes.

   d.  Key Blob Type -- this one-byte field holds one of four values:
        (i)  'C' -- a PKIX certificate
        (ii) 'F' -- a key fingerprint (the hash of the public key
                    using the specified hash algorithm)
        (iii)'K' -- the public key whose corresponding
                    private key is being used to sign these
        (iv) 'U' -- user-specific field with no defined
                    meaning in the standard.

   e.  Key Blob -- the raw data, base-64 encoded.

   f.  Signature -- a digital signature on fields a-e, encoded
       in base-64.

2.2.2. Building the Certificate Block

   The certificate block must get the payload block to the
   collector.  Since certificates can legitimately be much
   longer than 1024 bytes, each certificate block carries a
   piece of the payload block.

Expires June 2001                                               [Page 6]

Draft                      Syslog Sign                     December 2000

   The certificate block is built as follows:

   a.  Cookie -- an eight byte string, ``@#sigCer''.

   b.  Version -- a 12-bit field encoded in base-64 as two bytes.

   c.  Signature Group -- a 12-bit field encoded in base-64 as
       two bytes.

   d.  Total Payload Length -- a 32-bit field encoded in
       base-64 as six bytes.

   e.  Index into Payload -- a 32-bit field encoded in base-64
       as six bytes.

   f.  Fragment Length -- a 12-bit field encoded in base-64 as
       two bytes.

   g.  Payload Fragment -- a fragment of the payload, as
       specified by the above fields.

2.2.3. Redundancy

   Given the 1024-byte limit on syslog messages, a given
   payload block can be efficiently divided up into some
   number, P, of certificate blocks. (It is possible that
   P==1.)  The collector must end up with all P of these blocks
   to be able to verify that this key was in use at the time of
   this reboot session.

   The certificate blocks are sent as follows:

   a.  At reboot, we send all P certificate blocks once for
       each signature group.  These are sent as syslog messages,
       and they are sent before any other syslog messages are sent
       in this session.

   b.  After this, we resend the certificate blocks
       occasionally, based on the redundancy parameter R.  For each
       signature group, each time another R messages are sent for
       that signature group, we send along the next certificate
       block.  Note that this requires that we keep track of which
       certificate block we're on, for each signature group.  If
       R==0, then we never resend the certificate block.  (This
       would make sense if we were using syslog-sign over

3.0. Offline Review

   Reviewing the stored logs offline now becomes straightforward.

   a.  Verify that the next reboot session ID is valid, e.g.,
       is larger than the previously seen reboot session IDs.

Expires June 2001                                               [Page 7]

Draft                      Syslog Sign                     December 2000

   b.  Go through the log entries with this session ID, and
       pull out each of the certificate blocks.  Reassemble the
       payload block, and make whatever use of it is desired.

   c.  If more than one signature group appears in the logs,
       process each group separately as follows.

   d.  For each signature block:
        (i)  Verify the signature at the end of the block.
        If the signature verifies successfully, then
        continue processing.
        (ii) Determine what message numbers we're receiving
        based on the appropriate fields in the signature
        (iii)For each hash in the hash block, look in the
        nearby messages for a message with the same hash. If
        a message is found, then add that message, along
        with its message number, to the list of verified
        messages for this session ID and signature group.

   e.  When the processing is done, sort the list of verified
       messages for this session ID and signature group on the
       message numbers.  Eliminate duplicate message numbers, and
       the result is a verified log file, complete with gaps in the
       message numbers where there are gaps in the received

4 Acknowledgements

   The author wishes to thank Alex Brown, Chris Calabrese, Jon
   Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin
   New, Marshall Rose, Holt Sorenson, and the whole bunch of
   Counterpane engineering and operations people who commented
   on early or late versions of this proposal.

5 Bibliography

A Author's Address

John Kelsey
Counterpane Internet Security

Expires June 2001                                               [Page 8]

Draft                      Syslog Sign                     December 2000

B Full Copyright Statement

Copyright (C) The Internet Society (2000). All Rights Reserved.

This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it or
assist in its implementation may be prepared, copied, published and
distributed, in whole or in part, without restriction of any kind,
provided that the above copyright notice and this paragraph are included
on all such copies and derivative works. However, this document itself
may not be modified in any way, such as by removing the copyright notice
or references to the Internet Society or other Internet organizations,
except as needed for the purpose of developing Internet standards in
which case the procedures for copyrights defined in the Internet
Standards process must be followed, or as required to translate it into
languages other than English.

The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an "AS

Expires June 2001                                               [Page 9]