Applied Cryptography, Second Edition: Protocols, Algorthms .

Applied Cryptography: Second Edition - Bruce Schneierresearch report of the private Riverbank Laboratories [577]. And this, despite the fact that the workhad been done as part of the war effort. In the same year Edward H. Hebern of Oakland, Californiafiled the first patent for a rotor machine [710], the device destined to be a mainstay of militarycryptography for nearly 50 years.After the First World War, however, things began to change. U.S. Army and Navy organizations,working entirely in secret, began to make fundamental advances in cryptography. During the thirtiesand forties a few basic papers did appear in the open literature and several treatises on the subjectwere published, but the latter were farther and farther behind the state of the art. By the end of thewar the transition was complete. With one notable exception, the public literature had died. Thatexception was Claude Shannon’s paper “The Communication Theory of Secrecy Systems,” whichappeared in the Bell System Technical Journal in 1949 [1432]. It was similar to Friedman’s 1918paper, in that it grew out of wartime work of Shannon’s. After the Second World War ended it wasdeclassified, possibly by mistake.From 1949 until 1967 the cryptographic literature was barren. In that year a different sort ofcontribution appeared: David Kahn’s history, The Codebreakers [794]. It didn’t contain any newtechnical ideas, but it did contain a remarkably complete history of what had gone before, includingmention of some things that the government still considered secret. The significance of TheCodebreakers lay not just in its remarkable scope, but also in the fact that it enjoyed good sales andmade tens of thousands of people, who had never given the matter a moment’s thought, aware ofcryptography. A trickle of new cryptographic papers began to be written.At about the same time, Horst Feistel, who had earlier worked on identification friend or foe devicesfor the Air Force, took his lifelong passion for cryptography to the IBM Watson Laboratory inYorktown Heights, New York. There, he began development of what was to become the U.S. DataEncryption Standard; by the early 1970s several technical reports on this subject by Feistel and hiscolleagues had been made public by IBM [1482,1484,552].This was the situation when I entered the field in late 1972. The cryptographic literature wasn’tabundant, but what there was included some very shiny nuggets.Cryptology presents a difficulty not found in normal academic disciplines: the need for the properinteraction of cryptography and cryptanalysis. This arises out of the fact that in the absence of realcommunications requirements, it is easy to propose a system that appears unbreakable. Manyacademic designs are so complex that the would–be cryptanalyst doesn’t know where to start;exposing flaws in these designs is far harder than designing them in the first place. The result is thatthe competitive process, which is one strong motivation in academic research, cannot take hold.When Martin Hellman and I proposed public–key cryptography in 1975 [496], one of the indirectaspects of our contribution was to introduce a problem that does not even appear easy to solve. Nowan aspiring cryptosystem designer could produce something that would be recognized as clever—something that did more than just turn meaningful text into nonsense. The result has been aspectacular increase in the number of people working in cryptography, the number of meetings held,and the number of books and papers published.In my acceptance speech for the Donald E. Fink award—given for the best expository paper to appearin an IEEE journal—which I received jointly with Hellman in 1980, I told the audience that in writing“Privacy and Authentication,” I had an experience that I suspected was rare even among theprominent scholars who populate the IEEE awards ceremony: I had written the paper I had wantedto study, but could not find, when I first became seriously interested in cryptography. Had I been ableto go to the Stanford bookstore and pick up a modern cryptography text, I would probably havelearned about the field years earlier. But the only things available in the fall of 1972 were a few classicPage 7 of 666

Applied Cryptography: Second Edition - Bruce Schneierpapers and some obscure technical reports.The contemporary researcher has no such problem. The problem now is choosing where to startamong the thousands of papers and dozens of books. The contemporary researcher, yes, but whatabout the contemporary programmer or engineer who merely wants to use cryptography? Wheredoes that person turn? Until now, it has been necessary to spend long hours hunting out and thenstudying the research literature before being able to design the sort of cryptographic utilities gliblydescribed in popular articles.This is the gap that Bruce Schneier’s Applied Cryptography has come to fill. Beginning with theobjectives of communication security and elementary examples of programs used to achieve theseobjectives, Schneier gives us a panoramic view of the fruits of 20 years of public research. The titlesays it all; from the mundane objective of having a secure conversation the very first time you callsomeone to the possibilities of digital money and cryptographically secure elections, this is whereyou’ll find it.Not satisfied that the book was about the real world merely because it went all the way down to thecode, Schneier has included an account of the world in which cryptography is developed and applied,and discusses entities ranging from the International Association for Cryptologic Research to theNSA.When public interest in cryptography was just emerging in the late seventies and early eighties, theNational Security Agency (NSA), America’s official cryptographic organ, made several attempts toquash it. The first was a letter from a long–time NSA employee allegedly, avowedly, and apparentlyacting on his own. The letter was sent to the IEEE and warned that the publication of cryptographicmaterial was a violation of the International Traffic in Arms Regulations (ITAR). This viewpointturned out not even to be supported by the regulations themselves—which contained an explicitexemption for published material—but gave both the public practice of cryptography and the 1977Information Theory Workshop lots of unexpected publicity.A more serious attempt occurred in 1980, when the NSA funded the American Council on Educationto examine the issue with a view to persuading Congress to give it legal control of publications in thefield of cryptography. The results fell far short of NSA’s ambitions and resulted in a program ofvoluntary review of cryptographic papers; researchers were requested to ask the NSA’s opinion onwhether disclosure of results would adversely affect the national interest before publication.As the eighties progressed, pressure focused more on the practice than the study of cryptography.Existing laws gave the NSA the power, through the Department of State, to regulate the export ofcryptographic equipment. As business became more and more international and the Americanfraction of the world market declined, the pressure to have a single product in both domestic andoffshore markets increased. Such single products were subject to export control and thus the NSAacquired substantial influence not only over what was exported, but also over what was sold in theUnited States.As this is written, a new challenge confronts the public practice of cryptography. The government hasaugmented the widely published and available Data Encryption Standard, with a secret algorithmimplemented in tamper–resistant chips. These chips will incorporate a codified mechanism ofgovernment monitoring. The negative aspects of this “key–escrow” program range from a potentiallydisastrous impact on personal privacy to the high cost of having to add hardware to products that hadpreviously encrypted in software. So far key escrow products are enjoying less than stellar sales andthe scheme has attracted widespread negative comment, especially from the independentcryptographers. Some people, however, see more future in programming than politicking and haveredoubled their efforts to provide the world with strong cryptography that is accessible to publicPage 8 of 666

Applied Cryptography: Second Edition - Bruce Schneierscrutiny.A sharp step back from the notion that export control law could supersede the First Amendmentseemed to have been taken in 1980 when the Federal Register announcement of a revision to ITARincluded the statement: “.provision has been added to make it clear that the regulation of the exportof technical data does not purport to interfere with the First Amendment rights of individuals.” Butthe fact that tension between the First Amendment and the export control laws has not gone awayshould be evident from statements at a conference held by RSA Data Security. NSA’s representativefrom the export control office expressed the opinion that people who published cryptographicprograms were “in a grey area” with respect to the law. If that is so, it is a grey area on which the firstedition of this book has shed some light. Export applications for the book itself have been granted,with acknowledgement that published material lay beyond the authority of the Munitions ControlBoard. Applications to export the enclosed programs on disk, however, have been denied.The shift in the NSA’s strategy, from attempting to control cryptographic research to tightening itsgrip on the development and deployment of cryptographic products, is presumably due to itsrealization that all the great cryptographic papers in the world do not protect a single bit of traffic.Sitting on the shelf, this volume may be able to do no better than the books and papers that precededit, but sitting next to a workstation, where a programmer is writing cryptographic code, it just may.Whitfield DiffieMountain View, CAPrefaceThere are two kinds of cryptography in this world: cryptography that will stop your kid sister fromreading your files, and cryptography that will stop major governments from reading your files. Thisbook is about the latter.If I take a letter, lock it in a safe, hide the safe somewhere in New York, then tell you to read theletter, that’s not security. That’s obscurity. On the other hand, if I take a letter and lock it in a safe,and then give you the safe along with the design specifications of the safe and a hundred identicalsafes with their combinations so that you and the world’s best safecrackers can study the lockingmechanism—and you still can’t open the safe and read the letter—that’s security.For many years, this sort of cryptography was the exclusive domain of the military. The UnitedStates’ National Security Agency (NSA), and its counterparts in the former Soviet Union, England,France, Israel, and elsewhere, have spent billions of dollars in the very serious game of securing theirown communications while trying to break everyone else’s. Private individuals, with far less expertiseand budget, have been powerless to protect their own privacy against these governments.During the last 20 years, public academic research in cryptography has exploded. While classicalcryptography has been long used by ordinary citizens, computer cryptography was the exclusivedomain of the world’s militaries since World War II. Today, state–of–the–art computer cryptographyis practiced outside the secured walls of the military agencies. The layperson can now employ securitypractices that can protect against the most powerful of adversaries—security that may protect againstmilitary agencies for years to come.Do average people really need this kind of security? Yes. They may be planning a political campaign,discussing taxes, or having an illicit affair. They may be designing a new product, discussing aPage 9 of 666

Applied Cryptography: Second Edition - Bruce Schneiermarketing strategy, or planning a hostile business takeover. Or they may be living in a country thatdoes not respect the rights of privacy of its citizens. They may be doing something that they feelshouldn’t be illegal, but is. For whatever reason, the data and communications are personal, private,and no one else’s business.This book is being published in a tumultuous time. In 1994, the Clinton administration approved theEscrowed Encryption Standard (including the Clipper chip and Fortezza card) and signed the DigitalTelephony bill into law. Both of these initiatives try to ensure the government’s ability to conductelectronic surveillance.Some dangerously Orwellian assumptions are at work here: that the government has the right tolisten to private communications, and that there is something wrong with a private citizen trying tokeep a secret from the government. Law enforcement has always been able to conduct court–authorized surveillance if possible, but this is the first time that the people have been forced to takeactive measures to make themselves available for surveillance. These initiatives are not simplygovernment proposals in some obscure area; they are preemptive and unilateral attempts to usurppowers that previously belonged to the people.Clipper and Digital Telephony do not protect privacy; they force individuals to unconditionally trustthat the government will respect their privacy. The same law enforcement authorities who illegallytapped Martin Luther King Jr.’s phones can easily tap a phone protected with Clipper. In the recentpast, local police authorities have either been charged criminally or sued civilly in numerousjurisdictions—Maryland, Connecticut, Vermont, Georgia, Missouri, and Nevada—for conductingillegal wiretaps. It’s a poor idea to deploy a technology that could some day facilitate a police state.The lesson here is that it is insufficient to protect ourselves with laws; we need to protect ourselveswith mathematics. Encryption is too important to be left solely to governments.This book gives you the tools you need to protect your own privacy; cryptography products may bedeclared illegal, but the information will never be.How to Read This BookI wrote Applied Cryptography to be both a lively introduction to the field of cryptography and acomprehensive reference. I have tried to keep the text readable without sacrificing accuracy. Thisbook is not intended to be a mathematical text. Although I have not deliberately given any falseinformation, I do play fast and loose with theory. For those interested in formalism, there are copiousreferences to the academic literature.Chapter 1 introduces cryptography, defines many terms, and briefly discusses precomputercryptography.Chapters 2 through 6 (Part I) describe cryptographic protocols: what people can do withcryptography. The protocols range from the simple (sending encrypted messages from one person toanother) to the complex (flipping a coin over the telephone) to the esoteric (secure and anonymousdigital money exchange). Some of these protocols are obvious; others are almost amazing.Cryptography can solve a lot of problems that most people never realized it could.Chapters 7 through 10 (Part II) discuss cryptographic techniques. All four chapters in this section areimportant for even the most basic uses of cryptography. Chapters 7 and 8 are about keys: how long akey should be in order to be secure, how to generate keys, how to store keys, how to dispose of keys,and so on. Key management is the hardest part of cryptography and often the Achilles’ heel of anotherwise secure system. Chapter 9 discusses different ways of using cryptographic algorithms, andPage 10 of 666

Applied Cryptography: Second Edition - Bruce SchneierChapter 10 gives the odds and ends of algorithms: how to choose, implement, and use algorithms.Chapters 11 through 23 (Part III) list algorithms. Chapter 11 provides the mathematical background.This chapter is only required if you are interested in public–key algorithms. If you just want toimplement DES (or something similar), you can skip ahead. Chapter 12 discusses DES: the algorithm,its history, its security, and some variants. Chapters 13, 14, and 15 discuss other block algorithms; ifyou want something more secure than DES, skip to the section on IDEA and triple–DES. If you wantto read about a bunch of algorithms, some of which may be more secure than DES, read the wholechapter. Chapters 16 and 17 discuss stream algorithms. Chapter 18 focuses on one–way hashfunctions; MD5 and SHA are the most common, although I discuss many more. Chapter 19 discussespublic–key encryption algorithms, Chapter 20 discusses public–key digital signature algorithms,Chapter 21 discusses public–key identification algorithms, and Chapter 22 discusses public–key keyexchange algorithms. The important algorithms are RSA, DSA, Fiat–Shamir, and Diffie–Hellman,respectively. Chapter 23 has more esoteric public–key algorithms and protocols; the math in thischapter is quite complicated, so wear your seat belt.Chapters 24 and 25 (Part IV) turn to the real world of cryptography. Chapter 24 discusses some ofthe current implementations of these algorithms and protocols, while Chapter 25 touches on some ofthe political issues surrounding cryptography. These chapters are by no means intended to becomprehensive.Also included are source code listings for 10 algorithms discussed in Part III. I was unable to includeall the code I wanted to due to space limitations, and cryptographic source code cannot otherwise beexported. (Amazingly enough, the State Department allowed export of the first edition of this bookwith source code, but denied export for a computer disk with the exact same source code on it. Gofigure.) An associated source code disk set includes much more source code than I could fit in thisbook; it is probably the largest collection of cryptographic source code outside a military institution. Ican only send source code disks to U.S. and Canadian citizens living in the U.S. and Canada, buthopefully that will change someday. If you are interested in implementing or playing with thecryptographic algorithms in this book, get the disk. See the last page of the book for details.One criticism of this book is that its encyclopedic nature takes away from its readability. This is true,but I wanted to provide a single reference for those who might come across an algorithm in theacademic literature or in a product. For those who are more interested in a tutorial, I apologize. A lotis being done in the field; this is the first time so much of it has been gathered between two covers.Even so, space considerations forced me to leave many things out. I covered topics that I felt wereimportant, practical, or interesting. If I couldn’t cover a topic in depth, I gave references to articlesand papers that did.I have done my best to hunt down and eradicate all errors in this book, but many have assured methat it is an impossible task. Certainly, the second edition has far fewer errors than the first. Anerrata listing is available from me and will be periodically posted to the Usenet newsgroup sci.crypt. Ifany reader finds an error, please let me know. I’ll send the first person to find each error in the booka free copy of the source code disk.About the AuthorBRUCE SCHNEIER is president of Counterpane Systems, an Oak Park, Illinois consulting firmspecializing in cryptography and computer security. Bruce is also the author of E–Mail Security (JohnWiley & Sons, 1995) and Protect Your Macintosh (Peachpit Press, 1994); and has written dozens ofPage 11 of 666

Applied Cryptography: Second Edition - Bruce Schneierarticles on cryptography for major magazines. He is a contributing editor to Dr. Dobb’s Journal,where he edits the “Algorithms Alley” column, and a contributing editor to Computer andCommunications Security Reviews. Bruce serves on the board of directors of the InternationalAssociation for Cryptologic Research, is a member of the Advisory Board for the Electronic PrivacyInformation Center, and is on the program committee for the New Security Paradigms Workshop. Inaddition, he finds time to give frequent lectures on cryptography, computer security, and privacy.AcknowledgmentsThe list of people who had a hand in this book may seem unending, but all are worthy of mention. Iwould like to thank Don Alvarez, Ross Anderson, Dave Balenson, Karl Barrus, Steve Bellovin, DanBernstein, Eli Biham, Joan Boyar, Karen Cooper, Whit Diffie, Joan Feigenbaum, Phil Karn, NealKoblitz, Xuejia Lai, Tom Leranth, Mike Markowitz, Ralph Merkle, Bill Patton, Peter Pearson,Charles Pfleeger, Ken Pizzini, Bart Preneel, Mark Riordan, Joachim Schurman, and Marc Schwartzfor reading and editing all or parts of the first edition; Marc Vauclair for translating the first editioninto French; Abe Abraham, Ross Anderson, Dave Banisar, Steve Bellovin, Eli Biham, Matt Bishop,Matt Blaze, Gary Carter, Jan Camenisch, Claude CrŽpeau, Joan Daemen, Jorge Davila, Ed Dawson,Whit Diffie, Carl Ellison, Joan Feig

4.2 Subliminal Channel 4.3 Undeniable Digital Signatures 4.4 Designated Confirmer Signatures 4.5 Proxy Signatures 4.6 Group Signatures 4.7 Fail-Stop Digital Signatures 4.8 Computing with Encrypted Data 4.9 Bit Commitment 4.10 Fair Coin Flips 4.11 Mental Poker 4.12 One-W