idnits 2.17.1 draft-ietf-syslog-sign-03.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 Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == Unrecognized Status in 'Category: INTERNET-DRAFT', assuming Proposed Standard (Expected one of 'Standards Track', 'Full Standard', 'Draft Standard', 'Proposed Standard', 'Best Current Practice', 'Informational', 'Experimental', 'Informational', 'Historic'.) -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'MENEZES' is defined on line 722, but no explicit reference was found in the text == Unused Reference: 'RFC1983' is defined on line 730, but no explicit reference was found in the text == Unused Reference: 'RFC2085' is defined on line 733, but no explicit reference was found in the text == Unused Reference: 'RFC2104' is defined on line 736, but no explicit reference was found in the text == Unused Reference: 'RFC2119' is defined on line 740, but no explicit reference was found in the text == Unused Reference: 'RFC2434' is defined on line 743, but no explicit reference was found in the text == Unused Reference: 'SCHNEIER' is defined on line 754, but no explicit reference was found in the text == Unused Reference: 'SYSLOG-REL' is defined on line 757, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'DSA94' -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-180-1' -- Possible downref: Non-RFC (?) normative reference: ref. 'MENEZES' ** Obsolete normative reference: RFC 1750 (Obsoleted by RFC 4086) ** Downref: Normative reference to an Informational RFC: RFC 1983 ** Downref: Normative reference to an Informational RFC: RFC 2104 ** Obsolete normative reference: RFC 2434 (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 2440 (Obsoleted by RFC 4880) ** Obsolete normative reference: RFC 3164 (Obsoleted by RFC 5424) -- Possible downref: Non-RFC (?) normative reference: ref. 'SCHNEIER' -- Possible downref: Non-RFC (?) normative reference: ref. 'SYSLOG-REL' Summary: 10 errors (**), 0 flaws (~~), 9 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group John Kelsey 2 Category: INTERNET-DRAFT Certicom 3 draft-ietf-syslog-sign-03.txt 4 Expires Mar 2002 Jon Callas 5 September 2001 Wave Systems Corporation 7 Syslog-Sign Protocol 8 draft-ietf-syslog-sign-03.txt 10 Copyright Notice 12 Copyright 2001 by The Internet Society. All Rights Reserved. 14 Status of this Memo 16 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC2026. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as 22 Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six 25 months and may be updated, replaced, or obsoleted by other documents 26 at any time. It is inappropriate to use Internet-Drafts as 27 reference material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This work is a product of the IETF syslog Working Group. More 36 information about this effort may be found at 37 http://www.ietf.org/html.charters/syslog-charter.html 39 Comments about this draft should be directed to the syslog working 40 group at the mailing list of syslog-sec@employees.org. 42 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 43 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 44 document are to be interpreted as described in RFC 2119. 46 Abstract 48 This document describes syslog-sign, a mechanism adding origin 49 authentication, message integrity, replay-resistance, message 50 sequencing, and detection of missing messages to syslog. 51 Syslog-sign provides these security features in a way that has 52 minimal requirements and minimal impact on existing syslog 53 implementations. It is possible to support syslog-sign and gain 54 some of its security attributes by only changing the behavior of the 55 devices generating syslog messages. Some additional processing of 56 the received syslog messages and the syslog-sign messages on the 57 relays and collectors may realize additional security benefits. 59 Table of Contents 61 Copyright Notice 1 62 Status of this Memo 1 63 Abstract 1 64 Table of Contents 3 65 1. Introduction 4 66 2. Signature Block Format and Fields 4 67 2.1. syslog Packets Containing a Signature Block 4 68 2.2. Priority 5 69 2.3. Cookie 6 70 2.4. Version 6 71 2.5. Reboot Session ID 6 72 2.6. Signature Group 6 73 2.7. Global Block Counter 6 74 2.8. First Message Number 6 75 2.9. Count 7 76 2.10. Hash Block 7 77 2.11. Signature 7 78 3. Signature Groups 7 79 4. Payload and Certificate Blocks 8 80 4.1. Preliminaries: Key Management and Distribution Issues 8 81 4.2. Building the Payload Block 9 82 4.3. Building the Certificate Block 10 83 5. Redundancy and Flexibility 11 84 5.1. Redundancy 11 85 5.1.1. Certificate Blocks 11 86 5.1.2. Signature Blocks 11 87 5.2. Flexibility 11 88 6. Efficient Verification of Logs 12 89 6.1. Offline Review of Logs 12 90 6.2. Online Review of Logs 13 91 7. Security Considerations 14 92 8. IANA Considerations 15 93 9. Authors and Working Group Chair 15 94 10. Acknowledgements 15 95 11. References 15 96 12. Full Copyright Statement 16 98 1. Introduction 100 Syslog-sign is an enhancement to syslog [RFC3164] that adds origin 101 authentication, message integrity, replay resistance, message 102 sequencing, and detection of missing messages to syslog. This 103 mechanism makes no changes to the syslog packet format but does 104 require strict adherence to that format. A syslog-sign message 105 contains a signature block as the CONTENT field in the HEADER part 106 as defined in Section 4 of [RFC3164]. This signature block contains 107 a separate digital signature for each of a group of previously sent 108 syslog messages. The overall message is also signed as the last 109 value in this message. 111 Each signature block contains, in effect, a detached signature on 112 some number of previously sent messages. While most implementations 113 of syslog involve only a single device as the generator of each 114 message and a single receiver as the collector of each message, 115 provisions need to be made to cover messages being sent to multiple 116 receivers. This is generally performed based upon the Priority 117 value of the individual messages. For example, messages from any 118 Facility with a Severity value of 3, 2, 1 or 0 may be sent to one 119 collector while all messages of Facilities 4, 10, 13, and 14 may be 120 sent to another collector. Appropriate syslog-sign messages must be 121 kept with their proper syslog messages. To address this, 122 syslog-sign utilizes a signature-group. A signature group 123 identifies a group of messages that are all kept together for 124 signing purposes by the device. A signature block always belongs to 125 exactly one signature group and it always signs messages belonging 126 only to that signature group. 128 The receiver of the previous messages may verify that the digital 129 signature of each received message matches the signature contained 130 in the signature block. A collector may process these signature 131 blocks as they arrive, building an authenticated log file. 132 Alternatively, it may store all the log messages in the order they 133 were received. This allows a network operator to authenticate the 134 log file at the time the logs are reviewed. 136 2. Signature Block Format and Fields 138 Since the device generating the signature block message signs the 139 entire syslog message, it is imperative that the message MUST NOT be 140 changed in transit. In adherence with Section 4 of [RFC3164], a 141 fully formed syslog message containing a PRI part and a HEADER part 142 containing TIMESTAMP and HOSTNAME fields MUST NOT be changed or 143 modified by any relay. 145 2.1. syslog Packets Containing a Signature Block 147 Signature block messages MUST be completely formed syslog messages. 148 Signature block messages have PRI, HEADER, and MSG parts as 149 described in Sections 4.1.1 and 4.1.3 of [RFC3164]. The PRI part 150 MUST have a valid Priority value bounded by angled brackets. The 151 HEADER part MUST have a valid TIMESTAMP field as well as a HOSTNAME 152 field. It SHOULD also contain a valid TAG field. It is RECOMMENDED 153 that the TAG field have the value of "syslog " (without the double 154 quotes) to signify that this message was generated by the syslog 155 process. The CONTENT field of the syslog signature block messages 156 have the following fields. 158 The signature block is composed of the following fields. Each field 159 must be printable ASCII, and any binary values are base-64 encoded. 161 Field Size in bytes 162 ----- ---- -- ----- 164 Priority 3 166 Cookie 8 168 Version 4 170 Reboot Session ID 8 172 Signature Group 3 174 Global Block Counter 8 176 First Message Number 8 178 Count 2 180 Hash Block variable, size of hash 182 Signature variable 184 These fields are described below. 186 2.2. Priority 188 The signature group priority field is set depending on the settings 189 described in Section 3 below. This field is 1, 2, or 3 characters 190 in length and is terminated with a space character. The value in 191 this field specifies the version of the syslog-sign protocol and is 192 terminated with a space character. This is extensible to allow for 193 different hash algorithms and signature schemes to be used in the 194 future. The value of this field is calculated by determining the 195 base64 encoding of the protocol version, the hash algorithm and the 196 signature scheme. 198 Protocol Version - 2 bytes with the first version being the ABNF 199 value of %b0000000000000001 to denote Version 1. 201 Hash Algorithm - 1 byte with the definition that %b00000001 202 denotes SHA1. [FIPS-180-1] 204 Signature Scheme - 1 byte with the definition that %b00000001 205 denotes OpenPGP DSA [RFC2440], [DSA94]. 207 As such, the version, hash algorithm and signature scheme may be 208 represented as %h00010101. The priority field will be the base64 209 encoding of that value with a space character appended. 211 2.3. Cookie 213 The cookie is a nine-byte sequence to signal that this is a 214 signature block. This sequence is "@#sigSIG " (without the double 215 quotes). 217 2.4. Version 219 The version is 2 bytes with the first version being the ABNF value 220 of %b0000000000000001 to denote Version 1. 222 2.5. Reboot Session ID 224 The reboot session ID is a 48-bit quantity encoded in base 64 as 225 eight bytes, which is required to never repeat or decrease in the 226 lifetime of the device. 228 2.6. Signature Group 230 This is the SIG identifier, described above. It may take on any 231 value from 0-191 inclusive, and is encoded as two bytes in base 64. 233 2.7. Global Block Counter 235 The global block counter is a 48-bit quantity encoded in base 64 as 236 eight bytes, which is the number of signature blocks sent out by 237 syslog-sign before this one, in this reboot session. Note that this 238 counter crosses signature groups; it allows us to roughly 239 synchronize when two messages were sent, even though they went to 240 different collectors. 242 2.8. First Message Number 244 This is a 48-bit quantity encoded in base 64 as eight bytes, which 245 is the unique message number within this signature group of the 246 first message whose hash appears in this block. (That is, if this 247 signature group has processed 1000 messages so far, and the 1001st 248 message from this signature group is the first one whose hash 249 appears in this signature block, then this field is 1001.) 251 2.9. Count 253 The count is a 6-bit quantity encoded in base 64 as one byte, which 254 is the number of message hashes to follow. 256 2.10. Hash Block 258 The hash block is a block of hashes, each separately encoded in 259 base-64. The hashing algorithm used effectively specified by the 260 Version field determines the size of each hash, but the size MUST 261 NOT be shorter than 160 bits. 263 2.11. Signature 265 This is a digital signature, encoded in base-64. The Version field 266 effectively specifies the original encoding of the signature. 268 3. Signature Groups 270 Recall that syslog-sign doesn't alter messages. That means that the 271 signature group of a message doesn't appear anywhere in the message 272 itself. Instead, the device and any intermediate relays use 273 something inside the message to decide where to route it; the device 274 needs to use the same information to decide which signature group a 275 message belongs to. 277 Syslog-sign provides four options for handling signature groups, 278 linking them with PRI values. In all cases, no more than 192 279 signature groups (0-191) are permitted. In this list, SIG is the 280 signature group, and PRI is the PRI value of the signature and 281 certificate blocks in that signature group. 283 a. '0' -- Only one signature group, SIG = 0, PRI = XXX. The same 284 signature group is used for all certificate and signature 285 blocks, and for all messages. 287 b. '1' -- Each PRI value has its own signature group. Signature 288 and certificate blocks for a given signature group have SIG = 289 PRI for that signature group. 291 c. '2' -- Each signature group contains a range of PRI values. 292 Signature groups are assigned sequentially. A certificate or 293 signature block for a given signature group have its SIG value, 294 and the highest PRI value in that signature group. (That is, if 295 signature group 2 has PRI values in the range 100-191, then all 296 signature group 2's signature and certificate blocks will have 297 PRI=191, and SIG=2. 299 d. '3' -- Signature groups are not assigned with any simple 300 relationship to PRI values. A certificate or signature block in 301 a given signature group will have that group's SIG value, and 302 PRI = XXX. 304 Note that options (a) and (b) make the SIG value redundant. 305 However, in installations where log messages are forwarded to 306 different collectors based on some complicated criteria (e.g., 307 whether the message text matches some regular expression), the SIG 308 value gives an easy way for relays to decide where to route 309 signature and certificate blocks. This is necessary, since these 310 blocks almost certainly won't match the regular expressions. 312 Options (a) and (d) set the PRI value to XXX for all signature and 313 certificate blocks. This is intended to make it easier to process 314 these syslog messages separately from others handled by a relay. 315 One reasonable way to configure some installations is to have only 316 one signature group, send messages to many collectors, but send a 317 copy of each signature and certificate block to each collector. 318 This won't allow any collector to detect gaps in the messages, but 319 it will allow all messages that arrive at each collector to be put 320 into the right order, and to be verified. 322 4. Payload and Certificate Blocks 324 Certificate blocks and payload blocks provide key management in 325 syslog-sign. 327 4.1. Preliminaries: Key Management and Distribution Issues 329 The purpose of certificate blocks is to support key management using 330 public key cryptosystems. All devices send at least one certificate 331 block at the beginning of a new reboot session, carrying useful 332 information about the reboot session. 334 There are three key points to understand about certificate blocks: 336 a. They handle a variable-sized payload, fragmenting it if 337 necessary and transmitting the fragments as legal syslog 338 messages. This payload is built (as described below) at the 339 beginning of a reboot session and is transmitted in pieces with 340 each certificate block carrying a piece. Note that there is 341 exactly one payload block per reboot session. 343 b. The certificate blocks are digitally signed. The device does 344 not sign the payload block, but the signatures on the 345 certificate blocks ensure its authenticity. Note that it may 346 not even be possible to verify the signature on the certificate 347 blocks without the information in the payload block; in this 348 case the payload block is reconstructed, the key is extracted, 349 and then the certificate blocks are verified. (This is 350 necessary even when the payload block carries a certificate, 351 since some other fields of the payload block aren't otherwise 352 verified.) In practice, I expect that most installations will 353 keep the same public key over long periods of time, so that most 354 of the time, it's easy to verify the signatures on the 355 certificate blocks, and use the payload block to provide other 356 useful per-session information. 358 c. The kind of payload block that is expected is determined by what 359 kind of key material is on the collector that receives it. The 360 device and collector (or offline log viewer) has both some key 361 material (such as a root public key, or predistributed public 362 key), and an acceptable value for the Key Blob Type in the 363 payload block, below. The collector or offline log viewer MUST 364 NOT accept a payload block of the wrong type. 366 4.2. Building the Payload Block 368 The payload block is built when a new reboot session is started. 369 There is a one-to-one correspondence of reboot sessions to payload 370 blocks. That is, each reboot session has only one payload block, 371 regardless of how many signature groups it may support. 373 The payload block consists of the following: 375 a. Unique identifier of sender; by default, the sender's 128-bit IP 376 address encoded in base-64. 378 b. Full local timestamp for the device, including year if 379 available, at time reboot session started. 381 c. Signature Group Descriptor. This consists of a one-character 382 field specifying how signature groups are assigned. The 383 possibilities are: 385 (i) '0' -- Only one signature group supported. For all 386 signature blocks and certificate blocks, sig == pri == XXX. 388 (ii) '1' -- Each pri value gets its own signature group. For 389 each signature/certificate block, sig == pri. 391 (iii) '2' -- Signature groups are assigned in some way with no 392 simple relationship to pri values; for all 393 signature/certificate blocks, pri = XXX. 395 (iv) '3' -- Signature groups are assigned to ranges of pri 396 values. For each signature/certificate block, pri = largest 397 pri contained within that signature group. 399 d. Highest SIG Value -- a two-byte field base 64 encoded, must be a 400 number between 0 and 191, inclusive. 402 e. Key Blob Type, a one-byte field which holds one of four values: 404 (i) 'C' -- a PKIX certificate. 406 (ii) 'P' -- an OpenPGP certificate. 408 (iii) 'K' -- the public key whose corresponding private key is 409 being used to sign these messages. 411 (iv) 'N' -- no key information sent; key is predistributed. 413 (v) 'U' -- installation-specific key exchange information 415 f. The key blob, consisting of the raw key data, if any, base-64 416 encoded. 418 4.3. Building the Certificate Block 420 The certificate block must get the payload block to the collector. 421 Since certificates can legitimately be much longer than 1024 bytes, 422 each certificate block carries a piece of the payload block. Note 423 that the device MAY make the certificate blocks of any legal length 424 (that is, any length less than 1024 bytes) which will hold all the 425 required fields. Software that processes certificate blocks MUST 426 deal correctly with blocks of any legal length. 428 The certificate block is built as follows: 430 a. A pri value -- this variable-length (one, two, or 431 three byte) value is chosen to ensure 432 that every signature group will get a 433 full set of certificate blocks. 435 b. Cookie -- an eight byte string, "@#sigCer". 437 c. Version -- 12 bits base-64 encoded as two bytes. 439 d. Reboot Session ID -- as above, a 48-bit quantity encoded 440 in base 64 as eight bytes, which is 441 required to never repeat or decrease in 442 the lifetime of the device. 444 e. Signature Group -- 12 bits base-64 encoded as two bytes. 446 f. Total Payload Length -- 32 bits base-64 encoded as six bytes. 448 g. Index into Payload -- 32 bits base-64 encoded as six bytes. 450 h. Fragment Length -- 12 bits base-64 encoded as two bytes. 452 i. Payload Fragment -- a fragment of the payload, as specified 453 by the above fields. 455 j. Signature -- a digital signature on fields a-i. 457 5. Redundancy and Flexibility 459 There is a general rule that determines how redundancy works and 460 what level of flexibility the device and collector have in message 461 formats: in general, the device is allowed to send signature and 462 certificate blocks multiple times, to send signature and certificate 463 blocks of any legal length, to include fewer hashes in hash blocks, 464 etc. 466 5.1. Redundancy 468 Syslog messages are sent over unreliable transport, which means that 469 they can be lost in transit. However, the collector must receive 470 signature and certificate blocks or many messages may not be able to 471 be verified. Sending signature and certificate blocks multiple times 472 provides redundancy; since the collector MUST ignore 473 signature/certificate blocks it has already received and 474 authenticated, the device can in principle change its redundancy 475 level for any reason, without communicating this fact to the 476 collector. 478 Although the device isn't constrained in how it decides to send 479 redundant signature and certificate blocks, or even in whether it 480 decides to send along mutliple copies of normal syslog messages, 481 here I define some redundancy parameters below which may be useful 482 in controlling redundant transmission from the device to the 483 collector. 485 5.1.1. Certificate Blocks 487 certInitialRepeat = number of times each certificate block should be 488 sent before the first message is sent. 490 certResendDelay = maximum time delay in seconds to delay before 491 next redundant sending. 493 certResendCount = maximum number of sent messages to delay before 494 next redundant sending. 496 5.1.2. Signature Blocks 498 sigNumberResends = number of times a signature block is resent. 500 sigResendDelay = maximum time delay in seconds from original 501 sending to next redundant sending. 503 sigResendCount = maximum number of sent messages to delay before 504 next redundant sending. 506 5.2. Flexibility 508 The device may change many things about the makeup of signature and 509 certificate blocks in a given reboot session. The things it cannot 510 change are: 512 * The version 514 * The number or arrangements of signature groups 516 It is legitimate for a device to send our short signature blocks, in 517 order to keep the collector able to verify messages quickly. In 518 general, unless something verified by the payload block or 519 certificate blocks is changed within the reboot session ID, any 520 change is allowed to the signature or certificate blocks during the 521 session. The device may send shorter signature and certificate 522 blocks for 524 6. Efficient Verification of Logs 526 The logs secured with syslog-sign may either be reviewed online or 527 offline. Online review is somewhat more complicated and 528 computationally expensive, but not prohibitively so. 530 6.1. Offline Review of Logs 532 When the collector stores logs and reviewed later, they can be 533 authenticated offline just before they are reviewed. Reviewing 534 these logs offline is simple and relatively cheap in terms of 535 resources used, so long as there is enough space available on the 536 reviewing machine. Here, we will consider that the stored log files 537 have already been separated by sender, reboot session ID, and 538 signature group. This can be done very easily with a script file. 539 We then do the following: 541 a. First, we go through the raw log file, and split its contents 542 into three files. Each message in the raw log file is 543 classified as a normal message, a signature block, or a 544 certificate block. Certificate blocks and signature blocks are 545 stored in their own files. Normal messages are stored in a 546 keyed file, indexed on their hash values. 548 b. We sort the certificate block file by index value, and check to 549 see if we have a set of certificate blocks that can reconstruct 550 the payload block. If so, we reconstruct the payload block, 551 verify any key-identifying information, and then use this to 552 verify the signatures on the certificate blocks we've received. 553 When this is done, we have verified the reboot session and key 554 used for the rest of the process. 556 c. We sort the signature block file by firstMessageNumber. We now 557 create an authenticated log file, which will consist of some 558 header information, and then a sequence of message number, 559 message text pairs. We next go through the signature block 560 file. For each signature block in the file, we do the 561 following: 563 (i) Verify the signature on the block. 565 (ii) For each hashed message in the block: 567 (a) Look up the hash value in the keyed message file. 569 (b) If the message is found, write (message number, message 570 text) to the authenticated log file. 572 (iii) Skip all other signature blocks with the same 573 firstMessageNumber. 575 d. The resulting authenticated log file will contain all messages 576 that have been authenticated, and will indicate (by missing 577 message numbers) all gaps in the authenticated messages. 579 It's pretty easy to see that, assuming sufficient space for building 580 the keyed file, this whole process is linear in the number of 581 messages (generally two seeks, one to write and the other to read, 582 per normal message received), and O(N lg N) in the number of 583 signature blocks. This estimate comes with two caveats: first, the 584 signature blocks will arrive very nearly in sorted order, and so can 585 probably be sorted more cheaply on average than O(N lg N) steps. 586 Second, the signature verification on each signature block will 587 almost certainly be more expensive than the sorting step in 588 practice. We haven't discussed error-recovery, which may be 589 necessary for the certificate blocks. In practice, a very simple 590 error-recovery strategy is probably good enough -- if the payload 591 block doesn't come out as valid, then we can just try an alternate 592 instance of each certificate block, if such are available, until we 593 get the payload block right. 595 It's easy for an attacker to flood us with plausible-looking 596 messages, signature blocks, and certificate blocks. 598 6.2. Online Review of Logs 600 Some processes on the collector machine may need to monitor log 601 messages in something very close to real-time. This can be done 602 with syslog-sign, though it is somewhat more complex than the 603 offline analysis. This is done as follows: 605 a. We have an output queue, into which we write (message number, 606 message text) pairs which have been authenticated. Again, we'll 607 assume we're handling only one signature group, and only one 608 reboot session ID, at any given time. 610 b. We have three data structures: A queue into which (message 611 number, hash of message) pairs is kept in sorted order, a queue 612 into which (arrival sequence, hash of message) is kept in sorted 613 order, and a hash table which stores (message text, count) 614 indexed by hash value. In this file, count may be any number 615 greater than zero; when count is zero, the entry in the hash 616 table is cleared. 618 c. We must receive all the certificate blocks before any other 619 processing can really be done. (This is why they're sent 620 first.) Once that's done, any certificate block that arrives is 621 discarded. 623 d. Whenever a normal message arrives, we add (arrival sequence, 624 hash of message) to our message queue. If our hash table has an 625 entry for the message's hash value, we increment its count by 626 one; otherwise, we create a new entry with count = 1. When the 627 message queue is full, we roll the oldest messages off the queue 628 by taking the last entry in the queue, and using it to index the 629 hash table. If that entry has count is 1, we delete the entry 630 in the hash table; otherwise, we decrement its count. We then 631 delete the last entry in the queue. 633 e. Whenever a signature block arrives, we first check to see if the 634 firstMessageNumber value is too old, or if another signature 635 block with that firstMessageNumber has already been received. 636 If so, we discard the signature block unread. Otherwise, we 637 check its signature, and discard it if the signature isn't 638 valid. A signature block contains a sequence of (message 639 number, message hash) pairs. For each pair, we first check to 640 see if the message hash is in the hash table. If so, we write 641 out the (message number, message text) in the authenticated 642 message queue. Otherwise, we write the (message number, message 643 hash) to the message number queue. This generally involves 644 rolling the oldest entry out of this queue: before this is done, 645 that entry's hash value is again searched for in the hash table. 646 If a matching entry is found, the (message number, message 647 text) pair is written out to the authenticated message queue. 648 In either case, the oldest entry is then discarded. 650 f. The result of this is a sequence of messages in the 651 authenticated message queue, each of which has been 652 authenticated, and which are combined with numbers showing their 653 order of original transmission. 655 It's not too hard to see that this whole process is roughly linear 656 in the number of messages, and also in the number of signature 657 blocks received. The process is susceptible to flooding attacks; an 658 attacker can send enough normal messages that the messages roll off 659 their queue before their signature blocks can be processed. 661 7. Security Considerations 663 * As with any technology involving cryptography, you should check 664 the current literature to determine if any algorithms used here 665 have been found to be vulnerable to attack. 667 * This specification uses Public Key Cryptography technologies. 668 The proper party or parties must control the private key portion 669 of a public-private key pair. 671 * Certain operations in this specification involve the use of 672 random numbers. An appropriate entropy source should be used to 673 generate these numbers. See [RFC1750]. 675 8. IANA Considerations 677 As specified in this document, the Priority field contains options 678 for a hash algorithm and signature scheme. Values of zero are 679 reserved. A value of 1 is defined to be SHA-1, and OpenPGP-DSA, 680 respectively. Values 2 through 63 are to be assigned by IANA using 681 the "IETF Consensus" policy defined in RFC2434. Capability Code 682 values 64 through 127 are to be assigned by IANA, using the "First 683 Come First Served" policy defined in RFC2434. Capability Code values 684 128 through 255 are vendor-specific, and values in this range are 685 not to be assigned by IANA. 687 9. Authors and Working Group Chair 689 The working group can be contacted via the current chair: 691 Chris Lonvick 692 Cisco Systems 693 Email: clonvick@cisco.com 695 The authors of this draft are: 697 John Kelsey 698 Email: kelsey.j@ix.netcom.com 700 Jon Callas 701 Email: jon@callas.org 703 10. Acknowledgements 705 The authors wish to thank Alex Brown, Chris Calabrese, Carson 706 Gaspar, Drew Gross, Chris Lonvick, Darrin New, Marshall Rose, Holt 707 Sorenson, Rodney Thayer, and the many Counterpane Internet Security 708 engineering and operations people who commented on various versions 709 of this proposal. 711 11. References 713 [DSA94] NIST, FIPS PUB 186, "Digital Signature Standard", 714 May 1994. 716 [FIPS-180-1] "Secure Hash Standard", National Institute of 717 Standards and Technology, U.S. Department Of 718 Commerce, April 1995. 720 Also known as: 59 Fed Reg 35317 (1994). 722 [MENEZES] Alfred Menezes, Paul van Oorschot, and Scott 723 Vanstone, "Handbook of Applied Cryptography," CRC 724 Press, 1996. 726 [RFC1750] D. Eastlake, S. Crocker, and J. Schiller, 727 "Randomness Recommendations for Security", RFC 728 1750, December 1994. 730 [RFC1983] Malkin, G., "Internet Users' Glossary", FYI 18, RFC 731 1983, August 1996. 733 [RFC2085] M. Oehler and R. Glenn, "HMAC-MD5 IP Authentication 734 with Replay Prevention", RFC 2085, February 1997. 736 [RFC2104] H. Krawczyk, M. Bellare, and R. Canetti, "HMAC: 737 Keyed-Hashing for Message Authentication", RFC 2104 738 February 1997. 740 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 741 Requirement Level", BCP 14, RFC 2119, March 1997. 743 [RFC2434] T. Narten and H. Alvestrand, "Guidelines for 744 Writing an IANA Considerations Section in RFCs", 745 RFC 2434, October 1998 747 [RFC2440] J. Callas, L. Donnerhacke, H. Finney, and R. 748 Thayer,"OpenPGP Message Format", RFC 2440, November 749 1998. 751 [RFC3164] C. Lonvick, "The BSD Syslog Protocol", RFC 3164, 752 August 2001. 754 [SCHNEIER] Schneier, B., "Applied Cryptography Second Edition: 755 protocols, algorithms, and source code in C", 1996. 757 [SYSLOG-REL] D. New, M. Rose, "Reliable Delivery for syslog", 758 work in progress. 760 12. Full Copyright Statement 762 Copyright 2001 by The Internet Society. All Rights Reserved. 764 This document and translations of it may be copied and furnished to 765 others, and derivative works that comment on or otherwise explain it 766 or assist in its implementation may be prepared, copied, published 767 and distributed, in whole or in part, without restriction of any 768 kind, provided that the above copyright notice and this paragraph 769 are included on all such copies and derivative works. However, this 770 document itself may not be modified in any way, such as by removing 771 the copyright notice or references to the Internet Society or other 772 Internet organizations, except as needed for the purpose of 773 developing Internet standards in which case the procedures for 774 copyrights defined in the Internet Standards process must be 775 followed, or as required to translate it into languages other than 776 English. 778 The limited permissions granted above are perpetual and will not be 779 revoked by the Internet Society or its successors or assigns. 781 This document and the information contained herein is provided on an 782 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 783 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 784 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 785 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 786 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.