A Graduate Course in Applied Cryptography.pdf

所需积分/C币:10 2019-05-19 13:53:16 21.81MB PDF

Dan Boneh 和 Victor Shoup 合作写的一本适合研究生学习应用密码学的书
without losing continuity. a beginning reader nay also skip over the nlathenalical details seclions that explore nuances of ccrtain dcfinitions 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 and the first half of part II. The remaining chapters in parts Ii and part 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 December 2016 Contents 1 Introduction 1.1 Historic ciphers 1 1.2 Terminology used throughout the book I Secret key cryptograph 2 Encryptic 2.1 ntroduction 4 2.2 Shannon ciphers and perfect security 2.2.1 Dcfinition of a Shannon cipher 2.2.2 Perfect securit ·, 7 2.2.3 The bad news 13 2.3 Computational ciphers and semantic security 2.3.1 Definition of a computational cipher 14 2.3.2 Dcfinition of scmantic sccurity 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 2. 4 Mathematical details 27 2.4.1 Ncgligiblc, supcr-poly, and poly-bounded functions 2.4.2 Computational ciphers: the formalities 2.4.3 Efficient adversaries and attack games 32 2.4.4 Semantic security: the formalities 4 2.5 A fun application: anonymous routing 35 2.6 Notos,,,.,,. 2.7 Exercises 38 3 Stream ciphers 45 3.1 Pseudo-random generators 45 3.1.1 Definition of a pseudo-random generator 46 3.1.2 Mathematical details 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 V 3.3.2 The one-Line pad is malleable 53 3.4 Composing PrGs 54 3.4.1 A parallel construction 54 3.4.2 A sequential construction: the Blum-Micali method 3.4.3 Mathematical details 61 3.5 The next bit test .64 3.6 Casc study: the Salsa and cha cha 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 encry pion systeln 74 3.9 Casc study: cryptanalysis of the RC4 strcam cipher 76 3.9.1 Security of RC4 8 3.11 A broader perspective: computational indistinguishably 3.10 Generating random bits in practice 81 3.11.1 Mathemalical details 86 3.12 A fun application: coin dipping and commitments 87 3.13 Notes 3.14 Exercises 4 Block ciphers 94 4.1 Block ciphers: basic definitions and properties 94 4.1.1 Some implications of securit ...96 4.1.2 Efficient implementation of random permutations 99 4.1. 3 Strongly secure block ciphers 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 106 4.2.2 Exhaustive search on dEs: the des challenges 110 1.2.3 Strengthening ciphers against exhaustive search: the 38 construction 112 4.2.4 Case study: AES 114 4.3 Sophisticated attacks on ble Iphers ..119 4.3.1 Algorithmic attacks 120 4.3.2 Side-channel attacks 123 1.3.3 Fault-injection attacks on AES 127 4.3.4 Quant um exhaustive search attacks 128 4.4 Pseudo-random functions: basic definitions and properties 129 4.4.1 Definitions 129 1.1.3When is a secure block cipher a secure PRK? 4.4.2 Efficient implementation of random functions 130 .131 4.4.4 Constructing PRGs from PrFs 4.4.5 Mathematical details 136 4.5 Constructing block ciphers from PRFs ..138 4.6 The tr truction from prgs to prF 144 1.6.1 Variable length tree construction 148 4.7 The ideal cipher nodel 151 4.7.1 Formal dcfinitions 151 4.7.2 Exhaustive search in the ideal cipher model 152 4.7.3 The Even-Mansour block cipher and the &X construction 155 4.7.4 Proof of the even-Mansour and X theorems 156 4.8 Fun applicalion: comparing informalion without revealing il .162 4.9 Notos .164 4.10 Exercises 164 5 Chosen plaintext attack 173 5.1 Introduction ..173 5.2 Security against multi-key attacks 175 5.3 Semantic security against chosen plaintext attack 177 5.4 Building CPA secure ciphers 179 5.4.1 A generic hybrid construction 179 5.1.2 Randomized counter mode 184 5.4.3 CBC mode 189 Concrete parameters and a comparison of counter and CBC modes.....194 5.4.4 Case study: CBC padding in TLS 1.0 195 5.5 Nonce-based encryption 196 56 A fun application: revocable broadcast encryption.··、 5.5.1 Nonce-based generic hybrid encryption 198 5.5.2 Nonce-based counter mode 198 5.5.3 Nonce-based Cbc mode 199 200 5. 7 Notes 203 5.8 Exercises .203 6 Message integrity 209 6.1 Definition of a message authentication code 211 6.1.1 Mathematical details 214 6.2 MAC verification queries do not help the al lacker 214 6.3 Constructing Macs from PRFs 217 6.4 Prefix-free PRFs for long messages 19 6.4. 1 The CBC prefix-free secure PRF 6.4.2 The cascade prefix-free secure Phe 9 6.4.3 Extension attacks: CBC and cascade are insecure MAcs 224 6.5 From prefix-free secure PRF to fully secure PRF (method 1): encrypted PRF 224 6.5.1 ECBC and NMAC: MACs for variable length inputs ..226 6.6 From prefix-free secure PRF to fully secure PRF (method 2: prefix-free encodings. 228 6.6.1 Prefix free encodings 228 6.7 From prefix-free secure PrF to fully secure PRF(method 3: CMAC......... 229 6.8 Converting a block-wise PrF to bit-wise PRF 93 6.9 Case study: ANSI CBC-MAC 233 6. 10 Case study: CMAC ..,.234 6.11 PMAC: a parallel MAC 236 6. 12 A lun applicalion: searching on encry pled dala 6.13 Noles .,.239 6.14 Excrciscs ..239 7 Message integrity from universal hashing 244 7.1 Universal hash functions(UHFs) 7.1.1 Multi-query UHFs 216 7.1.2 Mathematical details 247 7.2 Constructing UhF ..,,.247 7.2.1 Construction 1: UHFS using polynomials 247 7.2.2 Construction 2: CBC and cascade are computational UHFs 7.2.3 Construction 3: a parallel uhf from a, small PrF .252 7.3 PRF(UHF)composition: constructing M ACs using UHFS 254 7.3.1 Using PRF(UHF) composition: ECBC and NMAC security 7 7.3.2 Using PRF(UHF) composition with polynomial UHFS 257 7.3.3 Using PRF(UHF) composition: PMACo security 7.1 The Carter-Wegman MAc 7.4.1 Using Carter-Wegman with polynomial UHFs 7.5 Nonce-based MACs 265 7.5.1 Secure nonce-based macs 7.6 Unconditionally secure one-time MACs 267 7.6.1 Pairwise unpredictable functions .,,,267 7.6.2 Building unpredictable functions 7.6.3 From PUFs to unconditionally secure one-time MACs 7.7 A fun application: timing attacks 269 7. 8 Notes .,,,,,,,,,,,,,,,,,,269 7.9 Exercises 8 Message integrity from collision resistant, hashing 279 8. 1 Definition of collision resistant hashing ...,.282 8.1.1 Mathematical details ..282 8.2 Building a MAC for large messages 283 8.3 Birthday attacks on collision resistant hash functions 285 8. 4 The Merkle-Damgard paradigm 287 8.4.1Joux’ s attack 8.5 Building Compression Functions ..290 8.5. 1 A simple but inefficient compression function 291 8.5.2 Davies-Meyer compression functions 291 8.5.3 Collision resistance of Davies-Meyer 293 8.6 Case study: SHA256 294 8.6.1 Other erkle-Damgard hash functions 296 8.7 Case study: HMAC 8.7.1Se Or UWO-key nes 299 8.7.2 The HMac standard 301 8.7. 3 Davies-Meyer is a secure PrF in the ideal cipher model ···.302 8. 8 The Sponge Construction and sha3 305 8.8.1 The sponge construction 305 V11 8.8.2 Case study: SHA3. SHAKE256, and SHAKE512 .,.310 8.9 Mcrklc trcs: using collision resistancc to prove databasc membership 311 8.10 Key derivation and the random oracle model 311 8. 10. 1 The key derivation problem .311 8. 10.2 Random oracles: a useful heuristic .,,.314 8.10.3 Randoin oracles: sale nodes of operation .319 8.10.4 Thc leftover hash lcmma 320 8. 10.5 Case study: HKDF 322 8. 11 Security without collision resistance 323 8.11.1 Second preimage resistance 323 8.11.2 Randomized hash functions: target collision resistance ...,324 8. 11.3 TCR from 2nd-prcimagc resistancc 325 8.11.4 Using target collision resistance 327 8. 12 A fun application: an efficient commitment scheme ..330 8. 13 Another fun application: proofs of work 330 8.14 Notes ..330 8.15 Exercises .331 9 Authenticated Encryption 338 9.1 Authenticated encryption: definitions 9. 2 Implications of authenticated encryption 311 9.2.1 Chosen ciphertext attacks: a motivating example 341 9.2.2 Chosen ciphertext attacks: definition .,342 9.2.3 Authenticated encryption implies chosen ciphertext security .344 9.3 Encryption as an abstract interface 346 9. 4 Authenticated encryption ciphers from generic composition .347 9.4.1 Encrypt-then-MAC 348 9.4.2 MAC-then-encrypt is not generally secure: padding oracle attacks on SSL.. 350 9.4.3 More padding oracle attacks .353 9.4.4 Secure instances of MAC-then-encrypt 9.1.5 Encrypt-then-MAC or MAC-then-encrypt' 354 358 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) 36l 9.8 Case study: the TlS 1.3 record protocol 364 9.9 Case study: an attack on non-atomic decryption in SsH 366 9.10 Case study: 802. 11b WEP, a badly broken system ..368 9. 11 Case study: IPsec 371 9 12 A fun application: private information retrieval 376 9.13 Notes .376 9.11 Exercises .,376 Ii Public key cryptography 383 10 Public key tools 385 10.1 a toy problem: anonymous key exchange ..385 10.2 One-way trapdoor functions 386 10.2.1 Key exchange using a one-way trapdoor function scheme 387 10.2.2 Mathematical details 10.3A trapdoor permutation scheme based on RSq 389 10.3. 1 Key exchange based on the RSA assumption 391 10.3.2 Mathematical details 391 10.1 Diffie-Hellman key exchange 10.4.1 The key exchange 10.4.2 Security of Diffie-Hellman key exchange 393 10.5 Discrete logarithm and related assumptions 394 10.5.1 Random self-reducibili 397 10.5.2 Mathematical details .398 10.6 Collision resistant, hash functions from number-theoretic primitives 400 10.6. 1 Collision resistance based on DL 10.6.2 Collision resistance based on rsa 401 10.7 Attacks on the anonymous Diffie-Hellman protocol 10.8 Merkle puzzles: a partial solution to key exchange using block ciphers 104 10.9 Fun application: Pedersen commitments 4095 10.noTes 10.11 Exercises 406 11 Public key encryption 414 11. 1 Two furthcr cxamplc applications 415 11.1.1 Sharing encrypted files 415 11.1.2K 415 11.2 Basic definit 416 11.2.1 Mathematical delails 417 11.3 Implications of scmantic securit 418 11.3. 1 The need for randomized encryption 418 11.3.2 Semantic security against chosen plaintext attack ....419 11.4 Encryption based on a trapdoor function scheme 421 11.4.1 Instantiating &TDF with RSA 424 11.5 ElGamal encryption 11.5.1 Semantic security of ElGamal in the random oracle model ..425 426 11.5.2 Semantic security of ElGamal without random oracles 428 11.6 Threshold decryption 431 11.6.1 Shamir's secret sharing scheme ,,,,,,433 11.6.2 ElGamal threshold decryption 11.7 Fun application: oblivious transfer from DDl 435 438 11.8 Notes 43 11.9 Exercises 12 Chosen ciphertext secure public key encryption 445 12. 1 Basic dcfinitions 445 12.2 Understanding CCa security 447 12.2.1 CCA security and ciphertext malleability 447 12.2.2 CCa security vs authentication ....448 12.2.3 CCA security and key escrow 449 12.2.4 Encryption as an abstract interfacc 450 12.3 CCA-Secure encryption from trapdoor function schemes 452 12.3. 1 Instantiating CTDF with rsa 457 12.4 CCA-secure ElGamal encryption 458 12.4.1 CCA security for basic ElGamal encryption 12.5 CCA sccurity from DDh without random oracles 463 12.6 CCA security via a generic transformation 470 12.6.1 A generic instantiation ....475 12.6.2 A concrete instantiation with elgamal 475 12.7 CCA-secure public-key encryption with associated dala ..477 12.8 Casc study: PKCS1, OAEP, OAEP I, and SAEP .478 12.8. 1 Padding schemes 12.8. 2 PKCS1 padding 479 12.8.3 Bleichenbacher's attack on the rsA-PKCSl encryption scheme.......480 12.8.4 Optimal Asymmetric Encryption Padding ( OAEP 483 12.8.5 OAEP+ and SaeP+ .485 12.9 Fun application: sealed bid auctions 486 12.10Notes ,,486 12.11 Exercises 486 13 Digital signatures 497 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 503 13.2. 1 Extending the message space using TCR functions 13. 3 Signatures from trapdoor permut ations: the full domain hash ,,,,,504 ..505 13.3.1 Signatures based on the RSa trapdoor permutation 506 13. 4 Security analysis of full domain hash 13.1.1 Repeated one-way functions: a useful lemma 509 13.4.2 Proofs of theorems 13.3 and 13.4 513 13.5 An RSA-based signature scheme with tighter security proof 514 13.6 Case study: PKOSI Signatures 516 13.6.1 Bleichenbacher's attack on PKcs1 signatures ...518 13.7 Signcryption: combining signatures and encryption 519 13.7. 1 Secure signcryption 521 13.7.2 Signcryption as an abstract interface ..523 13.7.3 Constructions: encrypt-then-sign and sign-then-encrypt ...526 13.7.4 A construction based on Diffie-Hellman key exchange 530 13.7.5 Additional desirable properties 532

...展开详情
img
shuqin_SQ

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐