commit ad2df1735810f234eaf99d77340d72968817ed94
parent 232a0ee5abe359af55b2f34f384dffacc5808c73
Author: Jared Tobin <jared@jtobin.io>
Date: Mon, 5 Jun 2023 23:13:11 +0400
Finish set 2.
Diffstat:
4 files changed, 117 insertions(+), 23 deletions(-)
diff --git a/docs/s2.md b/docs/s2.md
@@ -191,16 +191,17 @@ just feeding in more than a block's worth of them -- necessarily some
E.g.: one can determine that "AAAAAAAAAAAAAAAA" encrypts to
"57eef2e16c3867b9889350eb5732c183", so we can look for that ciphertext
in the result in order to locate an "origin," only analyzing ciphertexts
-in which it appears. By chopping that and any preceeding bytes from the
-ciphertext, the attack reduces to the simpler version we've already
-done.
+in which it appears (since, if it doesn't happen to align perfectly in
+a block, we won't see it in the ciphertext). By chopping that and any
+preceeding bytes from the ciphertext, the attack reduces to the simpler
+version we've already performed.
The `Cryptopals.Block.Attacks.hardIncrByteEcbAttack` function will
perform the attack; it's just a version of `incrByteEcbAttack`
from challenge 12 adapted to handle a monadic oracle.
`Cryptopals.Block.Attacks.attackProxy` wraps the `weirdEncrypter` oracle
-and does the work of locating our malicious block and pruning the
-ciphertext for us, so we can attack `weirdEncrypter` via:
+and does the work of inserting/locating our malicious block and pruning
+the ciphertext for us, so we can attack `weirdEncrypter` via:
> plain <- hardIncrByteEcbAttack (attackProxy weirdEncrypter) gen
> TIO.putStrLn $ TE.decodeUtf8 plain
@@ -224,3 +225,82 @@ Nothing on inputs with invalid padding:
Nothing
#### 2.16
+
+This one is pretty cool and tricky. AES encryption in CBC (cipher block
+chaining) mode proceeds as follows:
+
+ for plaintext p = (p_1, .., p_l)
+ block encryption w/key k enc_k
+ initialization vector IV
+ xor operator +
+
+ let c_0 = IV
+ c_1 = enc_k(c_0 + m_1)
+ c_2 = enc_k(c_1 + m_2)
+ ..
+ c_l = enc_k(c_{l-1} + m_l)
+
+ in ciphertext c = (c_0, c_1, c_2, .., c_l)
+
+and decryption goes like this:
+
+ for ciphertext c = (c_0, c_1, c_2, .., c_l)
+ block decryption w/key k dec_k
+ xor operator +
+
+ let p_1 = dec_k(c_1) + c_0
+ p_2 = dec_k(c_2) + c_1
+ ..
+ p_l = dec_k(c_1) + c_{l-1}
+
+ in plaintext p = (p_1, p_2, .., p_l)
+
+Let plaintext block 3 be "AAAAA!admin!true". Since:
+
+ p_2 = dec_k(c_2) + c_1
+
+if ciphertext block 2 is ".....X.....X...." for unspecified bytes ".",
+then we can recover the plaintext "AAAAA;admin=true" by substituting in
+the following ciphertext block instead:
+
+ .....X+a.....X+b....
+
+for '+' the XOR operator, 'a' the byte such that '!' + 'a' = ';', and 'b'
+the byte such that '!' + 'b' = '='. The second plaintext block, which is found
+by passing `c_2` through AES decryption, will be effectively destroyed, but
+the third plaintext block will be modified as desired.
+
+(Note by padding the malicious input block with 'A' bytes we line everything
+up so as to take advantage of the following semicolon.)
+
+Using an IV of all zero bytes, `Cryptopals.Block.Attacks.bfcEncrypter` will
+return the following, given the malicious input:
+
+ 00000000000000000000000000000000 ................
+ 63530f935e8a082aefc3010403ddd0c8 comment1=cooking
+ 5d7abe5ba83c8f15d5768e372b8d9d3e %20MCs;userdata=
+ d84ed53685df3c0fe1f047a8d8067e2b AAAAA!admin!true
+ ca8ca55382df2e963b10dec76fd282ce ;comment=%20like
+ cf39e6549b264c0eb44340b5f0e3ebdc %20a%20pound%20o
+ 214abfcb615d8c63406ee84093538051 fbacon__________
+
+We can see that 0x3c and 0x37 in ciphertext block 2 (i.e. the third, counting
+the IV) need to be changed. Some calculation shows what we need to XOR them
+by:
+
+ > showHex (ord '!' `B.xor` ord ';') mempty
+ "1a"
+
+and
+
+ > showHex (ord '!' `B.xor` ord '=') mempty
+ "`c"
+
+so we replace 0x3c in `c_2` with `0x3c + 0x1a` and 0x37
+with `0x37 + 0x1c` and pass the resulting munged ciphertext
+through the ";admin=true;" substring checker found in
+`Cryptopals.Block.Attacks.bfcChecker`:
+
+ > bfcChecker munged
+ True
+
diff --git a/lib/Cryptopals/AES.hs b/lib/Cryptopals/AES.hs
@@ -22,10 +22,10 @@ decryptEcbAES128 key = CT.ecbDecrypt (initAES128 key)
encryptCbcAES128
:: BS.ByteString -> BS.ByteString -> BS.ByteString -> BS.ByteString
-encryptCbcAES128 iv key plaintext = loop iv mempty (BS.splitAt 16 plaintext)
+encryptCbcAES128 iv key plaintext = loop iv iv (BS.splitAt 16 plaintext)
where
- loop !fiv !acc (b, bs) =
- let xed = CU.fixedXor fiv b
+ loop las !acc (b, bs) =
+ let xed = CU.fixedXor las b
enc = encryptEcbAES128 key xed
nacc = acc <> enc
in if BS.null bs
@@ -33,12 +33,14 @@ encryptCbcAES128 iv key plaintext = loop iv mempty (BS.splitAt 16 plaintext)
else loop enc nacc (BS.splitAt 16 bs)
decryptCbcAES128
- :: BS.ByteString -> BS.ByteString -> BS.ByteString -> BS.ByteString
-decryptCbcAES128 iv key ciphertext = loop iv mempty (BS.splitAt 16 ciphertext)
+ :: BS.ByteString -> BS.ByteString -> BS.ByteString
+decryptCbcAES128 key ciphertext =
+ let (iv, cip) = BS.splitAt 16 ciphertext
+ in loop iv mempty (BS.splitAt 16 cip)
where
- loop !fiv !acc (b, bs) =
+ loop !las !acc (b, bs) =
let dec = decryptEcbAES128 key b
- nacc = acc <> CU.fixedXor dec fiv
+ nacc = acc <> CU.fixedXor dec las
niv = b
in if BS.null bs
then nacc
diff --git a/lib/Cryptopals/Block/Attacks.hs b/lib/Cryptopals/Block/Attacks.hs
@@ -40,8 +40,7 @@ chaosEncrypter plaintext gen = do
pos <- MWC.uniformR (5, 10) gen >>= flip bytes gen
let tex = pre <> plaintext <> pos
- pad = CU.roundUpToMul 16 (BS.length tex)
- bs = CU.pkcs7 pad tex
+ bs = CU.lpkcs7 tex
ecb <- MWC.uniform gen
@@ -61,8 +60,7 @@ alienEncrypter plaintext =
]
par = plaintext <> pos
- pad = CU.roundUpToMul 16 (BS.length par)
- bs = CU.pkcs7 pad par
+ bs = CU.lpkcs7 par
in AES.encryptEcbAES128 consistentKey bs
@@ -147,8 +145,7 @@ cpeEncrypt :: BS.ByteString -> BS.ByteString
cpeEncrypt user =
let tex = TE.encodeUtf8 $ profileFor (TE.decodeUtf8 user)
- pad = CU.roundUpToMul 16 (BS.length tex)
- bs = CU.pkcs7 pad tex
+ bs = CU.lpkcs7 tex
in AES.encryptEcbAES128 consistentKey bs
@@ -173,8 +170,7 @@ weirdEncrypter plaintext gen = do
pre <- bytes bys gen
let par = pre <> plaintext <> pos
- pad = CU.roundUpToMul 16 (BS.length par)
- bs = CU.pkcs7 pad par
+ bs = CU.lpkcs7 par
pure $ AES.encryptEcbAES128 consistentKey bs
@@ -206,6 +202,17 @@ attackProxy oracle input gen = loop gen where
then loop g
else pure $ BS.drop 16 target
-nubplusplus :: (Eq a, Ord a) => [a] -> [a]
-nubplusplus = fmap NE.head . NE.group . L.sort
-
+-- bitflipping CBC
+bfcEncrypter :: BS.ByteString -> BS.ByteString
+bfcEncrypter input = AES.encryptCbcAES128 iv consistentKey padded where
+ iv = BS.replicate 16 0
+ filtered = BS.filter (`notElem` (BS.unpack ";=")) input
+ plaintext = "comment1=cooking%20MCs;userdata=" <> filtered <>
+ ";comment2=%20like%20a%20pound%20of%20bacon"
+ padded = CU.lpkcs7 plaintext
+
+bfcChecker :: BS.ByteString -> Bool
+bfcChecker ciphertext = target /= mempty where
+ iv = BS.replicate 16 0
+ plaintext = AES.decryptCbcAES128 consistentKey ciphertext
+ (_, target) = BS.breakSubstring ";admin=true;" plaintext
diff --git a/lib/Cryptopals/Util.hs b/lib/Cryptopals/Util.hs
@@ -2,6 +2,7 @@ module Cryptopals.Util (
CUB.chunks
, CUB.hamming
, fixedXor
+ , lpkcs7
, CUB.nhamming
, CUS.often
, CUB.panhamming
@@ -42,6 +43,10 @@ pkcs7 tar bs =
byt = tar - len `mod` tar
in bs <> BS.replicate byt (fromIntegral byt)
+-- lazy man's pkcs#7 padding
+lpkcs7 :: BS.ByteString -> BS.ByteString
+lpkcs7 bs = pkcs7 (roundUpToMul 16 (BS.length bs)) bs
+
unpkcs7 :: BS.ByteString -> Maybe BS.ByteString
unpkcs7 bs = do
(_, c) <- BS.unsnoc bs
