PPP Extensions Working Group Dennis Ferguson
INTERNET DRAFT Ravi Cherukuri
Expires May 1998 Juniper Networks
November 1997
Self-Synchronous Scramblers For PPP Over Sonet/SDH: Some Analysis
<draft-ferguson-pppsonet-selfsync-00.txt>
Status of this Memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''
To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited.
Abstract
The use of a self-synchronous scrambler to minimize the possibility
that a carefully chosen PPP over SONET/SDH payload can cause a long
sequence of zero bits to be transmitted is examined. It is pointed
out that, while self-synchronous scramblers have some attractive
properties for the application, the x^43 + 1 scrambler used by ATM
for the same purpose has some unfortunate interactions with the
16-bit CRC Frame Check Sequence which is the PPP default FCS. It is
suggested that adding a third term to the self-synchronous generator
polynomial might improve its behaviour, and that inverting the
scrambler bit ordering so it is applied to the data in the same bit
order as the PPP CRC FCS algorithms are defined for may eliminate any
remaining effect such scramblers have on either PPP FCS.
Ferguson & Cherukuri expires May 1998 [Page 1]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
Table of Contents
1. Overview .................................................... 2
2. The Problem ................................................. 3
2.1 SONET Hates Zeroes .......................................... 3
2.2 SONET/SDH Frame Scrambling and PPP .......................... 4
3. Self-Synchronous Scramblers ................................. 6
3.1 The ATM Self-Synchronous Scrambler .......................... 6
3.2 Using a Self-Synchronous Scrambler with PPP over SONET/SDH .. 9
3.3 Scrambler Impact on the 16-bit FCS .......................... 11
3.4 Scrambler Impact on the 32-bit FCS .......................... 14
4. Comparison with Other Possible Solutions .................... 15
5. Backwards Compatability ..................................... 18
1. Overview
The Internet Draft draft-ietf-pppext-pppsonet-scrambler-00.txt [1],
current at the time of writing, details a problem with the Point-to-
Point Protocol mapping to SONET/SDH specified in RFC 1619 [2] and
suggests a solution using a general purpose payload scrambler. This
document attempts to succinctly redescribe the (alleged) defect of
the RFC 1619 mapping and examines the strengths and weaknesses of the
use of self-synchronous scramblers as an alternative solution. The
intent of this draft is neither to assume a position with respect to
the specific actions that might be decided upon to address the
concern with RFC 1619, if any, nor to represent the authors as having
any particular expertise other than general knowledge of the
technology, but rather tries to convey information of a
non-controversial nature related to the problem, and a potential
approach to the solution, which it is hoped will clarify some of the
issues for those interested in the problem.
The use of a self-synchronous scrambler to minimize the possibility
that packets constructed by a malicious user will cause a long series
of zero bits to be transmitted on a SONET/SDH circuit is examined.
Self-synchronous scramblers are not ``general purpose'', in that
their use can exacerbate the effect of transmission errors on certain
types of payloads. On the other hand self-synchronous scramblers are
very secure, quite easy to implement, place no additional
implementation requirements on either the SONET/SDH framer or the
octet-synchronous HDLC framer, and would appear to be a good match
for the needs of PPP over SONET/SDH where only the interaction of the
scrambler with error detection in CRC-protected HDLC frames is of
Ferguson & Cherukuri expires May 1998 [Page 2]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
concern.
ATM deals with these same issues by employing a particular self-
synchronous scrambler to cell payload, using the x^43 + 1 polynomial.
This is given particular attention not only because of the
considerable implementation and deployment experience accrued from
its use in ATM networks but also because several recent PPP over
SONET/SDH products have made use of this. An unfortunate interaction
of the x^43 + 1 polynomial with the 16-bit CRC FCS optionally used
for PPP is noted, and it is shown that a three term self-synchronous
polynomial may eliminate any major effect on 16-bit CRC error
detection.
2. The Problem
2.1 SONET Hates Zeroes
The fundamental problem is that unhappy things can happen when a long
string of zeroes is transmitted on a SONET/SDH circuit. The most
serious of these is that a very long sequence of zero bits
transmitted on a SONET circuit (where ``very long'' is somewhere
between 2.3 and 100 microseconds, or between about 45 and 2000 bytes
of data at the STS-3c rate) is indistinguishable at the receiver from
a broken circuit. A sequence of this length may hence cause the
receiver to treat the incoming circuit as broken and to take whatever
actions it will in this situation.
Other more subtle difficulties can also be caused by shorter
sequences of zero bits. SONET/SDH receivers recover timing
information from the incoming data by filtering state transitions
through a phase-locked loop. The recovered timing information may be
used not only to clock in the data being received, but also as a
clock for the transmitter side of the same circuit as well as the
transmitters of other circuits terminating in the same piece of
equipment. Indeed, distribution of timing information throughout an
entire SONET/SDH network may be done via the circuit timing recovery
described above, so errors anywhere in the distribution tree might
effect a potentially some number of downstream nodes as well.
The problem that a lengthy sequence of zero bits causes here is that
the timing transitions that keep the PLL well synchronized only occur
when one bits are received; long sequences of zero bits are devoid of
timing information. A PLL which is receiving no input will begin to
drift at a rate related to the quality of the local clock source,
which will sometimes be inferior to the clock source steering the
received data. This lower quality time, if it is used to clock the
transmitters of other circuits, may in principle be propagated to
Ferguson & Cherukuri expires May 1998 [Page 3]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
other network nodes as well, causing a similar degradation of their
timing too. If the receiving clock drifts severely its ability to
decode even the incoming data stream from which it formerly obtaining
the timing may be compromised. While the issue of just how awful the
consequences of these shorter sequences might be is debatable, most
everyone will agree that nothing good can come of it. As for the
other somewhat controversial issue of how many zero bits in a row is
too many, 80 bits is often chosen since this approximately
corresponds to the number of zero bits which will cause many
commercial clock recovery circuits to transition from actively trying
to synchronize from the incoming data stream to ``holdover'' mode,
where they free-run on the local clock source steered by the most
recent error correction. Any reference to ``80 bits'' below should
be read as ``a relatively long sequence of zero bits'' since the
limits are relatively soft and implementation dependent.
2.2 SONET/SDH Frame Scrambling and PPP
The somewhat debatable issue of how many zero bits in a row is
``bad'', for some serious value of ``bad'', is reflected in the fact
that the SONET/SDH specifications do not attempt to completely avoid
the possibility that a long sequence of zeroes will be transmitted on
a SONET/SDH circuit (something that probably could only have been
achieved at the cost of additional overhead bandwidth), but instead
are satisfied with making the occurence of the event improbable
(which doesn't cost much of anything). Specifically it may be
observed that if only one particular n-bit sequence will do something
bad, and if all possible n-bit sequences are equally likely, then the
probability of something bad happening will be 1/2**n. If ``n'' is
80 or more the probability is pretty small indeed.
It is the case, however, that if the n-bit sequence which does bad
things is an n-bit sequence of zero bits the probable occurence of
this particular sequence in randomly selected real-life data probably
far exceeds 1/2**n. This issue is the (only) one which is addressed
in the SONET/SDH specifications by the use of a frame scrambler, to
effectively change the sequence of payload data which causes a series
of zeroes to be transmitted on the wire at the physical level from a
sequence of zeroes to some sequence whose occurence in a random
selection of real-life data is probably much closer to 1/2**n.
Understanding how this works requires a minimal understanding of how
SONET/SDH formats the data it is transmitting. SONET/SDH data is
transmitted in frames. A frame consists of 9 ``rows'', where each
row in a frame on an OC-N circuit consists of 3*N bytes of
SONET/SDH-defined frame overhead (or transport overhead, to be
consistant with SONET terminology) followed by 87*N bytes of payload
data. The payload data in each row sometimes includes other
Ferguson & Cherukuri expires May 1998 [Page 4]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
SONET/SDH-defined overhead, but sometimes just includes user data.
The SONET/SDH frame scrambler operates at the transmitter by
exclusive-or'ing the data sent in each SONET/SDH frame with the
output of a very simple pseudo-random number generator. The
generator is reinitialized to a well-known state at the start of each
frame (making this a ``frame-synchronous'' scrambler) and then the
output is applied to every byte in the frame except the transport
overhead in the first row of the frame. The receiver similarly
resets the generator to the well-known state at the beginning of each
frame, and then exclusive-or's the output into the appropriate
incoming bytes to recover the unscrambled data.
The pseudo-random number generator used is a 7-bit LFSR, which will
repetitively generate a sequence of 127 unique bytes (i.e. a 127 bit
sequence repeated eight times). Note well that the SONET/SDH frame
scrambler does not avoid the problem of zero transmission on a
SONET/SDH circuit, it just changes the payload data which can induce
the problem from a sequence of 0-valued bytes to a fixed sequence of
127 magic bytes which might be expected to occur relatively less
frequently in real life data. And for the multiplexed payloads
SONET/SDH was employed to carry early on, with user data derived from
many streams well mixed together along with lower speed framing
overhead, it is probably not a bad assumption that an 80-bit fragment
of the magic sequence matched in phase to the output of the LFSR
won't occur very often.
For PPP over SONET/SDH payloads, however, the contents of a datagram
transmitted across the circuit are laid out in consecutive payload
bytes of a concatentated SONET/SDH SPE edited only by the octet-
synchronous HDLC framer. Anyone who feels the urge to do so can send
packets filled with the magic 127 byte sequence, and while this
doesn't guarantee that the packet will cause a long sequence of
zeroes to be transmitted on any PPP over SONET/SDH circuit that the
packet transits, there is a probability of 1/127 that it will hit any
particular row in the SONET/SDH frame just right to synchronize with
the LFSR ouput. Reference [1] claims that one of every 21 1500 byte
datagrams carrying the sequence will probably cause a SONET/SDH
circuit difficulty, and I see no reason to doubt this.
Note that (if I've done the math right) the magic sequence does
include the two consecutive bytes <0x7d 0x0e>. Since a user can
neither transmit this sequence through an HDLC framer unscathed (the
0x7d byte will be escaped) nor cause the HDLC framer to generate this
output with any other packet contents, the longest run of zeroes that
a PPP over SONET/SDH packet payload can cause is 127 bytes. Since
127 bytes represents about 6.5 microseconds of transmission time on
an OC-3c circuit this is sufficient to possibly cause a loss of
signal condition there, and at any SONET/SDH rate far exceeds the 80
Ferguson & Cherukuri expires May 1998 [Page 5]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
bit times considered maximal if all possible clock synchonization
consequences are to be avoided.
Again, the authors do not have the expertise either to estimate the
seriousness of the described problem or to judge the validity of the
concerns about this expressed by both SONET/SDH equipment
manufacturers and network operators. The fact that such concern
exists at all, however, pragmatically represents an impediment to the
wide deployment and use of interoperable PPP over SONET/SDH, and this
by itself should be sufficient reason to search for an interoperable
solution.
3. Self-Synchronous Scramblers
3.1 The ATM Self-Synchronous Scrambler
ATM over SONET/SDH exhibits much the same behaviour as PPP over
SONET/SDH in that it inserts relatively long sequences of arbitrary
user data into consecutive bytes of SONET frame payload. ATM deals
with the possibility that someone might use knowledge of the magic
sequence to the detriment of a SONET/SDH circuit by applying yet
another scrambler to the payload of ATM cells. While this scrambler
is again intended only to make the occurence of a pattern which
causes long strings of zeroes to be transmitted on the circuit
improbable, rather than impossible, it differs from the SONET
frame-synchronous scrambler in that it does not generate a fixed
sequence of random numbers at all. It instead attempts to make the
magic sequence a constantly moving, and hard-to-guess, target so that
an informed attacker will have little better probability of hitting
the sequence than will random data.
The characteristics of self-synchronous scramblers in general are
best described starting from the details of a particular
implementation, and the ATM scrambler (called the x^43 + 1
self-synchronous scrambler from its polynomial representation) is of
particular interest since it there is considerable implementation and
deployment experience using it.
Schematically the transmitter side of the scrambler operates as
follows, on a bit-by-bit basis:
Ferguson & Cherukuri expires May 1998 [Page 6]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
Unscrambled Data
|
v
+-------------------------------------+ +---+
+->| --> 43 bit shift register --> |--->|xor|
| +-------------------------------------+ +---+
| |
+-----------------------------------------------+
|
v
Scrambled Data
The shift register is initialized once, at the start of operation,
and may be set to any random 43-bit value. Each bit of data
subsequently transmitted is exclusive-or'd with a bit shifted out of
the high order end of the register, and the result of this operation
is shifted back into the low order end of the register. The
scrambled data which is transmitted is essentially a copy of the
internal state of the scrambler.
The corresponding receiver schematic is shown following:
Scrambled Data
|
+-----------------------------------------------+
| |
| v
| +-------------------------------------+ +---+
+->| --> 43 bit shift register --> |--->|xor|
+-------------------------------------+ +---+
|
v
Unscrambled Data
The descrambler essentially operates by exclusive-or'ing each bit of
incoming scrambled data with the (scrambled) incoming data bit
received 43 bits previously. At startup the shift register may be
initialized with the first 43 bits of data which arrive, after which
it can begin unscrambling.
This scrambler, as with self-synchronous scramblers in general, has a
number of attractive properties. The state of the scrambler is
transmitted to the descrambler in the scrambled data stream itself,
avoiding the need for either restarting the scrambler periodically to
achieve synchronization between the transmitter and receiver (as the
SONET/SDH frame-synchronous scrambler does) or providing an
out-of-band channel for carrying synchronization information (as is
suggested in [1]). This independence from surrounding infrastructure
Ferguson & Cherukuri expires May 1998 [Page 7]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
allows a certain flexibility in implementation; for PPP over
SONET/SDH, for example, if the HDLC framer and SONET framer were
implemented on separate devices the scrambler could be implemented on
either device, or even a third device, without difficulty. The
scrambler is also easy to understand, which maximizes the probability
of interoperable implementations.
The security of this scrambler in making it hard to guess the
unscrambled input which would cause it to emit the magic sequence of
the frame-synchronous SONET scrambler at its output seems quite high.
Predicting the output of the scrambler for a given input requires
knowledge of the 43 bit state of the transmitter at the time
scrambling of the known input is begun. Assuming the attacker is not
in a position to wiretap the data on the circuit in scambled form (it
is assumed that an attacker in that position could think of much more
destructive things to do with the information than to cause zeroes to
be sent on the circuit) then predicting the state of the scrambler at
any point in time would appear to require knowledge of both the
initial 43 bit state of the scrambler when it was started and every
byte of data scrambled by the device since it was started. Even if
the attacker got his frame to the scrambler immediately after it was
initialized, the attacker would still have to have knowledge of the
value to which the scrambler was initialized, and this value may be
chosen at random by the transmitter. It hence appears that all
attacks reduce to guessing the state of a randomly chosen 43 bit
number, with a probability of 1/2**43 of guessing correctly and with
the additional probability of 1/127 that a correct guess will leave
the frame aligned in the SONET/SDH payload just right to cause an
extended sequence of zeroes to be transmitted. This seems pretty
secure.
While self-synchronous scramblers hence have some obvious strengths,
their use also comes with some drawbacks which need to be carefully
examined in the context of PPP over SONET/SDH. The first criticism
often leveled against self-synchronous scramblers is that they can
represent a performance problem, with design of very high performance
scramblers which need to process many bytes at a time becoming costly
since the feedback nature of the scrambler prevents effective
pipelining. This may indeed be true for ATM switches, where the cost
of processing cell payloads may be dominated by the cost of the
scrambler. For PPP over SONET/SDH, however, we also have the
implementation complexity of the octet-stuffing HDLC framer to bear,
and at speeds where byte-at-a-time processing is not an option
implementation of this HDLC framer becomes very complex indeed. It
is pretty much impossible to think of a situation where the
implementation complexity of a self-synchronous scrambler would even
come close to that of an HDLC framer, and it doesn't seem useful to
spend much effort optimizing a part of a PPP over SONET/SDH system
Ferguson & Cherukuri expires May 1998 [Page 8]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
which is unlikely in the extreme to be the part which represents a
barrier to the upward performance scalability of PPP over SONET/SDH.
The issue of scrambler performance is not persuasive in the context
of PPP over SONET/SDH.
The second, more serious, issue with self-synchronous scramblers is
the fact that they are error multiplying. Consideration of the
operation of the x^43 + 1 descrambler above shows that single bit
error in the scrambled data will result in two errors in the
unscrambled data, one error in the bit corresponding to the location
of the original error in the scrambled data and a second error 43
bits later. This fact probably makes self-synchronous scramblers
unsuitable for general-purpose use on some types of data payloads;
protocols which attempt to do error correction, or which perhaps use
some form of parity-based error detection, may find their performance
seriously impaired by error multiplication (though it might be noted
that ATM makes use of the x^43 + 1 scrambler despite the fact that
ATM is also sometimes represented as a general-purpose data
transport, a dichotomy which at least the first author finds slightly
odd).
This behaviour is less of a direct concern for PPP over SONET/SDH,
however. PPP over SONET/SDH attempts to, and is explicitly permitted
to, discard all frames where any transmission error at all has
occurred, it really doesn't matter much whether there are N bits of
the frame in error or 2*N. The error spreading does increase the
probability that a single error might damage two consecutive frames
instead of one (this happens without scrambling only if the error
occurs in the flag byte between frames), but this is unlikely to
significantly increase the overall errored frame rate on a circuit
given that most frames will be substantially longer than 43 bits.
The more serious potential problem caused by error multiplication for
PPP over SONET/SDH is that the errors produced by certain
self-synchronous scrambler polynomials, when applied in certain ways,
may interact badly with the CRC frame check sequences used by HDLC
such that the error detection power of the latter is reduced. This
dictates that careful consideration be given to the problem when
selecting a self-synchronous scrambler for use with PPP over
SONET/SDH. Some of these issues are addressed in a later section.
3.2 Using a Self-Synchronous Scrambler with PPP over SONET/SDH
The selection of a self-synchronous scrambler for use with PPP over
SONET/SDH is by itself insufficient to solve anything; agreement
about how the scrambler is employed is also a prerequisite for
interoperability. This section covers some of the issues related to
self-synchronous scrambler use which have occurred to the authors.
Ferguson & Cherukuri expires May 1998 [Page 9]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
For the purposes of discussion it will be assumed that a PPP over
SONET/SDH transmitter consists of a somewhat separable HDLC framer,
which takes PPP packets, computes and appends an FCS to them,
octet-stuffs the frame data for idle-flag transparency and generates
idle flags between frames, and SONET framer, which takes the stream
of bytes generated by the HDLC framer, surrounds them with the
appropriate SONET/SDH overhead and sends them on to the physical
layer. This gives a system block diagram which looks something like:
Transmitter
+----------+ +-----------+
(A) | HDLC |(B) | SONET/SDH |
---->| framer |--->| framer | - - - -
| | | |
+----------+ +-----------+
+-----------+ +----------+
| SONET/SDH |(B) | HDLC |(A)
- - - - | deframer |--->| deframer |--->
| | | |
+-----------+ +----------+
Receiver
To maximize the probability that the scrambler might be easily
retrofitted to existing equipment, and to ease the construction of
dual-mode equipment where use of the scrambler is a configuration
option to allow backward compatability, it seems prudent to leave the
operation of both the HDLC and the SONET/SDH framers unchanged by the
scrambler insertion. If this constraint is to be met it appears that
there are only two places where the scrambler could be applied,
marked (A) and (B) in the above diagram.
Placing the scrambler at (A), in effect scrambling the contents of
PPP packets prior to HDLC FCS insertion and flag escaping, has the
happy property of avoiding having to think about the scrambler's
effect on CRC error detection since the CRC would be checked at the
receiver prior to the error-multiplying descrambling operation. The
scheme appears to have a fatal flaw, however. Since the scrambler
only operates on packet data the receiver descrambler must receive 43
bits of packet data to reach synchronization with the transmitter.
This packet, received when the receiver was unsynchronized, must of
course be discarded since the receiver would have no way to
descramble the first 43 bits. While this might be acceptable, a
problem occurs should the receiver be out of synchronization with the
transmitter (perhaps because of an error at the end of the previous
packet) but be unaware of this. In this case the receiver will
mangle the first bits of the packet, but the error will be undetected
since the CRC has already been checked. Placement of the scrambler
Ferguson & Cherukuri expires May 1998 [Page 10]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
at (A) would hence appear to violate the end-to-endness of the HDLC
FCS error detection.
This leaves placement of the scrambler at (B), that is scrambling the
CRC'd, octet-stuffed, flag-delineated output of the HDLC framer.
Since the HDLC framer transmits constantly (it inserts a stream of
idle flags between frames) the receiver is assured a constant stream
of scrambled information on which to synchronize. Since the frame
FCS is computed before scrambling and checked after descrambling, the
FCS is useful for detecting and protecting against synchronization
errors as well as transmission errors. Since the scrambler is
operating on what is in effect a byte stream at this stage it needn't
have any sensitivity to frame boundaries (e.g. it needn't implement
the packet discard behaviour described for (A) when out of sync).
Implementing a configurable bypass for the scrambler to achieve
backward compatability with RFC 1619 should also be straight forward.
The remainder of this document hence presumes the self-synchronous
scrambler would be introduced between the SONET/SDH and HDLC
(de)framers.
Given the placement of the scrambler in the system, there still
remains a second issue with the application of a self-synchronous
scrambler which must be addressed. While the scrambler operates on a
byte stream (or a multi-byte stream at higher speeds) in
implementation, the scrambler is defined in terms of bit-by-bit
operation. This means there is a choice concerning the order in
which bits from each byte are presented to the scrambler; the
scrambler may scramble each byte starting at the high order bit and
working towards the low order bit, or it may scramble each byte
starting at the low order bit and working towards the high order bit.
And if the scrambler polynomial has terms whose exponents are not an
even multiple of 8 (e.g. 43) the two implementation choices will
produce different, non-interoperable results.
For ATM the x^43 + 1 self-synchronous scrambler is applied
big-bit-first, as this matches SONET/SDH's on-the-wire transmission
order. For PPP over SONET/SDH there is an additional consideration
relating to bit order, however, that being that CRC's used by PPP's
HDLC framing are computed as if the packet was being transmitted in
little-bit-first order. The scrambler bit order may thus be chosen
to match the on-the-wire transmission order, or the CRC computation
order, with different results. The bit order of scrambler hence
needs to be specified to avoid ambiguity. It also turns out that the
choice of bit order has some impact on the damage the scrambler
causes to CRC error detection such that making the bit order of
scrambler application match the CRC computation order may be a better
choice.
Ferguson & Cherukuri expires May 1998 [Page 11]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
3.3 Scrambler Impact on the 16-bit FCS
The only major defect related to the use of self-synchronous
scramblers with PPP over SONET/SDH that has been identified is the
damaging effect that error multiplication might, or might not, have
on the CRC error detection used by PPP over SONET/SDH. This section
attempts to examine the effect on the 16-bit CRC FCS in particular.
While RFC 1619 does recommend the use of the 32-bit FCS for PPP over
SONET, there still remain reasons why minimizing the impact of any
scrambling solution on the 16-bit CRC is important. In particular,
(a) the 16-bit CRC is inherently significantly weaker than the 32-bit
CRC, so any further weakening of the former is more likely to have
greater practical consequences than the latter, (b) the 16-bit FCS is
required for use on PPP LCP frames, (c) there are existing PPP over
SONET implementations which only implement the 16-bit FCS, and (d)
some may find the slightly reduced per-frame overhead of the 16-bit
FCS a reasonable tradeoff given the expectation of very low error
rates on SONET/SDH circuits.
To characterize the performance of a CRC error-detection code it is
necessary to define the term ``burst error''. In an errored frame
the number of bits between the first bit in the frame which is in
error and the last bit which is in error, inclusive, independent of
the state of the bits in between, is the length of the burst error in
that frame. There are two properties of a 16-bit CRC which
particularly define its strength. The first is that a 16-bit CRC
will detect all burst errors in a frame whose length is less than or
equal to 16. The second is that if all errors are equally probable
then the 16-bit CRC will detect burst errors with length greater than
16 with a probability of failure of 1/2**16. The issue with
scramblers, then, is that they turn an n-bit burst error on the wire
into an (n+43)-bit burst error at the HDLC framer (more or less, the
reversed view of bit ordering between SONET/SDH on-the-wire
tranmission and the CRC FCS definition, along with the bit order
chosen for the scrambler, all have an impact on how the on-the-wire
error looks by the time it gets to the HDLC framer). While this does
not necessarily weaken the CRC, since the error multiplication is
strictly correlated with the original on-the-wire error, it requires
some consideration to determine exactly what happens to the CRC
strength.
It turns out that the ATM x^43 + 1 scrambler would be a particularly
unfortunate choice for use with the HDLC 16-bit FCS. First,
exclusive-or'ing the two byte sequence <01 37> into any two
consecutive bytes of a correctly CRC'd message, after scrambling with
the x^43 + 1 scrambler in big-bit-first order, will cause an error
which will go undetected by the FCS check after descrambling.
Similarly, <0f f8> will cause the same problem when the scrambler is
Ferguson & Cherukuri expires May 1998 [Page 12]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
run in little-bit-first order (numbers included in hopes that someone
will check the math). As these are 9-bit burst errors, the x^43 + 1
scambler has effectively reduced the burst error detection length
from 16 to 8. Note that running the scrambler in big-bit-first order
is in fact slightly worse as it also causes some 14-bit (<02 41 d0>,
<03 76 d0>), 15-bit (<08 8a a0>, <09 bd a0>) and 16-bit burst errors
to also escape detection.
At least as bad is the effect of the x^43 + 1 scrambler on 16-bit CRC
detection of long bursts. While the 16-bit CRC will detect random
long burst errors with a probability of failure of 1/2**16, this
probability is a composite of the probability of detecting burst
errors with an odd number of bits in error, which the 16-bit CRC can
always detect, and burst errors with an even number of bits in error,
which the 16-bit CRC can detect with a probability of 1/2**15 of
getting it wrong (Tanenbaum [4], pages 211-212, provides a
particularly readable description of this). Note, however, that the
effect of the x^43 + 1 descrambler is to double the number of bits
which are in error in the unscrambled frame, i.e. a single bit error
in the scrambled frame becomes 2 errored bits in the unscrambled
frame, 2 becomes 4, 3 becomes 6 and so on. In effect the x^43 + 1
scrambler ensures that all errors in the unscrambled frame have an
even number of errored bits, which increases the probability of
detection failure from 1/2**16 to 1/2**15.
The ATM x^43 + 1 scrambler hence interacts badly with the 16-bit CRC
polynomial used by PPP, reducing its already relatively weak error
detection power. It should be noted, however, that the interaction
is a property of this particular choice of self-synchronous scrambler
rather than a defect of self-synchronous scramblers in general, since
it is clear that adding a third term to the self-synchronous
scrambler polynomial (i.e. multiplying the number of error bits by 3
rather than 2) should produce dramatically different results.
As an alternative the authors investigated a three-tap
self-synchronous scrambler with the polynomial representation x^43 +
x^23 + 1 (with the 23 being chosen arbitrarily, partly because it
doesn't significantly complicate a byte-by-byte scrambler
implementation, but otherwise on the sole basis that it is as weird a
number as 43). Schematically this yields a scrambler whose
transmitter operates as follows:
Ferguson & Cherukuri expires May 1998 [Page 13]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
Unscrambled Data
|
v
+-------------+ +---+ +---------------+ +---+
+->|-> 20 bits ->|-->|xor|-->|-> 23 bits ->|--->|xor|
| +-------------+ +---+ +---------------+ +---+
| ^ |
| | |
+----------------------+----------------------------+
|
v
Scrambled Data
This appears to have pretty much identical properties with respect to
initialization and security as the x^43 + 1 scrambler. Its
implementation complexity is probably increased somewhat, certainly
when scrambling multiple bytes at a time, though it is still very
simple compared to an HDLC framer.
The corresponding receiver schematic is shown following:
Scrambled Data
|
+----------------------+----------------------------+
| | |
| v v
| +-------------+ +---+ +---------------+ +---+
+->|-> 20 bits ->|-->|xor|-->|-> 23 bits ->|--->|xor|
+-------------+ +---+ +---------------+ +---+
|
v
Unscrambled Data
It turns out (making the somewhat dangerous assumption that the
authors have managed to do the computation without errors) that not
only does this restore the 1/2**16 probability of failing to detect
long burst errors, but it also restores the minimum burst length
detection of the 16-bit CRC to 16 when the scrambler is applied in
little-bit-first order (in big-bit-first order an undetected 15 bit
burst <08 0b 60> as well as a 16 bit burst <84 a3> can still occur).
In summary, while the x^43 + 1 self-synchronous scrambler in
particular is probably not a good match for the characteristics of
PPP over SONET/SDH a more carefully chosen scrambler, such as the
x^43 + x^23 + 1 scrambler suggested above when applied in
little-bit-first order, may be almost neutral in its impact on 16-bit
CRC error detection.
Ferguson & Cherukuri expires May 1998 [Page 14]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
3.4 Scrambler Impact on the 32-bit FCS
Given the inherent strength of the 32-bit PPP FCS compared to the
16-bit FCS, the impact of an error-multiplying scrambler on the
longer CRC is less of a concern. Some observations are
never-the-less included here for completeness.
Of primary interest is the fact that the error detection properties
of the 32-bit CRC polynomial used by PPP, which is also used for ATM
AAL5 frame protection except that the latter applies the polynomial
in big-bit-first order to match the transmission order, do not change
for long burst errors whether the number of bits in error is odd or
even. For long bursts neither the x^43 + 1 nor the x^43 + x^23 + 1
scrambler lessen the probability of not detecting an error compared
to unscrambled performance, that probability remains at 1/2**32 in
all cases.
For short bursts it should be noted that even without scrambling the
32-bit CRC fails to detect some error bursts which are less than or
equal to 32 bits in length. For example the 31-bit bursts <0a 1e e9
d5 e0> and <05 8f f4 6a 70> will go undetected. This appears to be
an artifact of the difference between SONET's actual transmission bit
ordering (i.e. big-bit-first) and the inverted bit ordering used in
the definition of the PPP 32-bit FCS. The errors noted above would
be 38 or 39 bits long if the transmission order actually matched the
definition from which the FCS is computed (this probably represents a
minor defect in RFC 1619 as well; it would have been better to have
made the FCS match the bit order of transmission, either by changing
the FCS definition used here from that in RFC 1662 [3] or by
specifying that PPP over SONET/SDH transmit payload bytes in
little-bit-first order).
Given this, the short burst detection capability is reduced still
further by both the x^43 + 1 scrambler (e.g. failure to detect the
28-bit burst error <02 ea 58 a0 40>) and the x^43 + x^23 + 1
scrambler (e.g. failure to detect the 24-bit burst error <11 f6 ca
e0>) when the scramblers are run over the data in big-bit-first
order. When run in little-bit-first order to match the CRC, on the
other hand, the presence of the scramblers has no effect on error
detection at all; the only errors which escape detection with either
scrambler in use are identically those which would escape detection
if the scrambler were not in use. Thus, with the proper choice of
bit ordering, it would appear that the use of either of these two
self-synchronous scramblers may have no effect on the 32-bit CRC FCS
error detection.
Ferguson & Cherukuri expires May 1998 [Page 15]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
4. Comparison with Other Possible Solutions
The authors are aware of two other suggested approaches to solve the
PPP over SONET/SDH magic sequence problem. This section attempts to
compare and contrast them with the use of a self-synchronous
scrambler as detailed here.
The first of these proposals is to deal with the problem in the HDLC
framer. The HDLC framer is free to insert frame escape characters at
arbitrary places in the frame, and if applied properly this could be
used to break up the magic sequence whenever it occured in a frame by
inserting an escape.
This technique has the very attractive property of being fully
backward compatable with nodes implementing the RFC 1619 procedures,
and has the merit of potentially providing ``perfect'' protection
against the sequence rather than the probable protection provided by
any sort of scrambler. The drawback appears to be one of
implementation complexity, particularly if one assumes the task of
getting it ``perfect'' should be to avoid any sequence of zeroes
longer than 80 bits from being transmitted. This could be done with
little additional complexity by unconditionally escaping every eighth
byte in the frame, for example, but the cost in terms of framing
overhead is really, really unacceptable. A more efficient approach
might be to detect 80-bit fragments of the sequence in the packet
being framed and inserting an escape only when these are detected,
but this leaves open the issue of exactly how one would go about
reliably detecting any 10 byte fragment from a 127 byte sequence, and
would still result in escapes being inserted 127 times more
frequently than necessary given the probability that such a sequence
would actually be aligned in the SONET/SDH frame just right to do
damage. The most efficient and implementable way this might be
accomplished would hence be to monitor the output of the SONET/SDH
frame scrambler for zeroes directly, taking action in the HDLC framer
only when a sufficiently long string of zeroes was actually detected
at the output. This might be workable, but only at the cost of
architecting in a strong connection between that SONET/SDH framer and
the HDLC framer which might preclude some otherwise very reasonable
implementation strategies which kept these two relatively separate.
In general, however, the least attractive aspect of this approach is
that no matter how it is done the net effect is to add complexity to
the HDLC framer, which is already the most complex and least scalable
component of a high-speed PPP over SONET/SDH implementation. In
comparison, scrambling approaches to the problem leave the HDLC
framer entirely alone, and while they might come with their own set
of complexities their application is less likely to present further
constraints to the upward performance scalability of PPP over
Ferguson & Cherukuri expires May 1998 [Page 16]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
SONET/SDH.
The second method, suggested in [1], is to use a conventional
pseudo-random number generator to scramble the output. The LFSR is
40 bits wide, hence producing a sequence of 2**40 - 1 bytes before
repeating, and is run continuously rather than being periodically
resynchronized, so given random initialization it should be about as
hard to guess the phase of the scrambler as it is to guess the state
of the self-synchronous scramblers described here. The scrambler is
applied to the output of the HDLC framer, as discussed above, before
the data is inserted into the SONET/SDH payload envelope. The
primary advantages of this method are that the scrambler is
non-error-multiplying, and hence would avoid causing damage to
sensitive payloads, and that very high performance implementations of
the scrambler itself would probably be slightly more straight forward
than a self-synchronous scrambler.
The complexity of this scheme arises from the issue of how one gets
the 5 bytes of state in the receiving scrambler synchronized with the
sender. Since there is no way to recover the state from the payload
itself the state must be transmitted to the receiver out-of-band; the
authors choose three bytes in the SONET/SDH Path Overhead (sent once
per SONET frame) to do this. Of course, since three bytes is
insufficient to carry the full 5 bytes of state along with the CRC
which is necessary to detect errors in the state, it requires three
frames to transmit the 5 bytes of scrambler state, the CRC and the
sequence numbers necessary to make sure the state information
collected from the three consecutive frames are indeed chunks of the
same 5 bytes. Since the transmitter must hence begin sending the
scrambler state several frames ahead of the time when the receiver
will be able to use it, the transmitter must have knowledge of not
only its current state but also what that state will be several
frames into the future. Starting from scratch will take the receiver
up to 5 frame times, or 600 microseconds (independent of the speed of
the SONET/SDH circuit) to synchronize, assuming no errors, and should
the receiver fall out of synchronization without knowing it will take
as many as five frames to tell for sure that it has been generating
crap. This synchronization scheme obviously necessitates the
scrambler being relatively intimate with the SONET/SDH framer, unlike
self-synchronous scramblers which may be placed anywhere where they
have access to the stream of deframed payload bytes, a requirement
which may preclude some otherwise reasonable implementation
strategies, and in comparison to a self-synchronous scrambler the
above is exceedingly slow and complex to synchronize.
The primary advantage of this scrambler over self-synchronous
scramblers, and perhaps the compelling advantage if the
characteristics of the payload being scrambled are indeterminate, is
Ferguson & Cherukuri expires May 1998 [Page 17]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
that it avoids error-multiplication and any side-effects that might
cause in the descrambled payload. The issue with respect to PPP over
SONET/SDH seems to be that this scrambler is solving a problem PPP
over SONET/SDH doesn't have. The characteristcs of the PPP over
SONET/SDH payload are very well known, and it appears that a
carefully chosen self-synchronous scrambler may be used for this
particular payload with little, if any, harm to the PPP payload at
all. This makes the synchronization complexity of the scheme, and
the constraints it places on implementations, gratituous for this
application and a possible impediment to interoperability, even
though it might make a fine choice for more general-purpose
applications.
5. Backwards Compatability
The disadvantage of the employment of a scrambler to solve the
SONET/SDH magic sequence problem is that equipment using the
scrambler will be incompatable with equipment implementing RFC 1619
alone. That is, the byte stream generated by the scrambler will
appear as random line noise to the RFC 1619 node, and vice versa.
Such a low level, complete incompatability between ends of a circuit
does not seem amenable to PPP LCP negotiation procedures either; any
automatic negotiation of the state of the circuit needs to be
implemented at a lower level.
Because of this, it is likely better that interoperability between
scrambled and RFC 1619 nodes be implemented at the SONET/SDH layer
instead. RFC 1619 PPP over SONET/SDH identifies itself using a Path
Signal Label (C2 byte) of 207 decimal. Obtaining a new Path Signal
Label value for use with scrambled PPP payloads, requiring that new
implementations provide both the scrambler and RFC 1619 compatability
as configuration options, and then using the Path Signal Label to
detect and correct mismatches in the configuration and/or capability
of each end of the circuit, should provide sufficient mechanism to
achieve interoperability with existing equipment.
Security Considerations
The scramblers discussed here are intended to provide protection for
SONET/SDH circuits from loss of clock problems which could otherwise
be caused by users repeatedly sending packets containing the same
sequence of bytes as is generated by the SONET/SDH frame-synchronous
scrambler. As it is improbable that a user would have a real need to
do this with the persistance that would be necessary to cause the
problem, the scrambler mechanism discussed here is in fact a defense
Ferguson & Cherukuri expires May 1998 [Page 18]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
against users with a malicious intent to cause these problems.
The self-synchronous scramblers discussed here operate some number of
bits of state which are initialized when the scrambler is first
started. The scramblers may be initialized to any arbitrarily chosen
value with the same number of bits. The security of this scheme
cannot be guaranteed to be any better than the guessability of the
initial value to which the scrambler is set. To minimize the
guessability the value should be secret, and should be selected using
the same considerations of randomness as detailed in RFC 1750 [5].
This paper asserts that the output of the self-synchronous scrambler
will always remain as unguessable as the value to which the scambler
was initialized, independent of the data which is scrambled and so
modifies the scrambler state. The authors can see no reason why this
would not be true, but the assertion probably should be checked by
someone more familiar with the evaluation of data security
mechanisms.
Self-synchronous scramblers do not prevent a user who is in a
position to wiretap the output of the scrambler, or the data on the
circuit which is transmitted in scrambled form, from attacking the
circuit using the knowledge of the scrambler state gained in this
fashion. If the security of the transmission infrastructure and the
data it is carrying cannot be guaranteed then some form of strong
encryption is probably necessary to avoid an attack by a user with
this type of access.
References
[1] J. Manchester, M. Krishnaswamy at al. ``PPP over SONET/SDH'',
<draft-ietf-pppext-pppsonet-scrambler-00.txt>, work in progress.
[2] W. Simpson. ``PPP over SONET/SDH'', RFC 1619, May 1994.
[3] W. Simpson, Editor. ``PPP in HDLC-like Framing'', RFC 1662,
July 1994.
[4] A. S. Tanenbaum. ``Computer Networks'', Prentice Hall, 1988.
[5] D. Eastlake, 3rd, S. Crocker & J. Schiller. ``Randomness
Recommendations for Security'', RFC 1750, December 1994.
Ferguson & Cherukuri expires May 1998 [Page 19]
INTERNET DRAFT Self-Synchronous Scramblers November 1997
Authors' Addresses
Dennis Ferguson
Email: dennis@juniper.net
Phone: +1 650 526 8004
Ravi Cherukuri
Email: ravi@juniper.net
Phone: +1 650 526 8082
Juniper Networks
385 Ravendale Drive
Mountain View, CA 94043
Fax: +1 650 526 8001
Ferguson & Cherukuri expires May 1998 [Page 20]