Network Working Group John Kelsey
Category: INTERNET-DRAFT Certicom
draft-ietf-syslog-sign-06.txt
Expires October 2002 Jon Callas
April 2002 Wave Systems Corporation
Syslog-Sign Protocol
draft-ietf-syslog-sign-06.txt
Copyright Notice
Copyright 2002 by The Internet Society. All Rights Reserved.
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.
Abstract
This document describes syslog-sign, a mechanism adding origin
authentication, message integrity, replay-resistance, message
sequencing, and detection of missing messages to syslog. Syslog-sign
provides these security features in a way that has minimal
Kelsey, Callas Expires October 25, 2002 [Page 1]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
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. Some additional processing of the received syslog
messages and the syslog-sign messages on the relays and collectors
may realize additional security benefits.
Kelsey, Callas Expires October 25, 2002 [Page 2]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
Table of Contents
Copyright Notice 1
Status of this Memo 1
Abstract 1
Table of Contents 3
1. Introduction 4
2. Required syslog Format 4
2.1. PRI Part 5
2.2. HEADER Part 6
2.3. MSG Part 7
2.4. Examples 7
3. Signature Block Format and Fields 8
3.1. syslog Packets Containing a Signature Block 8
3.2. Cookie 9
3.3. Version 9
3.4. Reboot Session ID 9
3.5. Signature Group 10
3.6. Global Block Counter 11
3.7. First Message Number 11
3.8. Count 11
3.9. Hash Block 11
3.10. Signature 11
4. Payload and Certificate Blocks 11
4.1. Preliminaries: Key Management and Distribution Issues 12
4.2. Building the Payload Block 12
4.3. Building the Certificate Block 13
5. Redundancy and Flexibility 14
5.1. Redundancy 14
5.1.1. Certificate Blocks 15
5.1.2. Signature Blocks 15
5.2. Flexibility 15
6. Efficient Verification of Logs 15
6.1. Offline Review of Logs 16
6.2. Online Review of Logs 17
7. Security Considerations 18
8. IANA Considerations 18
9. Authors and Working Group Chair 19
10. Acknowledgements 19
11. References 19
12. Full Copyright Statement 20
Kelsey, Callas Expires October 25, 2002 [Page 3]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
1. Introduction
Syslog-sign is an enhancement to syslog [RFC3164] that adds origin
authentication, message integrity, replay resistance, message
sequencing, and detection of missing messages to syslog. This
mechanism makes no changes to the syslog packet format but does
require strict adherence to that format. A syslog-sign message
contains a signature block within the MSG part of a syslog message.
This signature block contains a separate digital signature for each
of a group of previously sent syslog messages. The overall message
is also signed as the last value in this message.
Each signature block contains, in effect, a detached signature on
some number of previously sent messages. While most implementations
of syslog involve only a single device as the generator of each
message and a single receiver as the collector of each message,
provisions need to be made to cover messages being sent to multiple
receivers. This is generally performed based upon the Priority value
of the individual messages. For example, messages from any Facility
with a Severity value of 3, 2, 1 or 0 may be sent to one collector
while all messages of Facilities 4, 10, 13, and 14 may be sent to
another collector. Appropriate syslog-sign messages must be kept
with their proper syslog messages. To address this, syslog-sign
utilizes 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.
Additionally, a device will send a certificate block to provide key
management information between the sender and the receiver. This
certificate block has a field to denote the type of key material
which may be such things as a PKIX certificate, and OpenPGP
certificate, or even an indication that a key had been
predistributed. In all cases, these messages will still utilize the
syslog packet format. In the cases of certificates being sent, the
certificates may have to be split across multiple packets.
The receiver of the previous messages may verify that the digital
signature of each received message matches the signature contained
in the signature block. A collector may process these signature
blocks as they arrive, building an authenticated log file.
Alternatively, it may store all the log messages in the order they
were received. This allows a network operator to authenticate the
log file at the time the logs are reviewed.
2. Required syslog Format
The essential format of syslog messages is defined in RFC 3164. The
basis of the format is that anything delivered to UDP port 514 MUST
be accepted as a valid syslog message. However, there is a
RECOMMENDED format laid out in that work which this work REQUIRES.
Kelsey, Callas Expires October 25, 2002 [Page 4]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
Packets conforming to this specification will REQUIRE this format.
The full format of a syslog sign message seen on the wire has three
discernable parts. The first part is called the PRI, the second part
is the HEADER, and the third part is the MSG. The total length of
the packet MUST be 1024 bytes or less. There is no minimum length of
the syslog message although sending a syslog packet with no contents
is worthless and SHOULD NOT be transmitted.
The definitions of the fields are slightly changed in this document
from RFC 3164. While the format described in RFC 3164 is correct for
packet formation, the Working Group evaluating this work determined
that it would be better if the TAG field were to become a part of
the HEADER part rather than the CONTENT part. While IETF
documentation does not allow the specification of an API, people
developing code to adhere to this specification have found it
helpful to think about the parts in this format.
syslog-sign messages from devices MUST conform to this format. Other
syslog messages from devices SHOULD also conform to this format. If
they do not conform to this format, they may be reformatted by a
relay as described in Section 4.3 of RFC 3164. That would change the
format of the original messages and any cryptographic signature of
the original message would not match the cryptographic signature of
the changed message.
2.1. PRI Part
The PRI part MUST have three, four, or five characters and will be
bound with angle brackets as the first and last characters. The PRI
part starts with a leading "<" ('less-than' character), followed by
a number, which is followed by a ">" ('greater-than' character). The
code set used in this part MUST be seven-bit ASCII in an eight- bit
field as described in RFC 2234 [RFC2234]. These are the ASCII codes
as defined in "USA Standard Code for Information Interchange" [3].
In this, the "<" character is defined as the Augmented Backus-Naur
Form (ABNF) %d60, and the ">" character has ABNF value %d62. The
number contained within these angle brackets is known as the
Priority value and represents both the Facility and Severity as
described below. The Priority value consists of one, two, or three
decimal integers (ABNF DIGITS) using values of %d48 (for "0")
through %d57 (for "9").
The Facilities and Severities of the messages are defined in RFC
3164. The Priority value is calculated by first multiplying the
Facility number by 8 and then adding the numerical value of the
Severity. For example, a kernel message (Facility=0) with a Severity
of Emergency (Severity=0) would have a Priority value of 0. Also, a
"local use 4" message (Facility=20) with a Severity of Notice
(Severity=5) would have a Priority value of 165. In the PRI part of
a syslog message, these values would be placed between the angle
brackets as <0> and <165> respectively. The only time a value of "0"
Kelsey, Callas Expires October 25, 2002 [Page 5]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
will follow the "<" is for the Priority value of "0". Otherwise,
leading "0"s MUST NOT be used.
2.2. HEADER Part
The HEADER part contains a time stamp, an indication of the hostname
or IP address of the device, and a string indicating the source of
the message. The HEADER part of the syslog packet MUST contain
visible (printing) characters. The code set used MUST also been
seven-bit ASCII in an eight-bit field like that used in the PRI
part. In this code set, the only allowable characters are the ABNF
VCHAR values (%d33-126) and spaces (SP value %d32).
The HEADER contains three fields called the TIMESTAMP, the HOSTNAME,
and the TAG fields. The TIMESTAMP will immediately follow the
trailing ">" from the PRI part and single space characters MUST
follow each of the TIMESTAMP and HOSTNAME fields. HOSTNAME will
contain the hostname, as it knows itself. If it does not have a
hostname, then it will contain its own IP address. If a device has
multiple IP addresses, it has usually been seen to use the IP
address from which the message is transmitted. An alternative to
this behavior has also been seen. In that case, a device may be
configured to send all messages using a single source IP address
regardless of the interface from which the message is sent. This
will provide a single consistent HOSTNAME for all messages sent from
a device.
The TIMESTAMP field is the local time and is in the format of "Mmm
dd hh:mm:ss" (without the quote marks) where:
Mmm is the English language abbreviation for the month of the
year with the first character in uppercase and the other two
characters in lowercase. The following are the only acceptable
values:
Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec
dd is the day of the month. If the day of the month is less than
10, then it MUST be represented as a space and then the number.
For example, the 7th day of August would be represented as "Aug
7", with two spaces between the "g" and the "7".
hh:mm:ss is the local time. The hour (hh) is represented in a
24-hour format. Valid entries are between 00 and 23, inclusive.
The minute (mm) and second (ss) entries are between 00 and 59
inclusive.
A single space character MUST follow the TIMESTAMP field.
The HOSTNAME field will contain only the hostname, the IPv4 address,
or the IPv6 address of the originator of the message. The preferred
value is the hostname. If the hostname is used, the HOSTNAME field
Kelsey, Callas Expires October 25, 2002 [Page 6]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
MUST contain the hostname of the device as specified in STD-13 [4].
The Domain Name MUST NOT be included in the HOSTNAME field. If the
IPv4 address is used, it MUST be shown as the dotted decimal
notation as used in STD-13 [5]. If an IPv6 address is used, any
valid representation used in RFC-2373 [6] MAY be used. A single
space character MUST also follow the HOSTNAME field.
The TAG is a string of ABNF alphanumeric characters and other
certain special characters, that MUST NOT exceed 32 characters in
length. There are three special characters that are acceptable to
use in this field as well.
[ ABNF %d91
] ABNF %d93
: ABNF %d58
The first occurrence of a colon (":") character will terminate the
TAG field. Generally, the TAG will contain the name of the process
that generated the message. It may OPTIONALLY contain additional
information such as the numerical process ID of that process bound
within square brackets ("[" and "]"). A colon MUST be the last
character in this field.
2.3. MSG Part
The MSG part contains the details of the message. This has
traditionally been a freeform message that gives some detailed
information of the event. The MSG part of the syslog packet MUST
contain visible (printing) characters. The code set used MUST also
been seven-bit ASCII in an eight-bit field like that used in the PRI
part. In this code set, the only allowable characters are the ABNF
VCHAR values (%d33-126) and spaces (SP value %d32). Two message
types will be defined in this document. Each will have unique fields
within the MSG part and they will be described below.
2.4. Examples
The following examples are given.
Example 1
<34>Oct 11 22:14:15 mymachine su: 'su root' failed for
lonvick on /dev/pts/8
In this example, as it was originally described in RFC 3164, the PRI
part is "<34>". In this work, however, the HEADER part consists of
the TIMESTAMP, the HOSTNAME, and the TAG fields. The TIMESTAMP is
"Oct 11 22:14:15 ", the HOSTNAME is "mymachine ", and the TAG value
is "su:". The CONTENT field is " 'su root' failed for lonvick...".
The CONTENT field starts with a leading space character in this
case.
Kelsey, Callas Expires October 25, 2002 [Page 7]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
Example 2
<165>Aug 24 05:34:00 10.1.1.1 myproc[10]:%% It's time to
make the do-nuts. %% Ingredients: Mix=OK, Jelly=OK #
Devices: Mixer=OK, Jelly_Injector=OK, Frier=OK # Transport:
Conveyer1=OK, Conveyer2=OK # %%
In this example, the PRI part is <165> denoting that it came from a
locally defined facility (local4) with a severity of Notice. The
HEADER part has a proper TIMESTAMP field in the message. A relay
will not modify this message before sending it. The HOSTNAME is an
IPv4 address and the TAG field is "myproc[10]:". The MSG part starts
with "%% It's time to make the do-nuts. %% Ingredients: Mix=OK,
..." this time without a leading space character.
3. Signature Block Format and Fields
Since the device generating the signature block message signs the
entire syslog message, it is imperative that the message MUST NOT be
changed in transit. In adherence with Section 4 of [RFC3164], a
fully formed syslog message containing a PRI part and a HEADER part
containing TIMESTAMP and HOSTNAME fields MUST NOT be changed or
modified by any relay.
3.1. syslog Packets Containing a Signature Block
Signature block messages MUST be completely formed syslog messages.
Signature block messages have PRI, HEADER, and MSG parts as
described in Sections 4.1.1 and 4.1.3 of [RFC3164]. The PRI part
MUST have a valid Priority value bounded by angled brackets. The
HEADER part MUST have a valid TIMESTAMP field as well as a HOSTNAME
field. It SHOULD also contain a valid TAG field. It is RECOMMENDED
that the TAG field have the value of "syslog " (without the double
quotes) to signify that this message was generated by the syslog
process. The CONTENT field of the syslog signature block messages
have the following fields. Each of these fields are separated by a
single space character.
The signature block is composed of the following fields. Each field
must be printable ASCII, and any binary values are base-64 encoded.
Field Size in bytes
----- ---- -- -----
Cookie 8
Version 4
Reboot Session ID 1-10
Kelsey, Callas Expires October 25, 2002 [Page 8]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
Signature Group 1-3
Global Block Counter 1-10
First Message Number 1-10
Count 1-2
Hash Block variable, size of hash
Signature variable
These fields are described below.
3.2. Cookie
The cookie is a nine-byte sequence to signal that this is a
signature block. This sequence is "@#sigSIG " (without the double
quotes).
3.3. Version
The signature group version field is 4 characters in length and is
terminated with a space character. The value in this field specifies
the version of the syslog-sign protocol and is terminated with a
space character. This is extensible to allow for different hash
algorithms and signature schemes to be used in the future. The value
of this field is the grouping of the protocol version (2 bytes), the
hash algorithm (1 byte) and the signature scheme (1 byte).
Protocol Version - 2 bytes with the first version as described
in this document being value of 01 to denote Version 1.
Hash Algorithm - 1 byte with the definition that 1 denotes SHA1.
[FIPS-180-1]
Signature Scheme - 1 byte with the definition that 1 denotes
OpenPGP DSA [RFC2440], [DSA94].
As such, the version, hash algorithm and signature scheme may be
represented as "0111" (without the quote marks).
3.4. Reboot Session ID
The reboot session ID is a value between 1 and 10 bytes, which is
required to never repeat or decrease. The acceptable values for
this are between 0 and 9999999999. If the value latches at
9999999999, then manual intervention may be required to reset it to
0. Implementors MAY wish to consider using the snmpEngineBoots
value as a source for this counter as defined in [RFC 2574].
Kelsey, Callas Expires October 25, 2002 [Page 9]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
3.5. Signature Group
The SIG identifier as described above may take on any value from
0-191 inclusive, and is presented as the decimal value in the same
manner as is the PRI.
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 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 = XXX. 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.
b. '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 = XXX.
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 regular expression), 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 regular expressions.
Options (a) and (d) set the PRI value to XXX 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
Kelsey, Callas Expires October 25, 2002 [Page 10]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
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.
3.6. Global Block Counter
The global block counter is a value representing the number of
signature blocks sent out by syslog-sign before this one, in this
reboot session. This takes at least 1 byte and at most 10 bytes
displayed as a decimal counter and the acceptable values for this
are between 0 and 9999999999. If the value latches at 9999999999,
then the reboot session counter must be incremented by 1 and the
global block counter will resume at 0. 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.
3.7. First Message Number
This is a value between 1 and 10 bytes. It contains the unique
message number within this signature group of the first message
whose hash appears in this block.
For example, if this signature group has processed 1000 messages so
far and message number 1001 is the first message whose hash appears
in this signature block, then this field contains 1001.
3.8. Count
The count is a 1 or 2 byte field displaying the number of message
hashes to follow. The valid values for this field are between 1 and
99.
3.9. Hash Block
The hash block is a block of hashes, each separately encoded in
base-64. The hashing algorithm used effectively specified by the
Version field determines the size of each hash, but the size MUST
NOT be shorter than 160 bits.
3.10. Signature
This is a digital signature, encoded in base-64. The Version field
effectively specifies the original encoding of the signature.
4. Payload and Certificate Blocks
Certificate blocks and payload blocks provide key management in
syslog-sign.
Kelsey, Callas Expires October 25, 2002 [Page 11]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
4.1. Preliminaries: Key Management and Distribution Issues
The purpose of certificate blocks is to support key management using
public key cryptosystems. All devices send at least one certificate
block at the beginning of a new reboot session, carrying useful
information about the reboot session.
There are three key points to understand about certificate blocks:
a. They handle a variable-sized payload, fragmenting it if
necessary and transmitting the fragments as legal syslog
messages. This payload is built (as described below) at the
beginning of a reboot session and is transmitted in pieces with
each certificate block carrying a piece. Note that there is
exactly one payload block per reboot session.
b. The certificate blocks are digitally signed. The device does not
sign the payload block, but the signatures on the certificate
blocks ensure its authenticity. Note that it may not even be
possible to verify the signature on the certificate blocks
without the information in the payload block; in this case the
payload block is reconstructed, the key is extracted, and then
the certificate blocks are verified. (This is necessary even
when the payload block carries a certificate, since some other
fields of the payload block aren't otherwise verified.) In
practice, I expect that most installations will keep the same
public key over long periods of time, so that most of the time,
it's easy to verify the signatures on the certificate blocks,
and use the payload block to provide other useful per-session
information.
c. The kind of payload block that is expected is determined by what
kind of key material is on the collector that receives it. The
device and collector (or offline log viewer) has both some key
material (such as a root public key, or predistributed public
key), and an acceptable value for the Key Blob Type in the
payload block, below. The collector or offline log viewer MUST
NOT accept a payload block of the wrong type.
4.2. 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. Unique identifier of sender; by default, the sender's IP
address in dotted-decimal (IPv4) or colon-separated (IPv6)
notation.
Kelsey, Callas Expires October 25, 2002 [Page 12]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
b. Full local time stamp for the device, including year if
available, at time reboot session started.
c. 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 == XXX.
(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 way with no
simple relationship to pri values; for all
signature/certificate blocks, pri = XXX.
(iv) '3' -- Signature groups are assigned to ranges of pri
values. For each signature/certificate block, pri = largest
pri contained within that signature group.
d. Highest SIG Value -- a one, two, or three byte field, must be a
number between 0 and 191, inclusive.
e. Key Blob Type, a one-byte field which holds one of four values:
(i) 'C' -- a PKIX certificate.
(ii) 'P' -- an OpenPGP certificate.
(iii) 'K' -- the public key whose corresponding private key is
being used to sign these messages.
(iv) 'N' -- no key information sent; key is predistributed.
(v) 'U' -- installation-specific key exchange information
f. The key blob, consisting of the raw key data, if any, base-64
encoded.
4.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.
Kelsey, Callas Expires October 25, 2002 [Page 13]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
The certificate block is built as follows:
a. Cookie -- an eight byte string, "@#sigCer".
b. Version -- two bytes with 01 being the version
described in this document.
c. Reboot Session ID -- as above, a 10-byte quantity, which is
required to never repeat or decrease in
the lifetime of the device.
d. Signature Group -- 1 to 3 bytes as described above.
e. Total Payload Length -- 8 bytes numbering the total length
in bytes in decimal.
f. Index into Payload -- 1 to 8 bytes numbering the length into
the payload
g. Fragment Length -- 12 bits base-64 encoded as two bytes.
h. Payload Fragment -- a fragment of the payload, as specified
by the above fields. This fragment is a
piece of the certificate. When all the
fragments are combined, the resulting
data segment is the valid certificate.
i. Signature -- a digital signature on fields a-h.
5. 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 is allowed to send signature and
certificate blocks multiple times, to send signature and certificate
blocks of any legal length, to include fewer hashes in hash blocks,
etc.
5.1. Redundancy
Syslog messages are sent over unreliable transport, which means that
they can be lost in transit. However, the collector must receive
signature and certificate blocks or many messages may not be able to
be verified. Sending signature and certificate blocks multiple times
provides redundancy; 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.
Kelsey, Callas Expires October 25, 2002 [Page 14]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
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 I define some redundancy parameters below which may be useful
in controlling redundant transmission from the device to the
collector.
5.1.1. Certificate Blocks
certInitialRepeat = number of times each certificate block should be
sent before the first message is sent.
certResendDelay = maximum time delay in seconds to delay before
next redundant sending.
certResendCount = maximum number of sent messages to delay before
next redundant sending.
5.1.2. Signature Blocks
sigNumberResends = number of times a signature block is resent.
sigResendDelay = maximum time delay in seconds from original
sending to next redundant sending.
sigResendCount = maximum number of sent messages to delay before
next redundant sending.
5.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:
* The version
* The number or arrangements of signature groups
It is legitimate for a device to send our short signature blocks, in
order to keep the collector able to verify messages quickly. In
general, unless something verified by the payload block or
certificate blocks is changed within the reboot session ID, any
change is allowed to the signature or certificate blocks during the
session. The device may send shorter signature and certificate
blocks for
6. 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.
Kelsey, Callas Expires October 25, 2002 [Page 15]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
6.1. Offline Review of Logs
When the collector stores logs and reviewed later, they can be
authenticated offline just before they are 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 firstMessageNumber. 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
that 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
Kelsey, Callas Expires October 25, 2002 [Page 16]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
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.
6.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 (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 is zero, 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 is 1, we delete the entry in
the hash table; otherwise, we decrement its count. We then
delete the last entry in the queue.
Kelsey, Callas Expires October 25, 2002 [Page 17]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
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.
7. Security Considerations
* As with any technology involving cryptography, you should check
the current literature to determine if any algorithms used here
have been found to be vulnerable to attack.
* This specification uses Public Key Cryptography technologies.
The proper party or parties must control the private key portion
of a public-private key pair.
* Certain operations in this specification involve the use of
random numbers. An appropriate entropy source should be used to
generate these numbers. See [RFC1750].
8. IANA Considerations
As specified in this document, the Priority field contains options
for a hash algorithm and signature scheme. Values of zero are
reserved. A value of 1 is defined to be SHA-1, and OpenPGP-DSA,
respectively. Values 2 through 63 are to be assigned by IANA using
the "IETF Consensus" policy defined in RFC2434. Capability Code
values 64 through 127 are to be assigned by IANA, using the "First
Come First Served" policy defined in RFC2434. Capability Code values
128 through 255 are vendor-specific, and values in this range are
Kelsey, Callas Expires October 25, 2002 [Page 18]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
not to be assigned by IANA.
9. Authors and Working Group Chair
The working group can be contacted via the current chair:
Chris Lonvick
Cisco Systems
Email: clonvick@cisco.com
The authors of this draft are:
John Kelsey
Email: kelsey.j@ix.netcom.com
Jon Callas
Email: jon@callas.org
10. Acknowledgements
The authors wish to thank Alex Brown, Chris Calabrese, Carson
Gaspar, Drew Gross, Chris Lonvick, Darrin New, Marshall Rose, Holt
Sorenson, Rodney Thayer, and the many Counterpane Internet Security
engineering and operations people who commented on various versions
of this proposal.
11. References
[DSA94] NIST, FIPS PUB 186, "Digital Signature Standard",
May 1994.
[FIPS-180-1] "Secure Hash Standard", National Institute of
Standards and Technology, U.S. Department Of
Commerce, April 1995.
Also known as: 59 Fed Reg 35317 (1994).
[MENEZES] Alfred Menezes, Paul van Oorschot, and Scott
Vanstone, "Handbook of Applied Cryptography," CRC
Press, 1996.
[RFC1750] D. Eastlake, S. Crocker, and J. Schiller,
"Randomness Recommendations for Security", RFC
1750, December 1994.
[RFC1983] Malkin, G., "Internet Users' Glossary", FYI 18, RFC
1983, August 1996.
[RFC2085] M. Oehler and R. Glenn, "HMAC-MD5 IP Authentication
with Replay Prevention", RFC 2085, February 1997.
Kelsey, Callas Expires October 25, 2002 [Page 19]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
[RFC2104] H. Krawczyk, M. Bellare, and R. Canetti, "HMAC:
Keyed-Hashing for Message Authentication", RFC 2104
February 1997.
[RFC2119] S. Bradner, "Key words for use in RFCs to Indicate
Requirement Level", BCP 14, RFC 2119, March 1997.
[RFC2234] D. Crocker, P. Overell, "Augmented BNF for Syntax
Specifications: ABNF", RFC 2234, November 1997
[RFC2434] T. Narten and H. Alvestrand, "Guidelines for
Writing an IANA Considerations Section in RFCs",
RFC 2434, October 1998
[RFC2440] J. Callas, L. Donnerhacke, H. Finney, and R.
Thayer,"OpenPGP Message Format", RFC 2440, November
1998.
[RFC3164] C. Lonvick, "The BSD Syslog Protocol", RFC 3164,
August 2001.
[SCHNEIER] Schneier, B., "Applied Cryptography Second Edition:
protocols, algorithms, and source code in C", 1996.
[SYSLOG-REL] D. New, M. Rose, "Reliable Delivery for syslog",
work in progress.
12. Full Copyright Statement
Copyright 2002 by The Internet Society. All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
Kelsey, Callas Expires October 25, 2002 [Page 20]
INTERNET-DRAFT Syslog-Sign Protocol April 25, 2002
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Kelsey, Callas Expires October 25, 2002 [Page 21]