第1页 / 共400页
第2页 / 共400页
第3页 / 共400页
第4页 / 共400页
第5页 / 共400页
第6页 / 共400页
第7页 / 共400页
第8页 / 共400页
应用密码学研究生课程A Graduate Course in Applied Cryptography.pdf
1 Introduction
1.1 Historic ciphers
1.2 Terminology used throughout the book
I Secret key cryptography
2 Encryption
2.1 Introduction
2.2 Shannon ciphers and perfect security
2.2.1 Definition of a Shannon cipher
2.2.2 Perfect security
2.2.3 The bad news
2.3 Computational ciphers and semantic security
2.3.1 Definition of a computational cipher
2.3.2 Definition of semantic security
2.3.3 Connections to weaker notions of security
2.3.4 Consequences of semantic security
2.3.5 Bit guessing: an alternative characterization of semantic security
2.4 Mathematical details
2.4.1 Negligible, super-poly, and poly-bounded functions
2.4.2 Computational ciphers: the formalities
2.4.3 Efficient adversaries and attack games
2.4.4 Semantic security: the formalities
2.5 A fun application: anonymous routing
2.6 Notes
2.7 Exercises
3 Stream ciphers
3.1 Pseudo-random generators
3.1.1 Definition of a pseudo-random generator
3.1.2 Mathematical details
3.2 Stream ciphers: encryption with a PRG
3.3 Stream cipher limitations: attacks on the one time pad
3.3.1 The two-time pad is insecure
3.3.2 The one-time pad is malleable
3.4 Composing PRGs
3.4.1 A parallel construction
3.4.2 A sequential construction: the Blum-Micali method
3.4.3 Mathematical details
3.5 The next bit test
3.6 Case study: the Salsa and ChaCha PRGs
3.7 Case study: linear generators
3.7.1 An example cryptanalysis: linear congruential generators
3.7.2 The subset sum generator
3.8 Case study: cryptanalysis of the DVD encryption system
3.9 Case study: cryptanalysis of the RC4 stream cipher
3.9.1 Security of RC4
3.10 Generating random bits in practice
3.11 A broader perspective: computational indistinguishability
3.11.1 Mathematical details
3.12 A fun application: coin flipping and commitments
3.13 Notes
3.14 Exercises
4 Block ciphers
4.1 Block ciphers: basic definitions and properties
4.1.1 Some implications of security
4.1.2 Efficient implementation of random permutations
4.1.3 Strongly secure block ciphers
4.1.4 Using a block cipher directly for encryption
4.1.5 Mathematical details
4.2 Constructing block ciphers in practice
4.2.1 Case study: DES
4.2.2 Exhaustive search on DES: the DES challenges
4.2.3 Strengthening ciphers against exhaustive search: the 3E construction
4.2.4 Case study: AES
4.3 Sophisticated attacks on block ciphers
4.3.1 Algorithmic attacks
4.3.2 Side-channel attacks
4.3.3 Fault-injection attacks on AES
4.3.4 Quantum exhaustive search attacks
4.4 Pseudo-random functions: basic definitions and properties
4.4.1 Definitions
4.4.2 Efficient implementation of random functions
4.4.3 When is a secure block cipher a secure PRF?
4.4.4 Constructing PRGs from PRFs
4.4.5 Mathematical details
4.5 Constructing block ciphers from PRFs
4.6 The tree construction: from PRGs to PRFs
4.6.1 Variable length tree construction
4.7 The ideal cipher model
4.7.1 Formal definitions
4.7.2 Exhaustive search in the ideal cipher model
4.7.3 The Even-Mansour block cipher and the EX construction
4.7.4 Proof of the Even-Mansour and EX theorems
4.8 Fun application: comparing information without revealing it
4.9 Notes
4.10 Exercises
5 Chosen Plaintext Attack
5.1 Introduction
5.2 Security against multi-key attacks
5.3 Semantic security against chosen plaintext attack
5.4 Building CPA secure ciphers
5.4.1 A generic hybrid construction
5.4.2 Counter mode
5.4.3 CBC mode
5.4.4 Case study: CBC padding in TLS 1.0
5.4.5 Concrete parameters and a comparison of counter and CBC modes
5.5 Nonce-based encryption
5.5.1 Nonce-based generic hybrid encryption
5.5.2 Nonce-based Counter mode
5.5.3 Nonce-based CBC mode
5.6 A fun application: revocation schemes
5.7 Notes
5.8 Exercises
6 Message integrity
6.1 Definition of a message authentication code
6.1.1 Mathematical details
6.2 MAC verification queries do not help the attacker
6.3 Constructing MACs from PRFs
6.4 Prefix-free PRFs for long messages
6.4.1 The CBC prefix-free secure PRF
6.4.2 The cascade prefix-free secure PRF
6.4.3 Extension attacks: CBC and cascade are insecure MACs
6.5 From prefix-free secure PRF to fully secure PRF (method 1): encrypted PRF
6.5.1 ECBC and NMAC: MACs for variable length inputs
6.6 From prefix-free secure PRF to fully secure PRF (method 2): prefix-free encodings
6.6.1 Prefix free encodings
6.7 From prefix-free secure PRF to fully secure PRF (method 3): CMAC
6.8 Converting a block-wise PRF to bit-wise PRF
6.9 Case study: ANSI CBC-MAC
6.10 Case study: CMAC
6.11 PMAC: a parallel MAC
6.12 A fun application: searching on encrypted data
6.13 Notes
6.14 Exercises
7 Message integrity from universal hashing
7.1 Universal hash functions (UHFs)
7.1.1 Multi-query UHFs
7.1.2 Mathematical details
7.2 Constructing UHFs
7.2.1 Construction 1: UHFs using polynomials
7.2.2 Construction 2: CBC and cascade are computational UHFs
7.2.3 Construction 3: a parallel UHF from a small PRF
7.3 PRF-UHF composition: constructing MACs using UHFs
7.3.1 Using PRF-UHF composition: ECBC and NMAC security
7.3.2 Using PRF-UHF composition with polynomial UHFs
7.3.3 Using PRF-UHF composition: PMAC0 security
7.4 The Carter-Wegman MAC
7.4.1 Using Carter-Wegman with polynomial UHFs
7.5 Nonce-based MACs
7.5.1 Secure nonce-based MACs
7.6 Unconditionally secure one-time MACs
7.6.1 Pairwise unpredictable functions
7.6.2 Building unpredictable functions
7.6.3 From PUFs to unconditionally secure one-time MACs
7.7 A fun application: timing attacks
7.8 Notes
7.9 Exercises
8 Message integrity from collision resistant hashing
8.1 Definition of collision resistant hashing
8.1.1 Mathematical details
8.2 Building a MAC for large messages
8.3 Birthday attacks on collision resistant hash functions
8.4 The Merkle-Damgård paradigm
8.4.1 Joux's attack
8.5 Building Compression Functions
8.5.1 A simple but inefficient compression function
8.5.2 Davies-Meyer compression functions
8.5.3 Collision resistance of Davies-Meyer
8.6 Case study: SHA-256
8.6.1 Other Merkle-Damgård hash functions
8.7 Case study: HMAC
8.7.1 Security of two-key nest
8.7.2 The HMAC standard
8.7.3 Davies-Meyer is a secure PRF in the ideal cipher model
8.8 The Sponge Construction and SHA3
8.8.1 The sponge construction
8.8.2 Case study: SHA3, SHAKE256, and SHAKE512
8.9 Key derivation and the random oracle model
8.9.1 The key derivation problem
8.9.2 Random oracles: a useful heuristic
8.9.3 Random oracles: safe modes of operation
8.9.4 The leftover hash lemma
8.9.5 Case study: HKDF
8.10 Security without collision resistance
8.10.1 Second preimage resistance
8.10.2 Randomized hash functions: target collision resistance
8.10.3 TCR from 2nd-preimage resistance
8.10.4 Using target collision resistance
8.11 A fun application: commitment schemes
8.12 Notes
8.13 Exercises
9 Authenticated Encryption
9.1 Authenticated encryption: definitions
9.2 Chosen ciphertext attacks
9.2.1 Chosen ciphertext attacks: a motivating example
9.2.2 Chosen ciphertext attacks: definition
9.2.3 Authenticated encryption implies chosen ciphertext security
9.3 Encryption as an abstract interface
9.4 Authenticated encryption ciphers from generic composition
9.4.1 Encrypt-then-MAC
9.4.2 MAC-then-encrypt is not generally secure: padding oracle attacks on SSL
9.4.3 More padding oracle attacks.
9.4.4 Secure instances of MAC-then-encrypt
9.4.5 Encrypt-then-MAC or MAC-then-encrypt?
9.5 Nonce-based authenticated encryption with associated data
9.6 Case study: Galois counter mode (GCM)
9.7 Case study: the TLS 1.3 record protocol
9.8 Case study: an attack on non-atomic decryption in SSH
9.9 Case study: 802.11b WEP, a badly broken system
9.10 Case study: IPsec
9.11 A fun application: private information retrieval
9.12 Notes
9.13 Exercises
II Public key cryptography
10 Public key tools
10.1 A toy problem: anonymous key exchange
10.2 Trapdoor function schemes
10.2.1 Key exchange using a one-way trapdoor function scheme
10.3 A trapdoor function scheme based on RSA
10.3.1 Key exchange based on the RSA assumption
10.3.2 Mathematical details
10.4 Trapdoor function-pair schemes
10.4.1 Key exchange using an unpredictable trapdoor function-pair scheme
10.5 A trapdoor function-pair scheme based on discrete logarithms
10.5.1 Key exchange based on the CDH and DDH assumptions
10.5.2 Mathematical details
10.5.3 Decision Diffie-Hellman
10.6 Attacks on the anonymous Diffie-Hellman protocol
10.7 Merkle puzzles: a partial solution to key exchange using block ciphers
10.8 Collision resistant hash functions from number-theoretic primitves
10.8.1 The representation problem
10.9 Notes
10.10 Chapter summary
10.11 Exercises
11 Public key encryption
11.1 Introduction
11.1.1 Two further examples
11.2 Security against eavesdropping
11.2.1 Mathematical details
11.3 Encryption based on trapdoor function schemes and RSA
11.3.1 Instatiating ETF with RSA
11.4 ElGamal encryption
11.4.1 ElGamal and random oracles
11.4.2 ElGamal and secure key derivation functions
11.5 Implications of semantic security
11.5.1 Semantic security against chosen plaintext attack
11.5.2 Encryption as an abstract service
12 Chosen ciphertext secure public key encryption
12.1 Introduction
12.2 CCA secure encryption from trapdoor function schemes and RSA
12.2.1 Instatiating ETF with RSA
12.3 Implications of CCA security
12.3.1 CCA security against chosen plaintext attack
12.3.2 Encryption as an abstract service
12.4 CCA secure ElGamal encryption
12.4.1 CCA security for basic ElGamal encryption
12.4.2 Twin ElGamal encryption
12.4.3 CCA security without random oracles
12.5 CCA security via a generic transformation
12.5.1 Instantiation with ElGamal
12.5.2 Instantiation with a trapdoor function scheme
12.6 OAEP+
12.6.1 Instantiating OAEP+ with RSA
12.7 Case study: PKCS1 version 1.5
12.8 Case study: PGP
12.9 Case study: P1363
12.9.1 Case study:
12.10 Chapter Summary
12.11 Exercises
13 Digital signatures
13.1 Definition of a digital signature
13.1.1 Secure signatures
13.1.2 Mathematical details
13.1.3 Security against multi-key attacks
13.2 Extending the message space with collision resistance
13.2.1 Extending the message space using TCR functions
13.3 Repeated one-way functions: a simple lemma
13.4 Signatures from trapdoor functions: the full domain hash
13.4.1 Signatures based on the RSA trapdoor function
13.4.2 Security of RSA-FDH
13.4.3 A tight security proof in the random oracle model
13.4.4 Case study: PKCS1 v1.5
13.5 Signatures secure without random oracles
13.5.1 The basic GHR signature system
13.5.2 The strong RSA assumption
13.5.3 Security of the basic GHR system
13.5.4 Chameleon hashing
13.5.5 The full GHR signature system
13.6 Signcryption: combining signatures and encryption
13.7 Case study: legal aspects of digital signatures
13.8 Further topics
13.9 Notes
13.10 Chapter summary
13.11 Exercises
14 Fast signatures from one-way functions
14.1 Lamport signatures
14.1.1 A general Lamport framework
14.1.2 Optimized Lamport
14.2 HORS signatures: Lamport in the random oracle model
14.2.1 Merkle-HORS: reducing the public key size
14.3 Comparing one-time signatures
14.4 Applications of one-time signatures
14.4.1 Online/offline signatures from one-time signatures
14.4.2 Authenticating streamed data with one-time signatures
14.5 Merkle stateless signatures: many-time signatures from one-time signatures
14.5.1 Extending the number of signatures from a q-time signature
14.5.2 The complete Merkle stateless signature system
14.5.3 Stateful Merkle signatures
14.5.4 Comparing Merkle constructions
14.6 Notes
14.7 Chapter summary
14.8 Exercises
15 Analysis of number theoretic assumptions
15.1 How reasonable are the factoring and RSA assumptions?
15.1.1 Quadratic resudousity assumption
15.2 How reasonable are the DL and CDH assumptions?
15.2.1 The Baby step giant step algorithm
15.2.2 The Pohlig-Hellman algorithm
15.2.3 Information leakage
15.2.4 Random self-reducibility
15.3 Discrete log in Zp*
15.3.1 The number field sieve
15.3.2 Discrete-log records in Zp*
15.4 How reasonable is decision Diffie-Hellman?
15.5 Quantum attacks on number theoretic problems
15.6 Side channel attacks
15.7 Notes
15.8 Chapter summary
15.9 Exercises
16 Elliptic curve cryptography and pairings
16.1 The group of points of an elliptic curve
16.2 Pairings
16.3 Signature schemes from pairings
16.4 Advanced encryption schemes from pairings
16.4.1 Identity based encryption
16.4.2 Attribute based encryption
17 Lattice based cryptography
17.1 Integer lattices
17.2 Hard problems on lattices
17.2.1 The SIS problem
17.2.2 The learning with errors (LWE) problem
17.3 Signatures from lattice problems
17.4 Public-key encryption using lattices
III Protocols
18 Identification protocols
18.1 Definitions
18.2 Password protocols: security against direct attacks
18.2.1 Weak passwords and dictionary attacks
18.2.2 Preventing dictionary attacks: salts, peppers, and slow hashing
18.2.3 More password management issues
18.2.4 Case study: UNIX and Windows passwords
18.3 One time passwords: security against eavesdropping
18.3.1 The SecurID system
18.3.2 The S/key system
18.4 Challenge-response: security against active attacks
18.4.1 Challenge-response protocols
18.4.2 Concurrent attacks versus sequential attacks
18.5 Notes
18.6 Chapter summary
18.7 Exercises
19 Signatures from identification protocols
19.1 Schnorr's identification protocol
19.2 Honest verifier zero knowledge and security against eavesdropping
19.3 The Guillou-Quisquater identification protocol
19.4 From identification protocols to signatures
19.4.1 -protocols
19.4.2 Signature construction
19.4.3 The Schnorr signature scheme
19.4.4 The GQ signature scheme
19.5 Secure against active attacks: OR proofs
19.6 Okamoto's identification protocol
19.7 Case study: the digital signature standard (DSS)
19.7.1 Comparing signature schemes
19.8 Notes
19.9 Chapter summary
19.10 Exercises
20 Authenticated Key Exchange
20.1 Introduction
20.2 Identification and AKE
20.3 An encryption-based protocol
20.3.1 Insecure variations
20.3.2 Summary
20.4 Forward secrecy and an ephemeral encryption-based protocol
20.4.1 Insecure variations
20.5 Formal definitions
20.6 Security of protocol EBKE
20.7 Security of protocol EEBKE
20.8 Explicit key confirmation
20.9 Identity protection
20.9.1 Insecure variations
20.10 One-sided authenticated key exchange
20.10.1 One-sided authenticated variants of protocols EBKE and EEBKE
20.10.2 Real-world security: phishing attacks
20.11 Password authenticated key exchange
20.11.1 Protocol PAKE0
20.11.2 Protocol PAKE1
20.11.3 Protocol PAKE2
20.11.4 Protocol PAKE2+
20.11.5 Explicit key confirmation
20.11.6 Generic protection against server compromise
20.11.7 Phishing again
20.12 Case studies
20.12.1 SSL
20.12.2 IKE2
20.13 Further topics
20.14 Notes
20.15 Chapter Summary
20.16 Exercises
21 Key establishment with online Trusted Third Parties
21.1 A key exchange protocol with an online TTP
21.2 Insecure variations of protocol OnlineTTP
21.3 Security proof for protocol OnlineTTP
21.4 Case study: Kerberos V5
21.5 Offline TTP vs. Online TTP
21.6 Notes
21.7 Chapter summary
21.8 Exercises
22 Two-party and multi-party secure computation
22.1 Yao's two party protocol
22.2 Multi-party secure computation
IV Appendices
A Basic number theory
A.1 Cyclic groups
A.2 Arithmetic modulo primes
A.2.1 Basic concepts
A.2.2 Structure of Zp*
A.2.3 Quadratic residues
A.2.4 Computing in Zp
A.2.5 Summary: arithmetic modulo primes
A.3 Arithmetic modulo composites
B Basic probability theory
B.1 Birthday Paradox
B.1.1 More collision bounds
B.1.2 A simple distinguisher
C Basic complexity theory
D Probabilistic algorithms
A Graduate Course in Applied Cryptography
Dan Boneh
Victor Shoup
August 17, 2015
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 specification 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 satisfies 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 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 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. The first part develops symmetric encryption which
explains how two parties, Alice and Bob, can securely exchange information when they have a
shared key unknown to the attacker. The second part develops the concepts of public-key encryption
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 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 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 to learn how to do proofs in cryptog-
raphy. At the end of every chapter you will find 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 only contains part I. Parts II and III are forthcoming. We hope you enjoy this
write-up. Please send us comments and let us know if you find 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
August, 2015
3
Contents
1 Introduction
15
1.1 Historic ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Terminology used throughout the book . . . . . . . . . . . . . . . . . . . . . . . . . . 15
I Secret key cryptography
17
2 Encryption
18
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1
2.2 Shannon ciphers and perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Definition of a Shannon cipher
. . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 The bad news . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Computational ciphers and semantic security . . . . . . . . . . . . . . . . . . . . . . 27
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 characterization of semantic security . . . . . . . 39
2.4 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 Negligible, super-poly, and poly-bounded functions . . . . . . . . . . . . . . . 42
2.4.2 Computational ciphers: the formalities . . . . . . . . . . . . . . . . . . . . . . 43
2.4.3 E cient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . . 46
2.4.4
Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5 A fun application: anonymous routing . . . . . . . . . . . . . . . . . . . . . . . . . . 48
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.6 Notes
2.7 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Stream ciphers
58
3.1 Pseudo-random generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1.1 Definition of a pseudo-random generator . . . . . . . . . . . . . . . . . . . . . 59
3.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Stream ciphers: encryption with a PRG . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Stream cipher limitations: attacks on the one time pad . . . . . . . . . . . . . . . . . 65
3.3.1 The two-time pad is insecure . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4
3.3.2 The one-time pad is malleable
3.9.1
. . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.1 A parallel construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.2 A sequential construction: the Blum-Micali method . . . . . . . . . . . . . . 72
3.4.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5 The next bit test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6 Case study: the Salsa and ChaCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7 Case study: linear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7.1 An example cryptanalysis: 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
Security of RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.10 Generating random bits in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.11 A broader perspective: computational indistinguishability . . . . . . . . . . . . . . . 94
3.11.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
. . . . . . . . . . . . . . . . . . . 99
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.12 A fun application: coin flipping and commitments
3.13 Notes
3.14 Exercises
4 Block ciphers
107
4.1 Block ciphers: basic definitions and properties . . . . . . . . . . . . . . . . . . . . . . 107
Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.1.1
4.1.2 E cient implementation of random permutations . . . . . . . . . . . . . . . . 112
4.1.3
Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.1.4 Using a block cipher directly for encryption . . . . . . . . . . . . . . . . . . . 113
4.1.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2 Constructing block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Case study: DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.2 Exhaustive search on DES: the DES challenges . . . . . . . . . . . . . . . . . 124
Strengthening ciphers against exhaustive search: the 3E construction . . . . . 126
4.2.3
4.2.4 Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3 Sophisticated attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 133
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3.1 Algorithmic attacks
4.3.2
Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.3.3 Fault-injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.3.4 Quantum exhaustive search attacks . . . . . . . . . . . . . . . . . . . . . . . . 142
4.4 Pseudo-random functions: basic definitions and properties . . . . . . . . . . . . . . . 143
4.4.1 Definitions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.4.2 E cient implementation of random functions . . . . . . . . . . . . . . . . . . 144
4.4.3 When is a secure block cipher a secure PRF? . . . . . . . . . . . . . . . . . . 145
4.4.4 Constructing PRGs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.4.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.5 Constructing block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.6 The tree construction: from PRGs to PRFs . . . . . . . . . . . . . . . . . . . . . . . 158
4.6.1 Variable length tree construction . . . . . . . . . . . . . . . . . . . . . . . . . 162
5
4.7 The ideal cipher model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.7.1 Formal definitions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.7.2 Exhaustive search in the ideal cipher model
. . . . . . . . . . . . . . . . . . . 165
4.7.3 The Even-Mansour block cipher and the EX construction . . . . . . . . . . . 168
4.7.4 Proof of the Even-Mansour and EX theorems . . . . . . . . . . . . . . . . . . 169
4.8 Fun application: comparing information without revealing it . . . . . . . . . . . . . . 175
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.9 Notes
4.10 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5 Chosen Plaintext Attack
184
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.2 Security against multi-key attacks
5.3 Semantic security against chosen plaintext attack . . . . . . . . . . . . . . . . . . . . 188
5.4 Building CPA secure ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.4.1 A generic hybrid construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.4.2 Counter mode
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.4.3 CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.4.4 Case study: CBC padding in TLS 1.0 . . . . . . . . . . . . . . . . . . . . . . 204
5.4.5 Concrete parameters and a comparison of counter and CBC modes . . . . . . 205
5.5 Nonce-based encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
5.5.1 Nonce-based generic hybrid encryption . . . . . . . . . . . . . . . . . . . . . . 208
5.5.2 Nonce-based Counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.5.3 Nonce-based CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
5.6 A fun application: revocation schemes . . . . . . . . . . . . . . . . . . . . . . . . . . 209
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
5.7 Notes
5.8 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6 Message integrity
215
6.1 Definition of a message authentication code . . . . . . . . . . . . . . . . . . . . . . . 217
6.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.2 MAC verification queries do not help the attacker . . . . . . . . . . . . . . . . . . . . 220
6.3 Constructing MACs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
6.4 Prefix-free PRFs for long messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.4.1 The CBC prefix-free secure PRF . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.4.2 The cascade prefix-free secure PRF . . . . . . . . . . . . . . . . . . . . . . . . 229
6.4.3 Extension attacks: CBC and cascade are insecure MACs . . . . . . . . . . . . 230
6.5 From prefix-free secure PRF to fully secure PRF (method 1): encrypted PRF . . . . 231
6.5.1 ECBC and NMAC: MACs for variable length inputs . . . . . . . . . . . . . . 232
6.6 From prefix-free secure PRF to fully secure PRF (method 2): prefix-free encodings . 234
6.6.1 Prefix free encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.7 From prefix-free secure PRF to fully secure PRF (method 3): CMAC . . . . . . . . . 236
6.8 Converting a block-wise PRF to bit-wise PRF . . . . . . . . . . . . . . . . . . . . . . 239
6.9 Case study: ANSI CBC-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.10 Case study: CMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.11 PMAC: a parallel MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
6.12 A fun application: searching on encrypted data . . . . . . . . . . . . . . . . . . . . . 245
6
6.13 Notes
6.14 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
7 Message integrity from universal hashing
250
7.1 Universal hash functions (UHFs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
7.1.1 Multi-query UHFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
7.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.2 Constructing UHFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.2.1 Construction 1: UHFs using polynomials
. . . . . . . . . . . . . . . . . . . . 253
7.2.2 Construction 2: CBC and cascade are computational UHFs . . . . . . . . . . 255
7.2.3 Construction 3: a parallel UHF from a small PRF . . . . . . . . . . . . . . . 258
7.3 PRF-UHF composition: constructing MACs using UHFs . . . . . . . . . . . . . . . . 260
7.3.1 Using PRF-UHF composition: ECBC and NMAC security . . . . . . . . . . . 263
7.3.2 Using PRF-UHF composition with polynomial UHFs . . . . . . . . . . . . . . 263
7.3.3 Using PRF-UHF composition: PMAC0 security . . . . . . . . . . . . . . . . . 264
7.4 The Carter-Wegman MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
7.4.1 Using Carter-Wegman with polynomial UHFs . . . . . . . . . . . . . . . . . . 271
7.5 Nonce-based MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Secure nonce-based MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
7.6 Unconditionally secure one-time MACs . . . . . . . . . . . . . . . . . . . . . . . . . . 273
7.6.1 Pairwise unpredictable functions . . . . . . . . . . . . . . . . . . . . . . . . . 273
7.6.2 Building unpredictable functions . . . . . . . . . . . . . . . . . . . . . . . . . 274
7.6.3 From PUFs to unconditionally secure one-time MACs . . . . . . . . . . . . . 275
7.7 A fun application: timing attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
7.8 Notes
7.9 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
7.5.1
8 Message integrity from collision resistant hashing
8.4.1
8.5 Building Compression Functions
285
8.1 Definition of collision resistant hashing . . . . . . . . . . . . . . . . . . . . . . . . . . 288
8.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
8.2 Building a MAC for large messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
8.3 Birthday attacks on collision resistant hash functions . . . . . . . . . . . . . . . . . . 291
8.4 The Merkle-Damg˚ard paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Joux’s attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
8.5.1 A simple but ine cient compression function . . . . . . . . . . . . . . . . . . 297
8.5.2 Davies-Meyer compression functions . . . . . . . . . . . . . . . . . . . . . . . 297
8.5.3 Collision resistance of Davies-Meyer
. . . . . . . . . . . . . . . . . . . . . . . 299
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8.6.1 Other Merkle-Damg˚ard hash functions . . . . . . . . . . . . . . . . . . . . . . 302
8.7 Case study: HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
Security of two-key nest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
8.7.1
8.7.2 The HMAC standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
8.7.3 Davies-Meyer is a secure PRF in the ideal cipher model
. . . . . . . . . . . . 308
8.8 The Sponge Construction and SHA3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
8.8.1 The sponge construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
8.6 Case study: SHA-256
7
8.10 Security without collision resistance
8.9 Key derivation and the random oracle model
8.8.2 Case study: SHA3, SHAKE256, and SHAKE512 . . . . . . . . . . . . . . . . 316
. . . . . . . . . . . . . . . . . . . . . . 317
8.9.1 The key derivation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
8.9.2 Random oracles: a useful heuristic . . . . . . . . . . . . . . . . . . . . . . . . 320
8.9.3 Random oracles: safe modes of operation . . . . . . . . . . . . . . . . . . . . 324
8.9.4 The leftover hash lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
8.9.5 Case study: HKDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
. . . . . . . . . . . . . . . . . . . . . . . . . . . 328
8.10.1 Second preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
8.10.2 Randomized hash functions: target collision resistance . . . . . . . . . . . . . 329
8.10.3 TCR from 2nd-preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . 330
8.10.4 Using target collision resistance . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.11 A fun application: commitment schemes . . . . . . . . . . . . . . . . . . . . . . . . . 335
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
8.12 Notes
8.13 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9 Authenticated Encryption
342
9.1 Authenticated encryption: definitions
. . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.2 Chosen ciphertext attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
9.2.1 Chosen ciphertext attacks: a motivating example . . . . . . . . . . . . . . . . 345
9.2.2 Chosen ciphertext attacks: definition . . . . . . . . . . . . . . . . . . . . . . . 347
9.2.3 Authenticated encryption implies chosen ciphertext security . . . . . . . . . . 348
9.3 Encryption as an abstract interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
9.4 Authenticated encryption ciphers from generic composition . . . . . . . . . . . . . . 351
9.4.1 Encrypt-then-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
9.4.2 MAC-then-encrypt is not generally secure: padding oracle attacks on SSL . . 353
9.4.3 More padding oracle attacks.
. . . . . . . . . . . . . . . . . . . . . . . . . . . 356
9.4.4
Secure instances of MAC-then-encrypt . . . . . . . . . . . . . . . . . . . . . . 357
9.4.5 Encrypt-then-MAC or MAC-then-encrypt? . . . . . . . . . . . . . . . . . . . 361
9.5 Nonce-based authenticated encryption with associated data . . . . . . . . . . . . . . 361
9.6 Case study: Galois counter mode (GCM)
. . . . . . . . . . . . . . . . . . . . . . . . 363
9.7 Case study: the TLS 1.3 record protocol . . . . . . . . . . . . . . . . . . . . . . . . . 366
9.8 Case study: an attack on non-atomic decryption in SSH . . . . . . . . . . . . . . . . 368
9.9 Case study: 802.11b WEP, a badly broken system . . . . . . . . . . . . . . . . . . . 370
9.10 Case study: IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
9.11 A fun application: private information retrieval
. . . . . . . . . . . . . . . . . . . . . 378
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
9.12 Notes
9.13 Exercises
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
II Public key cryptography
384
10 Public key tools
10.1 A toy problem: anonymous key exchange
10.2 Trapdoor function schemes
386
. . . . . . . . . . . . . . . . . . . . . . . . 386
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
10.2.1 Key exchange using a one-way trapdoor function scheme . . . . . . . . . . . . 388
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
