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]
Datatracker
Report a datatracker bug
draft-ietf-syslog-sign-01
Internet-Draft
| Document | Document type |
This is an older version of an Internet-Draft that was ultimately published as RFC 5848.
Expired & archived
|
|
|---|---|---|---|
| Select version | |||
| Compare versions | |||
| Author | |||
| RFC stream |
|
||
| Other formats | |||
| Additional resources | Mailing list discussion |