3.4 Composing PRGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1 A parallel construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 A sequential construction: the Blum-Micali method . . . . . . . . . . . . . 59
3.4.3 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5 The next bit test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.6 Case study: the Salsa and ChaCha PRGs . . . . . . . . . . . . . . . . . . . . . . . . 67
3.7 Case study: linear generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.7.1 An example cryptanalysis: the linear congruential generator . . . . . . . . . 70
3.7.2 The subset sum generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.8 Case study: cryptanalysis of the DVD encryption system . . . . . . . . . . . . . . . 74
3.9 Case study: cryptanalysis of the RC4 stream cipher . . . . . . . . . . . . . . . . . . 77
3.9.1 Security of RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.10 Generating random bits in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.11 A broader perspective: computational and statistical indistinguishability . . . . . . 82
3.11.1 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.12 A fun application: coin flipping and bit commitment . . . . . . . . . . . . . . . . . . 88
3.13 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Block ciphers 96
4.1 Block ciphers: basic definitions and properties . . . . . . . . . . . . . . . . . . . . . 96
4.1.1 Some implications of security . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.1.2 Efficient implementation of random permutations . . . . . . . . . . . . . . . 101
4.1.3 Strongly secure block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.1.4 Using a block cipher directly for encryption . . . . . . . . . . . . . . . . . . 102
4.1.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.2 Constructing block ciphers in practice . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.1 Case study: DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2.2 Exhaustive search on DES: the DES challenges . . . . . . . . . . . . . . . . 113
4.2.3 Strengthening ciphers against exhaustive search: the 3E construction . . . . 115
4.2.4 Case study: AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.3 Sophisticated attacks on block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.3.1 Algorithmic attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3.2 Side-channel attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.3.3 Fault injection attacks on AES . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.3.4 Quantum exhaustive search attacks . . . . . . . . . . . . . . . . . . . . . . . 131
4.4 Pseudo-random functions: basic definitions and properties . . . . . . . . . . . . . . 132
4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.4.2 Efficient implementation of random functions . . . . . . . . . . . . . . . . . 133
4.4.3 When is a secure block cipher a secure PRF? . . . . . . . . . . . . . . . . . 134
4.4.4 Constructing PRGs from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.4.5 Mathematical details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.5 Constructing block ciphers from PRFs . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.6 The tree construction: from PRGs to PRFs . . . . . . . . . . . . . . . . . . . . . . . 147
4.6.1 Variable length tree construction . . . . . . . . . . . . . . . . . . . . . . . . 151
4.7 The ideal cipher model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
v
