VISA - EXHIBIT 1016
`Visa Inc. et al. v. Universal Secure Registry LLC
`IPR2018-01350
`
`

`

`from reviews of the first edition of
`
`APPLIED CRYPTOGRAPHY
`
`Protocols, Algorithms, and Source Code in C
`
`“. .
`
`.’
`.
`. the definitive text on the subject. .
`—-—Software Development Magazine: __-
`k,,,
`
`I
`
`“. .
`
`. good reading for anyone interested in cryptography.”
`-3 YTE
`
`.
`
`_
`
`,.
`
`“This book should be on the shelf of any computer professional
`involved in the use or implementation of cryptography. ”
`—IEEE Software
`
`if ..
`
`:9.
`
`:1;
`
`y“
`
`“
`
`. dazzling .
`“. .
`bookshelf .
`. .”
`
`.
`
`. fascinating. .
`
`.
`
`. This book absolutely must be on your
`
`I
`
`’.
`
`.
`
`. comprehensive .
`
`.
`
`—PC Techniques
`
`. .”
`. an encyclopedic work .
`—The Cryptogram
`
`. a fantastic book on cryptography today. It belongs in the library of
`“. .
`anyone interested in cryptography or anyone who deals with informa-
`tion security and cryptographic systems."
`—Computers 69 Security
`
`. could well have been subtitled ’The on of
`.
`“An encyclopedic survey .
`Encrypting’ .
`.
`. a useful addition to the library of any active or would-be
`security practitioner. "
`
`—Cryptologio
`
`. picks up where
`.
`. .well—inforrned .
`. readable .
`.
`. encyclopedic .
`“. .
`Dorothy Denning’s classic Cryptography and Data Security left off a
`dozen years ago. .
`.
`. This book would be a bargain at twice the price.”
`—,-login:
`
`“This is a marvelous resource—the best book on cryptography and its
`application available today. ”
`
`—Dorothy Denning
`Georgetown University
`
`. Schneier’s book is an indispensable reference and resource. .
`“. .
`recommend it highly. ”
`
`.
`
`. I
`
`—Martin Hellman
`
`Stanford University
`
`

`

` SEC.‘
`
`
` -
`
`PROTOCOLS, AL .-:.'= -
`
`a URCE CODE IN C
`
`New York
`
`John Wiley & Sons, Inc.
`0 Chichester
`0 Brisbane
`0 Toronto
`
`0 Singapore
`
`

`

`Publisher: Katherine Schowalter
`Editor: Phil Sutherland
`
`Assistant Editor: Allison Roarty
`Managing Editor: Robert Aroncls
`Text Design 81 Composition: North Market Street Graphics
`
`Designations used by companies to distinguish their products are often claimed as trademarks. In all
`instances where Iohn Wiley 81 Sons, Inc. is aware of a claim, the product names appear in initial capital
`or all capital letters. Readers, however, should contact the appropriate companies for more complete
`information regarding trademarks and registration.
`
`This text is printed on acid—free paper.
`
`Copyright © 1996 by Bruce Schneier
`Published by Iohn Wiley 3% Sons, Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`This publication is designed to provide accurate and authoritative information in regard to the subject
`matter covered. It is sold with the understanding that the publisher is not engaged in rendering legal,
`accounting, or other professional service. If legal advice or other expert assistance is required, the services
`of a competent professional person should be sought.
`
`In no event will the publisher or author be liable for any consequential, incidental, or indirect damages
`{including damages for loss of business profits, business interruption, loss of business information, and
`the like} arising from the use or inability to use the protocols and algorithms in this book, even if the pub
`lisher or author has been advised of the possibility of such damages.
`
`Some of the protocols and algorithms in this book are protected by patents and copyrights. It is the
`responsibility of the reader to obtain all necessary patent and copyright licenses before implementing in
`software any protocol or algorithm in this book. This book does not contain an exhaustive list of all appli—
`cable patents and copyrights.
`
`Some of the protocols and algorithms in this book are regulated under the United States Department of
`State International Traffic in Arms Regulations. It is the responsibility of the reader to obtain all neces-
`sary export licenses before implementing in software for export any protocol or algorithm in this book.
`
`Reproduction or translation of any part of this work beyond that permitted by section 107 or 108 of the
`1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests
`for permission or further information should be addressed to the Permissions Department, lohn Wiley 8:1.
`Sons, Inc.
`
`Library of Congress Cataloging-fn-Pubffcation Data:
`Schneier, Bruce
`
`Applied Cryptography Second Edition : protocols, algorithms, and source code in C
`/ Bruce Sehneier.
`p.
`cm.
`Includes bibliographical references {p 675}.
`ISBN 0-471-12845-7 {cloth : acid-free paper]. — ISBN
`0-471-11709-9 [paper ; acid—free paper)
`1. Computer security.
`2. Telecomrnunieation—Security measures.
`3. Cryptography.
`I. Title.
`QA76.9.A25835
`1996
`005.8 '2—dc20
`
`95—12398
`CIP
`
`Printed in the United States of America
`10 9 8 7 6 5 4 3 2 l
`
`

`

`F—A
`
`Contents in Brief
`
`Foreword by Whitfield Diffie
`Preface
`
`About the Author
`
`1 Foundations
`
`Part I Cryptographic Protocols
`
`Protocol Building Blocks
`Basic Protocols
`
`Intermediate Protocols
`
`Advanced Protocols
`
`Esoteric Protocols
`
`Part II Cryptographic Techniques
`
`Key Length
`Key Management
`Algorithm Types and Modes
`Using Algorithms
`
`GED-POOH
`
`C3\OOO‘\I
`
`Part III Cryptographic Algorithms
`
`11 Mathematical Background
`12 Data Encryption Standard (DES)
`13 Other Block Ciphers
`14 Still Other Block Ciphers
`15 Combining Block Ciphers
`16 Pseudo-Random—Sequence Generators and Stream Ciphers
`17 Other Stream Ciphers and Real Random—Sequence Generators
`18 One-Way Hash Functions
`19 Public—Key Algorithms
`20 Public-Key Digital Signature Algorithms
`21
`Identification Schemes
`
`22 Key-Exchange Algorithms
`23 Special Algorithms for Protocols
`
`Part IV The Real World
`
`24 Example Implementations
`25 Politics
`
`Afterword by Matt Blaze
`
`Part V Source Code
`
`References
`
`

`

`Contents
`
`Foreword by Whitfield Diffie XV
`Preface XIX
`HOW TO READ THIS BOOK XX
`
`ACKNOWLEDGMENTS xxii
`
`About the Author XXifl
`
`1 FOUNDATIONS 1
`
`TERMINOLOGY 1
`
`STEGANOGRAPHY 9
`
`SUBSTITUTION CIPHERS AND TRANSPOSITION CIPI—IERS
`
`10
`
`SIMPLE XOR 13
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.5 ONE-TIME PADS
`
`15
`
`1.6 COMPUTER ALGORITHMS
`
`17
`
`1.7 LARGE NUMBERS
`
`17
`
`PART! CRYPTOGRAPHIC PROTOCOLS
`
`2 PROTOCOL BUILDING BLOCKS 21
`
`2.1
`
`INTRODUCTION TO PROTOCOLS
`
`21
`
`2.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY 28
`
`2.3 ONE-WAY FUNCTIONS 29
`
`2.4 ONE—WAY HASH FUNCTIONS 30
`
`2.5 COMMUNICATIONS USING PUBLIC-KEY CRYPTOGRAPI-IY 31
`
`2.6 DIGITAL SIGNATURES
`
`34
`
`2.7 DIGITAL SIGNATURES WITH ENCRYPTION 41
`
`2.8 RANDOM AND PSEUDO-RANDOM-SEOUENCE GENERATION 44
`
`

`

`kh—contents
`
`3 BASIC PROTOCOLS 47
`
`3.1 KEY EXCHANGE 47
`
`3.2 AUTHENTICATION 52
`
`3.3 AUTHENTICATION AND KEY EXCHANGE 56
`
`3.4 FORMAL ANALYSIS OF AUTHENTICATION AND KEY-EXCHANGE PROTOCOLS
`
`65
`
`3.5 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 68
`
`3.6 SECRET SPLITTING 70
`
`3.7 SECRET SHARING 71
`
`3.8 CRYFTOGRAPHIC PROTECTION OF DATABASES
`
`73
`
`4 INTERMEDIATE PROTOCOLS 75
`
`4.1
`
`TIMESTAMPING SERVICES
`
`75
`
`4.2 SUBLIMINAL CHANNEL
`
`79
`
`4.3 UNDENIABLE DIGITAL SIGNATURES
`
`81
`
`4.4 DESIGNATED CONFIRMER SIGNATURES
`
`82
`
`4.5
`
`PROXY SIGNATURES
`
`83
`
`4.6 GROUP SIGNATURES
`
`84
`
`4.7 FAIL- STOP DIGITAL SIGNATURES
`
`85
`
`4.8 COMPUTING WITH ENCRYPTED DATA 85
`
`4.9 BIT COMMITMENT
`
`86
`
`4.10 FAIR COIN FLIPS
`
`89
`
`4.11 MENTAL POKER 92
`
`4.12 ONE-WAY ACCUMULATORS
`
`95
`
`4.13 ALL-OR-NOTHING DISCLOSURE OF SECRETS
`
`96
`
`4.14 KEY ESCROW 97
`
`5 ADVANCED PROTOCOLS 101
`
`5.1
`
`ZERO-KNOWLEDGE PROOFS
`
`101
`
`5.2 ZERO-KNOWLEDGE PROOFS OF IDENTITY 109
`
`5.3 BLIND SIGNATURES
`
`112
`
`5.4 IDENTITY-BASED PUBLIC—KEY CRYPTOGRAPHY 1 15
`
`5.5 OBLIVIOUS TRANSFER 116
`
`5.6 OELIVIOUS SIGNATURES
`
`117
`
`5.7 SIMULTANEOUS CONTRACT SIGNING 118
`
`5.8 DIGITAL CERTIFIED MAIL
`
`122
`
`5.9 SIMULTANEOUS EXCHANGE OF SECRETS
`
`123
`
`6 ESOTERIC PROTOCOLS 125
`
`6.1
`
`SECURE ELECTIONS
`
`125
`
`6.2 SECURE MULTIPARTY COMPUTATION 134
`
`6.3 ANONYMOUS MESSAGE BROADCAST
`
`137
`
`6.4 DIGITAL CASH 139
`
`

`

`
`
`PART " CRYPTOGRAPHIC TECHNIQUES
`
`7 KEY LENGTH 151
`
`7.1
`
`SYMMETRIC KEY LENGTH 151
`
`7.2 PUBLIC-KEY KEY LENGTH 158
`
`7.3 COMPARING SYMMETRIC AND PUBLIC-KEY KEY LENGTH 165
`
`7.4 BIRTHDAY ATTACKS AGAINST ONE-WAY HASH FUNCTIONS
`
`165
`
`7.5 HOW LONG SHOULD A KEY BE?
`
`166
`
`7.6 CAVEAT EMPTOR 168
`
`8 KEY MANAGEMENT 169
`
`8.1 GENERATING KEYS
`
`170
`
`8.2 NONLINEAR KEYSPACES
`
`175
`
`8.3 TRANSPERRING KEYS
`
`176
`
`8.4 VERIFYING KEYS
`
`178
`
`8.5 USING KEYS
`
`179
`
`8.6 UPDATING KEYS
`
`180
`
`8.7
`
`STORING KEYS
`
`180
`
`8.8 BACKUP KEYS
`
`181
`
`8.9 COMPROMISED KEYS
`
`182
`
`8.10 LIFETIME OP KEYS
`
`183
`
`8.11 DESTROYING KEYS
`
`184
`
`8.12 PUBLIC-KEY KEY MANAGEMENT
`
`185
`
`9 ALGORITHM TYPES AND MODES 189
`
`9.1
`
`ELECTRONIC CODEBOOK MODE
`
`189
`
`9.2 BLOCK REPLAY 191
`
`9.3 CIPHER BLOCK CHAINING MODE 193
`
`9.4 STREAM CIPHERS
`
`197
`
`9.5 SELE-SYNCHRONIZING STREAM CIPHERS
`
`198
`
`9.6 CIPHER—FEEDBACK MODE 200
`
`9.7 SYNCHRONOUS STREAM CIPHERS 202
`
`9.8 OUTPUT-FEEDBACK MODE 203
`
`9.9 COUNTER MODE 205
`
`9.10 OTHER BLOCK-CIPHER MODES 206
`
`9.11 CHOOSING A CIPHER MODE 208
`
`9.12 INTERLEAVING 210
`
`9.13 BLOCK CIPHERS VERSUS STREAM CIPHERS 210
`
`10 USING ALGORITHMS 213
`
`10.1 CHOOSING AN ALGORITHM 214
`
`10.2
`
`PUBLIC-KEY CRYPTOGRAPHY VERSUS SYMMETRIC CRYPTOGRAPHY 216
`
`10.3 ENCRYPTING COMMUNICATIONS CHANNELS 216
`
`10.4 ENCRYPTING DATA FOR STORAGE 220
`
`10.5 HARDWARE ENCRYPTION VERSUS SOETWARE ENCRYPTION 223
`
`

`

`: : :
`
`Contents
`
`10.6 COMPRESSION, ENCODING, AND ENCRYPTION 226
`10.7 DETECTING ENCRYPTION 226
`
`10.8 HIDING CIPHERTEXT IN CIPHERTEXT 227
`10.9 DESTROYING INFORMATION 228
`
`PART "I CRYPTOGRAPHIC ALGORITHMS
`
`1 1 MATHEMATICAL BACKGROUND 233
`INFORMATION THEORY 233
`
`11.1
`
`11.2 COMPLEXITY THEORY 237
`
`11.3 NUMBER THEORY 242
`
`11.4 FACTORINO 255
`
`11.5
`
`PRIME NUMBER GENERATION 258
`
`11.6 DISCRETE LOGARITHMS IN A FINITE FIELD 261
`
`12 DATA ENCRYPTION STANDARD (DES)
`12.1 BACKGROUND 265
`
`265
`
`12.2 DESCRIPTION OF DES 270
`
`12.3 SECURITY OF DES 278
`
`12.4 DIFFERENTIAL AND LINEAR CRYPTANALYSIS
`12.5 THE REAL DESIGN CRITERIA 293
`
`285
`
`12.6 DES VARIANTS
`
`294
`
`12.7 HOW SECURE Is DES TODAY?
`
`300
`
`13 OTHER BLOCK CIPHERS 303
`LUCIPER 303
`
`13.1
`
`13.2 MADRYGA 304
`
`13.3 NEWDES
`
`306
`
`13.4 FEAL 308
`
`13.5 REDOC 311
`
`13.6 LOKI 314
`
`13.7 KHUEU AND KHAPRE 316
`
`13.8 RC2 318
`
`13.9 IDEA 319
`
`13.10 MMB 325
`
`13.11 CA-1.1
`
`327
`
`13.12 SKIPIACK 328
`
`14 STILL OTHER BLOCK CIPHERS 331
`14.1 GOST 331
`
`14.2 CAST 334
`
`14.3 BLOWFISH 336
`
`14.4 SAFER 339
`
`14.5
`
`3-WAY 341
`
`

`

`contents A
`
`14.6 CRAB 342
`
`14.7 SXALS/MBAL 344
`14.8 RC5
`344
`
`14.9 OTHER BLOCK ALGORITHMS 346
`
`14.10 THEORY OF BLOCK CIPHER DESIGN 346
`
`14.11 USING ONE-WAY HASH FUNCTIONS
`
`351
`
`14.12 CHOOSING A BLOCK ALGORITHM 354
`
`15 COMBINING BLOCK CIPHERS 357
`
`15.1 DOUBLE ENCRYPTION 35 7
`
`15.2 TRIPLE ENCRYPTION 358
`
`15.3 DOUBLING THE BLOCK LENGTH 363
`
`15.4 OTHER MULTIPLE ENCRYPTION SCHEMES
`
`363
`
`15.5 CDMF KEY SHORTENING 366
`
`15.6 WHITENING 366
`
`15.7 CASCADING MULTIPLE BLOCK ALGORITHMS 367
`
`15.8 COMBINING MULTIPLE BLOCK ALGORITHMS
`
`368
`
`16 PSEUDO-RANDOM-SEQUENCE
`GENERATORS AND STREAM CIPHERS 369
`
`16.1
`
`LINEAR CONGRUENTIAL GENERATORS 369
`
`16.2 LINEAR FEEDBACK SHIET REGISTERS
`
`3 72
`
`16.3 DESIGN AND ANALYSIS OF STREAM CIPHERS 379
`
`16.4
`
`STREAM CIPHERS USING LFSRS
`
`381
`
`16.5 A5
`
`389
`
`16.6 HUGHES XPD/KPD 389
`16.7 NANOTEQ 390
`
`16.8 RAMBUTAN 390
`
`16.9 ADDITIVE GENERATORS 390
`
`16.10 GTPPORD 392
`
`16.11 ALGORITHM M 393
`
`16.12 PKZIP 394
`
`17 OTHER STREAM CIPHERS AND REAL
`
`RANDOM-SEQUENCE GENERATORS 397
`17.1 RC4 397
`
`17.2 SEAL 398
`
`17.3 WAKE 400
`
`17.4 FEEDBACK WITH CARRY SHIFT REGISTERS 402
`
`17.5
`
`STREAM CIPHERS USING FCSRS 405
`
`17.6 NONLINEAR-FEEDBACK SHIFT REGISTERS 412
`
`17.7 OTHER STREAM CIPHERS 413
`
`17.8
`
`SYSTEM-THEORETIC APPROACH TO STREAM-CIPHER DESIGN 415
`
`17.9 COMPLEXITY-THEMATIC APPROACH TO STREAM-CIEHER DESIGN 416
`
`17.10 OTHER APPROACHES TO STREAM-CIPHER DESIGN 418
`
`

`

`km—contents
`
`17.11 CASCADING MULTIPLE STREAM CIPHERS
`
`419
`
`17.12 CHOOSING A STREAM CIPHER 420
`
`17.18 GENERATING MULTIPLE STREAMS FROM A
`
`SINGLE PSEUDO-RANDOM-SEQUENCE GENERATOR 420
`
`17.14 REAL RANDOM-SEQUENCE GENERATORS
`
`421
`
`18 ONE-WAY HASH FUNCTIONS 4.29
`
`18.1 BACKGROUND 429
`
`18.2 SNEFRU 431
`
`18.3 N—HASH 432
`
`18.4 MD4 435
`
`18.5 MDS 436
`
`18.6 MD2 441
`
`18.7 SECURE HASH ALGORITHM [SHA]
`18.8 RIPE-MD 445
`
`441
`
`18.9 HAVAL 445
`
`18.10 OTHER ONE-WAY HASH FUNCTIONS 446
`
`18.11 ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS 446
`
`18.12 USING PUBLIC-KEY ALGORITHMS
`
`455
`
`18.18 CHOOSING A ONE-WAY HASH FUNCTION 455
`
`18.14 MESSAGE AUTHENTICATION CODES 455
`
`19 PUBLIC-KEY ALGORITHMS 461
`
`19.1 BACKGROUND 461
`
`19.2 KNAPSACK ALGORITHMS
`
`462
`
`19.3 RSA 466
`
`19.4 POHLIG-HELLMAN 474
`
`19.5 RAEIN 475
`
`19.6 ELGAMAL
`
`476
`
`19.7 McELIECE 479
`
`19.8
`
`ELLIPTIC CURVE CRYPTOSYSTEMS 480
`
`19.9 LUC 481
`
`19.10 FINITE AUTOMATION PUBLIC-KEY CRYPTOSYSTEMS
`
`482
`
`20 PUBLIC-KEY DIGITAL SIGNATURE ALGORITHMS 483
`
`20.1 DIGITAL SIGNATURE ALGORITHM (DSA)
`20.2 DSA VARIANTS 494
`
`483
`
`20.3 GOST DIGITAL SIGNATURE ALGORITHM 495
`
`20.4 DISCRETE LOGARITHM SIGNATURE SCHEMES 496
`
`20.5 ONG-SCHNORR-SHAMIR 498
`
`20.6 ESIGN 499
`
`20.7 CELLULAR AUTOMATA 500
`
`20.8 OTHER PUBLIC-KEY ALGORITHMS 500
`
`21 IDENTIFICATION SCHEMES 503
`
`21.1
`
`FEIGE-FIAT-SHAMIR 503
`
`

`

`21.2 GUILLOU-QUISQUATER 508
`21.3 SCHNORR 510
`
`21.4 CONVERTING IDENTIFICATION SCHEMES TO SIGNATURE SCHEMES
`
`512
`
`22 KEY-EXCHANGE ALGORITHMS 513
`
`22.1 DIFFIE-HELLMAN 513
`
`22.2 STATION-TO-STATION PROTOCOL 516
`
`22.3 SHAMIR’S THREE-PASS PROTOCOL
`
`516
`
`22.4 COMSET 51 7
`
`22.5 ENCRYPTED KEY EXCHANGE
`
`518
`
`22.6 FORTIFIED KEY NEGOTIATION 522
`
`22.7 CONFERENCE KEY DISTRIBUTION AND SECRET BROADCASTING 523
`
`23 SPECIAL ALGORITHMS FOR PROTOCOLS 527
`
`23.1 MULTIPLE-KEY PUBLIC-KEY CRYPTOGRAPHY 527
`
`23.2 SECRET-SHARING ALGORITHMS
`
`528
`
`23.3 SUBLIMINAL CHANNEL 531
`
`23.4 UNDENIAELE DIGITAL SIGNATURES
`
`536
`
`23.5 DESIGNATED CONFIRMER SIGNATURES 539
`
`23.6 COMPUTING WITH ENCRYPTED DATA 540
`
`23.7 FAIR COIN FLIPS
`
`541
`
`23.8 ONE-WAY ACCUMULATORS 543
`
`23.9 ALL-OR-NOTHING DISCLOSURE OF SECRETS
`
`543
`
`23.10 PAIR AND FAILSAFE CRYPTOSYSTEMS 546
`
`23.11 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE
`
`548
`
`23.12 BLIND SIGNATURES
`
`549
`
`23.13 OBLIVIOUS TRANSFER 550
`
`23.14 SECURE MULTIPARTY COMPUTATION 551
`
`23.15 PROBABILISTIC ENCRYPTION 552
`
`23.16 QUANTUM CRYPTOGRAPHY 554
`
`PART IV THE REAL WORLD
`
`24 EXAMPLE IMPLEMENTATIONS 561
`
`24.1
`
`IBM SECRET-KEY MANAGEMENT PROTOCOL
`
`561
`
`24.2 MITRENET 562
`
`24.3 ISBN 563
`
`24.4 STU-III
`
`565
`
`24.5 KERBEROS
`
`566
`
`24.6 KRYPTOKNIGHT 571
`
`24.7 SESAME 572
`
`24.8 IBM COMMON CRYPTOGRAPHIC ARCHITECTURE
`
`573
`
`24.9 ISO AUTHENTICATION FRAMEWORK 574
`
`577
`24.10 PRIVACY-ENHANCED MAIL (PEM)
`24.11 MESSAGE SECURITY PROTOCOL (MSP)
`
`584
`
`

`

`A contents
`
`24.12 PRETTY GOOD PRIVACY [PCP]
`24.13 SMART CARDS
`587
`
`584
`
`24.14 PUBLIC-KEY CRYPTOCRAPHY STANDARDS [PKCS]
`24.15 UNIVERSAL ELECTRONIC PAYMENT SYSTEM (UEPSI
`24.16 CLIPPER 591
`
`588
`589
`
`24.17 CAPSTONE
`593
`24.18 ATSIT MODEL 3600 TELEPHONE SECURITY DEVICE [TSD]
`
`594
`
`25 POLITICS 597
`
`597
`25.1 NATIONAL SECURITY AGENCY (NBA)
`599
`25.2 NATIONAL COMPUTER SECURITY CENTER (NCSC)
`25.3 NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY (NIST)
`25.4 RSA DATA SECURITY, INC.
`603
`25.5 PUBLIC KEY PARTNERS
`604
`25.6 INTERNATIONAL ASSOCIATION FOR CRYPTOGRAPHIC RESEARCH (LACR)
`25.7 RACE INTEGRITY PRIMITIVES EVALUATION (RIPE)
`605
`25.8 CONDITIONAL ACCESS FOR EUROPE (CAPE)
`606
`25.9 ISO/IEC 9979 607
`25.10 PROFESSIONAL, CIVIL LIBERTIES, AND INDUSTRY GROUPS
`25.11 SCI.CRYPT
`608
`
`608
`
`600
`
`605
`
`25.12 CYPHERPUNKS
`
`609
`
`25.13 PATENTS 609
`
`25.14 US. EXPORT RULES
`
`610
`
`25.15 FOREIGN IMPORT AND EXPORT OF CRYPTOCRAPHY 617
`25.16 LEGAL ISSUES 618
`
`Afterword by Matt Blaze
`
`619
`
`PART V SOURCE CODE
`
`Source Code 623
`
`References
`
`679
`
`

`

`A C
`
`HAPTER
`
`2
`
`
`
`Protocol Building Blocks
`
`2.1 INTRODUCTION TO PROTOCOLS
`
`The whole point of cryptography is to solve problems. (Actually, that’s the whole
`point of computers—something many people tend to forget.) Cryptography solves
`problems that involve secrecy, authentication, integrity, and dishonest people. You
`can learn all about cryptographic algorithms and techniques, but these are academic
`unless they can solve a problem. This is why we are going to look at protocols first.
`A protocol is a series of steps, involving two or more parties, designed to accom-
`plish a task. This is an important definition. A ”series of steps” means that the pro-
`tocol has a sequence, from start to finish. Every step must be executed in turn, and
`no step can be taken before the previous step is finished. “Involving two or more
`parties” means that at least two people are required to complete the protocol; one
`person alone does not make a protocol. A person alone can perform a series of steps
`to accomplish a task [like baking a cake), but this is not a protocol. [Someone else
`must eat the cake to make it a protocol.) Finally, ”designed to accomplish a task”
`means that the protocol must achieve something. Something that looks like a pro-
`tocol but does not accomplish a task is not a protocol—it’s a waste of time.
`Protocols have other characteristics as well:
`
`A Everyone involved in the protocol must know the protocol and all of
`the steps to follow in advance.
`
`— Everyone involved in the protocol must agree to follow it.
`
`— The protocol must be unambiguous,» each step must be well defined
`and there must be no chance of a misunderstanding.
`
`— The protocol must be complete, there must be a specified action for
`every possible situation.
`
`

`

`: :: :
`
`CHAPTERZ Protocol Building Blocks
`
`
`
`The protocols in this book are organized as a series of steps. Execution of the pro-
`tocol proceeds linearly through the steps, unless there are instructions to branch to
`another step. Each step involves at least one of two things: coniputations by one or
`more of the parties, or messages sent among the parties.
`A cryptographic protocol is a protocol that uses cryptography. The parties can be
`friends and trust each other implicitly or they can be adversaries and not trust one
`another to give the correct time of day. A cryptographic protocol involves some
`cryptographic algorithm, but generally the goal of the protocol is something beyond
`simple secrecy. The parties participating in the protocol might want to share parts
`of their secrets to compute a value, jointly generate a random sequence, convince
`one another of their identity, or simultaneously sign a contract. The Whole point of
`using cryptography in a protocol is to prevent or detect eavesdropping and cheating.
`If you have never seen these protocols before, they will radically change your ideas
`of what mutually distrustful parties can accomplish over a computer network. In
`general, this can be stated as:
`
`— It should not be possible to do more or learn more than what is spec-
`ified in the protocol.
`
`This is a lot harder than it looks. In the next few chapters I discuss a lot of proto-
`cols. In some of them it is possible for one of the participants to cheat the other. In
`others, it is possible for an eavesdropper to subvert the protocol or learn secret infor-
`mation. Some protocols fail because the designers weren’t thorough enough in their
`requirements definitions. Others fail because their designers weren’t
`thorough
`enough in their analysis. Like algorithms, it is much easier to prove insecurity than
`it is to prove security.
`
`The Purpose of Protocols
`
`In daily life. there are informal protocols for almost everything: ordering goods
`over the telephone, playing poker, voting in an election. No one thinks much about
`these protocols; they have evolved over time, everyone knows how to use them, and
`they work reasonably well.
`These days, more and more human interaction takes place over computer net-
`works instead of face-to—face. Computers need formal protocols to do the same
`things that peOple do without thinking. If you moved from one state to another and
`found a voting booth that looked completely different from the ones you were used
`to, you could easily adapt. Computers are not nearly so flexible.
`Many face-to-face protocols rely on people’s presence to ensure fairness and secu~
`rity. Would you send a stranger a pile of cash to buy groceries for you? Would you
`play poker with someone if you couldn’t see him shuffle and deal? Would you mail
`the government your secret ballot without some assurance of anonymity?
`It is naive to assume that people on computer networks are honest. It is naive to
`assume that the managers of computer networks are honest. It is even naive to
`assume that the designers of computer networks are honest. Most are, but the dis-
`
`

`

`
`
` 2.1 Introduction to Protocols A
`
`honest few can do a lot of damage. By formalizing protocols, we can examine ways
`in which dishonest parties can subvert them. Then we can develop protocols that
`are immune to that subversion.
`
`In addition to formalizing behavior, protocols abstract the process of accomplish-
`ing a task from the mechanism by which the task is accomplished. A communica-
`tions protocol is the same Whether implemented on PCs or VAXs. We can examine
`the protocol without getting bogged down in the implementation details. When we
`are convinced we have a good protocol, we can implement it in everything from
`computers to telephones to intelligent muffin toasters.
`
`The Players
`
`To help demonstrate protocols, I have enlisted the aid of several people (see Table
`2.1). Alice and Bob are the first two. They will perform all general two-person pro—
`tocols. As a rule, Alice will initiate all protocols and Bob will respond. If the proto-
`col requires a third or fourth person, Carol and Dave will perform those roles. Other
`actors will play specialized supporting roles,- they will be introduced later.
`
`Arbitrated Protocols
`
`An arbitrator is a disinterested third party trusted to complete a protocol [see Fig
`ure 2.121). Disinterested means that the arbitrator has no vested interest in the pro-
`tocol and no particular allegiance to any of the parties involved. Trusted means that
`all people involved in the protocol accept what he says as true, what he does as cor-
`rect, and that he will complete his part of the protocol. Arbitrators can help com—
`plete protocols between two mutually distrustful parties.
`In the real world, lawyers are often used as arbitrators. For example, Alice is sell:
`ing a car to Bob, a stranger. Bob wants to pay by check, but Alice has no way of
`knowing if the check is good. Alice wants the check to clear before she turns the
`title over to Bob. Bob, who doesn’t trust Alice any more than she trusts him, doesn’t
`want to hand over a check Without receiving a title.
`
`TABLE 2.1
`
`Dramatis Personae
`
`First participant in all the protocols
`Second participant in all the protocols
`Participant in the three and four~party protocols
`Participant in the four-party protocols
`Eavesdropper
`Malicious active attacker
`Trusted arbitrator
`
`Warden; he’ll be guarding Alice and Bob in some protocols
`Prover
`Verifier
`
`Alice
`Bob
`Carol
`Dave
`Eve
`Mallory
`Trent
`
`Walter
`Peggy
`Victor
`
`

`

`A CHAPTER 2 Protocol Building Blocks
`
`
`
`Alice
`
`Alice
`
`Bob
`
`Trent
`
`
`
`l
`
`(C) Self-enforcing protocol
`
`Figure 2.1 Types of protocols
`
`Enter a lawyer trusted by both. With his help, Alice and Bob can use the following
`protocol to ensure that neither cheats the other:
`
`[1) Alice gives the title to the lawyer.
`
`[2) Bob gives the check to Alice.
`
`[3) Alice deposits the check.
`
`[4) After waiting a specified time period for the check to clear, the lawyer
`gives the title to Bob. If the check does not clear within the specified time
`period, Alice shows proof of this to the lawyer and the lawyer returns the
`title to Alice.
`
`In this protocol, Alice trusts the lawyer not to give Bob the title unless the check
`has cleared, and to give it back to her if the check does not clear. Bob trusts the
`lawyer to hold the title until the check clears, and to give it to him once it does. The
`lawyer doesn’t care if the check clears. He will do his part of the protocol in either
`case, because he will be paid in either case.
`
`

`

`2.1 _Introduction to Protocols
`
`: :: :
`
`In the example, the lawyer is playing the part of an escrow agent. Lawyers also act
`as arbitrators for wills and sometimes for contract negotiations. The various stock
`exchanges act as arbitrators between buyers and sellers.
`Bankers also arbitrate protocols. Bob can use a certified check to buy a car from
`Alice:
`
`[1) Bob writes a check and gives it to the bank.
`
`[2) After putting enough of Bob’s money on hold to cover the check, the bank
`certifies the check and gives it back to Bob.
`
`(3) Alice gives the title to Bob and Bob gives the certified check to Alice.
`
`(4) Alice deposits the check.
`
`This protocol works because Alice trusts the banker’s certification. Alice trusts
`the bank to hold Bob’s money for her, and not to use it to finance shaky real estate
`operations in mosquito-infested countries.
`A notary public is another arbitrator. When Bob receives a notarized document
`from Alice, he is convinced that Alice signed the document voluntarily and with her
`own hand. The notary can, if necessary, stand up in court and attest to that fact.
`The concept of an arbitrator is as old as society. There have always been people—
`rulers, priests, and so on—who have the authority to act fairly. Arbitrators have a
`certain social role and position in our society; betraying the public trust would jeop-
`ardize that. Lawyers who play games with escrow accounts face almost-certain dis-
`barment, for example. This picture of trust doesn’t always exist in the real world,
`but it’s the ideal.
`This ideal can translate to the computer world, but there are several problems
`with computer arbitrators:
`
`—— It is easier to find and trust a neutral third party if you know who the
`party is and can see his face. Two parties suspicious of each other are
`also likely to be suspicious of a faceless arbitrator somewhere else on
`the network.
`
`— The computer network must bear the cost of maintaining an arbitra-
`tor. We all know what lawyers charge; who wants to bear that kind of
`network overhead?
`
`A There is a delay inherent in any arbitrated protocol.
`
`— The arbitrator must deal with every transaction; he is a bottleneck in
`large-scale implementations of any protocol. Increasing the number
`of arbitrators in the implementation can mitigate this problem, but
`that increases the cost.
`
`— Since everyone on the network must trust the arbitrator, he repre-
`sents a vulnerable point for anyone trying to subvert the network.
`
`

`

`A CHAPTER 2 Protocol Building Blocks
`
`Even so, arbitrators still have a role to play. In protocols using a trusted arbitrator,
`the part will be played by Trent.
`
`Adjudicated Protocols
`
`Because of the high cost of hiring arbitrators, arbitrated protocols can be subdi-
`vided into two lower-level subprotocols. One is a nonarbitrated subprotocol, exe-
`cuted every time parties want to complete the protocol. The other is an arbitrated
`subprotocol, executed only in exceptional circumstances—when there is a dispute.
`This special type of arbitrator is called an adjudicator (see Figure 2.1b].
`An adjudicator is also a disinterested and trusted third party. Unlike an arbitrator,
`he is not directly involved in every protocol. The adjudicator is called in only to
`determine Whether a protocol was performed fairly.
`judges are professional adjudicators. Unlike a notary public, a judge is brought in
`only if there is a dispute. Alice and Bob can enter into a contract without a judge. A
`judge never sees the contract until one of them hauls the other into court.
`This contract-signing protocol can be formalized in this way:
`Nonarbitrated subprotocol [executed every time}:
`
`[1] Alice and Bob negotiate the terms of the contract.
`
`(2] Alice signs the contract.
`
`(3) Bob signs the contract.
`
`Adjudicated subprotocol (executed only in case of a dispute):
`
`[4) Alice and Bob appear before a judge.
`
`[5] Alice presents her evidence.
`
`(6) Bob presents his evidence.
`
`(7) The judge rules on the evidence.
`
`The difference between an adjudicator and an arbitrator (as used in this book) is
`that the adjudicator is not always necessary. In a dispute, a judge is called in to adju-
`dicate. If there is no dispute, using a judge is unnecessary.
`There are adjudicated computer protocols. These protocols rely on the parties to
`be honest,- but if someone suspects cheating, a body of data exists so that a trusted
`third party could determine if someone cheated. In a good adjudicated protocol, the
`adjudicator could also determine the cheater’s identity. Instead of preventing cheat-
`ing, adjudicated protocols detect cheating. The inevitability of detection acts as a
`preventive and discourages cheating.
`
`Self-Enforcing Protocols
`
`A self-enforcing protocol is the best type of protocol. The protocol itself guaran-
`tees fairness (see Figure 2.1c). No arbitrator is required to complete the protocol. No
`adjudicator is required to resolve disputes. The protocol is constructed so that there
`
`

`

`2.1
`
`Introduction to Protocols
`
`cannot be any disputes. If one of the parties tries to cheat, the other party immedi-
`ately detects the cheating and the protocol stops. Whatever the cheating party
`hoped would happen by cheating, doesn’t happen.
`In the best of all possible worlds, every protocol would be self-enforcing. Unfor~
`tunately, there is not a self-enforcing protocol for every situation.
`
`Attacks against Protocols
`
`Cryptographic attacks can be directed against the cryptographic algorithms used
`in protocols, against the cryptographic techniques used to implement the algo—
`rithms and protocols, or against the protocols themselves. Since this section of the
`book discusses protocols, I will assume that the cryptographic algorithms and tech—
`niques are secure. I will only examine attacks against the protocols.
`People can try various ways to attack a protocol. Someone not involved in the pro-
`tocol can eavesdrop on some or all of the protocol. This is called a passive attack,
`because the attacker does not affect the protocol. All he can do is observe the proto-
`col and attempt to gain information. This kind of attack corresponds to a ciphertext-
`only attack, as discussed in Section 1.1. Since passive attacks are difficult to detect,
`protocols try to prevent passive attacks rather than detect them. In these protocols,
`the part of the eavesdropper will be played by Eve.
`Alternatively, an attacker could try to alter the protocol to his own advantage. He
`could pretend to be someone else, introduce new messages in the protocol, delete
`existing messages, substitute one message for another, replay old messages, inter—
`rupt a communications channel, or alter stored information in a computer. These
`are called active attacks, because they require active intervention. The form of these
`attacks depends on the network.
`Passive attackers try to gain information about the parties involved in the protocol.
`They collect messages passing among various parties and attempt to cryptanalyze
`them. Active attacks, on the other hand, can have much more diverse objectives. The
`attacker could be interested in obtaining information, degrading system performance,
`corrupting existing information, or gaining unauthorized access to resources.
`Active attacks are much more serious, especially in protocols in which the differ-
`ent parties don’t necessarily trust one another. The attacker does not have to be a
`complete outsider. He could be a legitimate system user. He could be the system
`administrator. There could even be many active attackers working together. Here,
`the part of the malicious active attacker will be played by Mallory.
`It is also possible that the attacker could be one of the parties involved in the pro-
`tocol. He may lie during the protocol or not follow the protocol at all. This type of
`attacker is called a cheater. Passive cheaters follow the protocol, but try to obtain
`more information than the protocol intends them to. Active cheaters disrupt the
`protocol in progress in an attempt to cheat.
`It is very difficult to maintain a protocol’s security if most of the parties involved
`are active cheaters, but sometimes it is possible for legitimate parties to detect that
`active cheating is going on. Certainly, protocols should be secure against passive
`cheating.
`
`

`

`A CHAPTER 2 Protocol Building Blocks
`
`2.2 COMMUNICATIONS USING SYMMETRIC CRYPTOGRAPHY
`
`How do two parties communicate securely? They encrypt their communications, of
`course. The complete protocol is more complicated than that. Let’s look at what
`must happen for Alice to send an encrypted message to Bob.
`
`(1) Alice and Bob agree on a cryptosystem.
`
`(2} Alice and Bob agree 011 a key.
`
`(3) Alice takes her plainteXt message and encrypts it using the encryption
`algorithm and the key. This creates a ciphertext message.
`
`(4) Alice sends the ciphertext message to Bob.
`
`(5] Bob decrypts the ciphertext message with the same algorithm and key and
`reads it.
`
`What can Eve, sitting between Alice and Bob, learn from listening in On this pro-
`tocoliI If all she hears is the transmission in step [4], she must try to cryptanalyze the
`ciphertext. This passive attack is a cipherteXt-only attack; we have algorithms that
`are resistant (as