Bulletproof Wireless Security - GSM, UMTS, 802.11, And Ad Hoc Security 2005

How this Book Organized

Chapter 1 looks at the basics of cryptography.

Chapter 2 delves into how cryptography is used to provide network security. We also look at some of the most prominent security protocols used in network security today. We do not distinguish between wireline and wireless networks at this stage of the book.

Chapter 3 explores the topic of security and the layered-network architecture. This is an often-neglected topic and one which, I think, is necessary to understand the archi-tectural integration of security and networking.

Chapter 4 lays the foundation of wireless networks and discusses the design of cellu-lar networks which were primarily designed for enabling voice communication.

Chapter 5 discusses wireless networks which are primarily designed for enabling data communication. These networks are a relatively new phenomenon and probably the most widely deployed technology in this field is IEEE’s 802.11. We look at 802.11 networks and also explore mobile ad hoc networking which is an active area of research today in wireless networking.

Chapter 6 looks at the evolution of security in cellular networks. We start with secu-rity implementation in the first generation (AMPS) cellular networks and see how security implementations evolved and improved in second generation (GSM) and then third generation (UMTS) cellular networks.

Chapter 7 studies security in 802.11 networks. This topic has been a topic of hot debate in the recent past. We look at the security implementation of 802.11 in detail and study what all the debate was about. We then look at how the 802.11i specifica-tions aim to fix the loopholes of 802.11 networks.

Finally in Chapter 8, we look at security in wireless ad hoc networks. Ad hoc net-works (and specifically multihop ad hoc networks) are an active area of research today. Needless to say, then, that security in such networks is also being actively researched. This chapter looks at the underlying security concepts which seem prom-ising for securing ad hoc networks.


A Brief History of Wireless

There is no doubt that the day will come, maybe when you and I are forgotten, when copper wires, gutta-percha coverings, and iron sheathings will be relegated to the Museum of Antiquities. Then, when a person wants to telegraph to a friend, he knows not where, he will call an electromagnetic voice, which will be heard loud by him who has the electromagnetic ear, but will be silent to everyone else. He will call “Where are you?” and the reply will come, “I am at the bottom of the coal-mine” or “Crossing the Andes” or “In the middle of the Pacific”; or perhaps no reply will come at all, and he may then conclude that his friend is dead.

—Professor W.E. Ayrton (member of the Institution of Electrical Engineers) said this at a lecture at the Imperial Institute...in 1897.

Arguably, wireless communication between humans is as old as the human civiliza-tion itself, for as soon as the first humans started communicating with each other using their vocal cords, we had achieved wireless communication. However, the term wireless communication is usually used to refer to wireless communication beyond the “line of sound.”

The foundations of wireless communication were laid by Michael Faraday’s work on electromagnetism, which established that electric and magnetic effects result from “lines of force” that surround conductors and magnets. Based on Faraday’s work, James Maxwell derived mathematical equations that represented the “lines of force” Faraday had explained. Maxwell published his work in a paper in 1855. Later, in 1861, Maxwell further developed his work showing that if an electric charge was applied to a (hypothetical) elastic fluid, it would result in the generation of waves that would travel through the medium. In effect, Maxwell predicted the existence of electromagnetic waves. Friedrich Kohlrausch and Wilhem Weber furthered Maxwell’s work by calculating that these waves would travel at the speed of light.

Up until 1888, the field of electromagnetism was that of pure theory. In that year, Heinrich Hertz discovered radio waves which are an example of electromagnetic radiation. Hertz did this by devising a transmitting oscillator and a “receiver.” The “receiver” was basically a metal loop with a gap on one side. When this loop was placed within the transmitter’s electromagnetic field, sparks were produced across the gap in the loop. This proved that electromagnetic waves could be sent out into space and remotely detected. In effect, Hertz showed that the elastic fluid that Maxwell had hypothesized could be the ether. The discovery of radio waves confirmed the ideasof Maxwell and other scientists who had worked on electromagnetism and sparked a greater interest in the field.

When Guglielmo Marconi learnt about Hertz’s work, he realized that if the radio waves could be transmitted over large distances, wireless telegraphy could be developed. Marconi started experimenting with this idea and by 1894, he managed to receive radio signals at a distance of over a mile. Marconi tried to develop his work further by taking the help of the Italian government. However, the Italian government was not interested. So, Marconi approached the British government. He was granted a patent for wireless telegraphy in 1897 and the world’s first radio factory was setup at Chelmsford in 1898. Soon, radios started to be used commercially. The world of wireless telegraphy got another big boost in 1901 when Marconi and his associates were able to receive a signal across the Atlantic successfully. Recognizing his contri-bution to the field of wireless communication, Marconi was awarded the Nobel Prize in 1909.

In 1914, physicists were able to use radio transmission to carry voice and by the 1920s, wireless mobile receivers were being installed in police cars in Detroit. Commercially, wireless deployment reached its first landmark in 1983 with the deployment of the Advanced Mobile Phone System (AMPS) in the United States. AMPS was an example of the first generation wireless networks that were deployed across the world. Although a major success story, the 1G (first generation) wireless networks soon outgrew the capacity needed to serve the exploding growth in the number of wireless subscribers. This motivated the development and deployment of the 2G (second generation) wireless networks like GSM in the late 1990s. Today, 2G is the dominant mobile technology. The deployment of 3G is expected to begin soon1, but on another note, the exploding growth in Wireless Local Area Networks (WLANs) is changing the field of wireless communication in unforeseen ways. As of the writing of this book, pundits are trying to envision how 3G, IP, PSTN and WLANs will come together to provide the ultimate communication dream—staying connected: anytime, anywhere.

A Brief History of Security

“Well, I never heard it before,” said the Mock Turtle, “but it sounds uncommon nonsense.”
—Lewis Carroll, Alice in Wonderland.

Secret communication achieved by hiding the existence of a message is known as steganography. The word is derived from the Greek word “steganos,” meaning cov-ered and “graphin” meaning to write.

The first written account of steganography comes from Herodotus, who chronicled the story of Histaiaeus. Histaiaeus wanted to encourage Aristagoras of Miletus to revolt against the Persian king. To convey his instructions securely, Histaiaeus shaved the head of his messenger, wrote the message on his scalp and then waited for the hair to regrow. From that humble beginning, steganography evolved to the microdot in World War II. The microdot was a technique wherein the German agents in Latin America would photographically shrink a page of text down to a dot less than 1 mm in diame-ter, and then hide this microdot on top of a full stop in an apparently innocuous letter. The first microdot to be spotted by the Federal Bureau of Investigation (FBI) (USA) was in 1941. The coming of the digital age further changed the face of steganography. Modern techniques involve hiding the content of a message in a picture by modifying the lower nibble of a pixel.

Whereas steganography deals with hiding the message, the other branch of secret communication, cryptography, deals with hiding the information content of the message. Cryptography consists of two basic operations—transposition and substitu-tion. Transposition involves rearranging the “letters” in the message and substitution involves mapping the “letters” in a message according to a predetermined mapping. In cryptographic lingo, the new message obtained by transforming the original message using cryptography is known as the ciphertext, whereas the original message is known as the plaintext.

The transformation of the plaintext to the ciphertext is achieved using a cipher. Each distinct cipher can be described in terms of the algorithm and the key. As an example, consider the Caesar cipher, one of the earliest military ciphers used by Julius Caesar. This cipher works by replacing each letter in the message with a letter which is three places down the alphabet. In this case, the algorithm part of the cipher is the act of substitution and the key is “three forward.” More generically, the mono-alphabetic substitution cipher is the generic name given to any substitution cipher in which each letter in the plaintext is replaced by exactly one letter or symbol in the ciphertext.The first documented use of mono-alphabetic substitution cryptography appears in the Kama Sutra, a text written in the fourth century B.C. by the Indian scholar Vatsyayna. Vatsyayna explains a technique of secret writing that works by pairing the letters of the alphabet at random and then substituting each letter in the message with its partner. With the passage of time, multiple variations of the mono-alphabetic cipher continued to be developed independently around the world.

The next biggest invention in the world of “secret writing” came with the invention of cryptanalysis, or the science of destroying ciphers. Cryptanalysis consists of obtain-ing the plaintext message from the ciphertext without the knowledge of the key. The invention of cryptanalysis can be traced back to the ninth century. In 815, the Caliph al-Mamun established the Bait al-Hikmah (“House of Wisdom”) in Baghdad and assigned Arabic theologians to scrutinize the revelations of Muhammad the Prophet and establish the chronology of the revelations.

The Arabic theologians did this by counting the frequencies of words contained in each revelation. The theory was that certain words had evolved relatively recently; and hence, if a revelation contained a high number of these new words, this would in-dicate that it came later in the chronology. Significantly, the scholars did not stop their scrutiny at the level of words. They also analyzed individual letters and discovered that some letters are more likely to occur in a given text than others.

Although it is not known who first realized that the variation in the frequencies of let-ters could be exploited in order to break ciphers, the earliest known description of this technique is by the ninth-century scientist Abu Yusuf Yaqub ibn Is-haq ibn as-Sabbah ibn omran ibn Ismail al-Kindi. The cryptanalysts had triumphed over the cryptographers and thus began the “war” between cryptographers trying to build unbreakable ciphers and cryptanalysts trying to break these ciphers. As we shall see, this war continues to this day and provides the impetus for the evolution of cryptography.

The onus was now on the cryptographers to come up with a new stronger cipher. The roots of this new stronger type of cipher can be traced back to an essay written some-time in the 1460s by the Florentine polymath Leon Battista Alberti. Alberti proposed mapping each plaintext letter to two or more ciphertext letters and switching between them during the encipherment. Although Alberti had hit upon the most significant breakthrough in cryptography for over a thousand years, he failed to develop this con-cept into a complete cipher.

Alberti made one other significant contribution to the field of cryptography—he invented the first cryptographic machine—the cipher disc. The cipher disc is the earliest known cryptographic machine and it consists of two concentric copper discs,one slightly larger than the other, with the alphabet inscribed along the circumference of both the discs. The smaller disc is placed on top of the larger disc and connected at the center using a needle which acts as an axis. Since the two discs could be in-dependently rotated, the two alphabets can have different relative positions and can therefore easily be used to encrypt messages using the mono-alphabetic cipher. In fact, the disk can also be used in more complicated ways. Alberti suggested changing the setting of the disk while encrypting the message to use the poly-alphabetic cipher that he had just invented.
Alberti’s initial idea regarding the poly-alphabetic cipher was further developed by Johannes Trithemius and Giovanni Porta over the years. However, the development of this idea to a complete cipher was left to Blaise de Vigenere. Although Alberti, Tri-themius and Porta all made vital contributions to this new poly-alphabetic cipher, the cipher is known as the Vigenere cipher in honor of the man who developed it into its final form. The strength of the Vigenere cipher lies in it’s using not one but 26 distinct cipher alphabets to encrypt a message. The great advantage of Vigenere cipher is that it is impregnable to the frequency analysis which the cryptanalysts had used to break the mono-alphabetic cipher. The fact that a letter which appears several times in the ciphertext can represent a different plaintext letter on each occasion generates tremen-dous ambiguity for the cryptanalyst. Besides being invulnerable to frequency analysis, the Vigenere cipher also has an enormous number of keys, making it difficult to try all possible keys. The creation of the poly-alphabetic Vigenere cipher meant that the cryptographers were now in control.

The Vigenere cipher remained unbreakable until the mid-nineteenth century. This is when Charles Babbage came along. Babbage is best known for developing the blueprint of the modern computer—the Difference Engine. However, Babbage also made the greatest breakthrough in cryptanalysis since the Arab scholars in the ninth century—he broke the Vigenere cipher. Babbage never publicized this discovery. His discovery came to light only in the twentieth century when scholars examined Bab-bage’s extensive notes. Meanwhile, in 1863 Friedrich Wilhelm Kasiki also broke the Vigenere cipher independently and published his discovery. The breaking of Vigenere cipher put the cryptanalysts back on the top.

Since the Vigenere cipher was broken, the cryptographers had been trying to come up with a better, more secure type of cipher. The need for such a cipher grew in the late nineteenth century with the invention of the telegraph and the radio. The use of the telegraph took the speed of communications to new heights. However, for business-men and the military to exploit the immediacy of the telegraph required the use of anunbreakable cipher, since messages sent using the telegraph ended up being handled by a whole group of people (telegraph operators, and so forth).

The demand for a secure cipher was further fueled by the invention of radio by the Italian physicist Guglielmo Marconi. Wireless communication was desirable for many reasons, especially by the military. Primary among them were that communica-tion could be achieved with minimal infrastructure support and that communication could be achieved even if the communicating parties were constantly moving. These advantages were inherent due to the all-pervasive nature of radio. However, the all-pervasive property of the radio was also its greatest weakness, since this meant that the messages sent from the transmitter to the receiver in the battlefield were also accessible to the enemy nearby. Consequently, an unbreakable cipher became an absolute necessity.

However, the discovery of the next great cipher was not to come until 1918, and the field of cryptography did not see any major advances during World War I (1914–1918). The field of cryptanalysis though, was another story. During the war, the French listening ports learnt to recognize a radio operator’s fist (his pauses, his speed of transmission and his relative lengths of dots and dashes). The French also established six direction finding stations which were able to detect the direction from which a radio message was coming. Since each enemy battalion usually had an assigned radio operator and since battalions were mobile, the above two pieces of information could be combined to track the movement of enemy battalions. This was probably the birth of traffic analysis as a form of cryptanalysis, and during the war this became an especially valuable tool when a new cipher was introduced by the enemy. In fact, the French also recognized that wireless communication was more un-secure than wired communication due to the ease of message collection and exploited this fact by destroying communication landlines as they retreated. This forced the advancing Germans to use radio communication; thus making message collection easier for the French.

In short, World War I was dominated by the cryptanalysts. New ciphers were introduced but all of them were broken one by one. Then, in 1918, Major Joseph Mauborgne, head of cryptographic research for the US Army, introduced the concept of a random key. The idea was inspired by the fact that the fundamental weakness of the Vigenere cipher that was exploited by Babbage and Kasiki to break it was the cyclical nature of the cipher when used with a short key. Since the key was limited in length, every nth letter of the plaintext was encrypted according to the same ciphertext alphabet. Mauborgne advocated employing message-length random keys as part of aVigenere cipher to give an unprecedented level of security. This cipher was known as the one-time pad cipher since it required the generation of large “pads” of random keys.

The security of the one-time pad cipher lay wholly in the randomness of the key. The key injects randomness into the ciphertext and if the ciphertext is truly random, there is no structure for the cryptanalyst to exploit. In fact, to date the one-time pad cipher is the only cipher which can be mathematically proven to be absolutely secure. At first thought, this may lead one to believe that the cryptographers had once and for all won the war against the cryptanalysts. If this were true, this book never would have been written. Perfectly secure as the one-time pad is, it suffers from two great operating difficulties—key generation and key distribution.

Generating truly random keys is not as easy as it might initially sound. As Voltaire put it, “Anybody who tries to generate random numbers by deterministic means is of course living in a state of sin.” Over the years, cryptographers have realized that the best random keys are those created by harnessing natural physical processes like ra-dioactivity. The bottom line is that it requires a great deal of time, effort and money to generate truly random keys. Difficult as key generation was, there was another major problem with the one-time pad cipher—the distribution of these large pads of keys. To be fair, key distribution had always been a problem in the world of cryptography—and a neglected one at that. The one-time pad cipher just brought the problem into the lime-light by making it a lot more difficult to solve (due to the sheer volume of the pads).

Even though the cryptographers had created the perfect cipher in 1918, it was of little use due to its huge operating cost. However, there was another development in 1918 that changed the field of cryptography. This was the development of the Enigma by the German inventor, Arthur Scherbius. The Enigma was a cryptographic machine which could be used for encrypting and decrypting messages. It was an electrical ver-sion of Alberti’s cipher disc but was much more powerful. A user could simply type in the plaintext alphabet (as in the keyboard of a typewriter) and obtain the correspond-ing ciphertext. The cryptographic core of the Enigma was the scrambling unit, which consisted of a set of scrambler discs (also known as rotors). The first disc automati-cally rotated by one-sixth of a revolution each time a letter was encrypted. The second disk rotated each time the first disc had completed a revolution, and so on.

It helps to think of the Enigma in terms of Alberti’s cipher disc. Enigma had combined the scramblers to implement a poly-alphabetic cipher which continually switched between different cipher alphabets. Consider what would happen if the inner disc of Alberti’s cipher disc was rotated after the encryption of each letter: we would have a poly-alphabetic cipher with a self-generating key. In fact, the length of the “key”would be as long as the message itself. So, was this the implementation of a one-time pad cipher? Well, not quite. Remember that the one-time pad cipher requires the key to be random. In the Enigma the generation of the “key” was a factor of the initial set-tings of the scramblers and the plaintext itself. Even though this made the discovery of the key very tough, the key was not really random—it was just mechanically (and therefore, mathematically) convoluted. Note that even the Enigma was faced with the problem of key distribution. In case of the Enigma, even though the key was gener-ated during encryption, the initial settings of the scrambler needed to be known to the sender(s) and the receiver(s) before secure communication would begin. However, the initial settings of the Enigma could be changed on a periodic basis—daily, weekly, and so forth. This made the amount of data that needed to be securely distributed much less than that required for a one-time pad cipher.

The invention of the Enigma was truly a great one, and one which changed the face of cryptography forever. The scrambler orientations, arrangements and the plug-board settings together offered a possible of 10,000,000,000,000,000 variations of the initial arrangements from which the cryptanalyst would have to search to break the cipher. The cryptographers were back on top in their battle with the cryptanalysts. To be fair, Scherbius was not the only one who had hit upon the idea of rotating scramblers. Alexander Koch in the Netherlands and Arvind Damm in Sweden had independently and almost simultaneously hit upon this idea. However, none of them could market the machine well enough to make it a commercial success. It was only in 1927, when the Germans realized that the Achilles heel of their World War I campaign was the breaking of their cipher, that the German government selected the Enigma for use by the military. In fact, the Enigma was to play a crucial role in World War II.

Enigma was at the heart of Hitler’s blitzkieg (literally—lightning war) strategy, whose ethos was “speed of attack through the speed of communication.” When the Americans and the French began to encounter messages encrypted with the Enigma, they were completely baffled and quickly gave up. This was probably due to the fact that in the wake of the victory in World War I, the Allies were in a dominant position and feared no one, least of all Germany. There was, therefore, no great motivation for the Allies’ cryptanalysts. There was one country, though, that could not afford to relax—Poland. After World War I, Poland had reestablished itself as an independent state. However, to the east of Poland lay Russia, a nation ambitious to spread its communism, and to the west lay Germany, desperate to regain territory ceded to Poland after the war. The Polish cryptanalysts therefore had plenty of motivation to attack the Enigma. Adver-sity, it seems, is one of the foundations of successful code breaking.The first step in the cracking of the Enigma came on November 8, 1931 when Hans-Thilo Schmidt, a German military employee, handed over German military documents containing instructions for using the military version of the Enigma machine, to the French in exchange for 10,000 marks. These documents contained enough informa-tion to allow the Allies to create an exact replica of the Enigma machine. However, the French cryptanalysts did not actually build a replica, since they were convinced that the next stage of breaking the cipher—that is, finding the key required to deci-pher a message—was impossible. This underscores one of the basic presumptions of cryptography—the strength of a good cipher depends not on keeping the algorithm (machine) secret but on keeping the key (initial setting of the machine) secret.

Fortunately for the Allies, the French cryptanalysts handed over the Schmidt documents to the Polish cryptanalysts thanks to an existing military co-operation agreement between the two countries. This allowed the Polish cryptanalysts to attack the Enigma even though the French cryptanalysts had given up hope. In attacking the Enigma, the Polish bureau of cryptography made a breakthrough in the field of cryp-tography. For centuries, it had been assumed that the best cryptanalysts were experts in the structure of language. However, the Polish theorized that since Enigma was a mechanical cipher, cryptanalysts with a more scientific mind might be better equipped to attack the Enigma. Working off this theory, the Polish bureau assigned three math-ematicians to work on the Enigma cipher—one of them was Marian Rejewski.

Working alone on the Enigma, Rejewski’s attack was based on the theory that repeti-tion is the enemy of security, since repetition leads to patterns which can be linked and therefore exploited. The Schmidt documents showed that the most obvious repetition in the Enigma cipher was the message key. To discourage attacks on the Enigma, the German cryptographers had decided that instead of using the day key (initial scrambler settings) to encrypt all messages of the day, the day key was instead used just to encrypt the message key. The message key was used to encrypt the mes-sage itself and the message key itself was transmitted encrypted with the day key. This process made the system more secure by avoiding the repeated use of a single day key to encrypt hundreds of messages. However, the fact that the message key was encrypt-ed and transmitted twice at the beginning of every message to avoid mistakes caused by radio interference made the process susceptible to Rejewski’s repetition theory.

Even though an explanation of Rejewski’s breakthrough in cracking the Enigma is beyond the scope of this book, it is imperative to mention here that Rejewski’s at-tack on Enigma is one of the truly great accomplishments of cryptanalysis. Not only did Rejewski break one of the greatest ciphers of the time, he also achieved anotherfirst in the cryptographic world by mechanizing the cryptanalysis. The machines that were used to automate the process of finding the day key were called bombes, a name attributed to the ticking noise they made while working. For the Allies, the cracking of the Enigma was a major breakthrough since it counteracted the ethos of Blitzkrieg, which was “speed of attack through speed of communications.”

However, in December of 1938 when the Germans added two more scramblers to the Enigma, Rejewski’s bombes were rendered useless and the Polish did not have the resources to tackle the new, even more complicated, cipher. Cracking the new Enigma was now left to Britain and France, which used Rejewski’s breakthrough as a starting step in this process. Bletchley Park in Buckinghamshire was selected as the center of Allied code-breaking with Enigma being one of the major challenges. Learning from the Polish experience, the team at Bletchley Park consisted of mathematicians and scientists, besides linguists and classicists. Working with the new Enigma cipher, over time, the Bletchley team invented their own short cuts for finding the Enigma message-keys.

There were many significant breakthroughs at Bletchley Park but the one that most deserves mention is that of Alan Turing. Turing is most known for his 1937 mathe-matical paper titled “On Computable Numbers.” The paper was an attempt to identify Gödel’s undecidable questions; that is, questions that were beyond the reach of logical proof. In order to identify these undecidable questions, Turing proposed a universal Turing machine whose internal working could be altered so that it could perform dif-ferent functions. In effect, Turing created the blueprint for the modern programmable computer.2 Turing joined Bletchley Park in September 1939 and focused his work on how to crack the Enigma cipher without using the message-key-repetition loophole. In effect, Turing was working to handle the scenario where the Germans would rectify this loophole in the Enigma cipher. Towards this aim, he studied the vast collec-tion of captured messages and the corresponding decrypted plaintext that Bletchley had accumulated in the past. Turing noticed that most of the messages sent by the Germans conformed to a certain structure. Using this knowledge, along with other aspects of the message like the time, source and destination of the message, Turing realized he could sometimes get enough information about the message to predict parts of the message. Turing used these “cribs” (ciphertext-plaintext pairs) along with his background in mathematics and science to build his version of the bombes, whichcould crack the new complicated version of the Enigma cipher. The effectiveness and success of Turing’s bombes can be estimated by the fact that a bombe could discover a message key in less than an hour, and there were as many as 49 bombes employed in Bletchley Park by the end of 1942.

Enigma was by no means the only cipher of World War II. There were many other ciphers used by the Germans and the Allied forces, cryptographers and cryptanalysts. Breakthroughs were achieved on either side of the fence, but perhaps no story is as interesting (or probably as well documented) as the story of the Enigma.

Read Comments To Download