Bulletproof Wireless Security

Chia sẻ: Phong Thinh | Ngày: | Loại File: PDF | Số trang:273

0
147
lượt xem
68
download

Bulletproof Wireless Security

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Bulletproof Wireless Security

  1. Bulletproof Wireless Security
  2. Bulletproof Wireless Security GSM, UMTS, 802.11 and Ad Hoc Security By Praphul Chandra AMSTERDAM • BOSTON • HEIDELBERG • LONDON NEW YORK • OXFORD • PARIS • SAN DIEGO SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO Newnes is an imprint of Elsevier
  3. Newnes is an imprint of Elsevier 30 Corporate Drive, Suite 400, Burlington, MA 01803, USA Linacre House, Jordan Hill, Oxford OX2 8DP, UK Copyright © 2005, Elsevier Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: permissions@elsevier.com.uk. You may also complete your request online via the Elsevier homepage (www.elsevier.com), by selecting “Customer Support” and then “Obtaining Permissions.” Recognizing the importance of preserving what has been written, Elsevier prints its books on acid-free paper whenever possible. Library of Congress Cataloging-in-Publication Data (Application submitted.) British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. ISBN: 0-7506-7746-5 For information on all Newnes publications, visit our website at www.books.elsevier.com. 05 06 07 08 09 10 10 9 8 7 6 5 4 3 2 1 Printed in the United States of America
  4. This book is dedicated— To my parents, whose love, support and example have helped me reach my goals; and To my wife, Shilpy, whose cheerful patience and constant encouragement made this book possible.
  5. Contents Preface .............................................................................................................. xi “... but where does the voice go?” ......................................................................................xi A Brief History of Wireless .............................................................................................. xii A Brief History of Security ..............................................................................................xiv Moving On ..................................................................................................................... xxii Reading Conventions ..................................................................................................... xxiii How to Read this Book? ................................................................................................ xxiii Acknowledgments ............................................................................................. xxv Acronyms ....................................................................................................... xxvii About the Author .......................................................................................... xxxiii Chapter 1: Security and Cryptography ...................................................................1 1.1 What is Security? ..........................................................................................................1 1.2 Cryptography ................................................................................................................3 1.2.1 Confidentiality .....................................................................................................3 1.2.2 Integrity ................................................................................................................9 1.2.3 Authentication ....................................................................................................11 1.2.4 Replay Protection and Nonrepudiation ..............................................................13 1.3 Cryptanalysis ..............................................................................................................13 1.4 Block Ciphers .............................................................................................................14 1.4.1 Using the Ciphers: The Modes ..........................................................................15 1.5 Stream Ciphers ............................................................................................................18 1.6 How Secure is Cryptography? ....................................................................................22 1.6.1 Strength of a Cipher ...........................................................................................22 1.6.2 Key-Length: How Long is Secure? ....................................................................23 1.7 Beyond Cryptography .................................................................................................24 1.7.1 Firewalls .............................................................................................................24 1.7.2 Denial of Service Attacks ..................................................................................25 1.7.3 Code Security .....................................................................................................26 1.7.4 Steganography....................................................................................................27 1.8 Conclusion ..................................................................................................................28 Chapter 2: Network Security Protocols.................................................................29 2.1 Introduction .................................................................................................................29 2.2 Key Establishment Protocols ......................................................................................29 2.2.1 Key Generation in SKC .....................................................................................30 vii
  6. Contents 2.2.2 Key Distribution in SKC ....................................................................................30 2.2.3 Key Establishment in PKC ................................................................................31 2.2.4 Diffie-Hellman Key Exchange ...........................................................................33 2.2.5 Enhanced Diffie-Hellman Key Exchange ..........................................................35 2.2.6 RSA ....................................................................................................................35 2.3 Authentication Protocols.............................................................................................38 2.3.1 Address-Based Authentication ...........................................................................38 2.3.2 Passwords for Local Authentication (Login) .....................................................39 2.3.3 Passwords for Network Authentication .............................................................41 2.3.4 Authentication Using SKC.................................................................................42 2.3.5 Authentication Using PKC.................................................................................47 2.3.6 What to Use for Authentication: SKC or PKC?.................................................48 2.3.7 Session Hijacking ..............................................................................................49 2.3.8 Needham Schroeder ...........................................................................................51 2.3.9 Kerberos .............................................................................................................52 2.4 Encryption Protocols...................................................................................................54 2.4.1 DES ....................................................................................................................56 2.4.2 TripleDES or 3DES ...........................................................................................56 2.4.3 AES ....................................................................................................................59 2.4.4 RC4 ....................................................................................................................60 2.5 Integrity Protocols.......................................................................................................61 2.5.1 CBC Residue......................................................................................................61 2.5.2 CRC32 ...............................................................................................................62 2.5.3 MD5 ...................................................................................................................63 Chapter 3: Security and the Layered Architecture ..................................................67 3.1 Introduction .................................................................................................................67 3.2 Security at Layer 1 ......................................................................................................68 3.3 Security at Layer 2 ......................................................................................................69 3.3.1 Extensible Authentication Protocol (EAP) ........................................................69 3.3.2 EAPoL: EAP Over LAN....................................................................................72 3.3.3 EAP-TLS: TLS Handshake Over EAP ..............................................................73 3.4 Security at Layer 3 ......................................................................................................75 3.5 Security at Layer 4: SSL/TLS .....................................................................................80 3.6 Security at Layer 5+....................................................................................................84 Chapter 4: Voice-Oriented Wireless Networks ......................................................85 4.1 The Wireless Medium .................................................................................................86 4.1.1 Radio Propagation Effects .................................................................................86 4.1.2 Hidden Terminal Problem ..................................................................................88 4.1.3 Exposed Terminal Problem ................................................................................89 4.1.4 Bandwidth ..........................................................................................................89 4.1.5 Other Constraints ..............................................................................................90 4.2 The Cellular Architecture............................................................................................90 4.3 TWNs: First Generation..............................................................................................93 4.3.1 Addresses in AMPS ...........................................................................................96 viii
  7. Contents 4.3.2 Call Setup in AMPS ...........................................................................................97 4.4 TWNs: Second Generation .........................................................................................98 4.4.1 Addresses in GSM ...........................................................................................102 4.4.2 Call Setup in GSM ...........................................................................................103 4.5 TWNs: Third Generation ..........................................................................................104 4.5.1 Connection Setup in UMTS .............................................................................106 4.6 The Overall Picture ...................................................................................................107 Chapter 5: Data-Oriented Wireless Networks.....................................................109 5.1 WLANs .....................................................................................................................109 5.1.1: Addresses in 802.11 ........................................................................................114 5.1.2 Connection Setup in 802.11 .............................................................................114 5.1.3 Media Access ...................................................................................................117 5.1.4 Spectrum Efficiency in 802.11.........................................................................120 5.2 MANETs ...................................................................................................................121 5.2.1 MAC for MANETs ..........................................................................................123 5.2.2 Routing in MANETs. .......................................................................................124 5.2.3 Address Allocation in MANETs ......................................................................126 5.2.4 Security in MANETs .......................................................................................127 5.3 Wireless Networks in the Near Future ......................................................................127 Chapter 6: Security in Traditional Wireless Networks ..........................................129 6.1 Security in First Generation TWNs ..........................................................................129 6.2 Security in Second Generation TWNs ......................................................................129 6.2.1 Anonymity in GSM ..........................................................................................130 6.2.2 Key Establishment in GSM .............................................................................131 6.2.3 Authentication in GSM ...................................................................................132 6.2.4 Confidentiality in GSM ....................................................................................136 6.2.5 What’s Wrong with GSM Security? ................................................................137 6.3 Security in 2.5 Generation TWNs.............................................................................140 6.3.1 WAP ................................................................................................................142 6.3.2 Code Security ...................................................................................................144 6.4 Security in 3G TWNs ...............................................................................................144 6.4.1 Anonymity in UMTS .......................................................................................144 6.4.2 Key Establishment in UMTS ...........................................................................146 6.4.3 Authentication in UMTS ..................................................................................146 6.4.4 Confidentiality in UMTS .................................................................................150 6.4.5 Integrity Protection in UMTS ..........................................................................151 6.4.6 Putting the Pieces Together ..............................................................................152 6.4.7 Network Domain Security ...............................................................................155 6.5 Summary ...................................................................................................................158 Chapter 7: Security in Wireless Local Area Networks ..........................................159 7.1 Introduction ...............................................................................................................159 7.2 Key Establishment in 802.11 ....................................................................................160 7.2.1 What’s Wrong? ................................................................................................160 7.3 Anonymity in 802.11 ................................................................................................161 ix
  8. Contents 7.4 Authentication in 802.11...........................................................................................162 7.4.1 Open System Authentication ...........................................................................164 7.4.2 Shared Key Authentication ..............................................................................165 7.4.3 Authentication and Handoffs ...........................................................................166 7.4.4 What’s Wrong with 802.11 Authentication? ....................................................167 7.4.5 Pseudo-Authentication Schemes......................................................................168 7.5 Confidentiality in 802.11 ..........................................................................................169 7.5.1 What’s Wrong with WEP? ...............................................................................170 7.6 Data Integrity in 802.11 ............................................................................................174 7.7 Loopholes in 802.11 Security ...................................................................................176 7.8 WPA ..........................................................................................................................177 7.8.1 Key Establishment ...........................................................................................178 7.8.2 Authentication ..................................................................................................183 7.8.3 Confidentiality ................................................................................................186 7.8.4 Integrity ............................................................................................................187 7.8.5 The Overall Picture: Confidentiality + Integrity ..............................................189 7.8.6 How Does WPA Fix WEP Loopholes? ............................................................189 7.9 WPA2 (802.11i) ........................................................................................................190 7.9.1 Key Establishment ...........................................................................................190 7.9.2 Authentication ..................................................................................................191 7.9.3 Confidentiality ...............................................................................................191 7.9.4 Integrity ............................................................................................................193 7.9.5 The Overall Picture: Confidentiality + Integrity ..............................................193 Chapter 8: Security in Wireless Ad Hoc Networks ...............................................199 8.1 Introduction ...............................................................................................................199 8.2 Routing in Multihop Ad Hoc Networks ....................................................................201 8.2.1 Proactive Routing.............................................................................................201 8.2.2 Reactive Routing ..............................................................................................202 8.2.3 Hybrid Routing ................................................................................................202 8.2.4. Routing Attacks...............................................................................................202 8.2.5 Secure Routing .................................................................................................203 8.3 Key Establishment and Authentication .....................................................................205 8.3.1 Threshold Secret Sharing .................................................................................205 8.4 Confidentiality and Integrity .....................................................................................210 8.5 Bluetooth ..................................................................................................................210 8.5.1 Bluetooth Basics ..............................................................................................211 8.5.2 Security Modes ................................................................................................213 8.5.3 Key Establishment ...........................................................................................216 8.5.4 Authentication ..................................................................................................223 8.5.5 Confidentiality .................................................................................................224 8.5.6 Integrity Protection ..........................................................................................227 8.5.7 Enhancements ..................................................................................................227 References ......................................................................................................229 Index ..............................................................................................................231 x
  9. Preface “... but where does the voice go?” A man has been arrested in New York for attempting to extort funds from ignorant and superstitious people by exhibiting a device which he says will convey the human voice any distance over metallic wires so that it will be heard by the listener at the other end. He calls this instrument a telephone. Well-informed people know that it is impossible to transmit the human voice over wires.” —News item in a New York newspaper, 1868. I remember a day not so long ago, when I was showing my mother how to use a cell phone. She asked me how it worked and I started describing the base-stations, switch- es and the cellular architecture. After I was done, she asked me “... but where does the voice go?”—Where indeed? Engineers sometimes tend to forget that the concept of wireless seems magical to most people. Being visual creatures, we can accept the fact that in a wired network, our voice (or data) travels “on” the wire but seeing a wireless network is almost magical—your voice (or data) disappears into your handset and reappears out of the handset of another person at the other side of the globe. Pause to think about it. If you told someone in the nineteenth century that you could do this, you would have probably been credited with supernatural powers. We really are doing magic. I had always been fascinated by wireless. Then during my college years, I took a course in cryptography and was intrigued by how secure communica- tion could be achieved over an unsecure channel. It was only natural then that the field of wireless security attracted me towards it and resulted in this book. I have always felt that for a complete understanding of any field, it helps to know how the field developed. We therefore start by looking at a brief history of wireless and a brief history of cryptography. Those with a purely technical inclination may, there- fore, skip this chapter but I think it makes for good light reading. I hope you enjoy this chapter and the rest of this book. xi
  10. Preface 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 ideas xii
  11. Preface of 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. 1 Some may argue that 3G may never happen and service providers may go straight from 2.5G to 4G. See Chapter 4 for more details. xiii
  12. Preface 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. xiv
  13. Preface 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, xv
  14. Preface 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 an xvi
  15. Preface unbreakable 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 a xvii
  16. Preface Vigenere 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” xviii
  17. Preface 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. xix
Đồng bộ tài khoản