Killer Packet

I received several pieces of mail regarding my comments in a previous newsletter vol. 5 number 5, SONET data coding to the effect that, "...the DC balance of SONET can be terrible." Here's the best of the threads:

To fix the problem with a long stream of 1's or 0's requires scrambling the data prior to sending. This fixed many low frequency random errors and is quite simple to do. A relatively simple scrambler with a polynomial of X9 + X4 + 1 is adequate. This process removes dc components and provides a constant average signal power.

Thanks for your interest in High-Speed Digital Design.

While scrambling may make you feel better, and it looks great in a technical presentation, it does *nothing* to improve the worst case DC balance. If you are depending on scrambling to save the DC balance of your circuit then, in my opinion, you have made a big mistake. I'll cite for your amusement a quick story from the 100BASE-TX (Fast Ethernet) committee whose members *thought* that scrambling provided adequate DC balance. As the standard neared completion they were shocked to discover that someone could produce (on purpose) a "killer packet" whose data patterns would occasionally align with the scrambler polynomial, causing very long runs of 1's, sufficiently long to defeat the time constant of their AC-coupling capacitors and cause data errors. Within a period of a few days after the discovery of this error mechanism people all over the world were running the "killer packet" on their networks and discovering that it really did "kill" their networks. The competition gloated. Eventually, DC restoration circuits were incorporated into the receivers of some parts to avoid the problem.

In the original design of Sonet I seem to remember arguments that because the Sonet data stream would be a composite of thousands of independent, unsynchronized voice channels the probability of every seeing a "killer pattern" would be acceptably low. In a world that supports IP over Sonet that assumption has been blown out of the water, leaving Sonet systems highly susceptible to giant "killer packets". If you build a system for transporting packets that depends on nothing more than scrambling to enforce DC balance, it's a virtual certainty that someone will figure out how to make a "killer packet" to defeat it.

Best Regards,
Dr. Howard Johnson

I used to work on digital radios at Digital microwave and they use scrambler polynomials of x1+x15+x23 and the output is balanced quite nicely. The system I worked on was T1, E1 based. This scrambler combined with Reed-Solomon error correction made the system virtually error free and totally independent of input data patterns. Scramblers remove the DC component packetized or not.
Stay in touch.

I'm sure a scrambler worked fine in your application, but that doesn't mean it couldn't be made to fail.
Here's what I'm trying to convey:

All I need to do to defeat a 23-bit scrambler polynomial is create a killer data pattern that contains within it a sizeable chunk of the scrambler polynomial sequence (kind of like a virus that contains a bunch of your own DNA). If the killer chunk is perhaps 100 bits long AND IF IT LINES UP WITH THE SCRAMBLER SEQUENCE WHEN TRANSMITTED then when XOR'd with the scrambler it will create an output of 100 zeroes. Obviously, this can be extended ad infinitum to create strings of zeros with arbitrary length.

Once the killer-pattern has been discovered, if it is transmitted repeatedly the probability of it lining up with your scrambler just at the moment that tranmission starts equals 1 part in 2^^23, which is approximately one part in eight million. This probability is far, far different from the probability that you would get 100 bits is a row that *randomly* happened to cancel the scrambler (that would be more like 2^^100, a MUCH bigger number).

I don't know what data speeds you are used to working with, but on a modern data link at 10 Gb/s, the link carries about 10 million packets per second (at roughly 120 bytes each) which gives your killer packet, if transmitted continuously, 10 million chances per second to break the system. That means an error would happen once per second.

The consequences of a failure of DC balance are usually that the slicer gets a HUGE burst of errors, possibly causing the link to lose sync, and possibly requiring a re-acquisition of the bit timing, word timing, and frame sync (in other words, it induces a major glitch in a data transmission system).

In terms of statistical analysis, the killer packet has equal probabilities of either lining up perfectly with your scrambler, or lining up exactly out-of-phase (creating all 1's), so the property of AVERAGE DC balance is preserved, the only problem is the instantaneous DC balance just took a 100-bit-long ride to the moon.

For any given system there isn't just one killer packet. The number of possible killer packets is quite large. For example, a partially broken killer packet that generated 100 zeros with a few ones scattered throughout would have about the same average low-frequency content, causing basically the same problem. Also, there are a lot of distinct segments within the scrambler sequence with which one may attempt to line up. The result is that there are literally millions of specific sequences that, if transmitted repetitively, could break a scrambled system. From a marketing standpoint, such behavior seems unacceptable even if you believe that no-one would ever bother to transmit the scrambled data packets (that's what the Fast Ethernet committee thought until a competitor started mailing out disks to customers with the killer packet on it, and instructions on how to use it).

Systems which scramble the data first and then follow up with a data code that guarantees (by design) strict limits to DC balance remain immune to DC-wander problems. Coding first and then scrambling (as was done for FDDI, which Fast Ethernet then inherited) does not constrain the worst-case DC balance.

In your digital radio, perhaps you were aggregating many telephone channels with time-domain multiplexing (that is a typical use for many microwave repeater tower). In that situation there is no practical way for a malicious user to coordinate packets among the many separate channels in order to create DC-balance-killing event. In a high-speed data transmission link, the system sends one packet at a time that can be several thousand bytes long. That's plenty long enough for malicious exploitation.

Best Regards,
Dr. Howard Johnson