应用密码学研究生课程A Graduate Course in Applied Cryptography

AGraduateCourseinAppliedCryptography

Dan Boneh Victor Shoup

August 17, 2015

Preface

Cryptography is an in di spensable tool used to protect information in computing systems. It is

used everywhere and by billions of people worldwide on a daily basis. It is used to protect data at

rest and data in motion. Cryptographic systems are an integral part of standard prot ocols, most

notably the Transport Layer Security (TLS) protocol, making it relatively easy to incorporate

strong encryption into a wide range of app l ic at i ons .

This b ook is about exactly that: constructing practical cryptosystems for which we can argue

security under plausible assumptions . The book covers many constructions for di↵erent tasks in

cryptography. For each task we define a precise security goal that we aim to achieve and then

present constructions that achieve the required goal. To analyze the constructions, we develop a

unified framework for d oi ng cryptographic proofs. A reader who masters this framework will be

capable of applying it to new constructions that may not be covered in the book.

Throughout the book we present many case st ud i es to survey how deployed systems operate.

We describe common mistakes to avoid as well as attacks on real-world systems that illustrate the

importance of rigor in cryptography. We end every chapter with a fun application that applies the

ideas in the chapter in some unexpect e d way.

and digital signatures, which allows Alice and Bob to do the same, but without having a shared,

secret key. The third part is about cryptographic protocols, such as protocols for user identification,

key exchange, and secur e computation.

A beginnin g reader can read though the book to learn how cry pt ogr aph i c systems work and

why they are secure. Every security theor em in the book is followed by a pro of idea that explains

at a high level why the scheme is secure. On a first read one can skip over the detailed proofs

2

without losing continuity. A beginning reader may also skip over the mathematical details sections

that explore nuances of certain definitions .

An advanced reader may enjoy reading the detailed proofs t o learn how to do p r oofs in cryptog-

Citations: While the current draft is mostly complete, we still do not include citations and

references to the many works on which this book is based. Those will be coming soon and will be

presented in the Notes section at the end of every chapter.

Dan Boneh and Victor Shoup

August, 2015

3

Contents

1 Introduction 15

1.1 Historic ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Termi nol ogy used throughout the book . . . . . . . . . . . . . . . . . . . . . . . . . . 15

I Secret key cryptography 17

2 Encryption 18

2.3.1 Definition of a computational cipher . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2 Definition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.3 Connections to weaker notions of security . . . . . . . . . . . . . . . . . . . . 32

2.3.4 Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . . . 36

2.3.5 Bit guessing: an alternative characteri zat i on of semantic security . . . . . . . 39

2.4 Mathemati c al details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.4.1 Negligible, super-poly, an d poly-bounded functions . . . . . . . . . . . . . . . 42

2.4.2 Computational ciphers: t he formalities . . . . . . . . . . . . . . . . . . . . . . 43

2.4.3 Efficient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . . 46

2.4.4 Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2 Stream ciphers: encryption with a PRG . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 Stream cipher limitations: attacks on the one t i me pad . . . . . . . . . . . . . . . . . 65

3.3.1 The two-time pad is insecure . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4

3.3.2 The one-time pad is malleable . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.4.1 A parallel construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.6 Case study: the Salsa and ChaCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 80

3.7 Case study: linear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.7.1 An example cryptanalysi s : linear congruential generators . . . . . . . . . . . 83

3.7.2 The subset sum generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.8 Case study: cryptanalysis of the DVD encryption system . . . . . . . . . . . . . . . 87

3.9 Case study: cryptanalysis of the RC4 stream cipher . . . . . . . . . . . . . . . . . . 89

3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4Blockciphers 107

4.1 Block ciphers: basic definitions and properties . . . . . . . . . . . . . . . . . . . . . . 107

4.1.1 Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.1.2 Efficient implementation of random permutations . . . . . . . . . . . . . . . . 112

4.1.3 Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.1.4 Using a block c i ph er directly for encryption . . . . . . . . . . . . . . . . . . . 113

4.1.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

4.2 Construct i n g block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 118

4.2.1 Case study: DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

4.3.3 Fault-injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . . 141

4.3.4 Quantum exhaustive search at t acks . . . . . . . . . . . . . . . . . . . . . . . . 142

4.4 Pseudo-ran dom functions: basic definitions and properties . . . . . . . . . . . . . . . 143

4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.4.2 Efficient implementation of random functions . . . . . . . . . . . . . . . . . . 144

4.4.3 When is a s ecu r e block cipher a secure PRF? . . . . . . . . . . . . . . . . . . 145

4.4.4 Constructing PRGs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 149

4.4.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.5 Construct i n g block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 151

4.6 The tree construction: from PRGs to PRFs . . . . . . . . . . . . . . . . . . . . . . . 158

5