-----BEGIN PGP SIGNED MESSAGE-----
This is my current description of syslog-sign. I probably missed a
few details, but it's strikingly simple by comparrison. I have
specified nothing about key management, except that you can (if you
want) send a PKIX certificate along with your signed log messages.
I'd appreciate comments.
- --John
/////
An Overview of Syslog-Sign
John Kelsey, Counterpane Internet Security,
[EMAIL PROTECTED]
1.0. Introduction
Syslog-sign is intended to be an in-band protocol for
signing messages within syslog, making no assumptions about
any delivery mechanisms. This means that all messages sent
along are valid syslog-syslog messages. The messages will
be received and stored normally by any syslog collector.
However, offline review of the stored logs by a
syslog-sign-aware program will allow verification of the
logs' origin, integrity, freshness, and completeness.
The basic design goals are thus:
a. The goal of syslog-sign is offline detection of
alterations of the logs. The signatures provide both
storage security and transmission security, but we provide
no support for any kind of online detection of alterations.
(There's nothing saying a collector can't implement such
detection online, assuming it can keep up with the workload.
But we add nothing to support such online detection.)
b. Over the course of a reasonably long session,
syslog-sign will transmit the certificate, public key, or
key ID on which its signatures are based several times.
c. Syslog-sign will provide data integrity, data origin
authentication, replay detection, and gap detection. It is
the responsibility of the users of syslog-sign to ensure
that all the logs in a ``signature group'' are sent to the
same receiver. (A ``signature group'' is a set of messages
signed in the same sequence of signature blocks.) How the
administrator sets things up to support this is outside the
scope of this document, but if messages from the same
signature group are somehow separated during transmission or
forwarding, we will generally be unable to authenticate the
messages stored by any one collector.
d. Because syslog-sign must operate in-band over unreliable
delivery mechanisms, there is always some chance that
critical information will not make it to the receiver.
However, syslog-sign can be configured on the sender side to
add redundancy to its messages, to decrease the likelihood
that any messages will be impossible to verify.
e. Syslog-sign supports multiple signature and hash sizes
and schemes. These are encoded in its version field. Larger
signatures lead to more bandwidth required by syslog-sign.
Syslog-sign even supports symmetric cryptosystems.
f. The only awareness of forwarding in syslog-sign is the
requirement that a syslog-sign relay (as well as a device)
signal some kind of an error if it is required by its
forwarding rules to send messages in the same signature
group to different recipients.
2.0. Syslog-Sign Message Formats
Syslog-sign uses syslog to transmit its messages. That
means that all of its messages have to fit inside legal
syslog-syslog messages. This determines most of the design.
Syslog-sign processes all syslog messages, but it generates
only two kinds of messages of its own: signature blocks and
certificate blocks. A signature block contains some header
information, a sequence of hashes from recently-sent
messages, and a signature of some kind, and a new signature
block is sent each time there have been N new messages whose
hashes need to be signed and sent out. A certificate block
contains some or all of the information needed to uniquely
identify the key being used in these signatures.
2.1. Signature Blocks
A signature block contains a signature for a sequence of
messages sent by syslog-sign. There are several key points
that must be understood before the format of the signature
block makes any sense:
a. In this document, we refer to the normal syslog messages
that aren't generated by syslog-sign as ``messages.'' When
we discuss processing messages, we never include signature
blocks or certificate blocks in this processing.
b. The sending device divides the set of messages it will
ever send into one or more ``signature groups.'' The
maximum number of signature groups allowed is 4095. The
only requirement for a signature group is that all messages
from that signature group must be routed to the same
collector.
c. Each time the device starts a new logging ``session,''
e.g. because it has rebooted, it must generate a unique
reboot session ID.
d. Because we must deal with unreliable delivery, we can't
assume that all the messages in this sequence arrived.
Therefore, we include the hash of each message sent in this
sequence in this signature block. When the logs are
reviewed, the messages are hashed and their hashes are found
in the appropriate signature block.
e. Messages are sent along unaltered. However, each
message is assigned a unique identifying number within its
reboot session and signature group. Each signature block
specifies the number of the first message whose hash is
included; the numbers of the succeeding messages are defined
by their position in the hash block.
f. The signature block is sent in-band, and may
legitimately be forwarded through old-style syslog machines.
Therefore, it must fit within the requirements of a syslog
message. That means it is always less than 1024 bytes, and
it contains only printable ASCII characters, and in fact,
only the 64 characters used in base 64 encoding.
2.1.1. Signature Block Format
The signature block consists of the following fields:
a. Cookie -- an eight byte sequence to signal to the
verifier that this is a signature block. This sequence is
``@#sigSIG''.
b. Version -- a 12-bit quantity encoded in base 64 as two
bytes, which effectively specifies the hash function,
signature mechanism, and other details of the processing of
this signature block.
c. Session ID -- a 48-bit quantity encoded in base 64 as
eight bytes, which is required to never repeat or decrease
over multiple reboots of the sender.
d. Signature Group -- a 12-bit quantity encoded in base 64
as two bytes, which indicates which signature group this
message belongs to. (Each raw message belongs to exactly
one signature group, and each signature block includes
hashes from only one signature group. Messages from the
same signature group MUST ultimately be routed to the same
collector, and MUST NOT ever be separated in transmission by
any device or relay.
e. Global Block Counter -- a 48-bit quantity encoded in
base 64 as eight bytes, which is the number of signature
blocks sent out by syslog-sign in this reboot session.
f. First Message Number -- a 48-bit quantity encoded in
base 64 as eight bytes, which is the unique message number
within this signature group of the first message whose hash
appears in this block. (That is, if this signature group
has processed 1000 messages so far, and the 1001st message
from this signature group is the first one whose hash
appears in this signature block, then this field is 1001.
g. Count -- a 6-bit quantity encoded in base 64 as one
byte, which is the number of message hashes to follow.
h. Message Hashes -- a block of hashes, each separately
encoded in base-64. The size of each hash is determined by
the hashing algorithm used, effectively specified by the
Version field, but the size MUST NOT be shorter than 160
bits.
i. Signature -- a digital signature, encoded in base-64.
The original encoding of the signature is effectively
specified by the Version field.
2.1.2. Variability of Format
The format has a certain amount of flexibility. Some of
this is determined by the version, and some, by the device
generating the messages based on requested level of
redundancy in transmission.
2.1.2.1.Versions and Field Sizes
The format has some variability, because different signature
schemes and hash functions will alter the size of the
fields. The following versions are defined right now:
1 = SHA1 and DSA/320
2 = SHA1 and RSA/1024
3 = SHA1 and RSA/2048
[[ I need to reference some specs for all this. --JMK ]]
2.1.2.2.Redundancy
The sending device has a tunable level of redundancy for the
signature blocks. If no redundancy is used, then if a
signature block is lost, no messages that were signed by
that block can be verified. The more redundancy is used,
the more signature blocks must be lost before a message
cannot be verified.
Redundancy is implemented in a simple way: Each message's
hash can be included in more than one signature block. If
each message's hash is included in two signature blocks,
then only when two successive signature blocks from the same
signature groups are lost in transit do we end up with
messages we can't verify. If each message's hash is
included in three signature blocks, then this can happen
only when three successive signature blocks from the same
signature group are lost in transit.
The signature block specifies the message number of the
first message whose hash is included in the block. If each
signature block contains 40 hashes, and each successive
signature block's first message is 20 messages higher than
the previous block's, then each message is signed by two
blocks.
Note that this is totally decided by the sending device, and
that any level of redundancy is supported. Similarly, the
only requirement about the number of hashes included in each
signature block is that it never be less than one, and that
it will never be large enough to cause the signature block
to go over 1024 bytes in length. (The field cannot support
more than 63 message hashes, but in practice, no more than
37 could appear in a 1024-byte message, ignoring the other
header fields and the signature block.)
In particular, note that it is legal for the sending device
to simply include one signature block per message.
2.2. Certificate Blocks
The purpose of a certificate block is provide some support
for key management in syslog-sign, by allowing the
transmission of a certificate and other identifying
information from the sending device. The sending device has
a certain initial key management blob to send, which may be
a PKIX certificate, or a raw public key, or a key
fingerprint. In fact, a syslog-sign device doesn't know
anything about this payload except what it's told to report
about it during device setup.
There are three key points to understand about certificate
blocks:
a. The handle a variable-sized payload, by fragmenting it
if necessary, and transmitting the fragments as legal
syslog-syslog messages. This payload is expected to be a
certificate, but the syslog-sign device does no checking of
its format or contents. Its goal is simply to make sure
that the payload gets sent along with a log of any
reasonable length.
b. There is an adjustable parameter for required
redundancy, just as in the signature blocks. However, the
redundancy functions a little differently.
c. Each signature group gets sent its own certificate
blocks.
2.2.1. Building the Payload Block
Note that we build a payload at the time the reboot
session starts, and that payload includes a digital
signature. The payload block for this reboot session
includes:
a. Version -- specifying the hash function and signature
used; this is the same version identifier as is used in the
signature blocks.
b. Reboot Session ID -- the same reboot session ID which
will be used in the signature blocks
c. IP Address of Sender -- the sender's IP address, a
128-bit number base-64 encoded as 22 bytes.
d. Key Blob Type -- this one-byte field holds one of four values:
(i) 'C' -- a PKIX certificate
(ii) 'F' -- a key fingerprint (the hash of the public key
using the specified hash algorithm)
(iii)'K' -- the public key whose corresponding
private key is being used to sign these
messages.
(iv) 'U' -- user-specific field with no defined
meaning in the standard.
e. Key Blob -- the raw data, base-64 encoded.
f. Signature -- a digital signature on fields a-e, encoded
in base-64.
2.2.2. Building the Certificate Block
The certificate block must get the payload block to the
collector. Since certificates can legitimately be much
longer than 1024 bytes, each certificate block carries a
piece of the payload block.
The certificate block is built as follows:
a. Cookie -- an eight byte string, ``@#sigCer''.
b. Version -- a 12-bit field encoded in base-64 as two
bytes.
c. Signature Group -- a 12-bit field encoded in base-64 as
two bytes.
d. Total Payload Length -- a 32-bit field encoded in
base-64 as six bytes.
e. Index into Payload -- a 32-bit field encoded in base-64
as six bytes.
f. Fragment Length -- a 12-bit field encoded in base-64 as
two bytes.
g. Payload Fragment -- a fragment of the payload, as
specified by the above fields.
2.2.3. Redundancy
Given the 1024-byte limit on syslog messages, a given
payload block can be efficiently divided up into some
number, P, of certificate blocks. (It is possible that
P==1.) The collector must end up with all P of these blocks
to be able to verify that this key was in use at the time of
this reboot session.
The certificate blocks are sent as follows:
a. At reboot, we send all P certificate blocks once for
each signature group. These are sent as syslog messages,
and they are sent before any other syslog messages are sent
in this session.
b. After this, we resend the certificate blocks
occasionally, based on the redundancy parameter R. For each
signature group, each time another R messages are sent for
that signature group, we send along the next certificate
block. Note that this requires that we keep track of which
certificate block we're on, for each signature group. If
R==0, then we never resend the certificate block. (This
would make sense if we were using syslog-sign over
syslog-reliable.)
3.0. Offline Review
Reviewing the stored logs offline now becomes
straightforward.
a. Verify that the next reboot session ID is valid, e.g.,
is larger than the previously seen reboot session IDs.
b. Go through the log entries with this session ID, and
pull out each of the certificate blocks. Reassemble the
payload block, and make whatever use of it is desired.
c. If more than one signature group appears in the logs,
process each group separately as follows.
d. For each signature block:
(i) Verify the signature at the end of the block.
If the signature verifies successfully, then
continue processing.
(ii) Determine what message numbers we're receiving
based on the appropriate fields in the signature
block.
(iii)For each hash in the hash block, look in the
nearby messages for a message with the same hash. If
a message is found, then add that message, along
with its message number, to the list of verified
messages for this session ID and signature group.
e. When the processing is done, sort the list of verified
messages for this session ID and signature group on the
message numbers. Eliminate duplicate message numbers, and
the result is a verified log file, complete with gaps in the
message numbers where there are gaps in the received
messages.
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 Int. for non-commercial use
<http://www.pgpinternational.com>
Comment: foo
iQCVAwUBOi8CxCZv+/Ry/LrBAQEBTwQAutQckW6L96BjiuFNLEVq/eFNHbzR1HA1
EbD9exT6yzCNqtLrUwlq9c+4qki6dOinDpxS7ZSI4PGd8YDcB+hr9HPCXNYaEOCA
j7rGNLC3aOkST9piTs9gu0rcfQ1jGwnk9nO5j4QLkXSWnmPs0gFuughyHJXEP0WN
NT+QIzqZeI0=
=AQIv
-----END PGP SIGNATURE-----
