[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 RFC 5848

        Internet Draft                                             J. Kelsey
        Document: draft-ietf-syslog-sign-01.txt                  Counterpane
                                                           Internet Security
        Expires: December, 2001                                    June 2001


                                  Syslog-Sign Protocol


     Status of this Memo

        This document is an Internet-Draft and is in full conformance with all
        provisions of Section 10 of RFC2026.


        Internet-Drafts are working documents of the Internet Engineering Task
        Force (IETF), its areas, and its working groups.  Note that other
        groups may also distribute working documents as Internet-Drafts.

        Internet-Drafts are draft documents valid for a maximum of six months
        and may be updated, replaced, or obsoleted by other documents at any
        time.  It is inappropriate to use Internet-Drafts as reference
        material or to cite them other than as "work in progress."


        The list of current Internet-Drafts can be accessed at
             http://www.ietf.org/ietf/1id-abstracts.txt
        The list of Internet-Draft Shadow Directories can be accessed at
             http://www.ietf.org/shadow.html.

        This work is a product of the IETF syslog Working Group.  More
        information about this effort may be found at
          http://www.ietf.org/html.charters/syslog-charter.html
        Comments about this draft should be directed to the syslog working
        group at the mailing list of syslog-sec@employees.org.

        The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
        "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
        document are to be interpreted as described in RFC 2119.


     Copyright Notice

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



     Abstract

        This document describes syslog-sign, a mechanism for adding origin
        authentication, message integrity, replay-resistance, message
        sequencing, and detection of missing messages to syslog.  The goal of





     Kelsey                  Expires November 2001                        [1]
                              Syslog-sign Protocol                  June 2001

        syslog-sign is to provide all these security features in a way that
has
        minimal requirements and minimal impact on existing syslog
        implementations.  It is possible to support syslog-sign and gain some
        of its security attributes by only changing the behavior of the
devices
        generating syslog messages.  Additional security benefits may be
        realized by some additional processing of the received syslog messages
        and the syslog-sign messages on the relays and collectors.


     Table of Contents

        Status of this
Memo...................................................1
        Copyright
Notice......................................................1

Abstract..............................................................1
        1
Introduction........................................................4
        1.1 Design Philosophy and
Goals.......................................4
        1.2 Guide to the
Document.............................................5
        2 Signature
Blocks....................................................5
        2.1 How Signature Blocks
Work.........................................5
        2.2 Signature Groups and PRI Values...................................6
        2.3 Signature Block Format and
Fields.................................8
        2.3.1 Text
Block......................................................8
        2.3.1.1
Priority......................................................8
        2.3.1.2
Timestamp.....................................................9
        2.3.1.3
Hostname......................................................9
        2.3.1.4
Cookie........................................................9
        2.3.1.5
SIG...........................................................9
        2.3.2 Base-64 Encoded Binary
Block....................................9
        2.3.2.1
Version.......................................................9
        2.3.2.2 Reboot Session
ID............................................10
        2.3.2.3 Global Block
Counter.........................................11
        2.3.2.4 First Message
Number.........................................11
        2.3.2.5
Count........................................................11
        2.3.2.6 Hash
Block...................................................11
        2.3.2.7
Signature....................................................11
        2.4 Notes on Upgrading
Versions......................................11
        3 Payload and Certificate
Blocks.....................................11
        3.1 Building the Payload
Block.......................................12
        3.3. Building the Certificate
Block..................................13
        3.4 Use of Certificate and Payload Blocks............................14
        4 Redundancy and
Flexibility.........................................15
        4.1
Redundancy.......................................................15
        4.1.1 Certificate
Blocks.............................................15
        4.1.2 Signature
Blocks...............................................16
        4.2
Flexibility......................................................16
        4.3 Short Signature or Certificate
Blocks............................17
        5 Efficient Verification of
Logs.....................................17
        5.1. Offline Review of
Logs..........................................17


     Kelsey                  Expires November 2001                        [2]
                              Syslog-sign Protocol                  June 2001

        5.2. Online Review of
Logs...........................................18
        6 Security
Considerations............................................20
        7 Conclusions and Open
Issues........................................21
        7.1 Initial
Version..................................................21
        8 Test
Values........................................................21
        8.1 Generating Signature
Blocks......................................22
        8.2 Generating Payload and Certificate Blocks........................22
        9
Acknowledgements...................................................22
        10
Bibliography......................................................22
        A Author's
Address...................................................22
        B Full Copyright
Statement...........................................22










































     Kelsey                  Expires November 2001                        [3]
                              Syslog-sign Protocol                  June 2001


     1 Introduction

        Syslog-sign is a protocol for adding origin authentication,
        message integrity, replay resistance, message sequencing,
        and detection of missing messages to syslog.  A major goal
        of the protocol is to do all this in a way that can be
        quickly deployed on existing networks, and that can be
        implemented mostly using off-the-shelf tools.  To this end,
        a number of basic design decisions were made that determined
        most of the design:

        a.  All messages sent in this protocol are legal syslog
        messages.  This ensures that relays and collectors can
        handle the new protocol's traffic without any changes.  It
        also inherits the problems of syslog messages in
        general: unreliable and out-of-sequence delivery, only
        printable characters allowed in the message text, and each
        message limited to 1024 bytes maximum.

        b.  Normal syslog messages are sent unchanged by the
        protocol, just as they would have been sent by syslog
        without any enhancements.

        c.  Every N messages, a signature block is sent along as a
        syslog message.  This contains, in effect, a detached
        signature on the previous N messages.  These signature
        blocks contain additional information to allow them to be
        put into sequence, and to allow any missing signature blocks
        to be noticed.

        d.  Because we must keep the logs in the correct sequence
        even across reboots of the device, we must differentiate
        different "sessions" in which a device is generating log
        messages and signature blocks. This is done with a "reboot
        session ID," a 48-bit identifier which is guaranteed never
        to be reused by a given device.

        e.  To support key and session management, we have a
        mechanism for sending along a certificate or other
        information on a per-reboot-session basis.  This is done
        using "certificate blocks," which are also legal syslog
        messages.


     1.1 Design Philosophy and Goals

        More than anything else, what ultimately drove this design
        was the decision to use syslog as the transport method for
        all syslog-sign messages. This requires the use of detached
        signatures (signature blocks), because there's no other way
        to add signatures and other information to all messages;
        some messages would have had to be truncated or fragmented.


     Kelsey                  Expires November 2001                        [4]
                              Syslog-sign Protocol                  June 2001

        Using signature blocks appeared the cleanest way to do this.
        As a side benefit, relatively expensive and large digital
        signatures can be spread out among N messages at a time,
        making the whole scheme more efficient.

        We decided to use syslog as the transport mechanism because
        altering every syslog message meant changing the software on
        every relay and collector, and probably dealing with very
        complicated cases where some relays and collectors could
        process authenticated messages, while others could not.  A
        previous attempt to design a scheme for doing authenticated
        syslog messages taught us not to try to tackle these issues,
        which would necessarily involve second-guessing every
        system administrator who wanted to use the scheme.

        Using digital signatures instead of symmetric MACs to authenticate
        messages makes the key management much simpler (though
        there's nothing inherent in the syslog-sign design that
        requires that nobody use symmetric algorithms), and makes
        the scheme suitable for providing storage security for the
        logs, as well as transmission security.


     1.2 Guide to the Document

        The rest of this document is organized as follows:  First,
        we discuss signature blocks, and the infrastructure that
        supports them.  Next, we discuss the key management tools in
        syslog-sign, built around payload blocks and certificate
        blocks.  We then discuss redundancy mechanisms in
        syslog-sign.  Next, we discuss efficient verification of logs
        and log messages, both online and offline.  Finally, we
        conclude the document with a brief summary and some open
        questions about the design.


     2 Signature Blocks


     2.1 How Signature Blocks Work

        A signature block contains a priority value (required for
        all syslog messages), some header information (to allow the
        signature blocks to be put into order on receipt), a
        sequence of N cryptographic hash values, and a digital
        signature.

        Signature Block:

        a.  PRI Value
        b.  Header Information
        c.  List of N hashes:
                (i)  Hash[0]


     Kelsey                  Expires November 2001                        [5]
                              Syslog-sign Protocol                  June 2001

                (ii) Hash[1]
                (iii)Hash[2]
                ...
        d.  Signature on fields a-c.

        Consider a device, which is sending log messages to a
        collector.  After every Nth normal log message, it sends an
        additional message with this format.  Again, this is just a
        syslog message, and so it needs no special treatment by the
        collector or any intermediate nodes.  To generate and send
        that additional message, (the "signature block"), the
        device keeps the cryptographic hash values of the previous N
        messages sent, and how many messages were sent before these
        most recently sent N messages.  Using that information, the
        device is able to build the signature block.  It digitally
        signs the block, and sends it along.

        The collector may process these signature blocks as they
        arrive, building an authenticated log file on the fly as the
        pieces arrive.  Alternatively, it may store all the log
        messages in the order they were received, and allow the
        system administrator to authenticate the log file when he reviews the
        logs.  In either case, out-of-order messages are put back
        into order based on the hash values in the signature block.
        (There are a number of efficient ways to do this.)


     2.2 Signature Groups and PRI Values

        Each signature block contains, in effect, a detached
        signature on the previously sent N messages.  However, a
        device may send messages that are ultimately routed to many
        different collectors.  If the N messages arrive at one
        collector, and the signature block at another, then neither
        collector will be able to verify anything.  Similarly, if
        half of the N messages go to one collector, while the
        signature block and the other half of the N messages go to
        the other, there is clearly a problem.

        The solution to this problem ultimately rests with the
        system administrator who uses the system; he must configure any relays
        and collectors to ensure that messages and their signature
        blocks arrive at the same place.  To make this easier,
        syslog-sign provides the idea of a "signature group."  A
        signature group identifies a group of messages that are all
        kept together for signing purposes by the device.  A
        signature block always belongs to exactly one signature
        group, and it always signs messages belonging only to that
        signature group.

        Recall that syslog-sign doesn't alter messages.  That means
        that the signature group of a message doesn't appear
        anywhere in the message itself.  Instead, the device and any


     Kelsey                  Expires November 2001                        [6]
                              Syslog-sign Protocol                  June 2001

        intermediate relays use something inside the message to
        decide where to route it; the device needs to use the same
        information to decide which signature group a message
        belongs to.

        Syslog-sign provides four options for handling signature
        groups, linking them with PRI values.  In all cases, no more
        than 192 signature groups (0-191) are permitted.  In this
        list, SIG is the signature group, and PRI is the PRI value
        of the signature and certificate blocks in that signature
        group.

        a.  '0' -- Only one signature group, SIG = 0, PRI = 046.
        The same signature group is used for all certificate and
        signature blocks, and for all messages.

        b.  '1' -- Each PRI value has its own signature group.
        Signature and certificate blocks for a given signature group
        have SIG = PRI for that signature group.

        c.  '2' -- Each signature group contains a range of PRI
        values.  Signature groups are assigned sequentially.  A
        certificate or signature block for a given signature group
        have its SIG value, and the highest PRI value in that
        signature group.  (That is, if signature group 2 has PRI
        values in the range 100-191, then all signature group 2's
        signature and certificate blocks will have PRI=191, and
        SIG=2.

        d.  '3' -- Signature groups are not assigned with any simple
        relationship to PRI values.  A certificate or signature
        block in a given signature group will have that group's SIG
        value, and PRI = 046.

        Note that options (a) and (b) make the SIG value redundant.
        However, in installations where log messages are forwarded
        to different collectors based on some complicated criteria
        (e.g., whether the message text matches some regex), the SIG
        value gives an easy way for relays to decide where to route
        signature and certificate blocks.  This is necessary, since
        these blocks almost certainly won't match the regexes.

        Options (a) and (d) set the PRI value to 046 for all
        signature and certificate blocks.  This is intended to make
        it easier to process these syslog messages separately from
        others handled by a relay.  One reasonable way to configure
        some installations is to have only one signature group,
        send messages to many collectors, but send a copy of each
        signature and certificate block to each collector.  This
        won't allow any collector to detect gaps in the messages,
        but it will allow all messages that arrive at each collector
        to be put into the right order, and to be verified.



     Kelsey                  Expires November 2001                        [7]
                              Syslog-sign Protocol                  June 2001


     2.3 Signature Block Format and Fields

        The signature block is composed of the following fields.
        Recall that every field must be printable ASCII, and any
        binary values are base-64 encoded.  The numbers in
        parentheses are the number of bytes taken up by the binary
        values inside the Base-64 encoded blob, and the number of
        characters for other values.

        a.  Text Block
             (i)   "<" (1)
             (ii)  PRI (3)
             (iii) ">" (1)
             (iv)  Timestamp(15)
             (v)   " " (1)
             (vi)  Hostname (variable)
             (vii) " " (1)
             (viii)Cookie (8)
             (ix)  Sig Group (3)
        b.  Base-64 Encoded Binary Block (variable)
              (i)   Version (4)
              (ii)  Reboot Session ID (6)
              (iii) Global Block Counter (6)
              (iv)  First Message Number (6)
              (v)   Count (2)
              (vi)  Hash Block (variable)
              (vii) Signature (variable)

     2.3.1 Text Block

        The text block contains information that is not binary-encoded.  This
        is generally the information that relays or the system administrator
        may need to be able to see "in the clear."  Some parts of the text
        block are required of all syslog messages; others make it easy to
        distinguish signature and certificate blocks from normal syslog
        messages.

        This block must be parsed field by field, using the angle brackets and
        spaces as delimiters.  It is not fixed-length, due to the need to
allow
        PRI, SIG, and hostname fields to vary in length.

     2.3.1.1 Priority

        All syslog messages need a three digit priority and facility code,
        ranging from 0 to 191 inclusive.  This value must be in angle
brackets,
        e.g., <12> or <185>.

        Signature blocks' priority values are determined by the configuration
        of syslog-sign, in order to make it as easy as possible to get all
        syslog messages going to the same final collector to arrive with their
        signature blocks.  In fact, if the syslog installation routes syslog
        messages based only on their priority+facility code, then the only


     Kelsey                  Expires November 2001                        [8]
                              Syslog-sign Protocol                  June 2001

        configuration required for syslog-sign is to give each
        priority+facility code its own signature group.  (Syslog-syslog
        [Lonvick, 2001] requires that syslog messages be routed only based on
        this code.)

     2.3.1.2 Timestamp

        The timestamp is of the form specified in syslog-syslog [Lonvick,
        2001], e.g. "Jan  1 14:33:54" or "Dec 19 02:01:00".  The timestamp
        contains the local time on the device at the time the message is
        signed.  Devices which do not have a clock MUST use the following
        format:
        "Jan  1 00:00:00".

     2.3.1.3 Hostname

        The hostname is part of the device's configuration.  The device will
        determine how many messages to include per signature block based
mainly
        on the length of this parameter, so we recommend keeping the hostname
        parameter relatively short.

     2.3.1.4 Cookie

        The cookie is an eight byte sequence to signal to the
        verifier that this is a signature block.  This sequence is
        "@#sigSIG", without the quotes.

     2.3.1.5 SIG

        The signature group appears at the end of the text block.  It is a one-
        to-three character string of ASCII digits, between 0 and 191
inclusive.
        Depending on the device's configuration, this number may be the
same as
        the PRI, or different.

     2.3.2 Base-64 Encoded Binary Block

        The binary fields in the signature block must be encoded in base-64,
        because syslog messages may only contain printable characters.  Again,
        the fields must be parsed individually, with the first five fields
        having fixed length, but the hash block's length varying according to
        how many messages have been signed.

     2.3.2.1 Version

        The version specifies what version of the syslog-sign
        protocol is being used, what hash algorithm is being used,
        and what signature scheme is being used.  This is broken up
        into three fields, as follows:

        a.  Protocol Version (0-65535)

        This is encoded as two bytes.  The version of the protocol
        in this document is 1, in binary %b0000000000000001.  Version 0 is


     Kelsey                  Expires November 2001                        [9]
                              Syslog-sign Protocol                  June 2001

        used to represent a local variant of the protocol, used exclusively
        within a single
        installation, and with no guarantee of interoperability with
        other systems.

        b.  Hash Algorithm (0-255)

        This is encoded as one byte.  The following hash algorithms
        are defined for syslog-sign[FIPS-180-1,1993]

                (i)  SHA-1 = 1 (in binary, %b00000001).

        Note that hash algorithms with output size less than 160
        bits, and hash algorithms known or suspected to be
        susceptible to collision-finding attacks, MUST NOT be used
        in syslog-sign.  In particular, MD4 and MD5 MUST NOT be used
        in syslog-sign.

        At the time of this writing, three new hash functions have been
        proposed to replace SHA-1, with output sizes of 256, 384, and 512
bits.
        These hash algorithms have not yet been specified as a new standard,
        and so are not included here.

        Version 0 is used to represent a locally-defined hash
        algorithm, with no promise of interoperability.


        c.  Signature Scheme (0-255)

        This is encoded as one byte.  The only signature scheme
        currently defined is OpenPGP[Callas, et. al,1998] DSA signatures[FIPS-
        186,1994] with p parameter of 1024 bits.  This signature scheme is
        specified as version 1, in binary %b00000001.

        The full version is a four byte string, encoding the first
        and second bytes of the protocol version, then the hash
        version, then the signature version.  Thus, in binary, the initial
        version is %b00000000000000010000000100000001.


        Some version numbers, and the right mechanism for extending
        syslog-sign versions, are discussed below.


     2.3.2.2 Reboot Session ID

        The reboot session ID is a 48-bit quantity, which is
        required to never repeat or decrease in the lifetime of the
        device.  There is no other requirement for how this value is
        set.  It is natural to set this from a timestamp or a reboot
        counter on the device.




     Kelsey                  Expires November 2001                       [10]
                              Syslog-sign Protocol                  June 2001

     2.3.2.3 Global Block Counter

        The global block counter is a 48-bit quantity, and
        represents the number of messages whose signature blocks had
        been sent out by syslog-sign before this one, in this reboot
        session.  Note that this counter crosses signature groups;
        it allows us to roughly synchronize when two messages were
        sent, even though they went to different collectors.


     2.3.2.4 First Message Number

        This is a 48-bit quantity, the unique message number within
        this signature group of the first message whose hash appears
        in this block. (That is, if this signature group has
        processed 1000 messages so far, and the 1001st message from
        this signature group is the first one whose hash appears in
        this signature block, then this field is 1001.)


     2.3.2.5 Count

        The count is a 16-bit quantity, the number of message hashes
        to follow.


     2.3.2.6 Hash Block

        The hash block is a sequence of hash values, their binary
        strings concatenated to make a long sequence of bytes.  The
        length of the binary hash block (before base-64 encoding) is
        the length of the hash values from the hash function used,
        times the count of message hashes specified in the count
        field.


     2.3.2.7 Signature

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

     2.4 Notes on Upgrading Versions

        Note that the format requires that the text block remain unchanged
        across all future versions.  That is, only the base-64 encoded binary
        block may have fields altered.  Also note that the version field MUST
        remain the first binary field in any future version of the protocol.

     3 Payload and Certificate Blocks

        Key management in syslog-sign is supported by certificate
        blocks and payload blocks.  At session startup, the device


     Kelsey                  Expires November 2001                       [11]
                              Syslog-sign Protocol                  June 2001

        builds a payload block; there is exactly one payload block
        built per session.  The payload block carries both
        key-management and session-management information.

        Certificate blocks are valid syslog messages which carry
        fragments of the payload block.  The collector receives
        these certificate blocks, and uses them to reassemble the
        payload block.  The payload block's contents can then be
        cryptographically verified, and its information used.

        All devices MUST generate a payload block at the start of a
        session, and this payload block MUST be transmitted to all
        signature groups by the device, by way of one or more
        certificate blocks.  Certificate blocks SHOULD be sent
        multiple times, to increase the probability that at least
        one copy of each certificate block will be received.

     3.1 Building the Payload Block

        The payload block is built when a new reboot session is
        started.  There is a one-to-one correspondence of reboot
        sessions to payload blocks.  That is, each reboot session
        has only one payload block, regardless of how many signature
        groups it may support.

        The payload block consists of the following:

        a.  Full local timestamp for the device, including year if
        available, at time reboot session started.  This SHOULD be a
        valid timestamp, but MAY be filled in with ASCII zeros if no
        internal clock is available.  The format of this timestamp
        is "yyyymmddhhmmss", where yyyy is the four-digit year in
        ASCII digits, the first mm is a two digit month value
        (01-12), dd is a two-digit date (01-31), hh is a two-digit
        hour in military time (00-23), the second mm is a two-digit
        minute value (00-59), and the ss is a two-digit seconds
        value (00-59).  For example, January 23, 2054 at 8:35:19 AM
        would be represented as "20540123083519", while February 8,
        2002 at 5:15:00 PM would be shown as "20020208171500".  A
        device without an internal clock would use "00000000000000".

        b.  Signature Group Descriptor.  This consists of a
        one-character field specifying how signature groups are
        assigned. The possibilities are:
                (i)  '0' -- Only one signature group supported.  For
                all signature blocks and certificate blocks,
                sig == pri == 046.

                (ii) '1' -- Each pri value gets its own signature
                group.  For each signature/certificate block,
                sig == pri.

                (iii)'2' -- Signature groups are assigned in some


     Kelsey                  Expires November 2001                       [12]
                              Syslog-sign Protocol                  June 2001

                way with no simple relationship to pri values; for
                all signature/certificate blocks, pri = 046.

                (iv) '3' -- Signature groups are assigned to ranges
                of pri values.  For each signature/certificate
                block, pri = largest pri contained within that
                signature group.

        c.  Highest SIG Value -- a three-character field showing the
        highest SIG value that will ever be seen on a
        signature/certificate block.  This may range from "000" to
        "191".

        d.  Key Blob Type, a one-byte field which holds one of the
        following values:
                (i)  'C' -- a PKIX certificate
                (ii) 'N' -- no key information sent; key is
                            predistributed.
                (iii)'S' -- signed public key

        e.  The key blob, consisting of the raw key data, if any,
        base-64 encoded.

     3.3. Building the Certificate Block

        The certificate block must get the payload block to the
        collector.  Since certificates can legitimately be much
        longer than 1024 bytes, each certificate block carries a
        piece of the payload block.  Note that the device MAY make
        the certificate blocks of any legal length (that is, any
        length less than 1024 bytes) which will hold all the
        required fields.  Software that processes certificate blocks
        MUST deal correctly with blocks of any legal length.

        The certificate block is built as follows:

        a.  "<"

        b.  A PRI value, derived and used exactly the
        same way it will be used for the signature blocks.  This may be one to
        three digits.

        c.  ">"

        d.  A timestamp, as described above for signature blocks.

        e.  " "

        f.  A hostname, as described above for signature blocks.

        g.  " "

        h.  Cookie, an eight byte string, "@#sigCer".


     Kelsey                  Expires November 2001                       [13]
                              Syslog-sign Protocol                  June 2001


        i.  SIG, a one to three-digit character string, as described above
        for signature blocks.

        j.  A base-64 encoded blob, which encodes the following
        binary fields:

                (i)  Version, as described above for signature
                     blocks.

                (ii) RSID, as described above for signature blocks.

                (iii)Payload length, a four-byte value encoding an
                     unsigned 32-bit integer, whose value is the
                     total payload block's length in bytes.

                (iv) Index, a 32-bit integer (encoded as four bytes)
                     that specifies where in the payload block
                     this fragment belongs.

                (v)  Fragment Length, a 16-bit integer (encoded as
                     two bytes) that specifies the number of bytes
                     in this certificate block's Fragment field.

                (vi) Fragment, the raw fragment.

                (vii)Signature, a digital signature on all the above
                     fields.

     3.4 Use of Certificate and Payload Blocks

        The certificate blocks carry signatures, which will
        sometimes only be verifiable after the payload block is
        reconstructed and used.  The certificate and payload blocks
        should be processed as follows:

        a.  Collect all the certificate blocks.  Verify that the
        versions, lengths, indexes, and RSIDs are all valid and
        internally consistent.

        b.  Rebuild the payload block.

        c.  Verify the parameters of the payload block, and
        particularly the key blob.

        d.  Extract or verify the key.

        e.  Verify all the certificate blocks' signatures.

        f.  If all verifications were successful, accept the key and
        session.  If any certificate block failed to be verified,
        then search for redundantly-sent versions of the certificate
        blocks.


     Kelsey                  Expires November 2001                       [14]
                              Syslog-sign Protocol                  June 2001


        There are two reasons for putting the signatures on
        certificate blocks:

        a.  Installations with predistributed keys can simply verify
        the signatures as the certificate blocks come in.

        b.  Information in the certificate blocks, such as hostname,
        RSID, etc., needs to be verified cryptographically before it
        can be trusted.  Otherwise, an attacker could send misleading
        certificate blocks reflecting the use of an old key with a new RSID.


     4 Redundancy and Flexibility

        There is a general rule that determines how redundancy
        works, and what level of flexibility the device and
        collector have in message formats:  In general, the device
        MAY send any legal signature or certificate block any number
        of times.  The collector MUST be able to process any legal
        signature or certificate block, and MUST NOT have its
        authenticated log output changed by receipt of any number of
        additional copies of a valid signature or certificate block
        after the first one.


     4.1 Redundancy

        Syslog messages are sent over unreliable transport, which
        means that they can be lost in transit.  However, signature
        and certificate blocks must be received by the collector, or
        many messages may not be able to be verified.  Redundancy is
        provided by sending signature and certificate blocks
        multiple times; since the collector MUST ignore
        signature/certificate blocks it has already received and
        authenticated, the device can in principle change its
        redundancy level for any reason, without communicating this
        fact to the collector.

        Although the device isn't constrained in how it decides to
        send redundant signature and certificate blocks, or even in
        whether it decides to send along multiple copies of normal
        syslog messages, here we define some redundancy parameters
        below which may be useful in controlling redundant
        transmission from the device to the collector.  The
        collector has no knowledge of these parameters; the device
        MAY use them, but is not required to.


     4.1.1 Certificate Blocks

        There are three parameters for certificate block
        redundancy:


     Kelsey                  Expires November 2001                       [15]
                              Syslog-sign Protocol                  June 2001


        a.  certInitialRepeat, the number of times each certificate block
        should be sent to each signature group before the first
        message is sent.

        b.  certResendDelay, the maximum time delay in seconds
        before next redundant sending of the certificate blocks.
        (Certificate blocks are resent periodically during a long
        message, so that offline analysis of the logs remains
        possible even if the initial certificate blocks are not
        received correctly.)

        c.  certResendCount, maximum number of sent messages to delay before
        next redundant sending.

     4.1.2 Signature Blocks

        The following parameters define a strategy for redundant
        signature blocks:

        a.  sigNumberResends, the number of times a signature block
        is resent.

        b.  sigResendDelay, the maximum time delay in seconds from
        original sending to next redundant sending.

        c.  sigResendCount, the maximum number of sent messages to
        delay before next redundant sending.


     4.2 Flexibility

        The device may change many things about the makeup of
        signature and certificate blocks in a given reboot session.
        The things it cannot change are:

        a.  The version.

        b.  The number or arrangements of signature groups

        c.  The signing key.

        d.  The RSID.

        These are fixed per session.  A device MUST NOT change these
        during a session.  A collector that sees
        signature or certificate blocks with any of these things
        different than the current session MUST check the RSID to
        see if the blocks come from an earlier or later session.
        Blocks from an earlier session MUST be ignored and
        discarded.  Blocks from a later session MUST cause the
        collector to switch to a new session, and to attempt to find
        the key for the new session.


     Kelsey                  Expires November 2001                       [16]
                              Syslog-sign Protocol                  June 2001


        When logs are to be verified, the collector MUST have the
        most recent RSID of a valid session.  It MUST NOT accept
        logs from a session whose RSID is less than or equal to the
        most recent RSID.  It MUST NOT accept a new RSID as valid
        unless the full payload block from that RSID has been
        received and verified, and its certificate blocks have also
        been verified.

     4.3 Short Signature or Certificate Blocks

        There is no requirement for signature or certificate blocks
        to be any specific length, so long as they are never longer
        than 1024 bytes.  A device MAY vary the length of successive
        certificate blocks for any reason, a collector or log
        verification program MUST process these correctly regardless
        of their length, so long as they are valid blocks.

     5 Efficient Verification of Logs

        The logs secured with syslog-sign may either be reviewed
        online or offline.  Online review is somewhat more
        complicated and computationally expensive, but not
        prohibitively so.

     5.1. Offline Review of Logs

        When logs are stored by the collector and reviewed later,
        they can be authenticated offline just before they are to be
        reviewed.  Reviewing these logs offline is simple and
        relatively cheap in terms of resources used, so long as
        there is enough space available on the reviewing machine.
        Here, we will consider that the stored log files have
        already been separated by sender, reboot session ID, and
        signature group.  This can be done very easily with a script
        file.  We then do the following:

        a.  First, we go through the raw log file, and split its
        contents into three files.  Each message in the raw log file
        is classified as a normal message, a signature block, or a
        certificate block.  Certificate blocks and signature blocks
        are stored in their own files.  Normal messages are stored
        in a keyed file, indexed on their hash values.

        b.  We sort the certificate block file by index value, and
        check to see if we have a set of certificate blocks that can
        reconstruct the payload block.  If so, we reconstruct the
        payload block, verify any key-identifying information, and
        then use this to verify the signatures on the certificate
        blocks we've received.  When this is done, we have verified
        the reboot session and key used for the rest of the process.

        c.  We sort the signature block file by the First Message


     Kelsey                  Expires November 2001                       [17]
                              Syslog-sign Protocol                  June 2001

        Number field.  We now create an authenticated log file,
        which will consist of some header information, and then a
        sequence of message number, message text pairs.  We next go
        through the signature block file.  For each signature block
        in the file, we do the following:

        (i)  Verify the signature on the block.
        (ii) For each hashed message in the block:
                (a) Look up the hash value in the keyed message file.
                (b)  If the message is found, write (message
                     number,message text) to the authenticated log
                     file.
        (iii)Skip all other signature blocks with the same
             firstMessageNumber.

        d.  The resulting authenticated log file will contain all
        messages which have been authenticated, and will indicate
        (by missing message numbers) all gaps in the authenticated
        messages.

        It's pretty easy to see that, assuming sufficient space for
        building the keyed file, this whole process is linear in the
        number of messages (generally two seeks, one to write and
        the other to read, per normal message received), and O(N lg
        N) in the number of signature blocks.  This estimate comes
        with two caveats:  First, the signature blocks will arrive
        very nearly in sorted order, and so can probably be sorted
        more cheaply on average than O(N lg N) steps.  Second, the
        signature verification on each signature block will almost
        certainly be more expensive than the sorting step in
        practice.  We haven't discussed error-recovery, which may be
        necessary for the certificate blocks.  In practice, a very
        simple error-recovery strategy is probably good enough--if
        the payload block doesn't come out as valid, then we can
        just try an alternate instance of each certificate block, if
        such are available, until we get the payload block right.

        It's easy for an attacker to flood us with plausible-looking
        messages, signature blocks, and certificate blocks.

     5.2. Online Review of Logs

        Some processes on the collector machine may need to monitor
        log messages in something very close to real-time.  This can
        be done with syslog-sign, though it is somewhat more
        complex than the offline analysis.  This is done as follows:

        a.  We have an output queue, into which we write (message
        number, message text) pairs which have been authenticated.
        Again, we'll assume we're handling only one signature group,
        and only one reboot session ID, at any given time.

        b.  We have three data structures:  A queue into which


     Kelsey                  Expires November 2001                       [18]
                              Syslog-sign Protocol                  June 2001

        (message number, hash of message) pairs is kept in sorted
        order, a queue into which (arrival sequence, hash of
        message) is kept in sorted order, and a hash table which
        stores (message text, count) indexed by hash value.  In this
        file, count may be any number greater than zero; when count
        ==0, the entry in the hash table is cleared.

        c.  We must receive all the certificate blocks before any
        other processing can really be done.  (This is why they're
        sent first.)  Once that's done, any certificate block that
        arrives is discarded.

        d.  Whenever a normal message arrives, we add (arrival
        sequence, hash of message) to our message queue.  If our
        hash table has an entry for the message's hash value, we
        increment its count by one; otherwise, we create a new entry
        with count = 1.  When the message queue is full, we roll the
        oldest messages off the queue by taking the last entry in
        the queue, and using it to index the hash table.  If that
        entry has count==1, we delete the entry in the hash table;
        otherwise, we decrement its count.  We then delete the last
        entry in the queue.

        e.  Whenever a signature block arrives, we first check to
        see if the firstMessageNumber value is too old, or if
        another signature block with that firstMessageNumber has
        already been received.  If so, we discard the signature
        block unread.  Otherwise, we check its signature, and
        discard it if the signature isn't valid.  A signature block
        contains a sequence of (message number, message hash) pairs.
        For each pair, we first check to see if the message hash is
        in the hash table.  If so, we write out the (message number,
        message text) in the authenticated message queue.
        Otherwise, we write the (message number, message hash) to
        the message number queue.  This generally involves rolling
        the oldest entry out of this queue: before this is done,
        that entry's hash value is again searched for in the hash
        table.  If a matching entry is found, the (message
        number,message text) pair is written out to the
        authenticated message queue.  In either case, the oldest
        entry is then discarded.

        f.  The result of this is a sequence of messages in the
        authenticated message queue, each of which has been
        authenticated, and which are combined with numbers showing
        their order of original transmission.

        It's not too hard to see that this whole process is roughly
        linear in the number of messages, and also in the number of
        signature blocks received.  The process is susceptible to
        flooding attacks; an attacker can send enough normal
        messages that the messages roll off their queue before their
        signature blocks can be processed.


     Kelsey                  Expires November 2001                       [19]
                              Syslog-sign Protocol                  June 2001



     6 Security Considerations

        The following are some important security considerations for
        using syslog-sign.

        a.  The strength of syslog-sign is totally dependent on the
        strength of the underlying hash function and digital
        signature algorithm, and on the quality of their
        implementation.  For this reason, it is critical that new
        versions of syslog-sign not be added to the standard without
        a thorough cryptographic review of:

                (i)  The signature scheme
                (ii) The hash algorithm
                (iii)Any changes to the protocol
                (iv) Any possible interactions between protocol
                     steps and versions.

        New versions and version numbers MUST NOT be added without a review by
        a
        competent person appointed by the area directors.

        b.  Local variations (assumed not to be compatible with
        external systems) are supported by setting the protocol,
        hash, or signature version to 0x00.  This is intended to
        allow sophisticated users to make use of existing
        cryptographic infrastructure.  Users are warned that making
        alterations of this kind locally should not be done without
        competent cryptographic review.

        c.  As with most cryptographic mechanisms, the quality of
        random number generation available for key and signature
        generation is a major factor in determining whether this
        system will be secure.  We strongly recommend the use of
        some well-tested and -reviewed cryptographic random number
        source.  Some recommendations may be found
        in [RFC1750], and a number of competent designs exist in
        cryptographic libraries.  (In particular, many UNIX systems
        have a /dev/random interface that meets these requirements.)

        d.  The implementation of syslog-sign which receives and
        processes logs, online or offline, must be carefully
        reviewed for programming errors that would allow buffer
        overruns or similar attacks, as these would allow an
        attacker to bypass all the cryptographic protection used.

        e.  In particular, certificate blocks and payload blocks
        have the problem that they are processed extensively before
        they may be verified.  Programs that process these MUST NOT
        be susceptible to buffer overrun or other program failures
        when the payload lengths, fragment lengths, or indexes of


     Kelsey                  Expires November 2001                       [20]
                              Syslog-sign Protocol                  June 2001

        the certificate blocks are inconsistent.

        f.  As processing power, memory, and bandwidth grow cheaper, extended
        key sizes will become necessary.  As of this writing, DSA has a
maximum
        supported parameter sizes of |q|==160, |p|==1024.  In the near future,
        we expect NIST to specify DSA variants with |q| up to 512 bits, and
|p|
        of 4096 or more bits, using a hash function whose output is the same
        size as |q|.  These extensions will change the number of messages per
        signature block that are possible, and may have a noticeable impact on
        the ultimate efficiency of the protocol.  However, even with |q|==512,
        we should be able to sign 7 messages per signature block; with a more
        realistic |q|==256, we should be able to sign 17 messages per
signature
        block.


     7 Conclusions and Open Issues

        In this note, we have described syslog-sign, a mechanism for
        adding origin authentication, data integrity, message
        sequencing, and gap and replay detection to syslog over UDP.
        Syslog-sign does not require moving syslog to TCP, and is
        intended to minimize the impact of required changes to
        existing devices, relays, and servers on the network.  In
        addition to meeting these goals, syslog-sign using digital
        signatures provides storage security, since an attacker who
        takes over the collector but doesn't know the device's
        private key cannot alter the saved logs.  Note, however,
        that nothing prevents such an attacker from simply deleting
        the log messages he finds inconvenient.  While those
        messages will obviously be missing from the log when it is
        reviewed, there is no way for the reviewer to know whether
        those messages ever really arrived at the collector.


     7.1 Initial Version

        We have specified the first complete version of syslog-sign
        as follows:

        Protocol Version: 1 (this protocol)
        Hash Function: 1 (SHA1)
        Signature: 1 (openPGP DSA signatures)

        The total version value is {0x00, 0x01, 0x01, 0x01} as a
        sequence of bytes.



     8 Test Values

        The following are some test values generated by the author.




     Kelsey                  Expires November 2001                       [21]
                              Syslog-sign Protocol                  June 2001

     8.1 Generating Signature Blocks

     8.2 Generating Payload and Certificate Blocks


     9 Acknowledgements

        The author wishes to thank Alex Brown, Chris Calabrese, Jon
        Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin
        New, Marshall Rose, Bruce Schneier, Holt Sorenson, Rodney
        Thayer, the many Counterpane Internet Security engineering
        and operations people who commented on various versions of
        this proposal, and Counterpane Internet Security and Certicom
        for their generous support of this work.


     10 Bibliography

        Schneier, _Applied Cryptography_, John Wiley & Sons, 1996.

        Menezes, van Oorschot, Vanstone, _Handbook of Applied
        Cryptography_, CRC Press, 1997.

        FIPS-180-1, "Secure Hash Standard," Federal Information
        Processing Standards Publication 180-1, U.S. Department of
        Commerce, 1993.

        FIPS-186, "Digital Signature Standard," Federal Information
        Processing Standards Publication 186, U.S. Department of
        Commerce, 1994.

        Callas, Donnerhacke, Finney, and Thayer, "OpenPGP Message
        Format," RFC2440, Nov 1998.

        Eastlake, Crocker and Schiller, "Randomness Recommendations
        for Security," RFC1750, Internet Engineering Task Force, Dec
        1994.

        Lonvick, "Syslog Protocol", Internet Draft,
        draft-ietf-syslog-syslog-06.txt, Feb 2001


     A Author's Address

        John Kelsey
        Certicom
        kelsey.j@ix.netcom.com / jkelsey@certicom.com

     B Full Copyright Statement

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

        This document and translations of it may be copied and furnished to


     Kelsey                  Expires November 2001                       [22]
                              Syslog-sign Protocol                  June 2001

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

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

        This document and the information contained herein is provided on an
        "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
        TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT
        NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN
WILL
        NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR
        FITNESS FOR A PARTICULAR PURPOSE.


































     Kelsey                  Expires November 2001                       [23]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/