Home > Utility > Jam Resistant Communication Without a Shared Key

Jam Resistant Communication Without a Shared Key

BBC Decoding TreeSome US Air Force Academy (USAFA) and National Security Agency (NSA) smart guys (Baird, Bahn, and Collins – BBC) have come up with a way to achieve the kind of jam resistance that shared keys provide (like spread spectrum) but without the need for a shared key. For the crypto guys out there, this would be analogous to what the Diffie-Hellman key exchange brought to the world of symmetric cryptography. In fact one would probably use such a key exchange over BBC and then revert to traditional jam-resistant communication techniques, just as we do with asymmetric/symmetric crypto. Their ideas extend beyond jam resistance, but that’s what we’ll look at here.

Of course they explain it better than I in two papers and an applet I copied here:

Baird has over a dozen papers published on the subject on his website.

First let’s understand the kind of attack we’re fighting. To fight jamming, you want to make your enemy work so hard or expend so many resources that the jamming is ineffective when on or not cost effective to even turn on. We cannot pretend to achieve “jam proof.”

Radio jamming adds energy to the spectrum, so a successful jamming adds energy at the specific frequencies that we are trying to read or at the specific moments in time we want to read them. With spread spectrum communication, as one example, successful jamming would require energy to be poured into many, many frequencies on the hope that the particular frequencies specified in the shared key will be covered. This is expensive for a jammer.

Note that a jammer cannot remove energy from the spectrum. This is an additive process, and this will be important.

Encoding

To encode a message, we step through the message, hashing each successively-longer piece, and we use the hash value to “place” energy in the spectrum. (You can use a time-based pulse method as easily). We scale the hash function (like a modulus operator) to an appropriate width (not discussed here).

Say we’re passing the (ridiculously-short) four-bit message 1011. We’ll arbitrarily set our hash width to 50. The hash value  of 1, I’m making this up, is h(1) = 37. We continue through the message as well as some padding bits on the end which are analogous to a checksum.

h(1) = 37
h(10) = 8
h(101) = 44
h(1011) = 23
h(10110) = 9
h(101100) = 17

We now have an encoded message that will have peaks at the points 8, 9, 17, 23, 37, and 44. Again this could be frequencies, timed pulses, etc. depending on your radio setup.

A jammer comes along but doesn’t have the energy to jam everything, so he jams points 1-5, 20-29, and 40-49 (for ease of illustration) by turning those points “on.”

Decoding

The listening end cannot distinguish between the original message and the jamming and so receives “on” energy at the points 1-5, 8, 9, 17, 20-29, 37, and 40-49.

We know a message must start with either a zero or a one, so the receiver hashes zero and one to see if their values appear in the received “on” list.

h(1) = 37 ON THE LIST
h(0) = 11 NOT ON THE LIST

So far we know the message begins with a one. The second bit must be zero or one.

h(10) = 8 ON THE LIST
h(11) = 28 ON THE LIST

Hmm, both 10 and 11 may be valid messages. We’ll continue our tree (imagine a tree) and consider adding a zero and one to both 10 and 11. At the end of the four-bit message we know that we add two zeroes, so messages that end with ones can be discarded.

With appropriately chosen hash widths, message lengths, and padding, we’ve successfully decoded the message, despite the jamming, and we’ve discovered that we can actually have multiple valid messages overlapping (protection against a sort of “friendly” jamming).

Visualization Applet

  1. Type a short message in the Message box and hit Return.
  2. See the Decoded Message at the bottom.
  3. “Jam” the communication channel by drawing all over the message.
  4. See how you can cover up to half the message before the message is degraded.


Conclusion

This new concurrent coding can provide keyless jam resistance. The papers linked above discuss other uses such as for RFID tags and even document searching. Since this is government-developed technology (and it’s not classified), it is free for use. Go forth and build more secure radios!

Categories: Utility Tags: , , , ,
  1. December 14th, 2009 at 19:08 | #1

    This is brilliant! I’m slowly making my way through Schneier’s _Applied Cryptography_, so it’s cool to see what’s new in the crypto world.

    One thing that bothers me, though, is the problem of the “hallucinations,” which are basically false-positives. Even though a reasonably sized checksum would make it highly unlikely, it will always be possible that a hallucination is decoded and mistaken for the intended message. Still, the chances are so low that I’m sure it is an acceptable margin of error for 99% of the applications out there.

    Very cool.

  2. anonymous
    February 3rd, 2010 at 17:46 | #2

    All communications have some probability of error. Both through wires and wireless. You can never be 100% sure your message got through, no matter what algorithms you use. But with checksums etc., you can make the probability of undetected errors to be exponentially small. BBC avoids errors in exactly the same way.

    And all crypto has that same kind of probabilistic security (except the OTP). If you encrypt a message with AES-256, an attacker could randomly guess your key in a single try. But the probability of that happening is 2^-256. That’s astronomically low (for comparison, there are only 2^266 atoms in the visible universe). So it’s practically impossible to break AES-256 using that attack, for all practical purposes. BBC is the same.

  3. William L. Bahn
    May 19th, 2010 at 22:56 | #3

    As already noted, the probability of a hallucination making it thorugh the decoding process can be made arbitrarily small. For a packet with a 33% mark density and an encoding that specifies 32 checksum bits, the likelihood of a hallucination that exists at the end of the message bits is (1/3)^32 or 5.4e-16 (1 in 1853 trillion).

    What is not as obvious is that the chance of a message that survives the checksum bits containing any errors at all is even less, so the receiver can safely assume that all received messages are error free. In other words, messages are either received correctly, or not received at all. As a result, there is no point in adding any form of error detector or correction within a message, but for traffic consisting of multiple messages (as would almost always be the case) you can add additional messages that enable you to recover from some specified minimum number of lost messages.

  4. November 5th, 2014 at 08:26 | #4

    Moisture may freeze at the expansion valve, giving some of the indication of under charging.
    From this airport, guests are able to rent a car or, as a
    more inexpensive option, take a shuttle from the airport to the north entrance.
    The articles and segments written on its pages are written by fishing
    aficionados and specialists themselves.

  1. No trackbacks yet.