Jam Resistant Communication Without a Shared Key
Some 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:
- Jam-Resistant Communication Without Shared Secrets Through the Use of Concurrent Codes, Baird, Bahn, Collins.
- Visually Understanding Jam Resistant Communication, Schweitzer, Baird, Bahn
- Visualization Applet further down this page
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.
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.”
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).
- Type a short message in the Message box and hit Return.
- See the Decoded Message at the bottom.
- “Jam” the communication channel by drawing all over the message.
- See how you can cover up to half the message before the message is degraded.
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!