idnits 2.17.1 draft-ietf-syslog-sign-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 7 longer pages, the longest (page 2) being 90 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. (A line matching the expected section header was found, but with an unexpected indentation: ' 1 Introduction' ) ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 6 Security Considerations' ) ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** There are 85 instances of too long lines in the document, the longest one being 7 characters in excess of 72. ** The abstract seems to contain references ([2], [FIPS-180-1,1993], [Lonvick,2001], [FIPS-186,1994], [RFC1750], [0], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 2001) is 8350 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '0' on line 252 looks like a reference -- Missing reference section? '1' on line 253 looks like a reference -- Missing reference section? '2' on line 254 looks like a reference -- Missing reference section? 'Lonvick' on line 414 looks like a reference -- Missing reference section? '2001' on line 414 looks like a reference -- Missing reference section? 'FIPS-180-1' on line 476 looks like a reference -- Missing reference section? '1993' on line 476 looks like a reference -- Missing reference section? 'RFC1750' on line 1024 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 3 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft J. Kelsey 2 Document: draft-ietf-syslog-sign-01.txt Counterpane 3 Internet Security 4 Expires: December, 2001 June 2001 6 Syslog-Sign Protocol 8 Status of this Memo 10 This document is an Internet-Draft and is in full conformance with all 11 provisions of Section 10 of RFC2026. 13 Internet-Drafts are working documents of the Internet Engineering Task 14 Force (IETF), its areas, and its working groups. Note that other 15 groups may also distribute working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference 20 material or to cite them other than as "work in progress." 22 The list of current Internet-Drafts can be accessed at 23 http://www.ietf.org/ietf/1id-abstracts.txt 24 The list of Internet-Draft Shadow Directories can be accessed at 25 http://www.ietf.org/shadow.html. 27 This work is a product of the IETF syslog Working Group. More 28 information about this effort may be found at 29 http://www.ietf.org/html.charters/syslog-charter.html 30 Comments about this draft should be directed to the syslog working 31 group at the mailing list of syslog-sec@employees.org. 33 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 34 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 35 document are to be interpreted as described in RFC 2119. 37 Copyright Notice 39 Copyright (C) The Internet Society (2001). All Rights Reserved. 41 Abstract 43 This document describes syslog-sign, a mechanism for adding origin 44 authentication, message integrity, replay-resistance, message 45 sequencing, and detection of missing messages to syslog. The goal of 46 syslog-sign is to provide all these security features in a way that 47 has 48 minimal requirements and minimal impact on existing syslog 49 implementations. It is possible to support syslog-sign and gain some 50 of its security attributes by only changing the behavior of the 51 devices 52 generating syslog messages. Additional security benefits may be 53 realized by some additional processing of the received syslog messages 54 and the syslog-sign messages on the relays and collectors. 56 Table of Contents 58 Status of this 59 Memo...................................................1 60 Copyright 61 Notice......................................................1 63 Abstract..............................................................1 64 1 65 Introduction........................................................4 66 1.1 Design Philosophy and 67 Goals.......................................4 68 1.2 Guide to the 69 Document.............................................5 70 2 Signature 71 Blocks....................................................5 72 2.1 How Signature Blocks 73 Work.........................................5 74 2.2 Signature Groups and PRI Values...................................6 75 2.3 Signature Block Format and 76 Fields.................................8 77 2.3.1 Text 78 Block......................................................8 79 2.3.1.1 80 Priority......................................................8 81 2.3.1.2 82 Timestamp.....................................................9 83 2.3.1.3 84 Hostname......................................................9 85 2.3.1.4 86 Cookie........................................................9 87 2.3.1.5 88 SIG...........................................................9 89 2.3.2 Base-64 Encoded Binary 90 Block....................................9 91 2.3.2.1 92 Version.......................................................9 93 2.3.2.2 Reboot Session 94 ID............................................10 95 2.3.2.3 Global Block 96 Counter.........................................11 97 2.3.2.4 First Message 98 Number.........................................11 99 2.3.2.5 100 Count........................................................11 101 2.3.2.6 Hash 102 Block...................................................11 103 2.3.2.7 104 Signature....................................................11 105 2.4 Notes on Upgrading 106 Versions......................................11 107 3 Payload and Certificate 108 Blocks.....................................11 109 3.1 Building the Payload 110 Block.......................................12 111 3.3. Building the Certificate 112 Block..................................13 113 3.4 Use of Certificate and Payload Blocks............................14 114 4 Redundancy and 115 Flexibility.........................................15 116 4.1 117 Redundancy.......................................................15 118 4.1.1 Certificate 119 Blocks.............................................15 120 4.1.2 Signature 121 Blocks...............................................16 122 4.2 123 Flexibility......................................................16 124 4.3 Short Signature or Certificate 125 Blocks............................17 126 5 Efficient Verification of 127 Logs.....................................17 128 5.1. Offline Review of 129 Logs..........................................17 130 5.2. Online Review of 131 Logs...........................................18 132 6 Security 133 Considerations............................................20 134 7 Conclusions and Open 135 Issues........................................21 136 7.1 Initial 137 Version..................................................21 138 8 Test 139 Values........................................................21 140 8.1 Generating Signature 141 Blocks......................................22 142 8.2 Generating Payload and Certificate Blocks........................22 143 9 144 Acknowledgements...................................................22 145 10 146 Bibliography......................................................22 147 A Author's 148 Address...................................................22 149 B Full Copyright 150 Statement...........................................22 151 1 Introduction 153 Syslog-sign is a protocol for adding origin authentication, 154 message integrity, replay resistance, message sequencing, 155 and detection of missing messages to syslog. A major goal 156 of the protocol is to do all this in a way that can be 157 quickly deployed on existing networks, and that can be 158 implemented mostly using off-the-shelf tools. To this end, 159 a number of basic design decisions were made that determined 160 most of the design: 162 a. All messages sent in this protocol are legal syslog 163 messages. This ensures that relays and collectors can 164 handle the new protocol's traffic without any changes. It 165 also inherits the problems of syslog messages in 166 general: unreliable and out-of-sequence delivery, only 167 printable characters allowed in the message text, and each 168 message limited to 1024 bytes maximum. 170 b. Normal syslog messages are sent unchanged by the 171 protocol, just as they would have been sent by syslog 172 without any enhancements. 174 c. Every N messages, a signature block is sent along as a 175 syslog message. This contains, in effect, a detached 176 signature on the previous N messages. These signature 177 blocks contain additional information to allow them to be 178 put into sequence, and to allow any missing signature blocks 179 to be noticed. 181 d. Because we must keep the logs in the correct sequence 182 even across reboots of the device, we must differentiate 183 different "sessions" in which a device is generating log 184 messages and signature blocks. This is done with a "reboot 185 session ID," a 48-bit identifier which is guaranteed never 186 to be reused by a given device. 188 e. To support key and session management, we have a 189 mechanism for sending along a certificate or other 190 information on a per-reboot-session basis. This is done 191 using "certificate blocks," which are also legal syslog 192 messages. 194 1.1 Design Philosophy and Goals 196 More than anything else, what ultimately drove this design 197 was the decision to use syslog as the transport method for 198 all syslog-sign messages. This requires the use of detached 199 signatures (signature blocks), because there's no other way 200 to add signatures and other information to all messages; 201 some messages would have had to be truncated or fragmented. 203 Using signature blocks appeared the cleanest way to do this. 204 As a side benefit, relatively expensive and large digital 205 signatures can be spread out among N messages at a time, 206 making the whole scheme more efficient. 208 We decided to use syslog as the transport mechanism because 209 altering every syslog message meant changing the software on 210 every relay and collector, and probably dealing with very 211 complicated cases where some relays and collectors could 212 process authenticated messages, while others could not. A 213 previous attempt to design a scheme for doing authenticated 214 syslog messages taught us not to try to tackle these issues, 215 which would necessarily involve second-guessing every 216 system administrator who wanted to use the scheme. 218 Using digital signatures instead of symmetric MACs to authenticate 219 messages makes the key management much simpler (though 220 there's nothing inherent in the syslog-sign design that 221 requires that nobody use symmetric algorithms), and makes 222 the scheme suitable for providing storage security for the 223 logs, as well as transmission security. 225 1.2 Guide to the Document 227 The rest of this document is organized as follows: First, 228 we discuss signature blocks, and the infrastructure that 229 supports them. Next, we discuss the key management tools in 230 syslog-sign, built around payload blocks and certificate 231 blocks. We then discuss redundancy mechanisms in 232 syslog-sign. Next, we discuss efficient verification of logs 233 and log messages, both online and offline. Finally, we 234 conclude the document with a brief summary and some open 235 questions about the design. 237 2 Signature Blocks 239 2.1 How Signature Blocks Work 241 A signature block contains a priority value (required for 242 all syslog messages), some header information (to allow the 243 signature blocks to be put into order on receipt), a 244 sequence of N cryptographic hash values, and a digital 245 signature. 247 Signature Block: 249 a. PRI Value 250 b. Header Information 251 c. List of N hashes: 252 (i) Hash[0] 253 (ii) Hash[1] 254 (iii)Hash[2] 255 ... 256 d. Signature on fields a-c. 258 Consider a device, which is sending log messages to a 259 collector. After every Nth normal log message, it sends an 260 additional message with this format. Again, this is just a 261 syslog message, and so it needs no special treatment by the 262 collector or any intermediate nodes. To generate and send 263 that additional message, (the "signature block"), the 264 device keeps the cryptographic hash values of the previous N 265 messages sent, and how many messages were sent before these 266 most recently sent N messages. Using that information, the 267 device is able to build the signature block. It digitally 268 signs the block, and sends it along. 270 The collector may process these signature blocks as they 271 arrive, building an authenticated log file on the fly as the 272 pieces arrive. Alternatively, it may store all the log 273 messages in the order they were received, and allow the 274 system administrator to authenticate the log file when he reviews the 275 logs. In either case, out-of-order messages are put back 276 into order based on the hash values in the signature block. 277 (There are a number of efficient ways to do this.) 279 2.2 Signature Groups and PRI Values 281 Each signature block contains, in effect, a detached 282 signature on the previously sent N messages. However, a 283 device may send messages that are ultimately routed to many 284 different collectors. If the N messages arrive at one 285 collector, and the signature block at another, then neither 286 collector will be able to verify anything. Similarly, if 287 half of the N messages go to one collector, while the 288 signature block and the other half of the N messages go to 289 the other, there is clearly a problem. 291 The solution to this problem ultimately rests with the 292 system administrator who uses the system; he must configure any relays 293 and collectors to ensure that messages and their signature 294 blocks arrive at the same place. To make this easier, 295 syslog-sign provides the idea of a "signature group." A 296 signature group identifies a group of messages that are all 297 kept together for signing purposes by the device. A 298 signature block always belongs to exactly one signature 299 group, and it always signs messages belonging only to that 300 signature group. 302 Recall that syslog-sign doesn't alter messages. That means 303 that the signature group of a message doesn't appear 304 anywhere in the message itself. Instead, the device and any 305 intermediate relays use something inside the message to 306 decide where to route it; the device needs to use the same 307 information to decide which signature group a message 308 belongs to. 310 Syslog-sign provides four options for handling signature 311 groups, linking them with PRI values. In all cases, no more 312 than 192 signature groups (0-191) are permitted. In this 313 list, SIG is the signature group, and PRI is the PRI value 314 of the signature and certificate blocks in that signature 315 group. 317 a. '0' -- Only one signature group, SIG = 0, PRI = 046. 318 The same signature group is used for all certificate and 319 signature blocks, and for all messages. 321 b. '1' -- Each PRI value has its own signature group. 322 Signature and certificate blocks for a given signature group 323 have SIG = PRI for that signature group. 325 c. '2' -- Each signature group contains a range of PRI 326 values. Signature groups are assigned sequentially. A 327 certificate or signature block for a given signature group 328 have its SIG value, and the highest PRI value in that 329 signature group. (That is, if signature group 2 has PRI 330 values in the range 100-191, then all signature group 2's 331 signature and certificate blocks will have PRI=191, and 332 SIG=2. 334 d. '3' -- Signature groups are not assigned with any simple 335 relationship to PRI values. A certificate or signature 336 block in a given signature group will have that group's SIG 337 value, and PRI = 046. 339 Note that options (a) and (b) make the SIG value redundant. 340 However, in installations where log messages are forwarded 341 to different collectors based on some complicated criteria 342 (e.g., whether the message text matches some regex), the SIG 343 value gives an easy way for relays to decide where to route 344 signature and certificate blocks. This is necessary, since 345 these blocks almost certainly won't match the regexes. 347 Options (a) and (d) set the PRI value to 046 for all 348 signature and certificate blocks. This is intended to make 349 it easier to process these syslog messages separately from 350 others handled by a relay. One reasonable way to configure 351 some installations is to have only one signature group, 352 send messages to many collectors, but send a copy of each 353 signature and certificate block to each collector. This 354 won't allow any collector to detect gaps in the messages, 355 but it will allow all messages that arrive at each collector 356 to be put into the right order, and to be verified. 358 2.3 Signature Block Format and Fields 360 The signature block is composed of the following fields. 361 Recall that every field must be printable ASCII, and any 362 binary values are base-64 encoded. The numbers in 363 parentheses are the number of bytes taken up by the binary 364 values inside the Base-64 encoded blob, and the number of 365 characters for other values. 367 a. Text Block 368 (i) "<" (1) 369 (ii) PRI (3) 370 (iii) ">" (1) 371 (iv) Timestamp(15) 372 (v) " " (1) 373 (vi) Hostname (variable) 374 (vii) " " (1) 375 (viii)Cookie (8) 376 (ix) Sig Group (3) 377 b. Base-64 Encoded Binary Block (variable) 378 (i) Version (4) 379 (ii) Reboot Session ID (6) 380 (iii) Global Block Counter (6) 381 (iv) First Message Number (6) 382 (v) Count (2) 383 (vi) Hash Block (variable) 384 (vii) Signature (variable) 386 2.3.1 Text Block 388 The text block contains information that is not binary-encoded. This 389 is generally the information that relays or the system administrator 390 may need to be able to see "in the clear." Some parts of the text 391 block are required of all syslog messages; others make it easy to 392 distinguish signature and certificate blocks from normal syslog 393 messages. 395 This block must be parsed field by field, using the angle brackets and 396 spaces as delimiters. It is not fixed-length, due to the need to 397 allow 398 PRI, SIG, and hostname fields to vary in length. 400 2.3.1.1 Priority 402 All syslog messages need a three digit priority and facility code, 403 ranging from 0 to 191 inclusive. This value must be in angle 404 brackets, 405 e.g., <12> or <185>. 407 Signature blocks' priority values are determined by the configuration 408 of syslog-sign, in order to make it as easy as possible to get all 409 syslog messages going to the same final collector to arrive with their 410 signature blocks. In fact, if the syslog installation routes syslog 411 messages based only on their priority+facility code, then the only 412 configuration required for syslog-sign is to give each 413 priority+facility code its own signature group. (Syslog-syslog 414 [Lonvick, 2001] requires that syslog messages be routed only based on 415 this code.) 417 2.3.1.2 Timestamp 419 The timestamp is of the form specified in syslog-syslog [Lonvick, 420 2001], e.g. "Jan 1 14:33:54" or "Dec 19 02:01:00". The timestamp 421 contains the local time on the device at the time the message is 422 signed. Devices which do not have a clock MUST use the following 423 format: 424 "Jan 1 00:00:00". 426 2.3.1.3 Hostname 428 The hostname is part of the device's configuration. The device will 429 determine how many messages to include per signature block based 430 mainly 431 on the length of this parameter, so we recommend keeping the hostname 432 parameter relatively short. 434 2.3.1.4 Cookie 436 The cookie is an eight byte sequence to signal to the 437 verifier that this is a signature block. This sequence is 438 "@#sigSIG", without the quotes. 440 2.3.1.5 SIG 442 The signature group appears at the end of the text block. It is a one- 443 to-three character string of ASCII digits, between 0 and 191 444 inclusive. 445 Depending on the device's configuration, this number may be the 446 same as 447 the PRI, or different. 449 2.3.2 Base-64 Encoded Binary Block 451 The binary fields in the signature block must be encoded in base-64, 452 because syslog messages may only contain printable characters. Again, 453 the fields must be parsed individually, with the first five fields 454 having fixed length, but the hash block's length varying according to 455 how many messages have been signed. 457 2.3.2.1 Version 459 The version specifies what version of the syslog-sign 460 protocol is being used, what hash algorithm is being used, 461 and what signature scheme is being used. This is broken up 462 into three fields, as follows: 464 a. Protocol Version (0-65535) 466 This is encoded as two bytes. The version of the protocol 467 in this document is 1, in binary %b0000000000000001. Version 0 is 468 used to represent a local variant of the protocol, used exclusively 469 within a single 470 installation, and with no guarantee of interoperability with 471 other systems. 473 b. Hash Algorithm (0-255) 475 This is encoded as one byte. The following hash algorithms 476 are defined for syslog-sign[FIPS-180-1,1993] 478 (i) SHA-1 = 1 (in binary, %b00000001). 480 Note that hash algorithms with output size less than 160 481 bits, and hash algorithms known or suspected to be 482 susceptible to collision-finding attacks, MUST NOT be used 483 in syslog-sign. In particular, MD4 and MD5 MUST NOT be used 484 in syslog-sign. 486 At the time of this writing, three new hash functions have been 487 proposed to replace SHA-1, with output sizes of 256, 384, and 512 488 bits. 489 These hash algorithms have not yet been specified as a new standard, 490 and so are not included here. 492 Version 0 is used to represent a locally-defined hash 493 algorithm, with no promise of interoperability. 495 c. Signature Scheme (0-255) 497 This is encoded as one byte. The only signature scheme 498 currently defined is OpenPGP[Callas, et. al,1998] DSA signatures[FIPS- 499 186,1994] with p parameter of 1024 bits. This signature scheme is 500 specified as version 1, in binary %b00000001. 502 The full version is a four byte string, encoding the first 503 and second bytes of the protocol version, then the hash 504 version, then the signature version. Thus, in binary, the initial 505 version is %b00000000000000010000000100000001. 507 Some version numbers, and the right mechanism for extending 508 syslog-sign versions, are discussed below. 510 2.3.2.2 Reboot Session ID 512 The reboot session ID is a 48-bit quantity, which is 513 required to never repeat or decrease in the lifetime of the 514 device. There is no other requirement for how this value is 515 set. It is natural to set this from a timestamp or a reboot 516 counter on the device. 518 2.3.2.3 Global Block Counter 520 The global block counter is a 48-bit quantity, and 521 represents the number of messages whose signature blocks had 522 been sent out by syslog-sign before this one, in this reboot 523 session. Note that this counter crosses signature groups; 524 it allows us to roughly synchronize when two messages were 525 sent, even though they went to different collectors. 527 2.3.2.4 First Message Number 529 This is a 48-bit quantity, the unique message number within 530 this signature group of the first message whose hash appears 531 in this block. (That is, if this signature group has 532 processed 1000 messages so far, and the 1001st message from 533 this signature group is the first one whose hash appears in 534 this signature block, then this field is 1001.) 536 2.3.2.5 Count 538 The count is a 16-bit quantity, the number of message hashes 539 to follow. 541 2.3.2.6 Hash Block 543 The hash block is a sequence of hash values, their binary 544 strings concatenated to make a long sequence of bytes. The 545 length of the binary hash block (before base-64 encoding) is 546 the length of the hash values from the hash function used, 547 times the count of message hashes specified in the count 548 field. 550 2.3.2.7 Signature 552 This is a digital signature, encoded in base-64. The 553 binary encoding of the signature is effectively specified by 554 the Version field. 556 2.4 Notes on Upgrading Versions 558 Note that the format requires that the text block remain unchanged 559 across all future versions. That is, only the base-64 encoded binary 560 block may have fields altered. Also note that the version field MUST 561 remain the first binary field in any future version of the protocol. 563 3 Payload and Certificate Blocks 565 Key management in syslog-sign is supported by certificate 566 blocks and payload blocks. At session startup, the device 567 builds a payload block; there is exactly one payload block 568 built per session. The payload block carries both 569 key-management and session-management information. 571 Certificate blocks are valid syslog messages which carry 572 fragments of the payload block. The collector receives 573 these certificate blocks, and uses them to reassemble the 574 payload block. The payload block's contents can then be 575 cryptographically verified, and its information used. 577 All devices MUST generate a payload block at the start of a 578 session, and this payload block MUST be transmitted to all 579 signature groups by the device, by way of one or more 580 certificate blocks. Certificate blocks SHOULD be sent 581 multiple times, to increase the probability that at least 582 one copy of each certificate block will be received. 584 3.1 Building the Payload Block 586 The payload block is built when a new reboot session is 587 started. There is a one-to-one correspondence of reboot 588 sessions to payload blocks. That is, each reboot session 589 has only one payload block, regardless of how many signature 590 groups it may support. 592 The payload block consists of the following: 594 a. Full local timestamp for the device, including year if 595 available, at time reboot session started. This SHOULD be a 596 valid timestamp, but MAY be filled in with ASCII zeros if no 597 internal clock is available. The format of this timestamp 598 is "yyyymmddhhmmss", where yyyy is the four-digit year in 599 ASCII digits, the first mm is a two digit month value 600 (01-12), dd is a two-digit date (01-31), hh is a two-digit 601 hour in military time (00-23), the second mm is a two-digit 602 minute value (00-59), and the ss is a two-digit seconds 603 value (00-59). For example, January 23, 2054 at 8:35:19 AM 604 would be represented as "20540123083519", while February 8, 605 2002 at 5:15:00 PM would be shown as "20020208171500". A 606 device without an internal clock would use "00000000000000". 608 b. Signature Group Descriptor. This consists of a 609 one-character field specifying how signature groups are 610 assigned. The possibilities are: 611 (i) '0' -- Only one signature group supported. For 612 all signature blocks and certificate blocks, 613 sig == pri == 046. 615 (ii) '1' -- Each pri value gets its own signature 616 group. For each signature/certificate block, 617 sig == pri. 619 (iii)'2' -- Signature groups are assigned in some 620 way with no simple relationship to pri values; for 621 all signature/certificate blocks, pri = 046. 623 (iv) '3' -- Signature groups are assigned to ranges 624 of pri values. For each signature/certificate 625 block, pri = largest pri contained within that 626 signature group. 628 c. Highest SIG Value -- a three-character field showing the 629 highest SIG value that will ever be seen on a 630 signature/certificate block. This may range from "000" to 631 "191". 633 d. Key Blob Type, a one-byte field which holds one of the 634 following values: 635 (i) 'C' -- a PKIX certificate 636 (ii) 'N' -- no key information sent; key is 637 predistributed. 638 (iii)'S' -- signed public key 640 e. The key blob, consisting of the raw key data, if any, 641 base-64 encoded. 643 3.3. Building the Certificate Block 645 The certificate block must get the payload block to the 646 collector. Since certificates can legitimately be much 647 longer than 1024 bytes, each certificate block carries a 648 piece of the payload block. Note that the device MAY make 649 the certificate blocks of any legal length (that is, any 650 length less than 1024 bytes) which will hold all the 651 required fields. Software that processes certificate blocks 652 MUST deal correctly with blocks of any legal length. 654 The certificate block is built as follows: 656 a. "<" 658 b. A PRI value, derived and used exactly the 659 same way it will be used for the signature blocks. This may be one to 660 three digits. 662 c. ">" 664 d. A timestamp, as described above for signature blocks. 666 e. " " 668 f. A hostname, as described above for signature blocks. 670 g. " " 672 h. Cookie, an eight byte string, "@#sigCer". 674 i. SIG, a one to three-digit character string, as described above 675 for signature blocks. 677 j. A base-64 encoded blob, which encodes the following 678 binary fields: 680 (i) Version, as described above for signature 681 blocks. 683 (ii) RSID, as described above for signature blocks. 685 (iii)Payload length, a four-byte value encoding an 686 unsigned 32-bit integer, whose value is the 687 total payload block's length in bytes. 689 (iv) Index, a 32-bit integer (encoded as four bytes) 690 that specifies where in the payload block 691 this fragment belongs. 693 (v) Fragment Length, a 16-bit integer (encoded as 694 two bytes) that specifies the number of bytes 695 in this certificate block's Fragment field. 697 (vi) Fragment, the raw fragment. 699 (vii)Signature, a digital signature on all the above 700 fields. 702 3.4 Use of Certificate and Payload Blocks 704 The certificate blocks carry signatures, which will 705 sometimes only be verifiable after the payload block is 706 reconstructed and used. The certificate and payload blocks 707 should be processed as follows: 709 a. Collect all the certificate blocks. Verify that the 710 versions, lengths, indexes, and RSIDs are all valid and 711 internally consistent. 713 b. Rebuild the payload block. 715 c. Verify the parameters of the payload block, and 716 particularly the key blob. 718 d. Extract or verify the key. 720 e. Verify all the certificate blocks' signatures. 722 f. If all verifications were successful, accept the key and 723 session. If any certificate block failed to be verified, 724 then search for redundantly-sent versions of the certificate 725 blocks. 727 There are two reasons for putting the signatures on 728 certificate blocks: 730 a. Installations with predistributed keys can simply verify 731 the signatures as the certificate blocks come in. 733 b. Information in the certificate blocks, such as hostname, 734 RSID, etc., needs to be verified cryptographically before it 735 can be trusted. Otherwise, an attacker could send misleading 736 certificate blocks reflecting the use of an old key with a new RSID. 738 4 Redundancy and Flexibility 740 There is a general rule that determines how redundancy 741 works, and what level of flexibility the device and 742 collector have in message formats: In general, the device 743 MAY send any legal signature or certificate block any number 744 of times. The collector MUST be able to process any legal 745 signature or certificate block, and MUST NOT have its 746 authenticated log output changed by receipt of any number of 747 additional copies of a valid signature or certificate block 748 after the first one. 750 4.1 Redundancy 752 Syslog messages are sent over unreliable transport, which 753 means that they can be lost in transit. However, signature 754 and certificate blocks must be received by the collector, or 755 many messages may not be able to be verified. Redundancy is 756 provided by sending signature and certificate blocks 757 multiple times; since the collector MUST ignore 758 signature/certificate blocks it has already received and 759 authenticated, the device can in principle change its 760 redundancy level for any reason, without communicating this 761 fact to the collector. 763 Although the device isn't constrained in how it decides to 764 send redundant signature and certificate blocks, or even in 765 whether it decides to send along multiple copies of normal 766 syslog messages, here we define some redundancy parameters 767 below which may be useful in controlling redundant 768 transmission from the device to the collector. The 769 collector has no knowledge of these parameters; the device 770 MAY use them, but is not required to. 772 4.1.1 Certificate Blocks 774 There are three parameters for certificate block 775 redundancy: 777 a. certInitialRepeat, the number of times each certificate block 778 should be sent to each signature group before the first 779 message is sent. 781 b. certResendDelay, the maximum time delay in seconds 782 before next redundant sending of the certificate blocks. 783 (Certificate blocks are resent periodically during a long 784 message, so that offline analysis of the logs remains 785 possible even if the initial certificate blocks are not 786 received correctly.) 788 c. certResendCount, maximum number of sent messages to delay before 789 next redundant sending. 791 4.1.2 Signature Blocks 793 The following parameters define a strategy for redundant 794 signature blocks: 796 a. sigNumberResends, the number of times a signature block 797 is resent. 799 b. sigResendDelay, the maximum time delay in seconds from 800 original sending to next redundant sending. 802 c. sigResendCount, the maximum number of sent messages to 803 delay before next redundant sending. 805 4.2 Flexibility 807 The device may change many things about the makeup of 808 signature and certificate blocks in a given reboot session. 809 The things it cannot change are: 811 a. The version. 813 b. The number or arrangements of signature groups 815 c. The signing key. 817 d. The RSID. 819 These are fixed per session. A device MUST NOT change these 820 during a session. A collector that sees 821 signature or certificate blocks with any of these things 822 different than the current session MUST check the RSID to 823 see if the blocks come from an earlier or later session. 824 Blocks from an earlier session MUST be ignored and 825 discarded. Blocks from a later session MUST cause the 826 collector to switch to a new session, and to attempt to find 827 the key for the new session. 829 When logs are to be verified, the collector MUST have the 830 most recent RSID of a valid session. It MUST NOT accept 831 logs from a session whose RSID is less than or equal to the 832 most recent RSID. It MUST NOT accept a new RSID as valid 833 unless the full payload block from that RSID has been 834 received and verified, and its certificate blocks have also 835 been verified. 837 4.3 Short Signature or Certificate Blocks 839 There is no requirement for signature or certificate blocks 840 to be any specific length, so long as they are never longer 841 than 1024 bytes. A device MAY vary the length of successive 842 certificate blocks for any reason, a collector or log 843 verification program MUST process these correctly regardless 844 of their length, so long as they are valid blocks. 846 5 Efficient Verification of Logs 848 The logs secured with syslog-sign may either be reviewed 849 online or offline. Online review is somewhat more 850 complicated and computationally expensive, but not 851 prohibitively so. 853 5.1. Offline Review of Logs 855 When logs are stored by the collector and reviewed later, 856 they can be authenticated offline just before they are to be 857 reviewed. Reviewing these logs offline is simple and 858 relatively cheap in terms of resources used, so long as 859 there is enough space available on the reviewing machine. 860 Here, we will consider that the stored log files have 861 already been separated by sender, reboot session ID, and 862 signature group. This can be done very easily with a script 863 file. We then do the following: 865 a. First, we go through the raw log file, and split its 866 contents into three files. Each message in the raw log file 867 is classified as a normal message, a signature block, or a 868 certificate block. Certificate blocks and signature blocks 869 are stored in their own files. Normal messages are stored 870 in a keyed file, indexed on their hash values. 872 b. We sort the certificate block file by index value, and 873 check to see if we have a set of certificate blocks that can 874 reconstruct the payload block. If so, we reconstruct the 875 payload block, verify any key-identifying information, and 876 then use this to verify the signatures on the certificate 877 blocks we've received. When this is done, we have verified 878 the reboot session and key used for the rest of the process. 880 c. We sort the signature block file by the First Message 881 Number field. We now create an authenticated log file, 882 which will consist of some header information, and then a 883 sequence of message number, message text pairs. We next go 884 through the signature block file. For each signature block 885 in the file, we do the following: 887 (i) Verify the signature on the block. 888 (ii) For each hashed message in the block: 889 (a) Look up the hash value in the keyed message file. 890 (b) If the message is found, write (message 891 number,message text) to the authenticated log 892 file. 893 (iii)Skip all other signature blocks with the same 894 firstMessageNumber. 896 d. The resulting authenticated log file will contain all 897 messages which have been authenticated, and will indicate 898 (by missing message numbers) all gaps in the authenticated 899 messages. 901 It's pretty easy to see that, assuming sufficient space for 902 building the keyed file, this whole process is linear in the 903 number of messages (generally two seeks, one to write and 904 the other to read, per normal message received), and O(N lg 905 N) in the number of signature blocks. This estimate comes 906 with two caveats: First, the signature blocks will arrive 907 very nearly in sorted order, and so can probably be sorted 908 more cheaply on average than O(N lg N) steps. Second, the 909 signature verification on each signature block will almost 910 certainly be more expensive than the sorting step in 911 practice. We haven't discussed error-recovery, which may be 912 necessary for the certificate blocks. In practice, a very 913 simple error-recovery strategy is probably good enough--if 914 the payload block doesn't come out as valid, then we can 915 just try an alternate instance of each certificate block, if 916 such are available, until we get the payload block right. 918 It's easy for an attacker to flood us with plausible-looking 919 messages, signature blocks, and certificate blocks. 921 5.2. Online Review of Logs 923 Some processes on the collector machine may need to monitor 924 log messages in something very close to real-time. This can 925 be done with syslog-sign, though it is somewhat more 926 complex than the offline analysis. This is done as follows: 928 a. We have an output queue, into which we write (message 929 number, message text) pairs which have been authenticated. 930 Again, we'll assume we're handling only one signature group, 931 and only one reboot session ID, at any given time. 933 b. We have three data structures: A queue into which 934 (message number, hash of message) pairs is kept in sorted 935 order, a queue into which (arrival sequence, hash of 936 message) is kept in sorted order, and a hash table which 937 stores (message text, count) indexed by hash value. In this 938 file, count may be any number greater than zero; when count 939 ==0, the entry in the hash table is cleared. 941 c. We must receive all the certificate blocks before any 942 other processing can really be done. (This is why they're 943 sent first.) Once that's done, any certificate block that 944 arrives is discarded. 946 d. Whenever a normal message arrives, we add (arrival 947 sequence, hash of message) to our message queue. If our 948 hash table has an entry for the message's hash value, we 949 increment its count by one; otherwise, we create a new entry 950 with count = 1. When the message queue is full, we roll the 951 oldest messages off the queue by taking the last entry in 952 the queue, and using it to index the hash table. If that 953 entry has count==1, we delete the entry in the hash table; 954 otherwise, we decrement its count. We then delete the last 955 entry in the queue. 957 e. Whenever a signature block arrives, we first check to 958 see if the firstMessageNumber value is too old, or if 959 another signature block with that firstMessageNumber has 960 already been received. If so, we discard the signature 961 block unread. Otherwise, we check its signature, and 962 discard it if the signature isn't valid. A signature block 963 contains a sequence of (message number, message hash) pairs. 964 For each pair, we first check to see if the message hash is 965 in the hash table. If so, we write out the (message number, 966 message text) in the authenticated message queue. 967 Otherwise, we write the (message number, message hash) to 968 the message number queue. This generally involves rolling 969 the oldest entry out of this queue: before this is done, 970 that entry's hash value is again searched for in the hash 971 table. If a matching entry is found, the (message 972 number,message text) pair is written out to the 973 authenticated message queue. In either case, the oldest 974 entry is then discarded. 976 f. The result of this is a sequence of messages in the 977 authenticated message queue, each of which has been 978 authenticated, and which are combined with numbers showing 979 their order of original transmission. 981 It's not too hard to see that this whole process is roughly 982 linear in the number of messages, and also in the number of 983 signature blocks received. The process is susceptible to 984 flooding attacks; an attacker can send enough normal 985 messages that the messages roll off their queue before their 986 signature blocks can be processed. 988 6 Security Considerations 990 The following are some important security considerations for 991 using syslog-sign. 993 a. The strength of syslog-sign is totally dependent on the 994 strength of the underlying hash function and digital 995 signature algorithm, and on the quality of their 996 implementation. For this reason, it is critical that new 997 versions of syslog-sign not be added to the standard without 998 a thorough cryptographic review of: 1000 (i) The signature scheme 1001 (ii) The hash algorithm 1002 (iii)Any changes to the protocol 1003 (iv) Any possible interactions between protocol 1004 steps and versions. 1006 New versions and version numbers MUST NOT be added without a review by 1007 a 1008 competent person appointed by the area directors. 1010 b. Local variations (assumed not to be compatible with 1011 external systems) are supported by setting the protocol, 1012 hash, or signature version to 0x00. This is intended to 1013 allow sophisticated users to make use of existing 1014 cryptographic infrastructure. Users are warned that making 1015 alterations of this kind locally should not be done without 1016 competent cryptographic review. 1018 c. As with most cryptographic mechanisms, the quality of 1019 random number generation available for key and signature 1020 generation is a major factor in determining whether this 1021 system will be secure. We strongly recommend the use of 1022 some well-tested and -reviewed cryptographic random number 1023 source. Some recommendations may be found 1024 in [RFC1750], and a number of competent designs exist in 1025 cryptographic libraries. (In particular, many UNIX systems 1026 have a /dev/random interface that meets these requirements.) 1028 d. The implementation of syslog-sign which receives and 1029 processes logs, online or offline, must be carefully 1030 reviewed for programming errors that would allow buffer 1031 overruns or similar attacks, as these would allow an 1032 attacker to bypass all the cryptographic protection used. 1034 e. In particular, certificate blocks and payload blocks 1035 have the problem that they are processed extensively before 1036 they may be verified. Programs that process these MUST NOT 1037 be susceptible to buffer overrun or other program failures 1038 when the payload lengths, fragment lengths, or indexes of 1039 the certificate blocks are inconsistent. 1041 f. As processing power, memory, and bandwidth grow cheaper, extended 1042 key sizes will become necessary. As of this writing, DSA has a 1043 maximum 1044 supported parameter sizes of |q|==160, |p|==1024. In the near future, 1045 we expect NIST to specify DSA variants with |q| up to 512 bits, and 1046 |p| 1047 of 4096 or more bits, using a hash function whose output is the same 1048 size as |q|. These extensions will change the number of messages per 1049 signature block that are possible, and may have a noticeable impact on 1050 the ultimate efficiency of the protocol. However, even with |q|==512, 1051 we should be able to sign 7 messages per signature block; with a more 1052 realistic |q|==256, we should be able to sign 17 messages per 1053 signature 1054 block. 1056 7 Conclusions and Open Issues 1058 In this note, we have described syslog-sign, a mechanism for 1059 adding origin authentication, data integrity, message 1060 sequencing, and gap and replay detection to syslog over UDP. 1061 Syslog-sign does not require moving syslog to TCP, and is 1062 intended to minimize the impact of required changes to 1063 existing devices, relays, and servers on the network. In 1064 addition to meeting these goals, syslog-sign using digital 1065 signatures provides storage security, since an attacker who 1066 takes over the collector but doesn't know the device's 1067 private key cannot alter the saved logs. Note, however, 1068 that nothing prevents such an attacker from simply deleting 1069 the log messages he finds inconvenient. While those 1070 messages will obviously be missing from the log when it is 1071 reviewed, there is no way for the reviewer to know whether 1072 those messages ever really arrived at the collector. 1074 7.1 Initial Version 1076 We have specified the first complete version of syslog-sign 1077 as follows: 1079 Protocol Version: 1 (this protocol) 1080 Hash Function: 1 (SHA1) 1081 Signature: 1 (openPGP DSA signatures) 1083 The total version value is {0x00, 0x01, 0x01, 0x01} as a 1084 sequence of bytes. 1086 8 Test Values 1088 The following are some test values generated by the author. 1090 8.1 Generating Signature Blocks 1092 8.2 Generating Payload and Certificate Blocks 1094 9 Acknowledgements 1096 The author wishes to thank Alex Brown, Chris Calabrese, Jon 1097 Callas, Carson Gaspar, Drew Gross, Chris Lonvick, Darrin 1098 New, Marshall Rose, Bruce Schneier, Holt Sorenson, Rodney 1099 Thayer, the many Counterpane Internet Security engineering 1100 and operations people who commented on various versions of 1101 this proposal, and Counterpane Internet Security and Certicom 1102 for their generous support of this work. 1104 10 Bibliography 1106 Schneier, _Applied Cryptography_, John Wiley & Sons, 1996. 1108 Menezes, van Oorschot, Vanstone, _Handbook of Applied 1109 Cryptography_, CRC Press, 1997. 1111 FIPS-180-1, "Secure Hash Standard," Federal Information 1112 Processing Standards Publication 180-1, U.S. Department of 1113 Commerce, 1993. 1115 FIPS-186, "Digital Signature Standard," Federal Information 1116 Processing Standards Publication 186, U.S. Department of 1117 Commerce, 1994. 1119 Callas, Donnerhacke, Finney, and Thayer, "OpenPGP Message 1120 Format," RFC2440, Nov 1998. 1122 Eastlake, Crocker and Schiller, "Randomness Recommendations 1123 for Security," RFC1750, Internet Engineering Task Force, Dec 1124 1994. 1126 Lonvick, "Syslog Protocol", Internet Draft, 1127 draft-ietf-syslog-syslog-06.txt, Feb 2001 1129 A Author's Address 1131 John Kelsey 1132 Certicom 1133 kelsey.j@ix.netcom.com / jkelsey@certicom.com 1135 B Full Copyright Statement 1137 Copyright (C) The Internet Society (2000). All Rights Reserved. 1139 This document and translations of it may be copied and furnished to 1140 others, and derivative works that comment on or otherwise explain 1141 it or 1142 assist in its implementation may be prepared, copied, published and 1143 distributed, in whole or in part, without restriction of any kind, 1144 provided that the above copyright notice and this paragraph are 1145 included on all such copies and derivative works. However, this 1146 document itself may not be modified in any way, such as by removing 1147 the 1148 copyright notice or references to the Internet Society or other 1149 Internet organizations, except as needed for the purpose of developing 1150 Internet standards in which case the procedures for copyrights defined 1151 in the Internet Standards process must be followed, or as required to 1152 translate it into languages other than English. 1154 The limited permissions granted above are perpetual and will not be 1155 revoked by the Internet Society or its successors or assigns. 1157 This document and the information contained herein is provided on an 1158 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1159 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT 1160 NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN 1161 WILL 1162 NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1163 MERCHANTABILITY OR 1164 FITNESS FOR A PARTICULAR PURPOSE.