[PDF] A Graduate Course in Applied Cryptography

View - Download A Graduate Course in Applied Cryptography

Previous PDF

Next PDF

A Graduate Course in Applied Cryptography

Dan Boneh and Victor ShoupVersion 0.5, Jan. 2020

Preface

Cryptography is an indispensable 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 protocols, most notably the Transport Layer Security (TLS) protocol, making it relatively easy to incorporate strong encryption into a wide range of applications. While extremely useful, cryptography is also highly brittle. The most secure cryptographic system can be rendered completely insecure by a single specication or programming error. No amount of unit testing will uncover a security vulnerability in a cryptosystem. Instead, to argue that a cryptosystem is secure, we rely on mathematical modeling and proofs to show that a particular system satises the security properties attributed to it. We often need to introduce certain plausible assumptions to push our security arguments through. This book is about exactly that: constructing practical cryptosystems for which we can argue security under plausible assumptions. The book covers many constructions for dierent tasks in cryptography. For each task we dene 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 unied framework for doing 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 studies 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 unexpected way.

Intended audience and how to use this book

The book is intended to be self contained. Some supplementary material covering basic facts from probability theory and algebra is provided in the appendices. The book is divided into three parts. Part I developssymmetric encryptionwhich explains how two parties, Alice and Bob, can securely exchange information when they have a shared key unknown to the attacker. We discuss data condentiality, data integrity, and the important concept of authenticated en- cryption. Part II develops the concepts ofpublic-key encryptionanddigital signatures, which allow Alice and Bob to communicate securely, without having a pre-shared secret key. Part III is aboutcryptographic protocols, such as protocols for user identication, key ex- change, zero knowledge, and secure computation. ii A beginning reader can read though the book to learn how cryptographic systems work and why they are secure. Every security theorem in the book is followed by a proof idea that explains at a high level why the scheme is secure. On a rst read one can skip over the detailed proofs without losing continuity. A beginning reader may also skip over the mathematical details sections that explore nuances of certain denitions. An advanced reader may enjoy reading the detailed proofs to learn how to do proofs in cryptog- raphy. At the end of every chapter you will nd many exercises that explore additional aspects of the material covered in the chapter. Some exercises rehearse what was learned, but many exercises expand on the material and discuss topics not covered in the chapter.

Status of the book

The current draft contains part I and most of parts II and III. The nal two chapters are forth- coming. We hope you enjoy this write-up. Please send us comments and let us know if you nd typos or mistakes. 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

Jan., 2020

iii

Contents

1 Introduction1

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

1

1.2 Terminology used throughout the book . . . . . . . . . . . . . . . . . . . . . . . . .

1

I Secret key cryptography 3

2 Encryption4

2.1 Shannon ciphers and perfect security . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.1.1 Denition of a Shannon cipher . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.1.2 Perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.3 The bad news . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2 Computational ciphers and semantic security . . . . . . . . . . . . . . . . . . . . . .

13

2.2.1 Denition of a computational cipher . . . . . . . . . . . . . . . . . . . . . .

13

2.2.2 Denition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2.3 Connections to weaker notions of security . . . . . . . . . . . . . . . . . . .

18

2.2.4 Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . .

22

2.2.5 Bit guessing: an alternative characterization of semantic security . . . . . .

25

2.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.3.1 Negligible, super-poly, and poly-bounded functions . . . . . . . . . . . . . .

28

2.3.2 Computational ciphers: the formalities . . . . . . . . . . . . . . . . . . . . .

29

2.3.3 Ecient adversaries and attack games . . . . . . . . . . . . . . . . . . . . .

32

2.3.4 Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . .

34

2.4 A fun application: anonymous routing . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3 Stream ciphers 45

3.1 Pseudo-random generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.1.1 Denition of a pseudo-random generator . . . . . . . . . . . . . . . . . . . .

46

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

48

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

48

3.3 Stream cipher limitations: attacks on the one time pad . . . . . . . . . . . . . . . .

52

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

53

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

53
iv

3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54

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

54

3.4.2 A sequential construction: the Blum-Micali method . . . . . . . . . . . . .

59

3.4.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.5 The next bit test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

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

67

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

70

3.7.1 An example cryptanalysis: linear congruential generators . . . . . . . . . .

70

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

73

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

74

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

76

3.9.1 Security of RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

3.10 Generating random bits in practice . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

3.11 A broader perspective: computational indistinguishability . . . . . . . . . . . . . . .

81

3.11.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

3.12 A fun application: coin

ipping and bit commitment . . . . . . . . . . . . . . . . . . 87

3.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

4 Block ciphers94

4.1 Block ciphers: basic denitions and properties . . . . . . . . . . . . . . . . . . . . .

94

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

96

4.1.2 Ecient implementation of random permutations . . . . . . . . . . . . . . .

99

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

99

4.1.4 Using a block cipher directly for encryption . . . . . . . . . . . . . . . . . .

100

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

104

4.2 Constructing block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . .

105

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

107

4.2.2 Exhaustive search on DES: the DES challenges . . . . . . . . . . . . . . . .

111

4.2.3 Strengthening ciphers against exhaustive search: the 3Econstruction . . . .113

4.2.4 Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

115

4.3 Sophisticated attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . .

120

4.3.1 Algorithmic attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

121

4.3.2 Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

124

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

128

4.3.4 Quantum exhaustive search attacks . . . . . . . . . . . . . . . . . . . . . . .

129

4.4 Pseudo-random functions: basic denitions and properties . . . . . . . . . . . . . .

130

4.4.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

130

4.4.2 Ecient implementation of random functions . . . . . . . . . . . . . . . . .

131

4.4.3 When is a secure block cipher a secure PRF? . . . . . . . . . . . . . . . . .

132

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

136

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

137

4.5 Constructing block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . .

139

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

145

4.6.1 Variable length tree construction . . . . . . . . . . . . . . . . . . . . . . . .

149

4.7 The ideal cipher model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

152
v

4.7.1 Formal denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152

4.7.2 Exhaustive search in the ideal cipher model . . . . . . . . . . . . . . . . . .

153

4.7.3 The Even-Mansour block cipher and theEXconstruction . . . . . . . . . .156

4.7.4 Proof of the Even-Mansour andEXtheorems . . . . . . . . . . . . . . . . .157

4.8 Fun application: comparing information without revealing it . . . . . . . . . . . . .

163

4.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

165

4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

165

5 Chosen Plaintext Attack 174

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

174

5.2 Security against multi-key attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . .

176

5.3 Semantic security against chosen plaintext attack . . . . . . . . . . . . . . . . . . .

178

5.4 Building CPA secure ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

180

5.4.1 A generic hybrid construction . . . . . . . . . . . . . . . . . . . . . . . . . .

180

5.4.2 Randomized counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . .

186

5.4.3 CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

191

5.4.4 Case study: CBC padding in TLS 1.0 . . . . . . . . . . . . . . . . . . . . .

196

5.4.5 Concrete parameters and a comparison of counter and CBC modes . . . . .

196

5.5 Nonce-based encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

198

5.5.1 Nonce-based generic hybrid encryption . . . . . . . . . . . . . . . . . . . . .

200

5.5.2 Nonce-based Counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . .

200

5.5.3 Nonce-based CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

201

5.6 A fun application: revocable broadcast encryption . . . . . . . . . . . . . . . . . . .

202

5.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

205

5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

205

6 Message integrity 212

6.1 Denition of a message authentication code . . . . . . . . . . . . . . . . . . . . . . .

214

6.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

217

6.2 MAC verication queries do not help the attacker . . . . . . . . . . . . . . . . . . .

217

6.3 Constructing MACs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

220

6.4 Prex-free PRFs for long messages . . . . . . . . . . . . . . . . . . . . . . . . . . . .

222

6.4.1 The CBC prex-free secure PRF . . . . . . . . . . . . . . . . . . . . . . . .

223

6.4.2 The cascade prex-free secure PRF . . . . . . . . . . . . . . . . . . . . . . .

226

6.4.3 Extension attacks: CBC and cascade are insecure MACs . . . . . . . . . . .

227

6.5 From prex-free secure PRF to fully secure PRF (method 1): encrypted PRF . . .

228

6.5.1 ECBC and NMAC: MACs for variable length inputs . . . . . . . . . . . . .

229

6.6 From prex-free secure PRF to fully secure PRF (method 2): prex-free encodings .

232

6.6.1 Prex free encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

232

6.7 From prex-free secure PRF to fully secure PRF (method 3): CMAC . . . . . . . .

233

6.8 Converting a block-wise PRF to bit-wise PRF . . . . . . . . . . . . . . . . . . . . .

236

6.9 Case study: ANSI CBC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

237

6.10 Case study: CMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

238

6.11 PMAC: a parallel MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

240

6.12 A fun application: searching on encrypted data . . . . . . . . . . . . . . . . . . . . .

242

6.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

242
vi

6.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .243

7 Message integrity from universal hashing 248

7.1 Universal hash functions (UHFs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

248

7.1.1 Multi-query UHFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

250

7.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

251

7.2 Constructing UHFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

251

7.2.1 Construction 1: UHFs using polynomials . . . . . . . . . . . . . . . . . . .

251

7.2.2 Construction 2: CBC and cascade are computational UHFs . . . . . . . . .

254

7.2.3 Construction 3: a parallel UHF from a small PRF . . . . . . . . . . . . . .

256

7.3 PRF(UHF) composition: constructing MACs using UHFs . . . . . . . . . . . . . . .

258

7.3.1 Using PRF(UHF) composition: ECBC and NMAC security . . . . . . . . .

261

7.3.2 Using PRF(UHF) composition with polynomial UHFs . . . . . . . . . . . .

261

7.3.3 Using PRF(UHF) composition: PMAC

0security . . . . . . . . . . . . . . .262

7.4 The Carter-Wegman MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

262

7.4.1 Using Carter-Wegman with polynomial UHFs . . . . . . . . . . . . . . . . .

269

7.5 Nonce-based MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

269

7.5.1 Secure nonce-based MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . .

269

7.6 Unconditionally secure one-time MACs . . . . . . . . . . . . . . . . . . . . . . . . .

270

7.6.1 Pairwise unpredictable functions . . . . . . . . . . . . . . . . . . . . . . . .

271

7.6.2 Building unpredictable functions . . . . . . . . . . . . . . . . . . . . . . . .

271

7.6.3 From PUFs to unconditionally secure one-time MACs . . . . . . . . . . . .

272

7.7 A fun application: timing attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . .

272

7.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

272

7.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

273

8 Message integrity from collision resistant hashing 283

8.1 Denition of collision resistant hashing . . . . . . . . . . . . . . . . . . . . . . . . .

286

8.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

286

8.2 Building a MAC for large messages . . . . . . . . . . . . . . . . . . . . . . . . . . .

287

8.3 Birthday attacks on collision resistant hash functions . . . . . . . . . . . . . . . . .

289

8.4 The Merkle-Damgard paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

291

8.4.1 Joux's attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

294

8.5 Building Compression Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

294

8.5.1 A simple but inecient compression function . . . . . . . . . . . . . . . . .

295

8.5.2 Davies-Meyer compression functions . . . . . . . . . . . . . . . . . . . . . .

quotesdbs_dbs28.pdfusesText_34

[PDF] decors chretiens de sainte sophie

[PDF] basilique sainte-sophie vikidia

[PDF] frise chronologique de sainte sophie

[PDF] chapelle du palais d'aix

[PDF] fonction dune basilique

[PDF] plan de la basilique sainte sophie

[PDF] sainte sophie plan

[PDF] conseiller d'animation sportive salaire

[PDF] fiches ressources eps lycée professionnel

[PDF] conseiller technique sportif salaire

[PDF] programme eps lycée professionnel 2016

[PDF] conseiller d'animation sportive fiche métier

[PDF] conseiller technique sportif fiche métier

[PDF] programme eps lycée 2010

[PDF] cqp aquagym