Explore Go Cryptography (John Arundel) (Z-Library)

Contents Praise for Explore Go: Cryptography 12 Introduction 13 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Why learn about cryptography? . . . . . . . . . . . . . . . . . . . . . . 14 What do you need to know? . . . . . . . . . . . . . . . . . . . . . . . . 14 About the book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 What you’ll learn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 How to use this book . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1. Ciphers 17 Codes and ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 A shift cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Key points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Wheels within wheels . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Enciphering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 One byte at a time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Assume a spherical cow . . . . . . . . . . . . . . . . . . . . . . . . . . 20 From behaviour to test . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Choose your own adventure . . . . . . . . . . . . . . . . . . . . . . . 22 A first test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Anatomy of a test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 When should the test fail? . . . . . . . . . . . . . . . . . . . . . . . . 23 The world’s greatest bug detector . . . . . . . . . . . . . . . . . . . . . 24 A function about nothing . . . . . . . . . . . . . . . . . . . . . . . . . 24 Cutting code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 The smarty‐pants answer . . . . . . . . . . . . . . . . . . . . . . . . . 26 We’re gonna need a bigger test . . . . . . . . . . . . . . . . . . . . . . 27 A table of cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Combining cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 A suspiciously similar test . . . . . . . . . . . . . . . . . . . . . . . . 28 A test case struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Looping over the cases . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Lighting a fire under the test . . . . . . . . . . . . . . . . . . . . . . . 30 Introducing subtests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Subtests and t.Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A litany of failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Adding more cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A working table test for Encipher . . . . . . . . . . . . . . . . . . . . . 34 2

2. Enciphering 36 A simple enciphering filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 A command package . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Garbage in, garbage out . . . . . . . . . . . . . . . . . . . . . . . . . . 37 All about Eve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Reverse engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Variable keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Adding a keyhole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 New keys, new cases . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Compiler complaints . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Stochastic debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Getting back to green . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Getting the key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Defining a key flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Getting the flag value . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Enciphering with arbitrary keys . . . . . . . . . . . . . . . . . . . . . 47 3. Deciphering 49 Brute force and ignorance . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 A statistical vulnerability . . . . . . . . . . . . . . . . . . . . . . . . . 50 Howmany possible keys are there? . . . . . . . . . . . . . . . . . . . . 50 How safe is your safe? . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Doing it for the crack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Cribs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Designing a cracking function . . . . . . . . . . . . . . . . . . . . . . 52 First, we need Decipher . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Do we even need a test, then? . . . . . . . . . . . . . . . . . . . . . . . 54 New test, same old table . . . . . . . . . . . . . . . . . . . . . . . . . 55 Look before you loop . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 A deciphering tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Let’s not complicate encipher . . . . . . . . . . . . . . . . . . . . . . 57 4. Cracking 60 Testing a Crack function . . . . . . . . . . . . . . . . . . . . . . . . . 60 Failure is an option . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 A key‐guessing function . . . . . . . . . . . . . . . . . . . . . . . . . . 62 A command‐line cracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 What do users want? . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Crib constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Cracking a real ciphertext . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Waiting for the tiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 The devil in the details . . . . . . . . . . . . . . . . . . . . . . . . . . 66 0x89 is the magic number . . . . . . . . . . . . . . . . . . . . . . . . . 67 Printing the unprintable . . . . . . . . . . . . . . . . . . . . . . . . . 68 5. Keys 69 3

Lost in keyspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 The space of all possible keys . . . . . . . . . . . . . . . . . . . . . . . 70 How long should the key be? . . . . . . . . . . . . . . . . . . . . . . . 70 A keyspace the size of the universe . . . . . . . . . . . . . . . . . . . . 71 Multi‐byte keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Embiggening the key . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Updating the test cases . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Bytes in, bytes out . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Fixing Encipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 A magical solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Constraining the key index . . . . . . . . . . . . . . . . . . . . . . . . 74 Modulate your enthusiasm . . . . . . . . . . . . . . . . . . . . . . . . 74 The modulus operator . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Refactoring will continue until morale improves . . . . . . . . . . . . . 76 Testing longer keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Designing the test cases . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Sharpening the tools . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 When the right answer is wrong . . . . . . . . . . . . . . . . . . . . . 79 What kind of flag do we need? . . . . . . . . . . . . . . . . . . . . . . 80 The joy of hex(adecimal) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Binary notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 A string flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Where’s the BEEF? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Changing frequencies . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6. Cribs 84 Cracking long keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 What needs to change? . . . . . . . . . . . . . . . . . . . . . . . . . . 85 A byte at the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Length limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Checking our guesses . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 Knowing when to stop . . . . . . . . . . . . . . . . . . . . . . . . . . 87 A proper little cracker . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Updating the crack tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Applying brute force . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Crib considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 A false deciphering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 On being the right size . . . . . . . . . . . . . . . . . . . . . . . . . . 91 7. Passwords 92 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Password spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Dictionary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Extremely guessable passwords . . . . . . . . . . . . . . . . . . . . . . 94 Passphrases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4

Character sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Password policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 You’re really not helping . . . . . . . . . . . . . . . . . . . . . . . . . 96 Maximising the keyspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Unicode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 What does “random” mean? . . . . . . . . . . . . . . . . . . . . . . . 98 Predictability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Binary choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8. Blocks 102 Block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Why blocks? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 The cipher.Block interface . . . . . . . . . . . . . . . . . . . . . . . 104 Plugs and sockets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Adapting the shift cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 The Encryptmethod . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Where’s the key? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Fixing the key size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 A cipher constructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 The NewCipher function . . . . . . . . . . . . . . . . . . . . . . . . . 107 If the key fits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 A polite refusal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 A special error value . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Wrapping errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Writing NewCipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Implementing the cipher.Block interface . . . . . . . . . . . . . . . . . . . 110 Testing Encrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Circumstances alter cases . . . . . . . . . . . . . . . . . . . . . . . . 111 Creating the cipher object . . . . . . . . . . . . . . . . . . . . . . . . 112 A test for Encrypt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Writing Encrypt and Decrypt . . . . . . . . . . . . . . . . . . . . . . . 113 Forgotten something? . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9. Modes 117 Handling data in blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Updating the encipher tool . . . . . . . . . . . . . . . . . . . . . . . . 118 Block by block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 The cipher.BlockMode interface . . . . . . . . . . . . . . . . . . . . . . . . 119 A simple block mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Testing CryptBlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Creating the encrypter object . . . . . . . . . . . . . . . . . . . . . . 122 Implementing CryptBlocks . . . . . . . . . . . . . . . . . . . . . . . 122 Using a BlockMode in encipher . . . . . . . . . . . . . . . . . . . . . . 124 5

Block alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 When misaligned data attacks . . . . . . . . . . . . . . . . . . . . . . 126 Checking our assumptions . . . . . . . . . . . . . . . . . . . . . . . . 126 The long and short of it . . . . . . . . . . . . . . . . . . . . . . . . . . 126 A test about nothing . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 A panic‐proof CryptBlocks . . . . . . . . . . . . . . . . . . . . . . . . 128 10. Padding 129 A padding scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Making ends meet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 The “illegal pixel” problem . . . . . . . . . . . . . . . . . . . . . . . . 130 An unambigous padding scheme . . . . . . . . . . . . . . . . . . . . . 130 Testing Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Implementing Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Writing Unpad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Padding input to encipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Adding the padding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Checking the results . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Deciphering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Adding the unpadding . . . . . . . . . . . . . . . . . . . . . . . . . . 138 A decrypter that implements BlockMode . . . . . . . . . . . . . . . . . 138 Waiting for the tiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 11. Enumeration 142 Adventures in keyspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 A new test for cracking long keys . . . . . . . . . . . . . . . . . . . . . 142 A block is a black box . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Enumerating long keys . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Designing a Next function . . . . . . . . . . . . . . . . . . . . . . . . 145 Testing Next . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Big endians and little endians . . . . . . . . . . . . . . . . . . . . . . . 147 A simple implementation . . . . . . . . . . . . . . . . . . . . . . . . . 147 Checking our key guesses . . . . . . . . . . . . . . . . . . . . . . . . . 148 The soul of a new cracker . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 We apologise for the delay . . . . . . . . . . . . . . . . . . . . . . . . 150 Benchmarking key cracking . . . . . . . . . . . . . . . . . . . . . . . 150 Pick an easier problem . . . . . . . . . . . . . . . . . . . . . . . . . . 151 Understanding benchmark output . . . . . . . . . . . . . . . . . . . . 151 Cranking up the difficulty . . . . . . . . . . . . . . . . . . . . . . . . . 152 Ballparking a realistic crack time . . . . . . . . . . . . . . . . . . . . . 152 A test we might live to see pass . . . . . . . . . . . . . . . . . . . . . . 153 Updating the crack tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Putting it all together . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Will it crack? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Parallelisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 Big computers are too slow . . . . . . . . . . . . . . . . . . . . . . . . 156 6

Dense computers become black holes . . . . . . . . . . . . . . . . . . 156 Parallel cracking is still useful . . . . . . . . . . . . . . . . . . . . . . 157 But we won’t implement it here . . . . . . . . . . . . . . . . . . . . . . 157 Strong keys can’t be cracked . . . . . . . . . . . . . . . . . . . . . . . 157 12. Entropy 159 Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Entropy: a measure of our ignorance . . . . . . . . . . . . . . . . . . . 160 Entropy of digital messages . . . . . . . . . . . . . . . . . . . . . . . . 161 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Enciphered data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Identifying ciphertexts . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Describing sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 A generating algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 163 The shortest program that describes a sequence . . . . . . . . . . . . . 164 Kolmogorov complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Complexity from simplicity . . . . . . . . . . . . . . . . . . . . . . . . 165 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Randomness is high entropy . . . . . . . . . . . . . . . . . . . . . . . 167 Key generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 Pragmatic non‐determinism . . . . . . . . . . . . . . . . . . . . . . . 167 A little entropy goes a long way . . . . . . . . . . . . . . . . . . . . . . 168 Being unpredictable . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 13. Randomness 170 Pseudo‐random generation . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Randomness in games . . . . . . . . . . . . . . . . . . . . . . . . . . 171 The Fibonacci sequence . . . . . . . . . . . . . . . . . . . . . . . . . 171 A simple random generator . . . . . . . . . . . . . . . . . . . . . . . . . . 171 A Fibonacci generator in Go . . . . . . . . . . . . . . . . . . . . . . . 172 Repeatability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Seeding the RNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Security problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Uniformity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 “Secure enough” random generators . . . . . . . . . . . . . . . . . . . . . . 175 Environmental noise . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 The system entropy pool . . . . . . . . . . . . . . . . . . . . . . . . . 176 Security is relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 You don’t need to outrun the bear . . . . . . . . . . . . . . . . . . . . . 176 Keeping secrets from the gods . . . . . . . . . . . . . . . . . . . . . . . . . 177 Hardware entropy sources . . . . . . . . . . . . . . . . . . . . . . . . 177 Defeating “God Emperor Eve” . . . . . . . . . . . . . . . . . . . . . . . 177 Quantummeasurements . . . . . . . . . . . . . . . . . . . . . . . . . 178 7

A quantum randomness source . . . . . . . . . . . . . . . . . . . . . . 178 Generating quantum keys . . . . . . . . . . . . . . . . . . . . . . . . . 179 14. Chains 180 Visualising the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 A completely random image . . . . . . . . . . . . . . . . . . . . . . . 181 Separating metadata and pixel data . . . . . . . . . . . . . . . . . . . . 183 Hidden figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Muddying the waters . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 What’s wrong with this picture? . . . . . . . . . . . . . . . . . . . . . . 186 Mallory in the middle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 ECB: a block‐headed operating mode . . . . . . . . . . . . . . . . . . . 187 Introducing Mallory . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Block replay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Dropping and modifying blocks . . . . . . . . . . . . . . . . . . . . . 188 More sophisticated modes . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Counter mode (CTR) . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Nonces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 Cipher Block Chain (CBC) . . . . . . . . . . . . . . . . . . . . . . . . . 189 Initialization Vector (IV) . . . . . . . . . . . . . . . . . . . . . . . . . 190 Generating a secure IV . . . . . . . . . . . . . . . . . . . . . . . . . . 190 Implementing CBC mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Enciphering in CBC mode . . . . . . . . . . . . . . . . . . . . . . . . 191 The updated encipher program . . . . . . . . . . . . . . . . . . . . . 192 Updating the decipher program . . . . . . . . . . . . . . . . . . . . . 194 The devil in disguise . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 15. Hashing 197 Message integrity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 The night is dark, and full of errors . . . . . . . . . . . . . . . . . . . . 198 Bit‐flipping and block‐dropping . . . . . . . . . . . . . . . . . . . . . . 198 Integrity checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Digests and hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Hash tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 Buckets and distribution . . . . . . . . . . . . . . . . . . . . . . . . . 200 Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Cryptographic hashing . . . . . . . . . . . . . . . . . . . . . . . . . . 201 Simple hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 A naïve algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 Implementing LenHash . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Problems with LenHash . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Preimage attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 A slight improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Implementing SumHash . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Testing SumHash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 A preimage attack on SumHash . . . . . . . . . . . . . . . . . . . . . . 206 8

The avalanche effect . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Real hash algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 SHA‐1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 SHA‐256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Password hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Zero‐knowledge secret storage . . . . . . . . . . . . . . . . . . . . . . 208 Password hashing requirements . . . . . . . . . . . . . . . . . . . . . 209 Rainbow tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Salting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 Slow down, you move too fast . . . . . . . . . . . . . . . . . . . . . . . 210 16. Coins 212 Cryptocurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Let there be “Bobcoin” . . . . . . . . . . . . . . . . . . . . . . . . . . 213 The problem of trust . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 A distributed digital ledger . . . . . . . . . . . . . . . . . . . . . . . . 214 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 The double‐spending problem . . . . . . . . . . . . . . . . . . . . . . 214 Ordering transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 The blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Doomed stubs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 Integrity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Proof of work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Up in smoke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 Proof of stake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 17. Authentication 219 Message integrity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Hash preimage attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 220 Chosen ciphertext attacks . . . . . . . . . . . . . . . . . . . . . . . . . 220 MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Length extension attacks . . . . . . . . . . . . . . . . . . . . . . . . . 221 HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Key exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Key splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Asymmetric encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Public and private keys . . . . . . . . . . . . . . . . . . . . . . . . . . 224 The Diffie‐Hellman‐Merkle protocol . . . . . . . . . . . . . . . . . . . . . . 224 A one‐way function for key exchange . . . . . . . . . . . . . . . . . . . 225 A DHMworked example . . . . . . . . . . . . . . . . . . . . . . . . . 226 The reveal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Public‐key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 9

Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 The chain of trust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 18. Cryptography 231 A little history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 The origins of DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Tripling down on DES . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 The starting grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Round and round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 Confusion and diffusion . . . . . . . . . . . . . . . . . . . . . . . . . 234 Putting it all together . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 Implementing AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Getting ready to rumble . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Ding ding, round one . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 The diffusion loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 The last round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 AES encryption in practice . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 Enciphering with AES‐CBC . . . . . . . . . . . . . . . . . . . . . . . . 240 Updating encipher and decipher . . . . . . . . . . . . . . . . . . . . . 241 Encryption plus authentication . . . . . . . . . . . . . . . . . . . . . . 244 Enciphering with AES‐GCM . . . . . . . . . . . . . . . . . . . . . . . . 245 The final final version . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Implementation fails . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Mashing the keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 Tomorrow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 The future is quantum . . . . . . . . . . . . . . . . . . . . . . . . . . 250 Quantum parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 The catch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Why your computer isn’t quantum… yet . . . . . . . . . . . . . . . . . 252 Post‐quantum cryptography . . . . . . . . . . . . . . . . . . . . . . . 253 Afterword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 About this book 254 Who wrote this? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Free updates to future editions . . . . . . . . . . . . . . . . . . . . . . . . . 255 Join my Go Club . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 For the Love of Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 The Power of Go: Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 Credits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 10

Acknowledgements 257 11

Praise for Explore Go: Cryptogra- phy I laughed, I learned. It’s a great book that manages to explain complicated ideas in really simple, straightforward language. —Dian Amencourt One of the most accessible and even fun books about cryptography I’ve ever read. John writes vividly, with many a neat turn of phrase, and the text is full of wit and humour. —Kurtis Connor This is a remarkable book, practically fizzing with enthusiasm for its subject. It whisks you through the worlds of cryptography, mathematics, physics, and com- puter science, and shows you that they’re all connected in surprising and thought- provoking ways. Highly enjoyable. —Cuong Quoc As a software engineer who works on a security product (I won’t say which one), I’ve always felt like a bit of an imposter when it comes to cryptography: I hoped no one would ever ask me how a cipher actually works. After reading this book, I now feel a lot more confident. Thanks, John! —Yuliana M So friendly and easy to read. This has really unlocked a few things for me. I can’t recommend this book highly enough! —Joseph Adewale John has a knack of writing almost luminously clear explanations that stick in your mind long after finishing the book. —Patrick Devlin 12

Introduction This book is all about keeping secrets. It shows you how to set up secret meeting places and a secret post office, and how to disguise your messages and maps. It shows you lots of secret codes and signals. —Falcon Travis and Judy Hindley, “The KnowHow Book of Spycraft”, 1975 First, why should you even read a book about cryptography? It’s a valid question. Cryptography When I was a kid, one of my favourite books (and there were many) was The KnowHow Book of Spycraft, which, as you might have gathered from the quotation above, is all about secret messages. Kids love secret messages and spies, of course, along with dinosaurs, trains, and poop. But our obsessive interest in these subjects tends to fade as we grow older (except for dinosaurs, perhaps). So why, assuming you didn’t grow up to become a spy yourself, is it worth your while to read this book, which is also all about secret messages? 13

Why learn about cryptography? Well, firstly, the subject is cool and interesting. I thought so when I was seven years old, evidently, and I still think so now, when I’m just a little older. It’s okay to study and learn about things just because they’re interesting, even if they don’t really have any practical value. That’s something kids don’t need telling, but many adults have forgot‐ ten, sadly enough. Actually, though, cryptography is rather important, and we rely on it every day of our lives, even though we might not be aware of it. The credit card or payment service you used to buy this book uses cryptographic algorithms and protocols to keep your trans‐ actions secure (we hope). The messages, photos, and videos that you exchange with friends, family, and co‐workers are encrypted so that they can’t fall into the wrong hands (we better hope). And so on. If you use cryptocurrencies such as Bitcoin, well, guess what? It’s not called “crypto” for nothing. And it’s not just criminals and fraudsters who value the security and anonymity that comes from strong, modern cryptography: we all do. Your computer, your phone, your car—heck, probably even your fridge—contain hardware and software dedicated to cryptography. The internet relies on it. The banking system depends on it. Basically, modern life is more or less built on cryptography. Isn’t it a bit weird that most of us don’t really know the first thing about it? Maybe it’s time we did. What do you need to know? Let’s start with what you don’t need to know. You don’t need to be able to design your own ciphers or cryptographic protocols. In fact, you shouldn’t do that at all unless you’re a real expert, and probably not even then. Some of the smartest people who ever lived have designed cipher systems that turned out later to be insecure, in many cases woefully so. Even if you’re one of those people (and you did buy this book, after all), you’re much better off just using one of the mod‐ ern cryptographic schemes in which no vulnerabilities have yet been found. Even using a genuinely secure cipher, though, it’s still possible that you (or I) might make mistakes when incorporating it into software (indeed, it’s highly likely: this hap‐ pens all the time). It’s incredibly easy to make small errors or omissions that render the resulting program dangerously insecure for its users: even worse, you (and they) might never know until it’s too late. If you’re wise, then, you won’t try to write your own cryptography software either. Just use existing programs that have been written and debugged by lots of smart people and tested by many more. To use cryptography securely, though, even something as simple as a password, you do need to know something about what makes things secure, or not. We can probably recognise a weak password when we see one (especially if it’s “password”), but what makes a strong password strong, and why? Similarly, we’re aware that some ciphers are weak and others are strong, but why? 14

The best way to answer that question, ironically enough, is to write your own cryptog‐ raphy software, and that’s what we’re going to do together in this book. I want to em‐ phasise, though, that we’ll be doing this purely for fun and learning purposes. You shouldn’t use any of the software we build here to protect actual secrets (at least, not until we get to the last chapter). Modern cryptography is extremely sophisticated, and if I tried to just explain that stuff right away it would probably kill both of us. Instead, we’ll work up to it, starting with something very simple, and gradually incorporating some of the many improvements in ciphers over the last two thousand years or so. In the beginning, we’ll sweat the details and look at every nut and bolt, while it’s still easy to do so. As things get more complicated and closer to the modern state of the art, there’ll be a bit less detail and a bit more hand‐waving, but that’s okay. You’ll still learn everything you want to know (and, indeed, should know), as a software engineer who occasionally has to dip a toe into cryptographic waters. About the book This book will explain the fundamental principles of ciphers, by introducing you to the simplest cipher scheme imaginable. You’ll learn how it works, implement it in Go, and then you’ll find out why it won’t protect your secrets from anybody who really wants to know them (except perhaps your kid sister). What you’ll learn You’ll learn about cipher keys: how they work, what makes them weak or strong, how to generate them, and how to defeat them. You’ll learn how to choose good passwords, and how to store and retrieve them securely, and you’ll learn the “10 Do’s and 500 Don’ts” of writing software applications that handle passwords. In the book, we’ll gradually improve the security and usability of our toy cipher scheme, adding better keys, blocks, operating modes, hashing, authentication, and so on. We’ll talk about predictability and randomness, message digests, cryptocurrency, and all sorts of other stuff that’s fun and interesting (at least, if you’re the kind of person who likes secret codes and dinosaurs). There’ll necessarily be a little bit of math. Now, computer programmers are often some‐ what mathematically inclined, but many aren’t, and that’s okay. If you’re one of the lat‐ ter, don’t worry. We will come across a few equations and formulas, but if they just look like illegible squiggles to you, it doesn’t matter. You will certainly understand the gen‐ eral principles involved, and that’s just fine. (If you are a math whiz, you’ll probably realise pretty soon that I am not. Please email me with a list of all the mistakes you find in the book: I always enjoy hearing from read‐ ers.) 15

How to use this book Throughout this book we’ll be working together to develop some cryptographic tools and packages in Go. There are dozens of challenges for you to solve throughout the book, each designed to help you test your understanding of the concepts you’ve just learned. If you get stuck on any of these, or just want to check your results, each challenge is ac‐ companied by hints, and a complete sample solution, including tests. These are linked in the text, and you can also find them on GitHub here: • https://github.com/bitfield/eg‐crypto You’ll need to install Go on your computer, if you don’t have it already. Follow the in‐ structions on the Go website to download and install Go: • https://go.dev/learn/ With that out of the way, let’s begin! 16

1. Ciphers If you reveal your secrets to the wind you should not blame the wind for revealing them to the trees. —Kahlil Gibran, “Sand and Foam” (photo by Earl Grey Ltd) Let’s start with a quick introduction to the basics of cryptography (from the Greek for “secret writing”). First, let’s distinguish codes from ciphers. These words are often used interchangeably, but strictly speaking they refer to two different things. Codes and ciphers To encrypt something is to hide or obscure its contents, and there are many ways to do this. One way is to use a code: an alternate, usually shorter, way of representing the text of a message. For example, you’ve probably heard of the Morse code, in which each letter of the al‐ phabet is represented by a distinct pattern of short and long sounds. If you can trans‐ mit sound, though, why not just send a spoken message instead of a bunch of beeps? 17

The answer is that human speech is complex and covers a broad spectrum of frequen‐ cies, meaning that it takes up a lot of bandwidth (or, equivalently, that it needs a high bitrate). If you’ve ever struggled to understand someone or to make yourself understood over a poor‐quality telephone connection, you’ll know what I mean. When there isn’t much bandwidth available, for example in a noisy or lossy channel such as a long telegraph wire, or a low‐power radio transmission, Morse and other codes are a far more efficient medium than speech for getting your message through, quickly and reliably. Note that a code isn’t necessarily intended to hide the contents of the message; it’s often just a way of shortening it or making it easier to transmit reliably, as with the Morse code. Codes can be used to send secret messages, though. For example, if we want to have a conversation that may be overheard, we might agree beforehand that the word “tomato” means “enemy in sight”, and that “parmesan” means “activate the hidden sleeping‐gas capsule”. Then I can send you the following message in clear (that is, without needing to hide its contents): TOMATO. PARMESAN. If the message should be intercepted, the enemy won’t be able to make anything of it. They’ll probably just assume it’s my shopping list. Note that it doesn’t matter what code words we choose, only that we both agree on what they signify. One drawback of such codes is that the list of code words and their meanings—the code book—tends to be large, and that makes it difficult to keep it secure. Should the code book fall into enemy hands, the code becomes useless until you can arrange to dis‐ tribute a new code book to all your agents, which is expensive and time‐consuming. So another kind of encryption—message hiding—is to use a cipher. This works by substi‐ tuting, usually, one letter for another, instead of a word or phrase. If the text is repre‐ sented digitally (that is, by using numbers to represent letters), then the cipher oper‐ ates by transforming one number into another, but the principle is the same. A shift cipher As long as both the sender and receiver (traditionally known as “Alice” and “Bob”, since that’s slightly more fun than just calling them A and B) agree on the cipher scheme, or algorithm, they can decrypt each other’s messages. Let’s see an example. Suppose Alice and Bob agree that every time the letter A occurs in the plaintext—the original message—Alice will replace it with B. Each B in the plaintext will be replaced by C, and so on. In effect, this scheme just “adds one” to each letter to encipher it. What does a plaintext like HEY BOB U UP look like, when enciphered using this scheme? If H becomes I, then the first letter of the ciphertext must be I. The second letter, E, be‐ comes F, and so on. Encipher the rest of the message for yourself. 18

How can we decipher such a message, then? Simple: just reverse the process. For exam‐ ple, suppose Bob sends the following reply: TVSF CBF DPNF PO PWFS Can you work out whether Alice and Bob will be getting together tonight? Of course you can. Just “subtract one” from each letter to recover the plaintext. For example, T becomes S, V becomes U, and so on. Key points You don’t have to always shift the letters by one place; you can choose a different num‐ ber if you like. Of course, the person reading the message will need to know this num‐ ber too, but you can agree that between you in advance. Naturally, it needs to be kept secret: anyone who knows this prearranged value will be able to decipher messages (and encipher them too). This key is an important input to the cipher, along with the plaintext. Indeed, we can think of a cipher as combining the plaintext with the key, in some arbitrary way, to pro‐ duce the ciphertext. Deciphering is the reverse of this process. Wheels within wheels A popular children’s toy illustrates this idea: the “decoder ring” or cipher wheel, con‐ structed from two rotating discs with the alphabet printed around them. It may not exactly be military‐grade encryption, but it’s an easy and fun way of exchanging secret messages with friends. Just choose your key (for example, 1) and rotate the outer disc by that number of places, and you’re ready for enciphering and deciphering. This kind of scheme—where we shift letters around the alphabet by some agreed number of places—is called a shift cipher, or sometimes a “Caesar” cipher, since Julius Caesar is popularly supposed to have used one to keep his messages secret. Not that it worked out awfully well for him in the end, but never mind. Modern ciphers are a bit more complicated in their detailed workings than Caesar’s shift cipher, but surprisingly similar in principle. So let’s start with this one and work our way up. Enciphering We’ll begin by trying to implement the shift cipher in a Go program. Our program should be able to take a message, encipher it using the shift cipher, and print out the resulting ciphertext. And let’s generalise the idea of a “message” to any arbitrary data. Maybe Julius Caesar didn’t have to worry about communicating things like graphics, video, or even binary executables, but we do. 19

One byte at a time In general, the most flexible way to represent arbitrary data in Go is as a []byte, that is, a slice of values each of which corresponds to one byte of data. A slice is the Go name for an ordered collection of values. You can think of the type []byte as meaning “a bunch of bytes”. For example, if you open and read a file from disk, or read from a network connection, you’ll find that you get the data as a bunch of bytes—a []byte—regardless of what kind of data the bytes actually represent. So the API to our shift cipher package (let’s call it shift, to be straightforward) is start‐ ing to take shape. We need to be able to accept data as bytes, transform it using the ci‐ pher scheme, and produce the resulting data as output, again in the form of bytes. Even with our fairly simple cipher scheme, this still sounds like a hard problem. I’ll let you into one of the software engineering fraternity’s best‐kept secrets now (make sure no one’s reading over your shoulder): We don’t like to solve hard problems. It can be done, of course, but it’s very much a last resort. Instead, we much prefer to turn a complicated problem into a simple problem, and solve that first. Then it’s just a case of tweaking our solution until it works for the orig‐ inal problem, as well as our simplified version. We’re not the only ones who like to do this; scientists call it the “spherical cow” tech‐ nique, after the old joke about the farmer who made the mistake of asking a physicist for advice on improving milk production. “First,” said the physicist, after a little thought, “assume a spherical cow…” Assume a spherical cow The simplest, most “spherical” version of our problem that we can think of is just some function that transforms a slice of bytes by enciphering it with the key of 1. Let’s call this imaginary function Encipher. For the moment, we won’t worry about using different keys, and we’ll also punt on the issue of getting the data in and out of the program. Let’s get the spherical cow working first, then we’ll add things step by step to make it more realistic. Before trying to implement any function, though, it’s always important to have a clear and specific idea of what it should do. Otherwise, it’s easy for us to get confused by try‐ ing to solve two problems at once: what the function should do, and how it should do it. So let’s take the first problem first. It helps to start by writing down a brief sentence or two describing the function’s be‐ haviour, ideally with specific examples: given some value as input, what should the function return as a result? 20