Spread Spectrum Techniques

I had no idea how WiFi works and ...

>And you find that unusual?
Pay attention.

Suppose we want to broadcast an FM radio signal so everybody can hear it.
Then we'd apply for a license to broadcast our news, weather & sports at, say 95.3 MHz.
Everybody in the neighbourhood could tune to that station and hear it.
Aah, but suppose we did NOT want everybody to hear it ... just a special few.

We might be transmitting secret data or trade secrets or ...

>Okay, I get it.
Then we could transmit for a fraction of a second at 95.3 MHz then continue at 95.7 MHz then continue at 95.1 MHz then ...

>So you keep changing the frequency, right?
Exactly! And those who knew the sequence of frequencies would have receivers that changed their tuning appropriately.
Everybody else would get garbage. Neat, eh?

>You should patent the idea. The army would love it. They'd use it for ...
Too late.
Such a frequency-hopping scheme was patented in 1942.
After the patent expired, the U.S. navy used the scheme in 1962 (during the blockade of Cuba) and, since then ...
>Wait! On the patent I see a co-inventor is called Hedy Kiesler Markey. Is that a girl?
Uh ... yes, that was her married name at the time -- but you might better recognize her as Hedy Lamarr.      

>You're kidding, right?
Would I kid you?

Okay, so this frequency hopping technique is known as frequency-hopping spread spectrum (or FHSS).
The "frequency-hopping" you understand, right?
The "spread spectrum" part is due to the fact that the frequency (95.3 MHz in the above example) is spread out to include a range of frequencies.

>So that's WiFi?
No. We're talking about the historical evolution of "spread spectrum" techniques.
WiFi uses what's called direct-sequence spread spectrum (or DSSS).
I should point out that WiFi doesn't stand for anything. Especially, it doesn't stand for "Wireless Fidelity".
WiFi is governed by the WiFi Alliance and the name was the brainchild of a company that invents names !!
In fact, Wi-Fi and the Ying Yang style logo were invented by Interbrand (who also created the names Prozac, Compaq and Celebrex).
Interbrand also submitted the alternate names Skybridge, Torchlight, and Flyover ... but WiFi was selected.    
I understand that the first choice was Trapeze, but perhaps the Ying Yang logo won for the name WiFi.

>I think that's better than a name like IEEE 802.11, eh?
I think so. Can you imagine saying "IEEE 802.11 encryption keys" or even "Trapeze-enabled device"?

However, before we go too far, let's remember that, today, everything is digital so we should explain how to scramble and unscramble digital signals.

Digital Scrambling

Suppose we have a digital signal - a sequence of 1s and 0s, like so:     11010011101
We introduce a "scrambling key", like so:11100010010
We "multiply" the two together, digit-by-digit, and get:00110001111

>Multiply them together?
Uh ... well, it's actually called Exclusive OR (XOR).
The result of "multiplying" two identical digits is a 0. The result of multiplying two different digits is a 1.
See how it goes? If we denote that XOR ritual as , we'd have:
1 1 = 0     and     0 0 = 0
0 1 = 1     and     1 0 = 1

To see this ritual in action, you can click here.

>Okay, so somebody gets that 00110001111. How does she regain the unscrambled signal?
Aah ... you mean the 11010011101.
Simple! She just does the digit-by-digit XOR with the same scrambling key, namely 11100010010.

That'd go like so:
The scrambled signal received is this guy:     00110001111
We use the same "scrambling key", namely:11100010010
We XOR the two together, digit-by-digit, and get:11010011101
So, if we both know the scrambling key, then you can unscramble my messages ... but nobody else can.

>But they can try various combinations of 1s and 0s until they get it right. After all, there aren't many digits in that key.
One of the first scrambling keys was a sequence of 40 1s and 0s called WEP-40.   (WEP stands for Wired Equivalent Privacy.)
To make it harder to unscramble, they now use 128-bit (or even 256-bit) encryption keys.

>Encryption key?
Yes, that's what it's called. I just said "scrambling key" for the fun of it.

Encryption keys might be a sequence of digits (0 - 9) and letters (A - F). That's 16 possible characters. Such a key might look like 98D9DE3ABCD5224F.
Each of these 16 characters can be represented by 4 binary digits: 0000 to 1111. That's 16 possible combinations of 1s and 0s.
A sequence of 64 such 4-bit combinations would be a 256-bit sequence. That'd give a 256-bit encryption key denoted by (for example): 98D9DE3ABCD5224F.
In other words, the 16 characters (like 98D9DE3ABCD5224F) would be 256 bits long ... in binary.

In 2007, Erik Tews (a researcher in the computer science department at Darmstadt University of Technology in Germany) cracked the WEP encryption in 60 seconds.

However, a safer encryption is WPA (which stands for Wi-Fi Protected Access).
With WEP, the encryption key don't hardly change. With WPA, the encryption key is changed every so often. That's Temporary Key Integrity Protocol (TKIP).

In practice, one can generate encryption keys from a sequence of random numbers.
Many such random number generators begin with a so-called "random seed", then generate "random" numbers beginning with this seed.
If you know the seed (and the prescription for generating the numbers), then you can generate the same sequence of "random" numbers.
SO - I need only give you the seed (and the prescription for generating the numbers) and you can know the sequence of encryption keys and are able to decrypt my messages.

>Huh? A random number generator?
Actually, since they're completely determined by that "seed", they aren't truly random -- they're "pseudo-random" numbers (PRN).
The first such pseudo-random number generator was the mid-square generator (originally suggested by von Neumann).
You start with an N-digit number (that's the "seed") then square it and select the middle N digits.
That's your next pseudo-random number. Then you ...

>Then you repeat ... again and again, right?
You got it.

Alas, even WPA isn't perfect. It can be cracked !
Guess who cracked WPA in 2008 - in about 15 minutes.

>Erik Tews!
Yeah, that's the guy.

>Is there yet another encryption method? One that's got more security?
There's WPA2 which is more sophisticated.

Note that, in encryption schemes, a sequence of digits passes through some magic transformation T to get the encrypted sequence.
When the encrypted sequence is received, the "inverse" of that magic transformation is applied to the encrypted signal to recover the original signal.

Sexier schemes could apply several magical transformations:

At the receiving end, the inverses of these transformations are applied in reverse order to recover the original signal.
>But ain't a bunch of magic transformations the same as one HUGE transformation?
Yes, but they can be quite different.
In the diagram above, T1 might be some encrytion-key encoding and T2 might be shifting digits and T3 might be ...

>T3 might be filling the zeros with peanut butter and T4 might be jam and ...

I (vaguely) recall schemes which are called public key cryptosystems. I think they use two keys -- one secret and one "public".

In fact, I remember Ron Mullin and Scott Vanstone working on these guys while I was at the University of Waterloo.

>Public key cryptosystems? How do they work?
I have no idea. However, I recall Scott describing some software that he wanted me to write ... so I did.

>And what was the purpose of the software?
I have no idea.

Barker Codes and Autocorrelation
In DSSS, Direct Sequence Spread Spectrum, things get a mite complicated.
Suppose the original signal has a sequence of digits 1 0 1 1 as in Figure 1a.
Part of the WiFi ritual involves "modulating" each digit of this signal with, say, the sequence 10110111000.  

This modulation results in the modified signal as shown in Figure 1b.
Note that the amplitude of each digit has the latter 11-digit sequence superimposed.

>Except that the original 0 digit has a different sequence superimposed.
Uh ... yes. It has the complement, namely: 01001000111.
It's like sending 10110111000 instead of a 1   and 01001000111 in place of a 0.

Note: If the original signal has a bit rate of 1 Mega bit per second (Mbps), this high frequency superposition will result in a signal with a bit rate of 11 Mbps.

>So that widens the frequency range covered, right?
Yes, and that's ...
>Don't tell me! It's "spectrum spreading".

Figure 1a

Figure 1b

>And that 11-digit modulating thing ... that's picked out of thin air?
Not exactly. That 11-digit spreading sequence is a Barker Code.

>Huh? Spreading sequence? Barker code?
That particular sequence of 1s and 0s, the Barker Code, is also called a "Chipping Sequence".
>Because the original signal looks "chipped" ... as in Fig. 1b?
Who knows? Note, however, that the actual information (in the above example) is contained in the 1 0 1 1, as in Figure 1a.
The addition of the chipping sequence introduces what could be considered "noise". It contains no information. Indeed, after decryption, it's gone!
The purpose of the Barker Code is to detect and correct errors in transmission and synchronizing transmitter and receiver. It has nothing to do "scrambling" the original signal.
The scrambling (or encryption) is done with that sequence of pseudo-randomly selected encryption keys. Remember?

>No... and by the way, what's this synchronization stuff?
In order to "despread" the encoded signal, the receiver has a "synchronized" replica of the "pseudo-noise" (or PN) Barker Code.
In fact, to the "stupid" receiver (not up to snuff in the details of WPA WiFi), the signal would appear to be noise.
Note that, once an encrypted and frequency-spread signal is generated, it's stuck onto a high frequency signal of (about) 2.4 GHz ... then sent to an antenna and transmitted.

In fact, there are 14 frequency bands in the neighbourhood of 2.4 GHz, each covering 22 MHz.    
Yet, the total range of frequencies allocated to WiFi is only 84.5 MHz ... so most of them overlap!
Only 3 channels do NOT overlap.

In Canada and the U.S., only channels 1 to 11 are available for WiFi use.

>Have you noticed that 22 MHz is twice the 11 Mbps?
I noticed that, too. The frequency range for each channel is ±11 Mhz from the centre frequency.

>So what's so special about that Barker Code?
Barker codes have magic properties ... and there aren't many of them.
If you calculate the Maximum Autocorrelation for all 11-digit codes, the Barker Code has the smallest, namely Max. Autocorrelation = 1.

Before I talk about autocorrelation, play with this spreadsheet to see if you can find a "better" code ... with smaller Max. Autocorrelation:
Just click on the picture to download the spreadsheet.

Suppose we have two 5-bit sequences of 1s and -1s, say: [a1 a2 a3 a4 a5] and [b1 b2 b3 b4 b5].
For example:
[A]       [1 -1 1 -1 1] and [-1 -1 1 -1 1].
To see if they are "related" in some way, a "correlation" is calculated like so:
a1b1 + a2b2 + a3b3 + a4b4 + a5b5.
For example:
[B]       (1)(-1) + (-1)(-1) + (1)(1) + (-1)(-1) + (1)(1) = -1+1+1+1+1 = 3.

If, for example, the second sequence contained digits equal to those of the first sequence, the "correlation" would be 5.
If the second sequence digits were the negative of those of the first sequence, the "correlation" would be -5.
In either case, the absolute value of this "correlation" would be 5 which is the largest possible |correlation| for two 5-digit sequences.
Because of this large "correlation", we'd conclude that they were "related".

>Huh? If the second sequence is identical to the first, then they're obviously related! Can't you see that?
In the above [A] [B] example, the "correlation" was 3, so they are "less" related.

>If you wanted unrelated sequences, then pick a couple where the correlation is 0.
Is there such a pair of 5-digit sequences? A pair where the absolute value of the maximum correlation is 0?
The answer is No!.

In any case, we're interested in Autocorrelation.
Instead of finding the "correlation" between distinct sequences, we find the "correlation" between two sequences where the second is obtained from the first by shifting.
In our 5-digit example, we get the second sequence by shifting the first by one digit to the right and consider these two:
[a1 a2 a3 a4] and [a2 a3 a4 a5]
For this 1 digit shift, the "correlation" is then:
    C1= a1a2 + a2a3 + a3a4 + a4a5.
Then we see if there's a "correlation" between the original and a second sequence shifted 2 digits:
    C2 = a1a3 + a2a4 + a3a5.
Then we see if there's a "correlation" between the original and a second sequence shifted 3 digits:
    C3 = a1a4 + a2a5.
Then we see ...

>Don't tell me! Now you look at C4 = a1a5, right?
Exactly. Now you calculate the maximum of them Cs: Max. Autocorrelation = Max[ Cj ] for j = 1, 2, 3, 4.

Finally, you vary the initial sequence so that Max[ Cj ] is less than or equal to 1.

>And that's a Barker sequence?
Yes ... and you'd get the Barker Sequence: 1 1 1 -1 1

You can play here. Keep pressing F9 to change the (random) code generated to see that you get the Barker Sequence when the Max. Autocorrelation is reduced to 1.

>Why do you always put "correlation" in quotes?
There are so many "correlations", but we're considering just the flavour defined above.
>Okay, so show me the first dozen Barker Codes ... just so I get a feel for how the digits are arranged.    
They're shown in Figure 2.

>Show me the first dozen!
Alas, them's all that have been found ... so far.

>Hey! Didn't you say, earlier, that the 11-digit Barker Code was 10110111000?
Uh ... yes, but ...

>So why doesn't that look like the 11-digit Barker in Figure 2?
I haven't figured that out ... yet.

When I google "Barker Codes", I get the Barker sequences shown in Figure 2.

When I google WiFi "Barker Codes", I get 10110111000.

Figure 2

>Why is that?
I haven't figured that out ... yet.

>Well, let's see ... uh ... if you change all them -1s to 0s we'd get (from Figure 2, for the 11-bit Barker): 11100010010
Good ... and if we take the complement we'd get: 00011101101.
>Aha! Now read it backwards and we get: 10110111000.
>Well, I helped.
Yes, you did ... but why that ritual? I guess the properties of the Barker code aren't changed when we do that transformation.
>Can you prove that?
Let me cogitate.
When defining a Barker as the minimum of the absolute value of Max. Autocorrelation, we could certainly get 0 by choosing every digit equal to 0.
>So we avoid that by having only digits 1 and -1.
Right! So Barker codes look like the sequences in Figure 2 ... with 1s and -1s.
>Exactly ... then we do that complement and reverse thing.