A Graduate Course in Applied Cryptography.pdf

A Graduate Course in Applied Cryptography

Dan Boneh and Victor Shoup

Version 0.3, December 2016

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 protocols, most

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

strong encryption into a wide range of applications.

This book is about exactly that: constructing practical cr yp t osy st e ms for which we can argue

security under plausible assumptions. The book covers many constructions for di↵erent t ask s 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 doin g 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 t hat 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.

and digital signatures, which allow 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 secure computation.

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 ex p lai n s

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

ii

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 t h e detailed proofs to learn how to do proofs in cryptog-

and let us know if you find typos or mistakes.

Citations: While the curre nt draft is mostly complete, we still do not include c i t ati on s 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

December, 2016

iii

Contents

1 Introduction 1

1.1 Historic cipher s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Terminology used through out th e book . . . . . . . . . . . . . . . . . . . . . . . . . . 1

I Secret key cryptography 3

2.3 Computati onal ciph er s and semantic security . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Definition of a computational cipher . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.2 Definition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . . . 15

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

2.3.4 Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.5 Bit guessing: an alternative characterization of semantic security . . . . . . . 25

2.4 Mathemati c al detail s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4.1 Negligible, super-pol y, and poly-bounded functions . . . . . . . . . . . . . . . 28

2.4.2 Computational ciphers: the formalities . . . . . . . . . . . . . . . . . . . . . . 29

2.4.3 Efficient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . . 32

3.1.1 Definition 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 limi t at ion s: attacks on the one time pad . . . . . . . . . . . . . . . . . 52

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

iv

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

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

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

3.6 Case study: the Salsa and Ch aCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 68

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.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4Blockciphers 94

4.1 Block ciphers: basic definiti on s and properties . . . . . . . . . . . . . . . . . . . . . . 94

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

4.1.2 Efficient 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 Construct i n g block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 105

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

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

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

4.4 Pseudo-ran dom funct i ons : basic definitions and properties . . . . . . . . . . . . . . . 129

4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

4.4.2 Efficient implementation of random functions . . . . . . . . . . . . . . . . . . 130

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

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

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

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

v