ńňđ. 1 |

Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C

by Bruce Schneier

Wiley Computer Publishing, John Wiley & Sons, Inc.

ISBN: 0471128457 Pub Date: 01/01/96

Foreword By Whitfield Diffie

Preface

About the Author

Chapter 1â€”Foundations

1.1 Terminology

1.2 Steganography

1.3 Substitution Ciphers and Transposition Ciphers

1.4 Simple XOR

1.5 One-Time Pads

1.6 Computer Algorithms

1.7 Large Numbers

Part Iâ€”Cryptographic Protocols

Chapter 2â€”Protocol Building Blocks

2.1 Introduction to Protocols

2.2 Communications Using Symmetric Cryptography

2.3 One-Way Functions

2.4 One-Way Hash Functions

2.5 Communications Using Public-Key Cryptography

2.6 Digital Signatures

2.7 Digital Signatures with Encryption

2.8 Random and Pseudo-Random-Sequence Generation

Chapter 3â€”Basic Protocols

3.1 Key Exchange

3.2 Authentication

3.3 Authentication and Key Exchange

3.4 Formal Analysis of Authentication and Key-Exchange Protocols

3.5 Multiple-Key Public-Key Cryptography

3.6 Secret Splitting

3.7 Secret Sharing

3.8 Cryptographic Protection of Databases

Chapter 4â€”Intermediate Protocols

4.1 Timestamping Services

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-Way Accumulators

4.13 All-or-Nothing Disclosure of Secrets

Page 1 of 666

Applied Cryptography: Second Edition - Bruce Schneier

4.14 Key Escrow

Chapter 5â€”Advanced Protocols

5.1 Zero-Knowledge Proofs

5.2 Zero-Knowledge Proofs of Identity

5.3 Blind Signatures

5.4 Identity-Based Public-Key Cryptography

5.5 Oblivious Transfer

5.6 Oblivious Signatures

5.7 Simultaneous Contract Signing

5.8 Digital Certified Mail

5.9 Simultaneous Exchange of Secrets

Chapter 6â€”Esoteric Protocols

6.1 Secure Elections

6.2 Secure Multiparty Computation

6.3 Anonymous Message Broadcast

6.4 Digital Cash

Part IIâ€”Cryptographic Techniques

Chapter 7â€”Key Length

7.1 Symmetric Key Length

7.2 Public-Key Key Length

7.3 Comparing Symmetric and Public-Key Key Length

7.4 Birthday Attacks against One-Way Hash Functions

7.5 How Long Should a Key Be?

7.6 Caveat Emptor

Chapter 8â€”Key Management

8.1 Generating Keys

8.2 Nonlinear Keyspaces

8.3 Transferring Keys

8.4 Verifying Keys

8.5 Using Keys

8.6 Updating Keys

8.7 Storing Keys

8.8 Backup Keys

8.9 Compromised Keys

8.10 Lifetime of Keys

8.11 Destroying Keys

8.12 Public-Key Key Management

Chapter 9â€”Algorithm Types and Modes

9.1 Electronic Codebook Mode

9.2 Block Replay

9.3 Cipher Block Chaining Mode

9.4 Stream Ciphers

9.5 Self-Synchronizing Stream Ciphers

9.6 Cipher-Feedback Mode

9.7 Synchronous Stream Ciphers

9.8 Output-Feedback Mode

9.9 Counter Mode

9.10 Other Block-Cipher Modes

9.11 Choosing a Cipher Mode

9.12 Interleaving

9.13 Block Ciphers versus Stream Ciphers

Page 2 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Chapter 10â€”Using Algorithms

10.1 Choosing an Algorithm

10.2 Public-Key Cryptography versus Symmetric Cryptography

10.3 Encrypting Communications Channels

10.4 Encrypting Data for Storage

10.5 Hardware Encryption versus Software Encryption

10.6 Compression, Encoding, and Encryption

10.7 Detecting Encryption

10.8 Hiding Ciphertext in Ciphertext

10.9 Destroying Information

Part IIIâ€”Cryptographic Algorithms

Chapter 11â€”Mathematical Background

11.1 Information Theory

11.2 Complexity Theory

11.3 Number Theory

11.4 Factoring

11.5 Prime Number Generation

11.6 Discrete Logarithms in a Finite Field

Chapter 12â€”Data Encryption Standard (DES)

12.1 Background

12.2 Description of DES

12.3 Security of DES

12.4 Differential and Linear Cryptanalysis

12.5 The Real Design Criteria

12.6 DES Variants

12.7 How Secure Is DES Today?

Chapter 13â€”Other Block Ciphers

13.1 Lucifer

13.2 Madryga

13.3 NewDES

13.4 FEAL

13.5 REDOC

13.6 LOKI

13.7 Khufu and Khafre

13.8 RC2

13.9 IDEA

13.10 MMB

13.11 CA-1.1

13.12 Skipjack

Chapter 14â€”Still Other Block Ciphers

14.1 GOST

14.2 CAST

14.3 Blowfish

14.4 SAFER

14.5 3-Way

14.6 Crab

14.7 SXAL8/MBAL

14.8 RC5

14.9 Other Block Algorithms

14.10 Theory of Block Cipher Design

14.11 Using one-Way Hash Functions

Page 3 of 666

Applied Cryptography: Second Edition - Bruce Schneier

14.12 Choosing a Block Algorithm

Chapter 15â€”Combining Block Ciphers

15.1 Double Encryption

15.2 Triple Encryption

15.3 Doubling the Block Length

15.4 Other Multiple Encryption Schemes

15.5 CDMF Key Shortening

15.6 Whitening

15.7 Cascading Multiple Block Algorithms

15.8 Combining Multiple Block Algorithms

Chapter 16â€”Pseudo-Random-Sequence Generators and Stream Ciphers

16.1 Linear Congruential Generators

16.2 Linear Feedback Shift Registers

16.3 Design and Analysis of Stream Ciphers

16.4 Stream Ciphers Using LFSRs

16.5 A5

16.6 Hughes XPD/KPD

16.7 Nanoteq

16.8 Rambutan

16.9 Additive Generators

16.10 Gifford

16.11 Algorithm M

16.12 PKZIP

Chapter 17â€”Other Stream Ciphers and Real Random-Sequence Generators

17.1 RC4

17.2 SEAL

17.3 WAKE

17.4 Feedback with Carry Shift Registers

17.5 Stream Ciphers Using FCSRs

17.6 Nonlinear-Feedback Shift Registers

17.7 Other Stream Ciphers

17.8 System-Theoretic Approach to Stream-Cipher Design

17.9 Complexity-Theoretic Approach to Stream-Cipher Design

17.10 Other Approaches to Stream-Cipher Design

17.11 Cascading Multiple Stream Ciphers

17.12 Choosing a Stream Cipher

17.13 Generating Multiple Streams from a Single Pseudo-Random-Sequence

Generator

17.14 Real Random-Sequence Generators

Chapter 18â€”One-Way Hash Functions

18.1 Background

18.2 Snefru

18.3 N- Hash

18.4 MD4

18.5 MD5

18.6 MD2

18.7 Secure Hash Algorithm (SHA)

18.8 RIPE-MD

18.9 HAVAL

18.10 Other One-Way Hash Functions

18.11 One-Way Hash Functions Using Symmetric Block Algorithms

18.12 Using Public-Key Algorithms

18.13 Choosing a One-Way Hash Function

Page 4 of 666

Applied Cryptography: Second Edition - Bruce Schneier

18.14 Message Authentication Codes

Chapter 19â€”Public-Key Algorithms

19.1 Background

19.2 Knapsack Algorithms

19.3 RSA

19.4 Pohlig-Hellman

19.5 Rabin

19.6 ElGamal

19.7 McEliece

19.8 Elliptic Curve Cryptosystems

19.9 LUC

19.10 Finite Automaton Public-Key Cryptosystems

Chapter 20â€”Public-Key Digital Signature Algorithms

20.1 Digital Signature Algorithm (DSA)

20.2 DSA Variants

20.3 Gost Digital Signature Algorithm

20.4 Discrete Logarithm Signature Schemes

20.5 Ong-Schnorr-Shamir

20.6 ESIGN

20.7 Cellular Automata

20.8 Other Public-Key Algorithms

Chapter 21â€”Identification Schemes

21.1 Feige-Fiat-Shamir

21.2 Guillou-Quisquater

21.3 Schnorr

21.4 Converting Identification Schemes to Signature Schemes

Chapter 22â€”Key-Exchange Algorithms

22.1 Diffie-Hellman

22.2 Station-to-Station Protocol

22.3 Shamirâ€™s Three-Pass Protocol

22.4 COMSET

22.5 Encrypted Key Exchange

22.6 Fortified Key Negotiation

22.7 Conference Key Distribution and Secret Broadcasting

Chapter 23â€”Special Algorithms for Protocols

23.1 Multiple-Key Public-Key Cryptography

23.2 Secret-Sharing Algorithms

23.3 Subliminal Channel

23.4 Undeniable Digital Signatures

23.5 Designated Confirmer Signatures

23.6 Computing with Encrypted Data

23.7 Fair Coin Flips

23.8 One-Way Accumulators

23.9 All-or-Nothing Disclosure of Secrets

23.10 Fair and Failsafe Cryptosystems

23.11 Zero-Knowledge Proofs of Knowledge

23.12 Blind Signatures

23.13 Oblivious Transfer

23.14 Secure Multiparty Computation

23.15 Probabilistic Encryption

23.16 Quantum Cryptography

Page 5 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Part IVâ€”The Real World

Chapter 24â€”Example Implementations

24.1 IBM Secret-Key Management Protocol

24.2 MITRENET

24.3 ISDN

24.4 STU-III

24.5 Kerberos

24.6 KryptoKnight

24.7 SESAME

24.8 IBM Common Cryptographic Architecture

24.9 ISO Authentication Framework

24.10 Privacy-Enhanced Mail (PEM)

24.11 Message Security Protocol (MSP)

24.12 Pretty Good Privacy (PGP)

24.13 Smart Cards

24.14 Public-Key Cryptography Standards (PKCS)

24.15 Universal Electronic Payment System (UEPS)

24.16 Clipper

24.17 Capstone

24.18 AT&T Model 3600 Telephone Security Device (TSD)

Chapter 25â€”Politics

25.1 National Security Agency (NSA)

25.2 National Computer Security Center (NCSC)

25.3 National Institute of Standards and Technology (NIST)

25.4 RSA Data Security, Inc.

25.5 Public Key Partners

25.6 International Association for Cryptologic Research (IACR)

25.7 RACE Integrity Primitives Evaluation (RIPE)

25.8 Conditional Access for Europe (CAFE)

25.9 ISO/IEC 9979

25.10 Professional, Civil Liberties, and Industry Groups

25.11 Sci.crypt

25.12 Cypherpunks

25.13 Patents

25.14 U.S. Export Rules

25.15 Foreign Import and Export of Cryptography

25.16 Legal Issues

Afterword by Matt Blaze

Part Vâ€”Source Code

References

Index

Foreword By Whitfield Diffie

The literature of cryptography has a curious history. Secrecy, of course, has always played a central

role, but until the First World War, important developments appeared in print in a more or less

timely fashion and the field moved forward in much the same way as other specialized disciplines. As

late as 1918, one of the most influential cryptanalytic papers of the twentieth century, William F.

Friedmanâ€™s monograph The Index of Coincidence and Its Applications in Cryptography, appeared as a

Page 6 of 666

Applied Cryptography: Second Edition - Bruce Schneier

research report of the private Riverbank Laboratories [577]. And this, despite the fact that the work

had been done as part of the war effort. In the same year Edward H. Hebern of Oakland, California

filed the first patent for a rotor machine [710], the device destined to be a mainstay of military

cryptography 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 thirties

and forties a few basic papers did appear in the open literature and several treatises on the subject

were published, but the latter were farther and farther behind the state of the art. By the end of the

war the transition was complete. With one notable exception, the public literature had died. That

exception was Claude Shannonâ€™s paper â€śThe Communication Theory of Secrecy Systems,â€ť which

appeared in the Bell System Technical Journal in 1949 [1432]. It was similar to Friedmanâ€™s 1918

paper, in that it grew out of wartime work of Shannonâ€™s. After the Second World War ended it was

declassified, possibly by mistake.

From 1949 until 1967 the cryptographic literature was barren. In that year a different sort of

contribution appeared: David Kahnâ€™s history, The Codebreakers [794]. It didnâ€™t contain any new

technical ideas, but it did contain a remarkably complete history of what had gone before, including

mention of some things that the government still considered secret. The significance of The

Codebreakers lay not just in its remarkable scope, but also in the fact that it enjoyed good sales and

made tens of thousands of people, who had never given the matter a momentâ€™s thought, aware of

cryptography. 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 devices

for the Air Force, took his lifelong passion for cryptography to the IBM Watson Laboratory in

Yorktown Heights, New York. There, he began development of what was to become the U.S. Data

Encryption Standard; by the early 1970s several technical reports on this subject by Feistel and his

colleagues 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â€™t

abundant, but what there was included some very shiny nuggets.

Cryptology presents a difficulty not found in normal academic disciplines: the need for the proper

interaction of cryptography and cryptanalysis. This arises out of the fact that in the absence of real

communications requirements, it is easy to propose a system that appears unbreakable. Many

academic 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 that

the 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 indirect

aspects of our contribution was to introduce a problem that does not even appear easy to solve. Now

an 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 a

spectacular 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 appear

in 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 the

prominent scholars who populate the IEEE awards ceremony: I had written the paper I had wanted

to study, but could not find, when I first became seriously interested in cryptography. Had I been able

to go to the Stanford bookstore and pick up a modern cryptography text, I would probably have

learned about the field years earlier. But the only things available in the fall of 1972 were a few classic

Page 7 of 666

Applied Cryptography: Second Edition - Bruce Schneier

papers and some obscure technical reports.

The contemporary researcher has no such problem. The problem now is choosing where to start

among the thousands of papers and dozens of books. The contemporary researcher, yes, but what

about the contemporary programmer or engineer who merely wants to use cryptography? Where

does that person turn? Until now, it has been necessary to spend long hours hunting out and then

studying the research literature before being able to design the sort of cryptographic utilities glibly

described in popular articles.

This is the gap that Bruce Schneierâ€™s Applied Cryptography has come to fill. Beginning with the

objectives of communication security and elementary examples of programs used to achieve these

objectives, Schneier gives us a panoramic view of the fruits of 20 years of public research. The title

says it all; from the mundane objective of having a secure conversation the very first time you call

someone to the possibilities of digital money and cryptographically secure elections, this is where

youâ€™ll find it.

Not satisfied that the book was about the real world merely because it went all the way down to the

code, 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 the

NSA.

When public interest in cryptography was just emerging in the late seventies and early eighties, the

National Security Agency (NSA), Americaâ€™s official cryptographic organ, made several attempts to

quash it. The first was a letter from a longâ€“time NSA employee allegedly, avowedly, and apparently

acting on his own. The letter was sent to the IEEE and warned that the publication of cryptographic

material was a violation of the International Traffic in Arms Regulations (ITAR). This viewpoint

turned out not even to be supported by the regulations themselvesâ€”which contained an explicit

exemption for published materialâ€”but gave both the public practice of cryptography and the 1977

Information Theory Workshop lots of unexpected publicity.

A more serious attempt occurred in 1980, when the NSA funded the American Council on Education

to examine the issue with a view to persuading Congress to give it legal control of publications in the

field of cryptography. The results fell far short of NSAâ€™s ambitions and resulted in a program of

voluntary review of cryptographic papers; researchers were requested to ask the NSAâ€™s opinion on

whether 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 of

cryptographic equipment. As business became more and more international and the American

fraction of the world market declined, the pressure to have a single product in both domestic and

offshore markets increased. Such single products were subject to export control and thus the NSA

acquired substantial influence not only over what was exported, but also over what was sold in the

United States.

As this is written, a new challenge confronts the public practice of cryptography. The government has

augmented the widely published and available Data Encryption Standard, with a secret algorithm

implemented in tamperâ€“resistant chips. These chips will incorporate a codified mechanism of

government monitoring. The negative aspects of this â€śkeyâ€“escrowâ€ť program range from a potentially

disastrous impact on personal privacy to the high cost of having to add hardware to products that had

previously encrypted in software. So far key escrow products are enjoying less than stellar sales and

the scheme has attracted widespread negative comment, especially from the independent

cryptographers. Some people, however, see more future in programming than politicking and have

redoubled their efforts to provide the world with strong cryptography that is accessible to public

Page 8 of 666

Applied Cryptography: Second Edition - Bruce Schneier

scrutiny.

A sharp step back from the notion that export control law could supersede the First Amendment

seemed to have been taken in 1980 when the Federal Register announcement of a revision to ITAR

included the statement: â€ś...provision has been added to make it clear that the regulation of the export

of technical data does not purport to interfere with the First Amendment rights of individuals.â€ť But

the fact that tension between the First Amendment and the export control laws has not gone away

should be evident from statements at a conference held by RSA Data Security. NSAâ€™s representative

from the export control office expressed the opinion that people who published cryptographic

programs were â€śin a grey areaâ€ť with respect to the law. If that is so, it is a grey area on which the first

edition 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 Control

Board. 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 its

grip on the development and deployment of cryptographic products, is presumably due to its

realization 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 preceded

it, but sitting next to a workstation, where a programmer is writing cryptographic code, it just may.

Whitfield Diffie

Mountain View, CA

Preface

There are two kinds of cryptography in this world: cryptography that will stop your kid sister from

reading your files, and cryptography that will stop major governments from reading your files. This

book 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 the

letter, 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 identical

safes with their combinations so that you and the worldâ€™s best safecrackers can study the locking

mechanismâ€”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 United

Statesâ€™ 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 their

own communications while trying to break everyone elseâ€™s. Private individuals, with far less expertise

and 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 classical

cryptography has been long used by ordinary citizens, computer cryptography was the exclusive

domain of the worldâ€™s militaries since World War II. Today, stateâ€“ofâ€“theâ€“art computer cryptography

is practiced outside the secured walls of the military agencies. The layperson can now employ security

practices that can protect against the most powerful of adversariesâ€”security that may protect against

military 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 a

Page 9 of 666

Applied Cryptography: Second Edition - Bruce Schneier

marketing strategy, or planning a hostile business takeover. Or they may be living in a country that

does not respect the rights of privacy of its citizens. They may be doing something that they feel

shouldnâ€™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 the

Escrowed Encryption Standard (including the Clipper chip and Fortezza card) and signed the Digital

Telephony bill into law. Both of these initiatives try to ensure the governmentâ€™s ability to conduct

electronic surveillance.

Some dangerously Orwellian assumptions are at work here: that the government has the right to

listen to private communications, and that there is something wrong with a private citizen trying to

keep 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 take

active measures to make themselves available for surveillance. These initiatives are not simply

government proposals in some obscure area; they are preemptive and unilateral attempts to usurp

powers that previously belonged to the people.

Clipper and Digital Telephony do not protect privacy; they force individuals to unconditionally trust

that the government will respect their privacy. The same law enforcement authorities who illegally

tapped Martin Luther King Jr.â€™s phones can easily tap a phone protected with Clipper. In the recent

past, local police authorities have either been charged criminally or sued civilly in numerous

jurisdictionsâ€”Maryland, Connecticut, Vermont, Georgia, Missouri, and Nevadaâ€”for conducting

illegal 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 ourselves

with 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 be

declared illegal, but the information will never be.

How to Read This Book

I wrote Applied Cryptography to be both a lively introduction to the field of cryptography and a

comprehensive reference. I have tried to keep the text readable without sacrificing accuracy. This

book is not intended to be a mathematical text. Although I have not deliberately given any false

information, I do play fast and loose with theory. For those interested in formalism, there are copious

references to the academic literature.

Chapter 1 introduces cryptography, defines many terms, and briefly discusses precomputer

cryptography.

Chapters 2 through 6 (Part I) describe cryptographic protocols: what people can do with

cryptography. The protocols range from the simple (sending encrypted messages from one person to

another) to the complex (flipping a coin over the telephone) to the esoteric (secure and anonymous

digital 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 are

important for even the most basic uses of cryptography. Chapters 7 and 8 are about keys: how long a

key 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 an

otherwise secure system. Chapter 9 discusses different ways of using cryptographic algorithms, and

Page 10 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Chapter 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 to

implement 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; if

you want something more secure than DES, skip to the section on IDEA and tripleâ€“DES. If you want

to read about a bunch of algorithms, some of which may be more secure than DES, read the whole

chapter. Chapters 16 and 17 discuss stream algorithms. Chapter 18 focuses on oneâ€“way hash

functions; MD5 and SHA are the most common, although I discuss many more. Chapter 19 discusses

publicâ€“key encryption algorithms, Chapter 20 discusses publicâ€“key digital signature algorithms,

Chapter 21 discusses publicâ€“key identification algorithms, and Chapter 22 discusses publicâ€“key key

exchange 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 this

chapter 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 of

the current implementations of these algorithms and protocols, while Chapter 25 touches on some of

the political issues surrounding cryptography. These chapters are by no means intended to be

comprehensive.

Also included are source code listings for 10 algorithms discussed in Part III. I was unable to include

all the code I wanted to due to space limitations, and cryptographic source code cannot otherwise be

exported. (Amazingly enough, the State Department allowed export of the first edition of this book

with source code, but denied export for a computer disk with the exact same source code on it. Go

figure.) An associated source code disk set includes much more source code than I could fit in this

book; it is probably the largest collection of cryptographic source code outside a military institution. I

can only send source code disks to U.S. and Canadian citizens living in the U.S. and Canada, but

hopefully that will change someday. If you are interested in implementing or playing with the

cryptographic 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 the

academic literature or in a product. For those who are more interested in a tutorial, I apologize. A lot

is 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 were

important, practical, or interesting. If I couldnâ€™t cover a topic in depth, I gave references to articles

and papers that did.

I have done my best to hunt down and eradicate all errors in this book, but many have assured me

that it is an impossible task. Certainly, the second edition has far fewer errors than the first. An

errata listing is available from me and will be periodically posted to the Usenet newsgroup sci.crypt. If

any reader finds an error, please let me know. Iâ€™ll send the first person to find each error in the book

a free copy of the source code disk.

About the Author

BRUCE SCHNEIER is president of Counterpane Systems, an Oak Park, Illinois consulting firm

specializing in cryptography and computer security. Bruce is also the author of Eâ€“Mail Security (John

Wiley & Sons, 1995) and Protect Your Macintosh (Peachpit Press, 1994); and has written dozens of

Page 11 of 666

Applied Cryptography: Second Edition - Bruce Schneier

articles 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 and

Communications Security Reviews. Bruce serves on the board of directors of the International

Association for Cryptologic Research, is a member of the Advisory Board for the Electronic Privacy

Information Center, and is on the program committee for the New Security Paradigms Workshop. In

addition, he finds time to give frequent lectures on cryptography, computer security, and privacy.

Acknowledgments

The list of people who had a hand in this book may seem unending, but all are worthy of mention. I

would like to thank Don Alvarez, Ross Anderson, Dave Balenson, Karl Barrus, Steve Bellovin, Dan

Bernstein, Eli Biham, Joan Boyar, Karen Cooper, Whit Diffie, Joan Feigenbaum, Phil Karn, Neal

Koblitz, Xuejia Lai, Tom Leranth, Mike Markowitz, Ralph Merkle, Bill Patton, Peter Pearson,

Charles Pfleeger, Ken Pizzini, Bart Preneel, Mark Riordan, Joachim Schurman, and Marc Schwartz

for reading and editing all or parts of the first edition; Marc Vauclair for translating the first edition

into 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 Feigenbaum, Niels Ferguson, Matt Franklin, Rosario Gennaro, Dieter

Gollmann, Mark Goresky, Richard Graveman, Stuart Haber, Jingman He, Bob Hogue, Kenneth

Iversen, Markus Jakobsson, Burt Kaliski, Phil Karn, John Kelsey, John Kennedy, Lars Knudsen,

Paul Kocher, John Ladwig, Xuejia Lai, Arjen Lenstra, Paul Leyland, Mike Markowitz, Jim Massey,

Bruce McNair, William Hugh Murray, Roger Needham, Clif Neuman, Kaisa Nyberg, Luke

Oâ€™Connor, Peter Pearson, RenĹ˝ Peralta, Bart Preneel, Yisrael Radai, Matt Robshaw, Michael Roe,

Phil Rogaway, Avi Rubin, Paul Rubin, Selwyn Russell, Kazue Sako, Mahmoud Salmasizadeh,

Markus Stadler, Dmitry Titov, Jimmy Upton, Marc Vauclair, Serge Vaudenay, Gideon Yuval, Glen

Zorn, and several anonymous government employees for reading and editing all or parts of the second

edition; Lawrie Brown, Leisa Condie, Joan Daemen, Peter Gutmann, Alan Insley, Chris Johnston,

John Kelsey, Xuejia Lai, Bill Leininger, Mike Markowitz, Richard Outerbridge, Peter Pearson, Ken

Pizzini, Colin Plumb, RSA Data Security, Inc., Michael Roe, Michael Wood, and Phil Zimmermann

for providing source code; Paul MacNerland for creating the figures for the first edition; Karen

Cooper for copyedit ing the second edition; Beth Friedman for proofreading the second edition; Carol

Kennedy for indexing the second edition; the readers of sci.crypt and the Cypherpunks mailing list

for commenting on ideas, answering questions, and finding errors in the first edition; Randy Seuss for

providing Internet access; Jeff Duntemann and Jon Erickson for helping me get started; assorted

random Insleys for the impetus, encouragement, support, conversations, friendship, and dinners; and

AT&T Bell Labs for firing me and making this all possible. All these people helped to create a far

better book than I could have created alone.

Bruce Schneier

Oak Park, Ill.

schneier@counterpane.com

Chapter 1

Foundations

1.1 Terminology

Sender and Receiver

Suppose a sender wants to send a message to a receiver. Moreover, this sender wants to send the

Page 12 of 666

Applied Cryptography: Second Edition - Bruce Schneier

message securely: She wants to make sure an eavesdropper cannot read the message.

Messages and Encryption

A message is plaintext (sometimes called cleartext). The process of disguising a message in such a way

as to hide its substance is encryption. An encrypted message is ciphertext. The process of turning

ciphertext back into plaintext is decryption. This is all shown in Figure 1.1.

(If you want to follow the ISO 7498-2 standard, use the terms â€śencipherâ€ť and â€śdecipher.â€ť It seems

that some cultures find the terms â€śencryptâ€ť and â€śdecryptâ€ť offensive, as they refer to dead bodies.)

The art and science of keeping messages secure is cryptography, and it is practiced by

cryptographers. Cryptanalysts are practitioners of cryptanalysis, the art and science of breaking

ciphertext; that is, seeing through the disguise. The branch of mathematics encompassing both

cryptography and cryptanalysis is cryptology and its practitioners are cryptologists. Modern

cryptologists are generally trained in theoretical mathematicsâ€”they have to be.

Figure 1.1 Encryption and Decryption.

Plaintext is denoted by M, for message, or P, for plaintext. It can be a stream of bits, a text file, a

bitmap, a stream of digitized voice, a digital video image...whatever. As far as a computer is

concerned, M is simply binary data. (After this chapter, this book concerns itself with binary data and

computer cryptography.) The plaintext can be intended for either transmission or storage. In any

case, M is the message to be encrypted.

Ciphertext is denoted by C. It is also binary data: sometimes the same size as M, sometimes larger. (By

combining encryption with compression, C may be smaller than M. However, encryption does not

accomplish this.) The encryption function E, operates on M to produce C. Or, in mathematical

notation:

E(M) = C

In the reverse process, the decryption function D operates on C to produce M:

D(C) = M

Since the whole point of encrypting and then decrypting a message is to recover the original plaintext,

the following identity must hold true:

D(E(M)) = M

Authentication, Integrity, and Nonrepudiation

In addition to providing confidentiality, cryptography is often asked to do other jobs:

â€” Authentication. It should be possible for the receiver of a message to ascertain its

origin; an intruder should not be able to masquerade as someone else.

â€” Integrity. It should be possible for the receiver of a message to verify that it has not

been modified in transit; an intruder should not be able to substitute a false message for a

legitimate one.

Page 13 of 666

Applied Cryptography: Second Edition - Bruce Schneier

â€” Nonrepudiation. A sender should not be able to falsely deny later that he sent a

message.

These are vital requirements for social interaction on computers, and are analogous to face-to-face

interactions. That someone is who he says he is...that someoneâ€™s credentialsâ€”whether a driverâ€™s

license, a medical degree, or a passportâ€”are valid...that a document purporting to come from a

person actually came from that person.... These are the things that authentication, integrity, and

nonrepudiation provide.

Algorithms and Keys

A cryptographic algorithm, also called a cipher, is the mathematical function used for encryption and

decryption. (Generally, there are two related functions: one for encryption and the other for

decryption.)

If the security of an algorithm is based on keeping the way that algorithm works a secret, it is a

restricted algorithm. Restricted algorithms have historical interest, but are woefully inadequate by

todayâ€™s standards. A large or changing group of users cannot use them, because every time a user

leaves the group everyone else must switch to a different algorithm. If someone accidentally reveals

the secret, everyone must change their algorithm.

Even more damning, restricted algorithms allow no quality control or standardization. Every group

of users must have their own unique algorithm. Such a group canâ€™t use off-the-shelf hardware or

software products; an eavesdropper can buy the same product and learn the algorithm. They have to

write their own algorithms and implementations. If no one in the group is a good cryptographer, then

they wonâ€™t know if they have a secure algorithm.

Despite these major drawbacks, restricted algorithms are enormously popular for low-security

applications. Users either donâ€™t realize or donâ€™t care about the security problems inherent in their

system.

Modern cryptography solves this problem with a key, denoted by K. This key might be any one of a

large number of values. The range of possible values of the key is called the keyspace. Both the

encryption and decryption operations use this key (i.e., they are dependent on the key and this fact is

denoted by the k subscript), so the functions now become:

EK(M) = C

DK(C) = M

Those functions have the property that (see Figure 1.2):

DK(EK(M)) = M

Some algorithms use a different encryption key and decryption key (see Figure 1.3). That is, the

encryption key, K1, is different from the corresponding decryption key, K2. In this case:

EK1(M) = C

DK2(C) = M

DK2(EK1 (M)) = M

Page 14 of 666

Applied Cryptography: Second Edition - Bruce Schneier

All of the security in these algorithms is based in the key (or keys); none is based in the details of the

algorithm. This means that the algorithm can be published and analyzed. Products using the

algorithm can be mass-produced. It doesnâ€™t matter if an eavesdropper knows your algorithm; if she

doesnâ€™t know your particular key, she canâ€™t read your messages.

Figure 1.2 Encryption and decryption with a key.

Figure 1.3 Encryption and decryption with two different keys.

A cryptosystem is an algorithm, plus all possible plaintexts, ciphertexts, and keys.

Symmetric Algorithms

There are two general types of key-based algorithms: symmetric and public-key. Symmetric

algorithms, sometimes called conventional algorithms, are algorithms where the encryption key can

be calculated from the decryption key and vice versa. In most symmetric algorithms, the encryption

key and the decryption key are the same. These algorithms, also called secret-key algorithms, single-

key algorithms, or one-key algorithms, require that the sender and receiver agree on a key before they

can communicate securely. The security of a symmetric algorithm rests in the key; divulging the key

means that anyone could encrypt and decrypt messages. As long as the communication needs to

remain secret, the key must remain secret.

Encryption and decryption with a symmetric algorithm are denoted by:

EK(M) = C

DK(C) = M

Symmetric algorithms can be divided into two categories. Some operate on the plaintext a single bit

(or sometimes byte) at a time; these are called stream algorithms or stream ciphers. Others operate on

the plaintext in groups of bits. The groups of bits are called blocks, and the algorithms are called

block algorithms or block ciphers. For modern computer algorithms, a typical block size is 64 bitsâ€”

large enough to preclude analysis and small enough to be workable. (Before computers, algorithms

generally operated on plaintext one character at a time. You can think of this as a stream algorithm

operating on a stream of characters.)

Public-Key Algorithms

Public-key algorithms (also called asymmetric algorithms) are designed so that the key used for

encryption is different from the key used for decryption. Furthermore, the decryption key cannot (at

least in any reasonable amount of time) be calculated from the encryption key. The algorithms are

called â€śpublic-keyâ€ť because the encryption key can be made public: A complete stranger can use the

encryption key to encrypt a message, but only a specific person with the corresponding decryption

key can decrypt the message. In these systems, the encryption key is often called the public key, and

Page 15 of 666

Applied Cryptography: Second Edition - Bruce Schneier

the decryption key is often called the private key. The private key is sometimes also called the secret

key, but to avoid confusion with symmetric algorithms, that tag wonâ€™t be used here.

Encryption using public key K is denoted by:

EK(M) = C

Even though the public key and private key are different, decryption with the corresponding private

key is denoted by:

DK(C) = M

Sometimes, messages will be encrypted with the private key and decrypted with the public key; this is

used in digital signatures (see Section 2.6). Despite the possible confusion, these operations are

denoted by, respectively:

EK(M) = C

DK(C) = M

Cryptanalysis

The whole point of cryptography is to keep the plaintext (or the key, or both) secret from

eavesdroppers (also called adversaries, attackers, interceptors, interlopers, intruders, opponents, or

simply the enemy). Eavesdroppers are assumed to have complete access to the communications

between the sender and receiver.

Cryptanalysis is the science of recovering the plaintext of a message without access to the key.

Successful cryptanalysis may recover the plaintext or the key. It also may find weaknesses in a

cryptosystem that eventually lead to the previous results. (The loss of a key through noncryptanalytic

means is called a compromise.)

An attempted cryptanalysis is called an attack. A fundamental assumption in cryptanalysis, first

enunciated by the Dutchman A. Kerckhoffs in the nineteenth century, is that the secrecy must reside

entirely in the key [794]. Kerckhoffs assumes that the cryptanalyst has complete details of the

cryptographic algorithm and implementation. (Of course, one would assume that the CIA does not

make a habit of telling Mossad about its cryptographic algorithms, but Mossad probably finds out

anyway.) While real-world cryptanalysts donâ€™t always have such detailed information, itâ€™s a good

assumption to make. If others canâ€™t break an algorithm, even with knowledge of how it works, then

they certainly wonâ€™t be able to break it without that knowledge.

There are four general types of cryptanalytic attacks. Of course, each of them assumes that the

cryptanalyst has complete knowledge of the encryption algorithm used:

1. Ciphertext-only attack. The cryptanalyst has the ciphertext of several messages, all of

which have been encrypted using the same encryption algorithm. The cryptanalystâ€™s job is to

recover the plaintext of as many messages as possible, or better yet to deduce the key (or keys)

used to encrypt the messages, in order to decrypt other messages encrypted with the same keys.

Given: C1 = Ek(P1), C2 = Ek(P2),...Ci = Ek(Pi)

Deduce: Either P1, P2,...Pi; k; or an algorithm to infer Pi+1 from Ci+1 = Ek(Pi+1)

2. Known-plaintext attack. The cryptanalyst has access not only to the ciphertext of several

messages, but also to the plaintext of those messages. His job is to deduce the key (or keys) used to

Page 16 of 666

Applied Cryptography: Second Edition - Bruce Schneier

encrypt the messages or an algorithm to decrypt any new messages encrypted with the same key (or

keys).

Given: P1, C1 = Ek(P1), P2, C2 = Ek(P2),...Pi, Ci = Ek(Pi)

Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek(Pi+1)

3. Chosen-plaintext attack. The cryptanalyst not only has access to the ciphertext and

associated plaintext for several messages, but he also chooses the plaintext that gets encrypted. This

is more powerful than a known-plaintext attack, because the cryptanalyst can choose specific

plaintext blocks to encrypt, ones that might yield more information about the key. His job is to

deduce the key (or keys) used to encrypt the messages or an algorithm to decrypt any new messages

encrypted with the same key (or keys).

Given: P1, C1 = Ek(P1), P2, C2 = Ek(P2),...Pi, Ci = Ek(Pi), where the cryptanalyst gets to

choose P1, P2,...Pi

Deduce: Either k, or an algorithm to infer Pi+1 from Ci+1 = Ek(Pi+1)

4. Adaptive-chosen-plaintext attack. This is a special case of a chosen-plaintext attack.

Not only can the cryptanalyst choose the plaintext that is encrypted, but he can also modify his

choice based on the results of previous encryption. In a chosen-plaintext attack, a cryptanalyst

might just be able to choose one large block of plaintext to be encrypted; in an adaptive-chosen-

plaintext attack he can choose a smaller block of plaintext and then choose another based on the

results of the first, and so forth.

There are at least three other types of cryptanalytic attack.

5. Chosen-ciphertext attack. The cryptanalyst can choose different ciphertexts to be

decrypted and has access to the decrypted plaintext. For example, the cryptanalyst has access to

a tamperproof box that does automatic decryption. His job is to deduce the key.

Given: C1, P1 = Dk(C1), C2, P2 = Dk(C2),...Ci, Pi = Dk(Ci)

Deduce: k

This attack is primarily applicable to public-key algorithms and will be discussed in Section

19.3. A chosen-ciphertext attack is sometimes effective against a symmetric algorithm as well.

(Sometimes a chosen-plaintext attack and a chosen-ciphertext attack are together known as a

chosen-text attack.)

6. Chosen-key attack. This attack doesnâ€™t mean that the cryptanalyst can choose the key;

it means that he has some knowledge about the relationship between different keys. Itâ€™s strange

and obscure, not very practical, and discussed in Section 12.4.

7. Rubber-hose cryptanalysis. The cryptanalyst threatens, blackmails, or tortures

someone until they give him the key. Bribery is sometimes referred to as a purchase-key attack.

These are all very powerful attacks and often the best way to break an algorithm.

Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It is

not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe

someone to encrypt a chosen message. You may not even have to bribe someone; if you give a message

to an ambassador, you will probably find that it gets encrypted and sent back to his country for

consideration. Many messages have standard beginnings and endings that might be known to the

cryptanalyst. Encrypted source code is especially vulnerable because of the regular appearance of

keywords: #define, struct, else, return. Encrypted executable code has the same kinds of problems:

functions, loop structures, and so on. Known-plaintext attacks (and even chosen-plaintext attacks)

were successfully used against both the Germans and the Japanese during World War II. David

Kahnâ€™s books [794,795,796] have historical examples of these kinds of attacks.

Page 17 of 666

Applied Cryptography: Second Edition - Bruce Schneier

And donâ€™t forget Kerckhoffsâ€™s assumption: If the strength of your new cryptosystem relies on the fact

that the attacker does not know the algorithmâ€™s inner workings, youâ€™re sunk. If you believe that

keeping the algorithmâ€™s insides secret improves the security of your cryptosystem more than letting

the academic community analyze it, youâ€™re wrong. And if you think that someone wonâ€™t disassemble

your code and reverse-engineer your algorithm, youâ€™re naĂŻve. (In 1994 this happened with the RC4

algorithmâ€”see Section 17.1.) The best algorithms we have are the ones that have been made public,

have been attacked by the worldâ€™s best cryptographers for years, and are still unbreakable. (The

National Security Agency keeps their algorithms secret from outsiders, but they have the best

cryptographers in the world working within their wallsâ€”you donâ€™t. Additionally, they discuss their

algorithms with one another, relying on peer review to uncover any weaknesses in their work.)

Cryptanalysts donâ€™t always have access to the algorithms, as when the United States broke the

Japanese diplomatic code PURPLE during World War II [794]â€”but they often do. If the algorithm is

being used in a commercial security program, it is simply a matter of time and money to disassemble

the program and recover the algorithm. If the algorithm is being used in a military communications

system, it is simply a matter of time and money to buy (or steal) the equipment and reverse-engineer

the algorithm.

Those who claim to have an unbreakable cipher simply because they canâ€™t break it are either geniuses

or fools. Unfortunately, there are more of the latter in the world. Beware of people who extol the

virtues of their algorithms, but refuse to make them public; trusting their algorithms is like trusting

snake oil.

Good cryptographers rely on peer review to separate the good algorithms from the bad.

Security of Algorithms

Different algorithms offer different degrees of security; it depends on how hard they are to break. If

the cost required to break an algorithm is greater than the value of the encrypted data, then youâ€™re

probably safe. If the time required to break an algorithm is longer than the time the encrypted data

must remain secret, then youâ€™re probably safe. If the amount of data encrypted with a single key is

less than the amount of data necessary to break the algorithm, then youâ€™re probably safe.

I say â€śprobablyâ€ť because there is always a chance of new breakthroughs in cryptanalysis. On the

other hand, the value of most data decreases over time. It is important that the value of the data

always remain less than the cost to break the security protecting it.

Lars Knudsen classified these different categories of breaking an algorithm. In decreasing order of

severity [858]:

1. Total break. A cryptanalyst finds the key, K, such that DK(C) = P.

2. Global deduction. A cryptanalyst finds an alternate algorithm, A, equivalent to DK(C),

without knowing K.

3. Instance (or local) deduction. A cryptanalyst finds the plaintext of an intercepted

ciphertext.

4. Information deduction. A cryptanalyst gains some information about the key or

plaintext. This information could be a few bits of the key, some information about the form of

the plaintext, and so forth.

An algorithm is unconditionally secure if, no matter how much ciphertext a cryptanalyst has, there is

not enough information to recover the plaintext. In point of fact, only a one-time pad (see Section 1.5)

Page 18 of 666

Applied Cryptography: Second Edition - Bruce Schneier

is unbreakable given infinite resources. All other cryptosystems are breakable in a ciphertext-only

attack, simply by trying every possible key one by one and checking whether the resulting plaintext is

meaningful. This is called a brute-force attack (see Section 7.1).

Cryptography is more concerned with cryptosystems that are computationally infeasible to break. An

algorithm is considered computationally secure (sometimes called strong) if it cannot be broken with

available resources, either current or future. Exactly what constitutes â€śavailable resourcesâ€ť is open to

interpretation.

You can measure the complexity (see Section 11.1) of an attack in different ways:

1. Data complexity. The amount of data needed as input to the attack.

2. Processing complexity. The time needed to perform the attack. This is often called the

work factor.

3. Storage requirements. The amount of memory needed to do the attack.

As a rule of thumb, the complexity of an attack is taken to be the minimum of these three factors.

Some attacks involve trading off the three complexities: A faster attack might be possible at the

expense of a greater storage requirement.

Complexities are expressed as orders of magnitude. If an algorithm has a processing complexity of

2128, then 2128 operations are required to break the algorithm. (These operations may be complex and

time-consuming.) Still, if you assume that you have enough computing speed to perform a million

operations every second and you set a million parallel processors against the task, it will still take over

1019 years to recover the key. Thatâ€™s a billion times the age of the universe.

While the complexity of an attack is constant (until some cryptanalyst finds a better attack, of course),

computing power is anything but. There have been phenomenal advances in computing power during

the last half-century and there is no reason to think this trend wonâ€™t continue. Many cryptanalytic

attacks are perfect for parallel machines: The task can be broken down into billions of tiny pieces and

none of the processors need to interact with each other. Pronouncing an algorithm secure simply

because it is infeasible to break, given current technology, is dicey at best. Good cryptosystems are

designed to be infeasible to break with the computing power that is expected to evolve many years in

the future.

Historical Terms

Historically, a code refers to a cryptosystem that deals with linguistic units: words, phrases, sentences,

and so forth. For example, the word â€śOCELOTâ€ť might be the ciphertext for the entire phrase

â€śTURN LEFT 90 DEGREES,â€ť the word â€śLOLLIPOPâ€ť might be the ciphertext for â€śTURN RIGHT

90 DEGREES,â€ť and the words â€śBENT EARâ€ť might be the ciphertext for â€śHOWITZER.â€ť Codes of

this type are not discussed in this book; see [794,795]. Codes are only useful for specialized

circumstances. Ciphers are useful for any circumstance. If your code has no entry for

â€śANTEATERS,â€ť then you canâ€™t say it. You can say anything with a cipher.

1.2 Steganography

Steganography serves to hide secret messages in other messages, such that the secretâ€™s very existence

is concealed. Generally the sender writes an innocuous message and then conceals a secret message on

the same piece of paper. Historical tricks include invisible inks, tiny pin punctures on selected

characters, minute differences between handwritten characters, pencil marks on typewritten

Page 19 of 666

Applied Cryptography: Second Edition - Bruce Schneier

characters, grilles which cover most of the message except for a few characters, and so on.

More recently, people are hiding secret messages in graphic images. Replace the least significant bit of

each byte of the image with the bits of the message. The graphical image wonâ€™t change appreciablyâ€”

most graphics standards specify more gradations of color than the human eye can noticeâ€”and the

message can be stripped out at the receiving end. You can store a 64-kilobyte message in a 1024 Ă—

1024 grey-scale picture this way. Several public-domain programs do this sort of thing.

Peter Waynerâ€™s mimic functions obfuscate messages. These functions modify a message so that its

statistical profile resembles that of something else: the classifieds section of The New York Times, a

play by Shakespeare, or a newsgroup on the Internet [1584,1585]. This type of steganography wonâ€™t

fool a person, but it might fool some big computers scanning the Internet for interesting messages.

1.3 Substitution Ciphers and Transposition Ciphers

Before computers, cryptography consisted of character-based algorithms. Different cryptographic

algorithms either substituted characters for one another or transposed characters with one another.

The better algorithms did both, many times each.

Things are more complex these days, but the philosophy remains the same. The primary change is

that algorithms work on bits instead of characters. This is actually just a change in the alphabet size:

from 26 elements to two elements. Most good cryptographic algorithms still combine elements of

substitution and transposition.

Substitution Ciphers

A substitution cipher is one in which each character in the plaintext is substituted for another

character in the ciphertext. The receiver inverts the substitution on the ciphertext to recover the

plaintext.

In classical cryptography, there are four types of substitution ciphers:

â€” A simple substitution cipher, or monoalphabetic cipher, is one in which each character

of the plaintext is replaced with a corresponding character of ciphertext. The cryptograms in

newspapers are simple substitution ciphers.

â€” A homophonic substitution cipher is like a simple substitution cryptosystem, except a

single character of plaintext can map to one of several characters of ciphertext. For example,

â€śAâ€ť could correspond to either 5, 13, 25, or 56, â€śBâ€ť could correspond to either 7, 19, 31, or 42,

and so on.

â€” A polygram substitution cipher is one in which blocks of characters are encrypted in

groups. For example, â€śABAâ€ť could correspond to â€śRTQ,â€ť â€śABBâ€ť could correspond to â€śSLL,â€ť

and so on.

â€” A polyalphabetic substitution cipher is made up of multiple simple substitution ciphers.

For example, there might be five different simple substitution ciphers used; the particular one

used changes with the position of each character of the plaintext.

The famous Caesar Cipher, in which each plaintext character is replaced by the character three to the

right modulo 26 (â€śAâ€ť is replaced by â€śD,â€ť â€śBâ€ť is replaced by â€śE,â€ť..., â€śWâ€ť is replaced by â€śZ,â€ť â€śXâ€ť is

replaced by â€śA,â€ť â€śYâ€ť is replaced by â€śB,â€ť and â€śZâ€ť is replaced by â€śCâ€ť) is a simple substitution cipher.

Itâ€™s actually even simpler, because the ciphertext alphabet is a rotation of the plaintext alphabet and

not an arbitrary permutation.

Page 20 of 666

Applied Cryptography: Second Edition - Bruce Schneier

ROT13 is a simple encryption program commonly found on UNIX systems; it is also a simple

substitution cipher. In this cipher, â€śAâ€ť is replaced by â€śN,â€ť â€śBâ€ť is replaced by â€śO,â€ť and so on. Every

letter is rotated 13 places.

Encrypting a file twice with ROT13 restores the original file.

P = ROT13 (ROT13 (P))

ROT13 is not intended for security; it is often used in Usenet posts to hide potentially offensive text, to

avoid giving away the solution to a puzzle, and so forth.

Simple substitution ciphers can be easily broken because the cipher does not hide the underlying

frequencies of the different letters of the plaintext. All it takes is about 25 English characters before a

good cryptanalyst can reconstruct the plaintext [1434]. An algorithm for solving these sorts of ciphers

can be found in [578,587,1600,78,1475,1236,880]. A good computer algorithm is [703].

Homophonic substitution ciphers were used as early as 1401 by the Duchy of Mantua [794]. They are

much more complicated to break than simple substitution ciphers, but still do not obscure all of the

statistical properties of the plaintext language. With a known-plaintext attack, the ciphers are trivial

to break. A ciphertext-only attack is harder, but only takes a few seconds on a computer. Details are

in [1261].

Polygram substitution ciphers are ciphers in which groups of letters are encrypted together. The

Playfair cipher, invented in 1854, was used by the British during World War I [794]. It encrypts pairs

of letters together. Its cryptanalysis is discussed in [587,1475,880]. The Hill cipher is another example

of a polygram substitution cipher [732]. Sometimes you see Huffman coding used as a cipher; this is

an insecure polygram substitution cipher.

Polyalphabetic substitution ciphers were invented by Leon Battista in 1568 [794]. They were used by

the Union army during the American Civil War. Despite the fact that they can be broken easily

[819,577,587,794] (especially with the help of computers), many commercial computer security

products use ciphers of this form [1387,1390,1502]. (Details on how to break this encryption scheme,

as used in WordPerfect, can be found in [135,139].) The VigenĂ¨re cipher, first published in 1586, and

the Beaufort cipher are also examples of polyalphabetic substitution ciphers.

Polyalphabetic substitution ciphers have multiple one-letter keys, each of which is used to encrypt one

letter of the plaintext. The first key encrypts the first letter of the plaintext, the second key encrypts

the second letter of the plaintext, and so on. After all the keys are used, the keys are recycled. If there

were 20 one-letter keys, then every twentieth letter would be encrypted with the same key. This is

called the period of the cipher. In classical cryptography, ciphers with longer periods were

significantly harder to break than ciphers with short periods. There are computer techniques that can

easily break substitution ciphers with very long periods.

A running-key cipherâ€”sometimes called a book cipherâ€”in which one text is used to encrypt another

text, is another example of this sort of cipher. Even though this cipher has a period the length of the

text, it can also be broken easily [576,794].

Transposition Ciphers

In a transposition cipher the plaintext remains the same, but the order of characters is shuffled

around. In a simple columnar transposition cipher, the plaintext is written horizontally onto a piece of

Page 21 of 666

Applied Cryptography: Second Edition - Bruce Schneier

graph paper of fixed width and the ciphertext is read off vertically (see Figure 1.4). Decryption is a

matter of writing the ciphertext vertically onto a piece of graph paper of identical width and then

reading the plaintext off horizontally.

Cryptanalysis of these ciphers is discussed in [587,1475]. Since the letters of the ciphertext are the

same as those of the plaintext, a frequency analysis on the ciphertext would reveal that each letter has

approximately the same likelihood as in English. This gives a very good clue to a cryptanalyst, who

can then use a variety of techniques to determine the right ordering of the letters to obtain the

plaintext. Putting the ciphertext through a second transposition cipher greatly enhances security.

There are even more complicated transposition ciphers, but computers can break almost all of them.

The German ADFGVX cipher, used during World War I, is a transposition cipher combined with a

simple substitution. It was a very complex algorithm for its day but was broken by Georges Painvin, a

French cryptanalyst [794].

Although many modern algorithms use transposition, it is troublesome because it requires a lot of

memory and sometimes requires messages to be only certain lengths. Substitution is far more

common.

Rotor Machines

In the 1920s, various mechanical encryption devices were invented to automate the process of

encryption. Most were based on the concept of a rotor, a mechanical wheel wired to perform a general

substitution.

A rotor machine has a keyboard and a series of rotors, and implements a version of the VigenĂ¨re

cipher. Each rotor is an arbitrary permutation of the alphabet, has 26 positions, and performs a

simple substitution. For example, a rotor might be wired to substitute â€śFâ€ť for â€śA,â€ť â€śUâ€ť for â€śB,â€ť â€śLâ€ť

for â€śC,â€ť and so on. And the output pins of one rotor are connected to the input pins of the next.

Figure 1.4 Columnar transposition cipher.

For example, in a 4-rotor machine the first rotor might substitute â€śFâ€ť for â€śA,â€ť the second might

substitute â€śYâ€ť for â€śF,â€ť the third might substitute â€śEâ€ť for â€śY,â€ť and the fourth might substitute â€śCâ€ť

for â€śEâ€ť; â€śCâ€ť would be the output ciphertext. Then some of the rotors shift, so next time the

substitutions will be different.

It is the combination of several rotors and the gears moving them that makes the machine secure.

Because the rotors all move at different rates, the period for an n-rotor machine is 26n. Some rotor

machines can also have a different number of positions on each rotor, further frustrating

cryptanalysis.

The best-known rotor device is the Enigma. The Enigma was used by the Germans during World

War II. The idea was invented by Arthur Scherbius and Arvid Gerhard Damm in Europe. It was

patented in the United States by Arthur Scherbius [1383]. The Germans beefed up the basic design

considerably for wartime use.

Page 22 of 666

Applied Cryptography: Second Edition - Bruce Schneier

The German Enigma had three rotors, chosen from a set of five, a plugboard that slightly permuted

the plaintext, and a reflecting rotor that caused each rotor to operate on each plaintext letter twice. As

complicated as the Enigma was, it was broken during World War II. First, a team of Polish

cryptographers broke the German Enigma and explained their attack to the British. The Germans

modified their Enigma as the war progressed, and the British continued to cryptanalyze the new

versions. For explanations of how rotor ciphers work and how they were broken, see

[794,86,448,498,446,880,1315,1587,690]. Two fascinating accounts of how the Enigma was broken are

[735,796].

Further Reading

This is not a book about classical cryptography, so I will not dwell further on these subjects. Two

excellent precomputer cryptology books are [587,1475]; [448] presents some modern cryptanalysis of

cipher machines. Dorothy Denning discusses many of these ciphers in [456] and [880] has some fairly

complex mathematical analysis of the same ciphers. Another older cryptography text, which discusses

analog cryptography, is [99]. An article that presents a good overview of the subject is [579]. David

Kahnâ€™s historical cryptography books are also excellent [794,795,796].

1.4 Simple XOR

XOR is exclusive-or operation: â€˜^â€™ in C or in mathematical notation. Itâ€™s a standard operation on

bits:

0 0=0

0 1=1

1 0=1

1 1=0

Also note that:

a a=0

a b b=a

The simple-XOR algorithm is really an embarrassment; itâ€™s nothing more than a VigenĂ¨re

polyalphabetic cipher. Itâ€™s here only because of its prevalence in commercial software packages, at

least those in the MS-DOS and Macintosh worlds [1502,1387]. Unfortunately, if a software security

program proclaims that it has a â€śproprietaryâ€ť encryption algorithmâ€”significantly faster than DESâ€”

the odds are that it is some variant of this.

/* Usage: crypto key input_file output_file */

void main (int argc, char *argv[])

{

FILE *fi, *fo;

char *cp;

int c;

if ((cp = argv[1]) && *cp!='\0') {

if ((fi = fopen(argv[2], â€śrbâ€ť)) != NULL) {

if ((fo = fopen(argv[3], â€śwbâ€ť)) != NULL) {

while ((c = getc(fi)) != EOF) {

if (!*cp) cp = argv[1];

c ^= *(cp++);

putc(c,fo);

Page 23 of 666

Applied Cryptography: Second Edition - Bruce Schneier

}

fclose(fo);

}

fclose(fi);

}

}

ńňđ. 1 |