第1页 / 共818页
第2页 / 共818页
第3页 / 共818页
第4页 / 共818页
第5页 / 共818页
第6页 / 共818页
第7页 / 共818页
第8页 / 共818页
danboneh 密码学.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 Randomized 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: revocable broadcast encryption
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: SHA256
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 Merkle trees: proving properties of a hashed sequence
8.9.1 Authenticated data structures
8.10 Key derivation and the random oracle model
8.10.1 The key derivation problem
8.10.2 Random oracles: a useful heuristic
8.10.3 Random oracles: safe modes of operation
8.10.4 The leftover hash lemma
8.10.5 Case study: HKDF
8.11 Security without collision resistance
8.11.1 Second preimage resistance
8.11.2 Randomized hash functions: target collision resistance
8.11.3 TCR from 2nd-preimage resistance
8.11.4 Using target collision resistance
8.12 A fun application: an efficient commitment scheme
8.13 Another fun application: proofs of work
8.14 Notes
8.15 Exercises
9 Authenticated Encryption
9.1 Authenticated encryption: definitions
9.1.1 One-time authenticated encryption
9.2 Implications of authenticated encryption
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 One more variation: CCA-secure ciphers with associated data
9.7 Case study: Galois counter mode (GCM)
9.8 Case study: the TLS 1.3 record protocol
9.9 Case study: an attack on non-atomic decryption in SSH
9.10 Case study: 802.11b WEP, a badly broken system
9.11 Case study: IPsec
9.12 A fun application: private information retrieval
9.13 Notes
9.14 Exercises
II Public key cryptography
10 Public key tools
10.1 A toy problem: anonymous key exchange
10.2 One-way trapdoor functions
10.2.1 Key exchange using a one-way trapdoor function scheme
10.2.2 Mathematical details
10.3 A trapdoor permutation scheme based on RSA
10.3.1 Key exchange based on the RSA assumption
10.3.2 Mathematical details
10.4 Diffie-Hellman key exchange
10.4.1 The key exchange protocol
10.4.2 Security of Diffie-Hellman key exchange
10.5 Discrete logarithm and related assumptions
10.5.1 Random self-reducibility
10.5.2 Mathematical details
10.6 Collision resistant hash functions from number-theoretic primitives
10.6.1 Collision resistance based on DL
10.6.2 Collision resistance based on RSA
10.7 Attacks on the anonymous Diffie-Hellman protocol
10.8 Merkle puzzles: a partial solution to key exchange using block ciphers
10.9 Fun application: Pedersen commitments
10.10 Notes
10.11 Exercises
11 Public key encryption
11.1 Two further example applications
11.1.1 Sharing encrypted files
11.1.2 Key escrow
11.2 Basic definitions
11.2.1 Mathematical details
11.3 Implications of semantic security
11.3.1 The need for randomized encryption
11.3.2 Semantic security against chosen plaintext attack
11.4 Encryption based on a trapdoor function scheme
11.4.1 Instantiating ETDF with RSA
11.5 ElGamal encryption
11.5.1 Semantic security of ElGamal in the random oracle model
11.5.2 Semantic security of ElGamal without random oracles
11.6 Threshold decryption
11.6.1 Shamir's secret sharing scheme
11.6.2 ElGamal threshold decryption
11.7 Fun application: oblivious transfer from DDH
11.8 Notes
11.9 Exercises
12 Chosen ciphertext secure public key encryption
12.1 Basic definitions
12.2 Understanding CCA security
12.2.1 CCA security and ciphertext malleability
12.2.2 CCA security vs authentication
12.2.3 CCA security and key escrow
12.2.4 Encryption as an abstract interface
12.3 CCA-secure encryption from trapdoor function schemes
12.3.1 Instantiating ETDF' with RSA
12.4 CCA-secure ElGamal encryption
12.5 CCA security from DDH without random oracles
12.5.1 Universal projective hash functions
12.5.2 Universal2 projective hash functions
12.5.3 The ECS scheme
12.6 CCA security via a generic transformation
12.6.1 A generic instantiation
12.6.2 A concrete instantiation with ElGamal
12.7 CCA-secure public-key encryption with associated data
12.8 Case study: PKCS1, OAEP, OAEP+, and SAEP
12.8.1 Padding schemes
12.8.2 PKCS1 padding
12.8.3 Bleichenbacher's attack on the RSA-PKCS1 encryption scheme
12.8.4 Optimal Asymmetric Encryption Padding (OAEP)
12.8.5 OAEP+ and SAEP+
12.9 Fun application: sealed bid auctions
12.10 Notes
12.11 Exercises
13 Digital signatures
13.1 Definition of a digital signature
13.1.1 Secure signatures
13.1.2 Mathematical details
13.2 Extending the message space with collision resistant hashing
13.2.1 Extending the message space using TCR functions
13.3 Signatures from trapdoor permutations: the full domain hash
13.3.1 Signatures based on the RSA trapdoor permutation
13.4 Security analysis of full domain hash
13.4.1 Repeated one-way functions: a useful lemma
13.4.2 Proofs of Theorems 13.3 and 13.4
13.5 An RSA-based signature scheme with tighter security proof
13.6 Case study: PKCS1 signatures
13.6.1 Bleichenbacher's attack on PKCS1 signatures
13.7 Signcryption: combining signatures and encryption
13.7.1 Secure signcryption
13.7.2 Signcryption as an abstract interface
13.7.3 Constructions: encrypt-then-sign and sign-then-encrypt
13.7.4 A construction based on Diffie-Hellman key exchange
13.7.5 Additional desirable properties: forward secrecy and non-repudiation
13.8 Certificates and the public-key infrastructure
13.8.1 Coping with malicious or negligent certificate authorities
13.8.2 Certificate revocation
13.9 Case study: legal aspects of digital signatures
13.10 A fun application: private information retrieval
13.11 Notes
13.12 Exercises
14 Fast hash-based signatures
14.1 Basic Lamport signatures
14.1.1 Shrinking the signature using an enhanced TCR
14.2 A general Lamport framework
14.2.1 An explicit containment free function
14.3 Winternitz one-time signatures
14.3.1 A domination free function for Winternitz signatures
14.4 HORS: short Lamport signatures
14.4.1 Shrinking the public-key using a Merkle tree
14.5 Applications of one-time signatures
14.5.1 Online/offline signatures from one-time signatures
14.5.2 Authenticating streamed data with one-time signatures
14.6 From one-time signatures to many-time signatures
14.6.1 Indexed signatures
14.6.2 A many-time signature scheme from an indexed signature
14.6.3 The complete Merkle stateless signature system
14.6.4 Nonce-based Merkle signatures
14.7 A fun application
14.8 Notes
14.9 Exercises
15 Elliptic curve cryptography and pairings
15.1 The group of points of an elliptic curve
15.2 Elliptic curves over finite fields
15.2.1 Montgomery and Edwards curves
15.3 Elliptic curve cryptography
15.3.1 The curve P256
15.3.2 The curve 25519
15.4 Pairings
15.5 Signature schemes from pairings
15.5.1 BLS signatures
15.5.2 Group signatures
15.6 Advanced encryption schemes from pairings
15.6.1 Identity based encryption
15.6.2 Threshold decryption with ciphertext security
15.6.3 Broadcast encryption
15.6.4 Homomorphic encryption
15.7 Multilinear maps
15.8 A fun application: secret handshakes
15.9 Notes
15.10 Exercises
16 Lattice based cryptography
16.1 Integer lattices
16.2 Hard problems on lattices
16.2.1 The SIS problem
16.2.2 The learning with errors (LWE) problem
16.2.3 The ring LWE problem
16.3 Trapdoor sampling from a lattice
16.4 Signatures from lattice problems
16.5 Public-key encryption from lattices
16.6 Fully homomorphic encryption
16.7 A fun application: factoring integers using lattices
16.8 Exercises
17 Analysis of number theoretic assumptions
17.1 How reasonable are the factoring and RSA assumptions?
17.1.1 Quadratic resudousity assumption
17.2 How reasonable are the DL and CDH assumptions?
17.2.1 Brute-force search
17.2.2 The baby-step/giant-step method
17.2.3 Groups of order qe
17.2.4 The Pohlig-Hellman algorithm
17.2.5 The Pohlig-Hellman algorithm
17.2.6 Information leakage
17.3 Discrete log in Zp*
17.3.1 The number field sieve
17.3.2 Discrete-log records in Zp*
17.4 How reasonable is decision Diffie-Hellman?
17.5 Quantum attacks on number theoretic problems
17.6 Side channel and fault attacks
17.7 Notes
17.8 Chapter summary
17.9 Exercises
III Protocols
18 Protocols for identification and login
18.1 Interactive protocols: general notions
18.1.1 Mathematical details
18.2 ID protocols: definitions
18.3 Password protocols: security against direct attacks
18.3.1 Password cracking using a dictionary attack
18.4 Making dictionary attacks harder
18.4.1 Public salts
18.4.2 Secret salts
18.4.3 Slow hash functions
18.4.4 Slow memory-hard hash functions
18.4.5 More password management issues
18.5 One time passwords: security against eavesdropping
18.5.1 PRF-based one-time passwords: HOTP and TOTP
18.5.2 The S/key system
18.6 Challenge-response: security against active attacks
18.6.1 Challenge-response protocols
18.7 A fun application: rainbow tables
18.8 Another fun application: hardening password storage
18.9 Notes
18.10 Exercises
19 Identification and signatures from sigma protocols
19.1 Schnorr's identification protocol
19.1.1 Honest verifier zero knowledge and security against eavesdropping
19.2 From identification protocols to signatures
19.2.1 A useful abstraction: repeated impersonation attacks
19.2.2 Security analysis of Schnorr signatures
19.2.3 A concrete implementation and an optimization
19.3 Case study: ECDSA signatures
19.4 Sigma protocols: basic definitions
19.4.1 Knowledge soundness
19.4.2 Special honest verifier zero knowledge
19.5 Sigma protocols: examples
19.5.1 Okamoto's protocol for representations
19.5.2 The Chaum-Pedersen protocol for DH-triples
19.5.3 A Sigma protocol for arbitrary linear relations
19.5.4 A Sigma protocol for RSA
19.6 Identification and signatures from Sigma protocols
19.6.1 The Fiat-Shamir heuristic for signatures
19.7 Combining Sigma protocols: AND and OR proofs
19.7.1 The AND-proof construction
19.7.2 The OR-proof construction
19.8 Witness independence and applications
19.8.1 Definition of witness independence
19.8.2 Special HVZK implies witness independence
19.8.3 Actively secure identification protocols
19.8.4 Okamoto's identification protocol
19.9 A fun application: a two round witness independent protocol
19.10 Notes
19.11 Exercises
20 Proving properties in zero-knowledge
20.1 Languages and existential soundness
20.2 Proving properties on encrypted data
20.2.1 A generic protocol for non-linear relations
20.3 Non-interactive proof systems
20.3.1 Example: a voting protocol
20.3.2 Non-interactive proofs: basic syntax
20.3.3 The Fiat-Shamir transform
20.3.4 Non-interactive existential soundness
20.3.5 Non-interactive zero knowledge
20.4 Computational zero-knowledge and applications
20.4.1 Example: range proofs
20.4.2 Special computational HVZK
20.4.3 An unconstrained generic protocol for non-linear relations
20.5 Efficient multi-round protocols
20.6 Succinct non-interactive zero-knowledge proofs (SNARKs)
20.7 A fun application: everything that can be proved, can be proved in zero knowledge
20.8 Notes
20.9 Exercises
21 Authenticated Key Exchange
21.1 Identification and AKE
21.2 An encryption-based protocol
21.2.1 Insecure variations
21.2.2 Summary
21.3 Perfect forward secrecy and a protocol based on ephemeral encryption
21.3.1 Assuming only semantically secure encryption
21.4 HSM security
21.4.1 A technical requirement: strongly unpredictable ciphertexts
21.4.2 Insecure variations
21.5 Identity protection
21.6 One-sided authenticated key exchange
21.6.1 A one-sided authenticated variant of AKE4
21.7 Deniability
21.7.1 Deniability without identity protection
21.7.2 Deniability with identity protection
21.8 Channel bindings
21.9 Formal definitions
21.9.1 Understanding the definition
21.9.2 Security of protocol AKE1
21.9.3 Modeling perfect forward secrecy
21.9.4 Modeling HSM security
21.9.5 Modeling one-sided authentication
21.9.6 Modeling channel bindings
21.10 Case study: TLS session setup
21.10.1 Authenticated key exchange with preshared keys
21.11 Password authenticated key exchange
21.11.1 Phishing attacks
21.11.2 PAKE: an introduction
21.11.3 Protocol PAKE0
21.11.4 Protocol PAKE1
21.11.5 Protocol PAKE2
21.11.6 Protocol PAKE2+
21.11.7 Explicit key confirmation
21.11.8 Phishing again
21.12 A fun application: establishing Tor channels
21.13 Notes
21.14 Exercises
22 Key establishment with online Trusted Third Parties
22.1 A key exchange protocol with an online TTP
22.2 Insecure variations of protocol OnlineTTP
22.3 Security proof for protocol OnlineTTP
22.4 Case study: Kerberos V5
22.5 Offline TTP vs. Online TTP
22.6 Notes
22.7 Exercises
23 Two-party and multi-party secure computation
23.1 Yao's two party protocol
23.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 and Victor Shoup
Version 0.4, September 2017
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.
• Part I 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. We
discuss data confidentiality, data integrity, and the important concept of authenticated en-
cryption.
• Part II develops the concepts of public-key encryption and digital signatures, which allow
Alice and Bob to communicate securely, without having a pre-shared secret key.
• Part III is about cryptographic protocols, such as protocols for user identification, 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 first 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 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 contains part I and most of parts II and III. The remaining four chapters 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
September, 2017
iii
Contents
1 Introduction
1.1 Historic ciphers
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Terminology used throughout the book . . . . . . . . . . . . . . . . . . . . . . . . .
I Secret key cryptography
1
1
1
3
2 Encryption
2.1
2.2
4
4
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Shannon ciphers and perfect security . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Definition of a Shannon cipher
2.2.1
. . . . . . . . . . . . . . . . . . . . . . . . .
Perfect security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2
7
The bad news . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3
2.3 Computational ciphers and semantic security . . . . . . . . . . . . . . . . . . . . . . 13
Definition of a computational cipher . . . . . . . . . . . . . . . . . . . . . . 14
Definition of semantic security . . . . . . . . . . . . . . . . . . . . . . . . . 15
Connections to weaker notions of security . . . . . . . . . . . . . . . . . . . 18
Consequences of semantic security . . . . . . . . . . . . . . . . . . . . . . . 22
Bit guessing: an alternative characterization of semantic security . . . . . . 25
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Negligible, super-poly, and poly-bounded functions . . . . . . . . . . . . . . 28
Computational ciphers: the formalities . . . . . . . . . . . . . . . . . . . . . 29
E cient adversaries and attack games . . . . . . . . . . . . . . . . . . . . . 32
Semantic security: the formalities . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5 A fun application: anonymous routing . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Mathematical details
2.3.1
2.3.2
2.3.3
2.3.4
2.3.5
2.4.1
2.4.2
2.4.3
2.4.4
3 Stream ciphers
3.1 Pseudo-random generators
45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1
Definition of a pseudo-random generator . . . . . . . . . . . . . . . . . . . . 46
3.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Stream ciphers: encryption with a PRG . . . . . . . . . . . . . . . . . . . . . . . . . 48
Stream cipher limitations: attacks on the one time pad . . . . . . . . . . . . . . . . 52
3.3.1
The two-time pad is insecure . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2
3.3
iv
3.3.2
3.7.1
3.7.2
3.4 Composing PRGs
The one-time pad is malleable . . . . . . . . . . . . . . . . . . . . . . . . . . 53
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
A parallel construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1
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
An example cryptanalysis: linear congruential generators
. . . . . . . . . . 70
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
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 flipping and commitments . . . . . . . . . . . . . . . . . . . 87
3.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.9.1
4 Block ciphers
4.3
4.1 Block ciphers: basic definitions and properties
94
. . . . . . . . . . . . . . . . . . . . . 94
Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.1.1
E cient implementation of random permutations . . . . . . . . . . . . . . . 99
4.1.2
Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.1.3
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
Strengthening ciphers against exhaustive search: the 3E construction . . . . 113
4.2.3
4.2.4
Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Sophisticated attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.3.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Algorithmic attacks
Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.3.2
4.3.3
Fault-injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3.4 Quantum exhaustive search attacks . . . . . . . . . . . . . . . . . . . . . . . 129
. . . . . . . . . . . . . . 130
Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.4.1
4.4.2
E cient 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
Variable length tree construction . . . . . . . . . . . . . . . . . . . . . . . . 149
4.4 Pseudo-random functions: basic definitions and properties
4.6.1
v
4.7 The ideal cipher model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Formal definitions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.7.1
Exhaustive search in the ideal cipher model
. . . . . . . . . . . . . . . . . . 153
4.7.2
The Even-Mansour block cipher and the EX construction . . . . . . . . . . 156
4.7.3
Proof of the Even-Mansour and EX theorems . . . . . . . . . . . . . . . . . 157
4.7.4
4.8
Fun application: comparing information without revealing it . . . . . . . . . . . . . 163
4.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
5 Chosen Plaintext Attack
5.4.1
5.4.2
5.4.3
5.4.4
5.4.5
174
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.1
Security against multi-key attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.2
5.3
Semantic security against chosen plaintext attack . . . . . . . . . . . . . . . . . . . 178
5.4 Building CPA secure ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
A generic hybrid construction . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Randomized counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
CBC mode
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Case study: CBC padding in TLS 1.0 . . . . . . . . . . . . . . . . . . . . . 196
Concrete parameters and a comparison of counter and CBC modes . . . . . 196
5.5 Nonce-based encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Nonce-based generic hybrid encryption . . . . . . . . . . . . . . . . . . . . . 200
Nonce-based Counter mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Nonce-based CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.6 A fun application: revocable broadcast encryption . . . . . . . . . . . . . . . . . . . 202
5.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.5.1
5.5.2
5.5.3
6 Message integrity
212
6.1 Definition of a message authentication code . . . . . . . . . . . . . . . . . . . . . . . 214
6.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.2 MAC verification queries do not help the attacker . . . . . . . . . . . . . . . . . . . 217
6.3 Constructing MACs from PRFs
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.4 Prefix-free PRFs for long messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
The CBC prefix-free secure PRF . . . . . . . . . . . . . . . . . . . . . . . . 223
6.4.1
The cascade prefix-free secure PRF . . . . . . . . . . . . . . . . . . . . . . . 226
6.4.2
6.4.3
Extension attacks: CBC and cascade are insecure MACs . . . . . . . . . . . 227
From prefix-free secure PRF to fully secure PRF (method 1): encrypted PRF . . . 228
6.5.1
ECBC and NMAC: MACs for variable length inputs . . . . . . . . . . . . . 229
From prefix-free secure PRF to fully secure PRF (method 2): prefix-free encodings . 232
6.6.1
Prefix free encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
6.7
From prefix-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.5
6.6
vi
6.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
6.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
7 Message integrity from universal hashing
7.3.1
7.3.2
7.3.3
7.2.1
7.2.2
7.2.3
7.2 Constructing UHFs
248
7.1 Universal hash functions (UHFs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
7.1.1 Multi-query UHFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
7.1.2 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Construction 1: UHFs using polynomials
. . . . . . . . . . . . . . . . . . . 251
Construction 2: CBC and cascade are computational UHFs . . . . . . . . . 254
Construction 3: a parallel UHF from a small PRF . . . . . . . . . . . . . . 256
7.3 PRF(UHF) composition: constructing MACs using UHFs . . . . . . . . . . . . . . . 258
Using PRF(UHF) composition: ECBC and NMAC security . . . . . . . . . 261
Using PRF(UHF) composition with polynomial UHFs . . . . . . . . . . . . 261
Using PRF(UHF) composition: PMAC0 security . . . . . . . . . . . . . . . 262
7.4 The Carter-Wegman MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Using Carter-Wegman with polynomial UHFs . . . . . . . . . . . . . . . . . 269
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
Secure nonce-based MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
7.6 Unconditionally secure one-time MACs . . . . . . . . . . . . . . . . . . . . . . . . . 270
Pairwise unpredictable functions
. . . . . . . . . . . . . . . . . . . . . . . . 271
Building unpredictable functions . . . . . . . . . . . . . . . . . . . . . . . . 271
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
7.5 Nonce-based MACs
7.6.1
7.6.2
7.6.3
7.4.1
7.5.1
8 Message integrity from collision resistant hashing
8.4.1
283
8.1 Definition of collision resistant hashing . . . . . . . . . . . . . . . . . . . . . . . . . 286
8.1.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
. . . . . . . . . . . . . . . . . . . . . . . . . . . 287
8.2 Building a MAC for large messages
8.3 Birthday attacks on collision resistant hash functions
. . . . . . . . . . . . . . . . . 289
8.4 The Merkle-Damg˚ard paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
Joux’s attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
8.5 Building Compression Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
A simple but ine cient compression function . . . . . . . . . . . . . . . . . 295
Davies-Meyer compression functions . . . . . . . . . . . . . . . . . . . . . . 295
Collision resistance of Davies-Meyer
. . . . . . . . . . . . . . . . . . . . . . 297
8.6 Case study: SHA256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
8.6.1 Other Merkle-Damg˚ard hash functions . . . . . . . . . . . . . . . . . . . . . 300
8.7 Case study: HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Security of two-key nest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
The HMAC standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Davies-Meyer is a secure PRF in the ideal cipher model
. . . . . . . . . . . 306
8.8 The Sponge Construction and SHA3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
The sponge construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
8.7.1
8.7.2
8.7.3
8.5.1
8.5.2
8.5.3
8.8.1
vii
8.9.1
8.8.2
8.10 Key derivation and the random oracle model
Case study: SHA3, SHAKE256, and SHAKE512 . . . . . . . . . . . . . . . 314
8.9 Merkle trees: proving properties of a hashed sequence . . . . . . . . . . . . . . . . . 315
Authenticated data structures . . . . . . . . . . . . . . . . . . . . . . . . . . 318
. . . . . . . . . . . . . . . . . . . . . . 320
8.10.1 The key derivation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
8.10.2 Random oracles: a useful heuristic . . . . . . . . . . . . . . . . . . . . . . . 322
8.10.3 Random oracles: safe modes of operation . . . . . . . . . . . . . . . . . . . 327
8.10.4 The leftover hash lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
8.10.5 Case study: HKDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
8.11 Security without collision resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
8.11.1 Second preimage resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
8.11.2 Randomized hash functions: target collision resistance . . . . . . . . . . . . 333
8.11.3 TCR from 2nd-preimage resistance . . . . . . . . . . . . . . . . . . . . . . . 333
8.11.4 Using target collision resistance . . . . . . . . . . . . . . . . . . . . . . . . . 336
8.12 A fun application: an e cient commitment scheme
. . . . . . . . . . . . . . . . . . 339
8.13 Another fun application: proofs of work . . . . . . . . . . . . . . . . . . . . . . . . . 339
8.14 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
8.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9 Authenticated Encryption
9.2
347
9.1 Authenticated encryption: definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 348
9.1.1 One-time authenticated encryption . . . . . . . . . . . . . . . . . . . . . . . 349
Implications of authenticated encryption . . . . . . . . . . . . . . . . . . . . . . . . 350
Chosen ciphertext attacks: a motivating example . . . . . . . . . . . . . . . 350
9.2.1
Chosen ciphertext attacks: definition . . . . . . . . . . . . . . . . . . . . . . 352
9.2.2
Authenticated encryption implies chosen ciphertext security . . . . . . . . . 353
9.2.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . 355
9.3 Encryption as an abstract interface
9.4 Authenticated encryption ciphers from generic composition . . . . . . . . . . . . . . 357
9.4.1
Encrypt-then-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
9.4.2 MAC-then-encrypt is not generally secure: padding oracle attacks on SSL . 359
9.4.3 More padding oracle attacks.
. . . . . . . . . . . . . . . . . . . . . . . . . . 362
Secure instances of MAC-then-encrypt . . . . . . . . . . . . . . . . . . . . . 363
9.4.4
9.4.5
Encrypt-then-MAC or MAC-then-encrypt? . . . . . . . . . . . . . . . . . . 367
9.5 Nonce-based authenticated encryption with associated data . . . . . . . . . . . . . . 367
9.6 One more variation: CCA-secure ciphers with associated data . . . . . . . . . . . . 370
9.7 Case study: Galois counter mode (GCM) . . . . . . . . . . . . . . . . . . . . . . . . 371
9.8 Case study: the TLS 1.3 record protocol
. . . . . . . . . . . . . . . . . . . . . . . . 373
9.9 Case study: an attack on non-atomic decryption in SSH . . . . . . . . . . . . . . . . 376
9.10 Case study: 802.11b WEP, a badly broken system . . . . . . . . . . . . . . . . . . . 379
9.11 Case study: IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
9.12 A fun application: private information retrieval . . . . . . . . . . . . . . . . . . . . . 386
9.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
viii
相关推荐
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
