s2.md (11895B)
1 ### Set 2 2 3 #### 2.9 4 5 PKCS #7 padding (see section 10.3 of [RFC-2315][pkcs]) just means that 6 to pad a message of length 'l' to 'k' bytes, one appends `k - (l mod k)` 7 bytes -- each of value `k - (l mod k)` -- to the message. So here we get 8 four bytes' worth of padding, each of value 04: 9 10 $ pkcs7 20 "YELLOW SUBMARINE" | xxd 11 00000000: 5945 4c4c 4f57 2053 5542 4d41 5249 4e45 YELLOW SUBMARINE 12 00000010: 0404 0404 .... 13 14 Of note, the case for `l mod k = 0` is interesting, since even though 15 we don't necessarily *need* padding in such a case, we get k bytes 16 of padding, each with value k, anyway. If one asks for padding, he's 17 getting padding. 18 19 (N.b., the reason is that a deciphering algorithm can thus always treat 20 a string as padded and look only at the last byte to determine the 21 number of padding bytes to strip. In the case of `l mod k = 0`, the 22 extra padded block just gets chopped entirely.) 23 24 [pkcs]: https://datatracker.ietf.org/doc/html/rfc2315#section-10.3 25 26 #### 2.10 27 28 Here we're implementing CBC mode for AES. The essential difference 29 compared to ECB is that CBC (i.e., cipher block chaining) operates 30 sequentially; ciphertext is produced by folding over the initialization 31 vector + plaintext in 16-byte blocks, each time XOR-ing the current 32 block with the previous one before encrypting the result with AES-128 in 33 ECB mode. 34 35 Again, I think it's worth using the openssl tool to gain familiarity 36 with it: 37 38 $ key=$(echo -n "YELLOW SUBMARINE" | xxd -p) 39 $ openssl enc -aes-128-cbc \ 40 -a -d -K "$key" -nosalt -iv 0 \ 41 -in data/s2/q10_input.txt | head -2 42 I'm back and I'm ringin' the bell 43 A rockin' on the mike while the fly girls yell 44 45 The `aes` binary will also get the job done: 46 47 $ key=$(echo -n "YELLOW SUBMARINE" | xxd -p) 48 $ ciphertext=$(cat data/s2/q10_input.txt | \ 49 base64 -d | xxd -p | tr -d '\n') 50 $ iv=$(printf '0%.0s' {1..32}) 51 $ aes decrypt cbc --iv "$iv" "$key" "$ciphertext" | xxd -r -p | head -2 52 I'm back and I'm ringin' the bell 53 A rockin' on the mike while the fly girls yell 54 55 #### 2.11 56 57 Here we want to build what I've dubbed a `chaosEncrypter` and then something 58 to detect what it might be using on any given iteration. Easy enough: 59 60 -- in Cryptopals.Block.Attacks 61 62 chaosEncrypter 63 :: PrimMonad m 64 => BS.ByteString 65 -> MWC.Gen (PrimState m) 66 -> m BS.ByteString 67 chaosEncrypter plaintext gen = do 68 key <- bytes 16 gen 69 pre <- MWC.uniformR (5, 10) gen >>= flip bytes gen 70 pos <- MWC.uniformR (5, 10) gen >>= flip bytes gen 71 72 let tex = pre <> plaintext <> pos 73 pad = roundUpToMul 16 (BS.length tex) 74 bs = CU.pkcs7 pad tex 75 76 ecb <- MWC.uniform gen 77 78 if ecb 79 then pure $ AES.encryptEcbAES128 key bs 80 else do 81 iv <- bytes 16 gen 82 pure $ AES.encryptCbcAES128 iv key bs 83 84 Note the use of PKCS#7 padding in order to make sure the input length is 85 always valid. The detection oracle can be produced by simply fmapping 86 `Cryptopals.Block.Tools.detectMode` over this. 87 88 Checking it in action, with some tracing to determine it's working 89 properly: 90 91 > fmap detectMode $ chaosEncrypter "yellow submarineyellow 92 submarineyellow submarineyellow submarine" gen 93 was really CBC 94 CBC 95 96 > fmap detectMode $ chaosEncrypter "yellow submarineyellow 97 submarineyellow submarineyellow submarine" gen 98 was really ECB 99 ECB 100 101 #### 2.12 102 103 Here we're breaking AES in ECB mode via byte-at-a-time decryption. The 104 idea is that, given an AES encryption oracle, we can incrementally 105 add or subtract bytes from our input to 1) identify that the oracle 106 is using ECB mode, 2) figure out the block size of the cipher, and 3) 107 incrementally decrypt the ciphertext it produces. 108 109 The block size in AES-128 is 16 bytes, and this becomes apparent when 110 encrypting at least 17 repeated bytes (as the initial 16-byte ciphertext 111 block will be unchanged). Here `alienEncrypter` is the oracle: 112 113 > B16.encodeBase16 $ alienEncrypter (BS.replicate 32 65) 114 57eef2e16c3867b9889350eb5732c183 115 57eef2e16c3867b9889350eb5732c183 116 99203986e6420a8cfed14ef4052331cd 117 912d36f3419517ff9092e2f53d814a7b 118 41d4bfa372eca117569d2ccbbf34e848 119 [..] 120 121 The mode detector correctly guesses this to be running in ECB mode when 122 using 32 bytes of repeated input or more, since that gives us enough 123 bytes to get repeated blocks in the ciphertext: 124 125 > detectMode $ alienEncrypter (BS.replicate 32 65) 126 ECB 127 128 The `Cryptopals.Block.Attacks.incrByteEcbAttack` function attacks the provided 129 oracle by incrementally decrypting bytes: 130 131 > TIO.putStrLn $ TE.decodeUtf8 $ incrByteEcbAttack alienEncrypter 132 Rollin' in my 5.0 133 With my rag-top down so my hair can blow 134 The girlies on standby waving just to say hi 135 Did you stop? No, I just drove by 136 137 #### 2.13 138 139 (N.b., I thought this was super fun.) 140 141 The idea here is to craft a ciphertext block that can be swapped into 142 the opportune position. We want to align everything so that the final 143 block will start right after the `role=` string, and then craft it as 144 the enciphered `admin` plus padding. 145 146 A 13-byte long email address will be sufficient to push everything to 147 the desired block boundaries. I used the following: 148 149 > B16.encodeBase16 $ cpeEncrypt "me@retorts.io" 150 151 which produces the following hex-encoded ciphertext (aligned in blocks): 152 153 c4352ebf0bbf88ab50941d47fe7b9e90 154 38fa40090568d9af9fa626a8a55409fd 155 921defeffad5601a06500289684b16ca <- 'user' block 156 157 Now, inserting some malicious plaintext: 158 159 > let admin = "admin" <> BS.replicate 11 11 160 > B16.encodeBase16 $ cpeEncrypt ("me@retorts" <> admin <> ".io") 161 162 and that produces the following hex-encoded ciphertext: 163 164 c4352ebf0bbf88ab50941d47fe7b9e90 165 d5adeeedb90f079930a3d9c4492746e5 <- evil block 166 38fa40090568d9af9fa626a8a55409fd 167 921defeffad5601a06500289684b16ca <- 'user' block 168 169 Now all we want to do is replace the final block in the initial 170 ciphertext, corresponding to `user` and padding, with our malicious 171 enciphered block: 172 173 c4352ebf0bbf88ab50941d47fe7b9e90 174 38fa40090568d9af9fa626a8a55409fd 175 d5adeeedb90f079930a3d9c4492746e5 <- evil block 176 177 Now we decrypt it (called `evil` below), mua ha ha: 178 179 > let Right ciph = B16.decodeBase16 $ TE.encodeUtf8 evil 180 > cpeDecrypt ciph 181 "email=me@retorts.io&uid=10&role=admin\v\v\v\v\v\v\v\v\v\v\v" 182 183 It's even nicer when one strips the padding as per challenge 15: 184 185 > CU.unpkcs7 $ cpeDecrypt ciph 186 Just "email=me@retorts.io&uid=10&role=admin" 187 188 #### 2.14 189 190 The idea is to inject a block whose ciphertext is known, followed by the 191 malicious alignment block(s) necessary to perform the attack. One can 192 figure out ciphertext corresponding to any block of repeated bytes by 193 just feeding in more than a block's worth of them -- necessarily some 194 (plaintext) block will then include only that repeated byte. 195 196 E.g.: one can determine that "AAAAAAAAAAAAAAAA" encrypts to 197 "57eef2e16c3867b9889350eb5732c183", so we can look for that ciphertext 198 in the result in order to locate an "origin," only analyzing ciphertexts 199 in which it appears (since, if it doesn't happen to align perfectly in 200 a block, we won't see it in the ciphertext). By chopping that and any 201 preceeding bytes from the ciphertext, the attack reduces to the simpler 202 version we've already performed. 203 204 The `Cryptopals.Block.Attacks.hardIncrByteEcbAttack` function will 205 perform the attack; it's just a version of `incrByteEcbAttack` 206 from challenge 12 adapted to handle a monadic oracle. 207 `Cryptopals.Block.Attacks.attackProxy` wraps the `weirdEncrypter` oracle 208 and does the work of inserting/locating our malicious block and pruning 209 the ciphertext for us, so we can attack `weirdEncrypter` via: 210 211 > plain <- hardIncrByteEcbAttack (attackProxy weirdEncrypter) gen 212 > TIO.putStrLn $ TE.decodeUtf8 plain 213 Rollin' in my 5.0 214 With my rag-top down so my hair can blow 215 The girlies on standby waving just to say hi 216 Did you stop? No, I just drove by 217 218 #### 2.15 219 220 To validate PKCS#7 padding, just look at the last byte of the input, 221 take that many bytes from the end, and check that they're all the same. 222 `Cryptopals.Util.unpkcs7` will do it (and strip the padding), returning 223 Nothing on inputs with invalid padding: 224 225 > CU.unpkcs7 ("ICE ICE BABY\x04\x04\x04\x04" :: BS.ByteString) 226 Just "ICE ICE BABY" 227 > CU.unpkcs7 ("ICE ICE BABY\x05\x05\x05\x05" :: BS.ByteString) 228 Nothing 229 > CU.unpkcs7 ("ICE ICE BABY\x01\x02\x03\x04" :: BS.ByteString) 230 Nothing 231 232 #### 2.16 233 234 This one is pretty cool and tricky. AES encryption in CBC (cipher block 235 chaining) mode proceeds as follows: 236 237 for plaintext p = (p_1, .., p_l) 238 block encryption w/key k enc_k 239 initialization vector IV 240 xor operator + 241 242 let c_0 = IV 243 c_1 = enc_k(c_0 + p_1) 244 c_2 = enc_k(c_1 + p_2) 245 .. 246 c_l = enc_k(c_{l-1} + p_l) 247 248 in ciphertext c = (c_0, c_1, c_2, .., c_l) 249 250 and decryption goes like this: 251 252 for ciphertext c = (c_0, c_1, c_2, .., c_l) 253 block decryption w/key k dec_k 254 xor operator + 255 256 let p_1 = dec_k(c_1) + c_0 257 p_2 = dec_k(c_2) + c_1 258 .. 259 p_l = dec_k(c_1) + c_{l-1} 260 261 in plaintext p = (p_1, p_2, .., p_l) 262 263 Let plaintext block 3 be "AAAAA!admin!true". Since: 264 265 p_2 = dec_k(c_2) + c_1 266 267 if ciphertext block 2 is ".....X.....X...." for unspecified bytes ".", 268 then we can recover the plaintext "AAAAA;admin=true" by substituting in 269 the following ciphertext block instead: 270 271 .....X+a.....X+b.... 272 273 for '+' the XOR operator, 'a' the byte such that '!' + 'a' = ';', and 'b' 274 the byte such that '!' + 'b' = '='. The second plaintext block, which is found 275 by passing `c_2` through AES decryption, will be effectively destroyed, but 276 the third plaintext block will be modified as desired. 277 278 (Note by padding the malicious input block with 'A' bytes we line everything 279 up so as to take advantage of the following semicolon.) 280 281 Using an IV of all zero bytes, `Cryptopals.Block.Attacks.bfcEncrypter` will 282 return the following, given the malicious input: 283 284 00000000000000000000000000000000 ................ 285 63530f935e8a082aefc3010403ddd0c8 comment1=cooking 286 5d7abe5ba83c8f15d5768e372b8d9d3e %20MCs;userdata= 287 d84ed53685df3c0fe1f047a8d8067e2b AAAAA!admin!true 288 ca8ca55382df2e963b10dec76fd282ce ;comment=%20like 289 cf39e6549b264c0eb44340b5f0e3ebdc %20a%20pound%20o 290 214abfcb615d8c63406ee84093538051 fbacon__________ 291 292 We can see that 0x3c and 0x37 in ciphertext block 2 (i.e. the third, 293 counting the IV) need to be changed. The bytes are at index 37 and 43 in 294 the raw ciphertext, respectively; some calculation shows what we need to 295 XOR them by: 296 297 > showHex (ord '!' `B.xor` ord ';') mempty 298 "1a" 299 300 and 301 302 > showHex (ord '!' `B.xor` ord '=') mempty 303 "1c" 304 305 so we replace 0x3c in `c_2` with `0x3c + 0x1a` and 0x37 306 with `0x37 + 0x1c` and pass the resulting munged ciphertext 307 through the ";admin=true;" substring checker found in 308 `Cryptopals.Block.Attacks.bfcChecker`: 309 310 > let cip = bfcEncrypter "AAAAA!admin!true" 311 > :{ 312 ghci| let munge = loop 0 mempty where 313 ghci| loop j acc !bs = case BS.uncons bs of 314 ghci| Nothing -> acc 315 ghci| Just (b, etc) 316 ghci| | j == 37 -> let nex = BS.snoc acc (0x3c `B.xor` 0x1a) 317 ghci| in loop (succ j) nex etc 318 ghci| | j == 43 -> let nex = BS.snoc acc (0x37 `B.xor` 0x1c) 319 ghci| in loop (succ j) nex etc 320 ghci| | otherwise -> loop (succ j) (BS.snoc acc b) etc 321 ghci| :} 322 > let munged = munge cip 323 > bfcChecker cip 324 False 325 > bfcChecker munged 326 True 327 328 indicating that the evil substring is present, as desired.