idnits 2.17.1 draft-ferguson-pppsonet-selfsync-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-25) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (November 1997) is 9658 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) -- Possible downref: Non-RFC (?) normative reference: ref. '1' ** Obsolete normative reference: RFC 1619 (ref. '2') (Obsoleted by RFC 2615) -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Obsolete normative reference: RFC 1750 (ref. '5') (Obsoleted by RFC 4086) Summary: 10 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 PPP Extensions Working Group Dennis Ferguson 3 INTERNET DRAFT Ravi Cherukuri 4 Expires May 1998 Juniper Networks 5 November 1997 7 Self-Synchronous Scramblers For PPP Over Sonet/SDH: Some Analysis 9 11 Status of this Memo 13 This document is an Internet-Draft. Internet-Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its areas, 15 and its working groups. Note that other groups may also distribute 16 working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six months 19 and may be updated, replaced, or obsoleted by other documents at any 20 time. It is inappropriate to use Internet-Drafts as reference 21 material or to cite them other than as ``work in progress.'' 23 To learn the current status of any Internet-Draft, please check the 24 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 25 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 26 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 27 ftp.isi.edu (US West Coast). 29 Distribution of this memo is unlimited. 31 Abstract 33 The use of a self-synchronous scrambler to minimize the possibility 34 that a carefully chosen PPP over SONET/SDH payload can cause a long 35 sequence of zero bits to be transmitted is examined. It is pointed 36 out that, while self-synchronous scramblers have some attractive 37 properties for the application, the x^43 + 1 scrambler used by ATM 38 for the same purpose has some unfortunate interactions with the 39 16-bit CRC Frame Check Sequence which is the PPP default FCS. It is 40 suggested that adding a third term to the self-synchronous generator 41 polynomial might improve its behaviour, and that inverting the 42 scrambler bit ordering so it is applied to the data in the same bit 43 order as the PPP CRC FCS algorithms are defined for may eliminate any 44 remaining effect such scramblers have on either PPP FCS. 46 Table of Contents 48 1. Overview .................................................... 2 50 2. The Problem ................................................. 3 51 2.1 SONET Hates Zeroes .......................................... 3 52 2.2 SONET/SDH Frame Scrambling and PPP .......................... 4 54 3. Self-Synchronous Scramblers ................................. 6 55 3.1 The ATM Self-Synchronous Scrambler .......................... 6 56 3.2 Using a Self-Synchronous Scrambler with PPP over SONET/SDH .. 9 57 3.3 Scrambler Impact on the 16-bit FCS .......................... 11 58 3.4 Scrambler Impact on the 32-bit FCS .......................... 14 60 4. Comparison with Other Possible Solutions .................... 15 62 5. Backwards Compatability ..................................... 18 64 1. Overview 66 The Internet Draft draft-ietf-pppext-pppsonet-scrambler-00.txt [1], 67 current at the time of writing, details a problem with the Point-to- 68 Point Protocol mapping to SONET/SDH specified in RFC 1619 [2] and 69 suggests a solution using a general purpose payload scrambler. This 70 document attempts to succinctly redescribe the (alleged) defect of 71 the RFC 1619 mapping and examines the strengths and weaknesses of the 72 use of self-synchronous scramblers as an alternative solution. The 73 intent of this draft is neither to assume a position with respect to 74 the specific actions that might be decided upon to address the 75 concern with RFC 1619, if any, nor to represent the authors as having 76 any particular expertise other than general knowledge of the 77 technology, but rather tries to convey information of a 78 non-controversial nature related to the problem, and a potential 79 approach to the solution, which it is hoped will clarify some of the 80 issues for those interested in the problem. 82 The use of a self-synchronous scrambler to minimize the possibility 83 that packets constructed by a malicious user will cause a long series 84 of zero bits to be transmitted on a SONET/SDH circuit is examined. 85 Self-synchronous scramblers are not ``general purpose'', in that 86 their use can exacerbate the effect of transmission errors on certain 87 types of payloads. On the other hand self-synchronous scramblers are 88 very secure, quite easy to implement, place no additional 89 implementation requirements on either the SONET/SDH framer or the 90 octet-synchronous HDLC framer, and would appear to be a good match 91 for the needs of PPP over SONET/SDH where only the interaction of the 92 scrambler with error detection in CRC-protected HDLC frames is of 93 concern. 95 ATM deals with these same issues by employing a particular self- 96 synchronous scrambler to cell payload, using the x^43 + 1 polynomial. 97 This is given particular attention not only because of the 98 considerable implementation and deployment experience accrued from 99 its use in ATM networks but also because several recent PPP over 100 SONET/SDH products have made use of this. An unfortunate interaction 101 of the x^43 + 1 polynomial with the 16-bit CRC FCS optionally used 102 for PPP is noted, and it is shown that a three term self-synchronous 103 polynomial may eliminate any major effect on 16-bit CRC error 104 detection. 106 2. The Problem 108 2.1 SONET Hates Zeroes 110 The fundamental problem is that unhappy things can happen when a long 111 string of zeroes is transmitted on a SONET/SDH circuit. The most 112 serious of these is that a very long sequence of zero bits 113 transmitted on a SONET circuit (where ``very long'' is somewhere 114 between 2.3 and 100 microseconds, or between about 45 and 2000 bytes 115 of data at the STS-3c rate) is indistinguishable at the receiver from 116 a broken circuit. A sequence of this length may hence cause the 117 receiver to treat the incoming circuit as broken and to take whatever 118 actions it will in this situation. 120 Other more subtle difficulties can also be caused by shorter 121 sequences of zero bits. SONET/SDH receivers recover timing 122 information from the incoming data by filtering state transitions 123 through a phase-locked loop. The recovered timing information may be 124 used not only to clock in the data being received, but also as a 125 clock for the transmitter side of the same circuit as well as the 126 transmitters of other circuits terminating in the same piece of 127 equipment. Indeed, distribution of timing information throughout an 128 entire SONET/SDH network may be done via the circuit timing recovery 129 described above, so errors anywhere in the distribution tree might 130 effect a potentially some number of downstream nodes as well. 132 The problem that a lengthy sequence of zero bits causes here is that 133 the timing transitions that keep the PLL well synchronized only occur 134 when one bits are received; long sequences of zero bits are devoid of 135 timing information. A PLL which is receiving no input will begin to 136 drift at a rate related to the quality of the local clock source, 137 which will sometimes be inferior to the clock source steering the 138 received data. This lower quality time, if it is used to clock the 139 transmitters of other circuits, may in principle be propagated to 140 other network nodes as well, causing a similar degradation of their 141 timing too. If the receiving clock drifts severely its ability to 142 decode even the incoming data stream from which it formerly obtaining 143 the timing may be compromised. While the issue of just how awful the 144 consequences of these shorter sequences might be is debatable, most 145 everyone will agree that nothing good can come of it. As for the 146 other somewhat controversial issue of how many zero bits in a row is 147 too many, 80 bits is often chosen since this approximately 148 corresponds to the number of zero bits which will cause many 149 commercial clock recovery circuits to transition from actively trying 150 to synchronize from the incoming data stream to ``holdover'' mode, 151 where they free-run on the local clock source steered by the most 152 recent error correction. Any reference to ``80 bits'' below should 153 be read as ``a relatively long sequence of zero bits'' since the 154 limits are relatively soft and implementation dependent. 156 2.2 SONET/SDH Frame Scrambling and PPP 158 The somewhat debatable issue of how many zero bits in a row is 159 ``bad'', for some serious value of ``bad'', is reflected in the fact 160 that the SONET/SDH specifications do not attempt to completely avoid 161 the possibility that a long sequence of zeroes will be transmitted on 162 a SONET/SDH circuit (something that probably could only have been 163 achieved at the cost of additional overhead bandwidth), but instead 164 are satisfied with making the occurence of the event improbable 165 (which doesn't cost much of anything). Specifically it may be 166 observed that if only one particular n-bit sequence will do something 167 bad, and if all possible n-bit sequences are equally likely, then the 168 probability of something bad happening will be 1/2**n. If ``n'' is 169 80 or more the probability is pretty small indeed. 171 It is the case, however, that if the n-bit sequence which does bad 172 things is an n-bit sequence of zero bits the probable occurence of 173 this particular sequence in randomly selected real-life data probably 174 far exceeds 1/2**n. This issue is the (only) one which is addressed 175 in the SONET/SDH specifications by the use of a frame scrambler, to 176 effectively change the sequence of payload data which causes a series 177 of zeroes to be transmitted on the wire at the physical level from a 178 sequence of zeroes to some sequence whose occurence in a random 179 selection of real-life data is probably much closer to 1/2**n. 181 Understanding how this works requires a minimal understanding of how 182 SONET/SDH formats the data it is transmitting. SONET/SDH data is 183 transmitted in frames. A frame consists of 9 ``rows'', where each 184 row in a frame on an OC-N circuit consists of 3*N bytes of 185 SONET/SDH-defined frame overhead (or transport overhead, to be 186 consistant with SONET terminology) followed by 87*N bytes of payload 187 data. The payload data in each row sometimes includes other 188 SONET/SDH-defined overhead, but sometimes just includes user data. 189 The SONET/SDH frame scrambler operates at the transmitter by 190 exclusive-or'ing the data sent in each SONET/SDH frame with the 191 output of a very simple pseudo-random number generator. The 192 generator is reinitialized to a well-known state at the start of each 193 frame (making this a ``frame-synchronous'' scrambler) and then the 194 output is applied to every byte in the frame except the transport 195 overhead in the first row of the frame. The receiver similarly 196 resets the generator to the well-known state at the beginning of each 197 frame, and then exclusive-or's the output into the appropriate 198 incoming bytes to recover the unscrambled data. 200 The pseudo-random number generator used is a 7-bit LFSR, which will 201 repetitively generate a sequence of 127 unique bytes (i.e. a 127 bit 202 sequence repeated eight times). Note well that the SONET/SDH frame 203 scrambler does not avoid the problem of zero transmission on a 204 SONET/SDH circuit, it just changes the payload data which can induce 205 the problem from a sequence of 0-valued bytes to a fixed sequence of 206 127 magic bytes which might be expected to occur relatively less 207 frequently in real life data. And for the multiplexed payloads 208 SONET/SDH was employed to carry early on, with user data derived from 209 many streams well mixed together along with lower speed framing 210 overhead, it is probably not a bad assumption that an 80-bit fragment 211 of the magic sequence matched in phase to the output of the LFSR 212 won't occur very often. 214 For PPP over SONET/SDH payloads, however, the contents of a datagram 215 transmitted across the circuit are laid out in consecutive payload 216 bytes of a concatentated SONET/SDH SPE edited only by the octet- 217 synchronous HDLC framer. Anyone who feels the urge to do so can send 218 packets filled with the magic 127 byte sequence, and while this 219 doesn't guarantee that the packet will cause a long sequence of 220 zeroes to be transmitted on any PPP over SONET/SDH circuit that the 221 packet transits, there is a probability of 1/127 that it will hit any 222 particular row in the SONET/SDH frame just right to synchronize with 223 the LFSR ouput. Reference [1] claims that one of every 21 1500 byte 224 datagrams carrying the sequence will probably cause a SONET/SDH 225 circuit difficulty, and I see no reason to doubt this. 227 Note that (if I've done the math right) the magic sequence does 228 include the two consecutive bytes <0x7d 0x0e>. Since a user can 229 neither transmit this sequence through an HDLC framer unscathed (the 230 0x7d byte will be escaped) nor cause the HDLC framer to generate this 231 output with any other packet contents, the longest run of zeroes that 232 a PPP over SONET/SDH packet payload can cause is 127 bytes. Since 233 127 bytes represents about 6.5 microseconds of transmission time on 234 an OC-3c circuit this is sufficient to possibly cause a loss of 235 signal condition there, and at any SONET/SDH rate far exceeds the 80 236 bit times considered maximal if all possible clock synchonization 237 consequences are to be avoided. 239 Again, the authors do not have the expertise either to estimate the 240 seriousness of the described problem or to judge the validity of the 241 concerns about this expressed by both SONET/SDH equipment 242 manufacturers and network operators. The fact that such concern 243 exists at all, however, pragmatically represents an impediment to the 244 wide deployment and use of interoperable PPP over SONET/SDH, and this 245 by itself should be sufficient reason to search for an interoperable 246 solution. 248 3. Self-Synchronous Scramblers 250 3.1 The ATM Self-Synchronous Scrambler 252 ATM over SONET/SDH exhibits much the same behaviour as PPP over 253 SONET/SDH in that it inserts relatively long sequences of arbitrary 254 user data into consecutive bytes of SONET frame payload. ATM deals 255 with the possibility that someone might use knowledge of the magic 256 sequence to the detriment of a SONET/SDH circuit by applying yet 257 another scrambler to the payload of ATM cells. While this scrambler 258 is again intended only to make the occurence of a pattern which 259 causes long strings of zeroes to be transmitted on the circuit 260 improbable, rather than impossible, it differs from the SONET 261 frame-synchronous scrambler in that it does not generate a fixed 262 sequence of random numbers at all. It instead attempts to make the 263 magic sequence a constantly moving, and hard-to-guess, target so that 264 an informed attacker will have little better probability of hitting 265 the sequence than will random data. 267 The characteristics of self-synchronous scramblers in general are 268 best described starting from the details of a particular 269 implementation, and the ATM scrambler (called the x^43 + 1 270 self-synchronous scrambler from its polynomial representation) is of 271 particular interest since it there is considerable implementation and 272 deployment experience using it. 274 Schematically the transmitter side of the scrambler operates as 275 follows, on a bit-by-bit basis: 277 Unscrambled Data 278 | 279 v 280 +-------------------------------------+ +---+ 281 +->| --> 43 bit shift register --> |--->|xor| 282 | +-------------------------------------+ +---+ 283 | | 284 +-----------------------------------------------+ 285 | 286 v 287 Scrambled Data 289 The shift register is initialized once, at the start of operation, 290 and may be set to any random 43-bit value. Each bit of data 291 subsequently transmitted is exclusive-or'd with a bit shifted out of 292 the high order end of the register, and the result of this operation 293 is shifted back into the low order end of the register. The 294 scrambled data which is transmitted is essentially a copy of the 295 internal state of the scrambler. 297 The corresponding receiver schematic is shown following: 299 Scrambled Data 300 | 301 +-----------------------------------------------+ 302 | | 303 | v 304 | +-------------------------------------+ +---+ 305 +->| --> 43 bit shift register --> |--->|xor| 306 +-------------------------------------+ +---+ 307 | 308 v 309 Unscrambled Data 311 The descrambler essentially operates by exclusive-or'ing each bit of 312 incoming scrambled data with the (scrambled) incoming data bit 313 received 43 bits previously. At startup the shift register may be 314 initialized with the first 43 bits of data which arrive, after which 315 it can begin unscrambling. 317 This scrambler, as with self-synchronous scramblers in general, has a 318 number of attractive properties. The state of the scrambler is 319 transmitted to the descrambler in the scrambled data stream itself, 320 avoiding the need for either restarting the scrambler periodically to 321 achieve synchronization between the transmitter and receiver (as the 322 SONET/SDH frame-synchronous scrambler does) or providing an 323 out-of-band channel for carrying synchronization information (as is 324 suggested in [1]). This independence from surrounding infrastructure 325 allows a certain flexibility in implementation; for PPP over 326 SONET/SDH, for example, if the HDLC framer and SONET framer were 327 implemented on separate devices the scrambler could be implemented on 328 either device, or even a third device, without difficulty. The 329 scrambler is also easy to understand, which maximizes the probability 330 of interoperable implementations. 332 The security of this scrambler in making it hard to guess the 333 unscrambled input which would cause it to emit the magic sequence of 334 the frame-synchronous SONET scrambler at its output seems quite high. 335 Predicting the output of the scrambler for a given input requires 336 knowledge of the 43 bit state of the transmitter at the time 337 scrambling of the known input is begun. Assuming the attacker is not 338 in a position to wiretap the data on the circuit in scambled form (it 339 is assumed that an attacker in that position could think of much more 340 destructive things to do with the information than to cause zeroes to 341 be sent on the circuit) then predicting the state of the scrambler at 342 any point in time would appear to require knowledge of both the 343 initial 43 bit state of the scrambler when it was started and every 344 byte of data scrambled by the device since it was started. Even if 345 the attacker got his frame to the scrambler immediately after it was 346 initialized, the attacker would still have to have knowledge of the 347 value to which the scrambler was initialized, and this value may be 348 chosen at random by the transmitter. It hence appears that all 349 attacks reduce to guessing the state of a randomly chosen 43 bit 350 number, with a probability of 1/2**43 of guessing correctly and with 351 the additional probability of 1/127 that a correct guess will leave 352 the frame aligned in the SONET/SDH payload just right to cause an 353 extended sequence of zeroes to be transmitted. This seems pretty 354 secure. 356 While self-synchronous scramblers hence have some obvious strengths, 357 their use also comes with some drawbacks which need to be carefully 358 examined in the context of PPP over SONET/SDH. The first criticism 359 often leveled against self-synchronous scramblers is that they can 360 represent a performance problem, with design of very high performance 361 scramblers which need to process many bytes at a time becoming costly 362 since the feedback nature of the scrambler prevents effective 363 pipelining. This may indeed be true for ATM switches, where the cost 364 of processing cell payloads may be dominated by the cost of the 365 scrambler. For PPP over SONET/SDH, however, we also have the 366 implementation complexity of the octet-stuffing HDLC framer to bear, 367 and at speeds where byte-at-a-time processing is not an option 368 implementation of this HDLC framer becomes very complex indeed. It 369 is pretty much impossible to think of a situation where the 370 implementation complexity of a self-synchronous scrambler would even 371 come close to that of an HDLC framer, and it doesn't seem useful to 372 spend much effort optimizing a part of a PPP over SONET/SDH system 373 which is unlikely in the extreme to be the part which represents a 374 barrier to the upward performance scalability of PPP over SONET/SDH. 375 The issue of scrambler performance is not persuasive in the context 376 of PPP over SONET/SDH. 378 The second, more serious, issue with self-synchronous scramblers is 379 the fact that they are error multiplying. Consideration of the 380 operation of the x^43 + 1 descrambler above shows that single bit 381 error in the scrambled data will result in two errors in the 382 unscrambled data, one error in the bit corresponding to the location 383 of the original error in the scrambled data and a second error 43 384 bits later. This fact probably makes self-synchronous scramblers 385 unsuitable for general-purpose use on some types of data payloads; 386 protocols which attempt to do error correction, or which perhaps use 387 some form of parity-based error detection, may find their performance 388 seriously impaired by error multiplication (though it might be noted 389 that ATM makes use of the x^43 + 1 scrambler despite the fact that 390 ATM is also sometimes represented as a general-purpose data 391 transport, a dichotomy which at least the first author finds slightly 392 odd). 394 This behaviour is less of a direct concern for PPP over SONET/SDH, 395 however. PPP over SONET/SDH attempts to, and is explicitly permitted 396 to, discard all frames where any transmission error at all has 397 occurred, it really doesn't matter much whether there are N bits of 398 the frame in error or 2*N. The error spreading does increase the 399 probability that a single error might damage two consecutive frames 400 instead of one (this happens without scrambling only if the error 401 occurs in the flag byte between frames), but this is unlikely to 402 significantly increase the overall errored frame rate on a circuit 403 given that most frames will be substantially longer than 43 bits. 404 The more serious potential problem caused by error multiplication for 405 PPP over SONET/SDH is that the errors produced by certain 406 self-synchronous scrambler polynomials, when applied in certain ways, 407 may interact badly with the CRC frame check sequences used by HDLC 408 such that the error detection power of the latter is reduced. This 409 dictates that careful consideration be given to the problem when 410 selecting a self-synchronous scrambler for use with PPP over 411 SONET/SDH. Some of these issues are addressed in a later section. 413 3.2 Using a Self-Synchronous Scrambler with PPP over SONET/SDH 415 The selection of a self-synchronous scrambler for use with PPP over 416 SONET/SDH is by itself insufficient to solve anything; agreement 417 about how the scrambler is employed is also a prerequisite for 418 interoperability. This section covers some of the issues related to 419 self-synchronous scrambler use which have occurred to the authors. 421 For the purposes of discussion it will be assumed that a PPP over 422 SONET/SDH transmitter consists of a somewhat separable HDLC framer, 423 which takes PPP packets, computes and appends an FCS to them, 424 octet-stuffs the frame data for idle-flag transparency and generates 425 idle flags between frames, and SONET framer, which takes the stream 426 of bytes generated by the HDLC framer, surrounds them with the 427 appropriate SONET/SDH overhead and sends them on to the physical 428 layer. This gives a system block diagram which looks something like: 430 Transmitter 431 +----------+ +-----------+ 432 (A) | HDLC |(B) | SONET/SDH | 433 ---->| framer |--->| framer | - - - - 434 | | | | 435 +----------+ +-----------+ 437 +-----------+ +----------+ 438 | SONET/SDH |(B) | HDLC |(A) 439 - - - - | deframer |--->| deframer |---> 440 | | | | 441 +-----------+ +----------+ 442 Receiver 444 To maximize the probability that the scrambler might be easily 445 retrofitted to existing equipment, and to ease the construction of 446 dual-mode equipment where use of the scrambler is a configuration 447 option to allow backward compatability, it seems prudent to leave the 448 operation of both the HDLC and the SONET/SDH framers unchanged by the 449 scrambler insertion. If this constraint is to be met it appears that 450 there are only two places where the scrambler could be applied, 451 marked (A) and (B) in the above diagram. 453 Placing the scrambler at (A), in effect scrambling the contents of 454 PPP packets prior to HDLC FCS insertion and flag escaping, has the 455 happy property of avoiding having to think about the scrambler's 456 effect on CRC error detection since the CRC would be checked at the 457 receiver prior to the error-multiplying descrambling operation. The 458 scheme appears to have a fatal flaw, however. Since the scrambler 459 only operates on packet data the receiver descrambler must receive 43 460 bits of packet data to reach synchronization with the transmitter. 461 This packet, received when the receiver was unsynchronized, must of 462 course be discarded since the receiver would have no way to 463 descramble the first 43 bits. While this might be acceptable, a 464 problem occurs should the receiver be out of synchronization with the 465 transmitter (perhaps because of an error at the end of the previous 466 packet) but be unaware of this. In this case the receiver will 467 mangle the first bits of the packet, but the error will be undetected 468 since the CRC has already been checked. Placement of the scrambler 469 at (A) would hence appear to violate the end-to-endness of the HDLC 470 FCS error detection. 472 This leaves placement of the scrambler at (B), that is scrambling the 473 CRC'd, octet-stuffed, flag-delineated output of the HDLC framer. 474 Since the HDLC framer transmits constantly (it inserts a stream of 475 idle flags between frames) the receiver is assured a constant stream 476 of scrambled information on which to synchronize. Since the frame 477 FCS is computed before scrambling and checked after descrambling, the 478 FCS is useful for detecting and protecting against synchronization 479 errors as well as transmission errors. Since the scrambler is 480 operating on what is in effect a byte stream at this stage it needn't 481 have any sensitivity to frame boundaries (e.g. it needn't implement 482 the packet discard behaviour described for (A) when out of sync). 483 Implementing a configurable bypass for the scrambler to achieve 484 backward compatability with RFC 1619 should also be straight forward. 485 The remainder of this document hence presumes the self-synchronous 486 scrambler would be introduced between the SONET/SDH and HDLC 487 (de)framers. 489 Given the placement of the scrambler in the system, there still 490 remains a second issue with the application of a self-synchronous 491 scrambler which must be addressed. While the scrambler operates on a 492 byte stream (or a multi-byte stream at higher speeds) in 493 implementation, the scrambler is defined in terms of bit-by-bit 494 operation. This means there is a choice concerning the order in 495 which bits from each byte are presented to the scrambler; the 496 scrambler may scramble each byte starting at the high order bit and 497 working towards the low order bit, or it may scramble each byte 498 starting at the low order bit and working towards the high order bit. 499 And if the scrambler polynomial has terms whose exponents are not an 500 even multiple of 8 (e.g. 43) the two implementation choices will 501 produce different, non-interoperable results. 503 For ATM the x^43 + 1 self-synchronous scrambler is applied 504 big-bit-first, as this matches SONET/SDH's on-the-wire transmission 505 order. For PPP over SONET/SDH there is an additional consideration 506 relating to bit order, however, that being that CRC's used by PPP's 507 HDLC framing are computed as if the packet was being transmitted in 508 little-bit-first order. The scrambler bit order may thus be chosen 509 to match the on-the-wire transmission order, or the CRC computation 510 order, with different results. The bit order of scrambler hence 511 needs to be specified to avoid ambiguity. It also turns out that the 512 choice of bit order has some impact on the damage the scrambler 513 causes to CRC error detection such that making the bit order of 514 scrambler application match the CRC computation order may be a better 515 choice. 517 3.3 Scrambler Impact on the 16-bit FCS 519 The only major defect related to the use of self-synchronous 520 scramblers with PPP over SONET/SDH that has been identified is the 521 damaging effect that error multiplication might, or might not, have 522 on the CRC error detection used by PPP over SONET/SDH. This section 523 attempts to examine the effect on the 16-bit CRC FCS in particular. 524 While RFC 1619 does recommend the use of the 32-bit FCS for PPP over 525 SONET, there still remain reasons why minimizing the impact of any 526 scrambling solution on the 16-bit CRC is important. In particular, 527 (a) the 16-bit CRC is inherently significantly weaker than the 32-bit 528 CRC, so any further weakening of the former is more likely to have 529 greater practical consequences than the latter, (b) the 16-bit FCS is 530 required for use on PPP LCP frames, (c) there are existing PPP over 531 SONET implementations which only implement the 16-bit FCS, and (d) 532 some may find the slightly reduced per-frame overhead of the 16-bit 533 FCS a reasonable tradeoff given the expectation of very low error 534 rates on SONET/SDH circuits. 536 To characterize the performance of a CRC error-detection code it is 537 necessary to define the term ``burst error''. In an errored frame 538 the number of bits between the first bit in the frame which is in 539 error and the last bit which is in error, inclusive, independent of 540 the state of the bits in between, is the length of the burst error in 541 that frame. There are two properties of a 16-bit CRC which 542 particularly define its strength. The first is that a 16-bit CRC 543 will detect all burst errors in a frame whose length is less than or 544 equal to 16. The second is that if all errors are equally probable 545 then the 16-bit CRC will detect burst errors with length greater than 546 16 with a probability of failure of 1/2**16. The issue with 547 scramblers, then, is that they turn an n-bit burst error on the wire 548 into an (n+43)-bit burst error at the HDLC framer (more or less, the 549 reversed view of bit ordering between SONET/SDH on-the-wire 550 tranmission and the CRC FCS definition, along with the bit order 551 chosen for the scrambler, all have an impact on how the on-the-wire 552 error looks by the time it gets to the HDLC framer). While this does 553 not necessarily weaken the CRC, since the error multiplication is 554 strictly correlated with the original on-the-wire error, it requires 555 some consideration to determine exactly what happens to the CRC 556 strength. 558 It turns out that the ATM x^43 + 1 scrambler would be a particularly 559 unfortunate choice for use with the HDLC 16-bit FCS. First, 560 exclusive-or'ing the two byte sequence <01 37> into any two 561 consecutive bytes of a correctly CRC'd message, after scrambling with 562 the x^43 + 1 scrambler in big-bit-first order, will cause an error 563 which will go undetected by the FCS check after descrambling. 564 Similarly, <0f f8> will cause the same problem when the scrambler is 565 run in little-bit-first order (numbers included in hopes that someone 566 will check the math). As these are 9-bit burst errors, the x^43 + 1 567 scambler has effectively reduced the burst error detection length 568 from 16 to 8. Note that running the scrambler in big-bit-first order 569 is in fact slightly worse as it also causes some 14-bit (<02 41 d0>, 570 <03 76 d0>), 15-bit (<08 8a a0>, <09 bd a0>) and 16-bit burst errors 571 to also escape detection. 573 At least as bad is the effect of the x^43 + 1 scrambler on 16-bit CRC 574 detection of long bursts. While the 16-bit CRC will detect random 575 long burst errors with a probability of failure of 1/2**16, this 576 probability is a composite of the probability of detecting burst 577 errors with an odd number of bits in error, which the 16-bit CRC can 578 always detect, and burst errors with an even number of bits in error, 579 which the 16-bit CRC can detect with a probability of 1/2**15 of 580 getting it wrong (Tanenbaum [4], pages 211-212, provides a 581 particularly readable description of this). Note, however, that the 582 effect of the x^43 + 1 descrambler is to double the number of bits 583 which are in error in the unscrambled frame, i.e. a single bit error 584 in the scrambled frame becomes 2 errored bits in the unscrambled 585 frame, 2 becomes 4, 3 becomes 6 and so on. In effect the x^43 + 1 586 scrambler ensures that all errors in the unscrambled frame have an 587 even number of errored bits, which increases the probability of 588 detection failure from 1/2**16 to 1/2**15. 590 The ATM x^43 + 1 scrambler hence interacts badly with the 16-bit CRC 591 polynomial used by PPP, reducing its already relatively weak error 592 detection power. It should be noted, however, that the interaction 593 is a property of this particular choice of self-synchronous scrambler 594 rather than a defect of self-synchronous scramblers in general, since 595 it is clear that adding a third term to the self-synchronous 596 scrambler polynomial (i.e. multiplying the number of error bits by 3 597 rather than 2) should produce dramatically different results. 599 As an alternative the authors investigated a three-tap 600 self-synchronous scrambler with the polynomial representation x^43 + 601 x^23 + 1 (with the 23 being chosen arbitrarily, partly because it 602 doesn't significantly complicate a byte-by-byte scrambler 603 implementation, but otherwise on the sole basis that it is as weird a 604 number as 43). Schematically this yields a scrambler whose 605 transmitter operates as follows: 607 Unscrambled Data 608 | 609 v 610 +-------------+ +---+ +---------------+ +---+ 611 +->|-> 20 bits ->|-->|xor|-->|-> 23 bits ->|--->|xor| 612 | +-------------+ +---+ +---------------+ +---+ 613 | ^ | 614 | | | 615 +----------------------+----------------------------+ 616 | 617 v 618 Scrambled Data 620 This appears to have pretty much identical properties with respect to 621 initialization and security as the x^43 + 1 scrambler. Its 622 implementation complexity is probably increased somewhat, certainly 623 when scrambling multiple bytes at a time, though it is still very 624 simple compared to an HDLC framer. 626 The corresponding receiver schematic is shown following: 628 Scrambled Data 629 | 630 +----------------------+----------------------------+ 631 | | | 632 | v v 633 | +-------------+ +---+ +---------------+ +---+ 634 +->|-> 20 bits ->|-->|xor|-->|-> 23 bits ->|--->|xor| 635 +-------------+ +---+ +---------------+ +---+ 636 | 637 v 638 Unscrambled Data 640 It turns out (making the somewhat dangerous assumption that the 641 authors have managed to do the computation without errors) that not 642 only does this restore the 1/2**16 probability of failing to detect 643 long burst errors, but it also restores the minimum burst length 644 detection of the 16-bit CRC to 16 when the scrambler is applied in 645 little-bit-first order (in big-bit-first order an undetected 15 bit 646 burst <08 0b 60> as well as a 16 bit burst <84 a3> can still occur). 647 In summary, while the x^43 + 1 self-synchronous scrambler in 648 particular is probably not a good match for the characteristics of 649 PPP over SONET/SDH a more carefully chosen scrambler, such as the 650 x^43 + x^23 + 1 scrambler suggested above when applied in 651 little-bit-first order, may be almost neutral in its impact on 16-bit 652 CRC error detection. 654 3.4 Scrambler Impact on the 32-bit FCS 656 Given the inherent strength of the 32-bit PPP FCS compared to the 657 16-bit FCS, the impact of an error-multiplying scrambler on the 658 longer CRC is less of a concern. Some observations are 659 never-the-less included here for completeness. 661 Of primary interest is the fact that the error detection properties 662 of the 32-bit CRC polynomial used by PPP, which is also used for ATM 663 AAL5 frame protection except that the latter applies the polynomial 664 in big-bit-first order to match the transmission order, do not change 665 for long burst errors whether the number of bits in error is odd or 666 even. For long bursts neither the x^43 + 1 nor the x^43 + x^23 + 1 667 scrambler lessen the probability of not detecting an error compared 668 to unscrambled performance, that probability remains at 1/2**32 in 669 all cases. 671 For short bursts it should be noted that even without scrambling the 672 32-bit CRC fails to detect some error bursts which are less than or 673 equal to 32 bits in length. For example the 31-bit bursts <0a 1e e9 674 d5 e0> and <05 8f f4 6a 70> will go undetected. This appears to be 675 an artifact of the difference between SONET's actual transmission bit 676 ordering (i.e. big-bit-first) and the inverted bit ordering used in 677 the definition of the PPP 32-bit FCS. The errors noted above would 678 be 38 or 39 bits long if the transmission order actually matched the 679 definition from which the FCS is computed (this probably represents a 680 minor defect in RFC 1619 as well; it would have been better to have 681 made the FCS match the bit order of transmission, either by changing 682 the FCS definition used here from that in RFC 1662 [3] or by 683 specifying that PPP over SONET/SDH transmit payload bytes in 684 little-bit-first order). 686 Given this, the short burst detection capability is reduced still 687 further by both the x^43 + 1 scrambler (e.g. failure to detect the 688 28-bit burst error <02 ea 58 a0 40>) and the x^43 + x^23 + 1 689 scrambler (e.g. failure to detect the 24-bit burst error <11 f6 ca 690 e0>) when the scramblers are run over the data in big-bit-first 691 order. When run in little-bit-first order to match the CRC, on the 692 other hand, the presence of the scramblers has no effect on error 693 detection at all; the only errors which escape detection with either 694 scrambler in use are identically those which would escape detection 695 if the scrambler were not in use. Thus, with the proper choice of 696 bit ordering, it would appear that the use of either of these two 697 self-synchronous scramblers may have no effect on the 32-bit CRC FCS 698 error detection. 700 4. Comparison with Other Possible Solutions 702 The authors are aware of two other suggested approaches to solve the 703 PPP over SONET/SDH magic sequence problem. This section attempts to 704 compare and contrast them with the use of a self-synchronous 705 scrambler as detailed here. 707 The first of these proposals is to deal with the problem in the HDLC 708 framer. The HDLC framer is free to insert frame escape characters at 709 arbitrary places in the frame, and if applied properly this could be 710 used to break up the magic sequence whenever it occured in a frame by 711 inserting an escape. 713 This technique has the very attractive property of being fully 714 backward compatable with nodes implementing the RFC 1619 procedures, 715 and has the merit of potentially providing ``perfect'' protection 716 against the sequence rather than the probable protection provided by 717 any sort of scrambler. The drawback appears to be one of 718 implementation complexity, particularly if one assumes the task of 719 getting it ``perfect'' should be to avoid any sequence of zeroes 720 longer than 80 bits from being transmitted. This could be done with 721 little additional complexity by unconditionally escaping every eighth 722 byte in the frame, for example, but the cost in terms of framing 723 overhead is really, really unacceptable. A more efficient approach 724 might be to detect 80-bit fragments of the sequence in the packet 725 being framed and inserting an escape only when these are detected, 726 but this leaves open the issue of exactly how one would go about 727 reliably detecting any 10 byte fragment from a 127 byte sequence, and 728 would still result in escapes being inserted 127 times more 729 frequently than necessary given the probability that such a sequence 730 would actually be aligned in the SONET/SDH frame just right to do 731 damage. The most efficient and implementable way this might be 732 accomplished would hence be to monitor the output of the SONET/SDH 733 frame scrambler for zeroes directly, taking action in the HDLC framer 734 only when a sufficiently long string of zeroes was actually detected 735 at the output. This might be workable, but only at the cost of 736 architecting in a strong connection between that SONET/SDH framer and 737 the HDLC framer which might preclude some otherwise very reasonable 738 implementation strategies which kept these two relatively separate. 740 In general, however, the least attractive aspect of this approach is 741 that no matter how it is done the net effect is to add complexity to 742 the HDLC framer, which is already the most complex and least scalable 743 component of a high-speed PPP over SONET/SDH implementation. In 744 comparison, scrambling approaches to the problem leave the HDLC 745 framer entirely alone, and while they might come with their own set 746 of complexities their application is less likely to present further 747 constraints to the upward performance scalability of PPP over 748 SONET/SDH. 750 The second method, suggested in [1], is to use a conventional 751 pseudo-random number generator to scramble the output. The LFSR is 752 40 bits wide, hence producing a sequence of 2**40 - 1 bytes before 753 repeating, and is run continuously rather than being periodically 754 resynchronized, so given random initialization it should be about as 755 hard to guess the phase of the scrambler as it is to guess the state 756 of the self-synchronous scramblers described here. The scrambler is 757 applied to the output of the HDLC framer, as discussed above, before 758 the data is inserted into the SONET/SDH payload envelope. The 759 primary advantages of this method are that the scrambler is 760 non-error-multiplying, and hence would avoid causing damage to 761 sensitive payloads, and that very high performance implementations of 762 the scrambler itself would probably be slightly more straight forward 763 than a self-synchronous scrambler. 765 The complexity of this scheme arises from the issue of how one gets 766 the 5 bytes of state in the receiving scrambler synchronized with the 767 sender. Since there is no way to recover the state from the payload 768 itself the state must be transmitted to the receiver out-of-band; the 769 authors choose three bytes in the SONET/SDH Path Overhead (sent once 770 per SONET frame) to do this. Of course, since three bytes is 771 insufficient to carry the full 5 bytes of state along with the CRC 772 which is necessary to detect errors in the state, it requires three 773 frames to transmit the 5 bytes of scrambler state, the CRC and the 774 sequence numbers necessary to make sure the state information 775 collected from the three consecutive frames are indeed chunks of the 776 same 5 bytes. Since the transmitter must hence begin sending the 777 scrambler state several frames ahead of the time when the receiver 778 will be able to use it, the transmitter must have knowledge of not 779 only its current state but also what that state will be several 780 frames into the future. Starting from scratch will take the receiver 781 up to 5 frame times, or 600 microseconds (independent of the speed of 782 the SONET/SDH circuit) to synchronize, assuming no errors, and should 783 the receiver fall out of synchronization without knowing it will take 784 as many as five frames to tell for sure that it has been generating 785 crap. This synchronization scheme obviously necessitates the 786 scrambler being relatively intimate with the SONET/SDH framer, unlike 787 self-synchronous scramblers which may be placed anywhere where they 788 have access to the stream of deframed payload bytes, a requirement 789 which may preclude some otherwise reasonable implementation 790 strategies, and in comparison to a self-synchronous scrambler the 791 above is exceedingly slow and complex to synchronize. 793 The primary advantage of this scrambler over self-synchronous 794 scramblers, and perhaps the compelling advantage if the 795 characteristics of the payload being scrambled are indeterminate, is 796 that it avoids error-multiplication and any side-effects that might 797 cause in the descrambled payload. The issue with respect to PPP over 798 SONET/SDH seems to be that this scrambler is solving a problem PPP 799 over SONET/SDH doesn't have. The characteristcs of the PPP over 800 SONET/SDH payload are very well known, and it appears that a 801 carefully chosen self-synchronous scrambler may be used for this 802 particular payload with little, if any, harm to the PPP payload at 803 all. This makes the synchronization complexity of the scheme, and 804 the constraints it places on implementations, gratituous for this 805 application and a possible impediment to interoperability, even 806 though it might make a fine choice for more general-purpose 807 applications. 809 5. Backwards Compatability 811 The disadvantage of the employment of a scrambler to solve the 812 SONET/SDH magic sequence problem is that equipment using the 813 scrambler will be incompatable with equipment implementing RFC 1619 814 alone. That is, the byte stream generated by the scrambler will 815 appear as random line noise to the RFC 1619 node, and vice versa. 816 Such a low level, complete incompatability between ends of a circuit 817 does not seem amenable to PPP LCP negotiation procedures either; any 818 automatic negotiation of the state of the circuit needs to be 819 implemented at a lower level. 821 Because of this, it is likely better that interoperability between 822 scrambled and RFC 1619 nodes be implemented at the SONET/SDH layer 823 instead. RFC 1619 PPP over SONET/SDH identifies itself using a Path 824 Signal Label (C2 byte) of 207 decimal. Obtaining a new Path Signal 825 Label value for use with scrambled PPP payloads, requiring that new 826 implementations provide both the scrambler and RFC 1619 compatability 827 as configuration options, and then using the Path Signal Label to 828 detect and correct mismatches in the configuration and/or capability 829 of each end of the circuit, should provide sufficient mechanism to 830 achieve interoperability with existing equipment. 832 Security Considerations 834 The scramblers discussed here are intended to provide protection for 835 SONET/SDH circuits from loss of clock problems which could otherwise 836 be caused by users repeatedly sending packets containing the same 837 sequence of bytes as is generated by the SONET/SDH frame-synchronous 838 scrambler. As it is improbable that a user would have a real need to 839 do this with the persistance that would be necessary to cause the 840 problem, the scrambler mechanism discussed here is in fact a defense 841 against users with a malicious intent to cause these problems. 843 The self-synchronous scramblers discussed here operate some number of 844 bits of state which are initialized when the scrambler is first 845 started. The scramblers may be initialized to any arbitrarily chosen 846 value with the same number of bits. The security of this scheme 847 cannot be guaranteed to be any better than the guessability of the 848 initial value to which the scrambler is set. To minimize the 849 guessability the value should be secret, and should be selected using 850 the same considerations of randomness as detailed in RFC 1750 [5]. 852 This paper asserts that the output of the self-synchronous scrambler 853 will always remain as unguessable as the value to which the scambler 854 was initialized, independent of the data which is scrambled and so 855 modifies the scrambler state. The authors can see no reason why this 856 would not be true, but the assertion probably should be checked by 857 someone more familiar with the evaluation of data security 858 mechanisms. 860 Self-synchronous scramblers do not prevent a user who is in a 861 position to wiretap the output of the scrambler, or the data on the 862 circuit which is transmitted in scrambled form, from attacking the 863 circuit using the knowledge of the scrambler state gained in this 864 fashion. If the security of the transmission infrastructure and the 865 data it is carrying cannot be guaranteed then some form of strong 866 encryption is probably necessary to avoid an attack by a user with 867 this type of access. 869 References 871 [1] J. Manchester, M. Krishnaswamy at al. ``PPP over SONET/SDH'', 872 , work in progress. 874 [2] W. Simpson. ``PPP over SONET/SDH'', RFC 1619, May 1994. 876 [3] W. Simpson, Editor. ``PPP in HDLC-like Framing'', RFC 1662, 877 July 1994. 879 [4] A. S. Tanenbaum. ``Computer Networks'', Prentice Hall, 1988. 881 [5] D. Eastlake, 3rd, S. Crocker & J. Schiller. ``Randomness 882 Recommendations for Security'', RFC 1750, December 1994. 884 Authors' Addresses 886 Dennis Ferguson 887 Email: dennis@juniper.net 888 Phone: +1 650 526 8004 890 Ravi Cherukuri 891 Email: ravi@juniper.net 892 Phone: +1 650 526 8082 894 Juniper Networks 895 385 Ravendale Drive 896 Mountain View, CA 94043 897 Fax: +1 650 526 8001