cryptopals

Matasano's cryptopals challenges (cryptopals.com).
Log | Files | Refs | README | LICENSE

commit 88dd2825e002d0a1e81b5657a10dbba1a2f5afaf
parent 4cbdd9642f058c671959a42f92eeb10fb7f501c8
Author: Jared Tobin <jared@jtobin.io>
Date:   Fri, 28 Jul 2023 14:41:29 -0230

Add padding oracle attack writeup.

Diffstat:
Mdocs/s2.md | 12+++++++++---
Adocs/s3.md | 77+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 86 insertions(+), 3 deletions(-)

diff --git a/docs/s2.md b/docs/s2.md @@ -11,10 +11,15 @@ four bytes' worth of padding, each of value 04: 00000000: 5945 4c4c 4f57 2053 5542 4d41 5249 4e45 YELLOW SUBMARINE 00000010: 0404 0404 .... -(Of note, the case for `l mod k = 0` is interesting, since even though +Of note, the case for `l mod k = 0` is interesting, since even though we don't necessarily *need* padding in such a case, we get k bytes of padding, each with value k, anyway. If one asks for padding, he's -getting padding.) +getting padding. + +(N.b., the reason is that a deciphering algorithm can thus always treat +a string as padded and look only at the last byte to determine the +number of padding bytes to strip. In the case of `l mod k = 0`, the +extra padded block just gets chopped entirely.) [pkcs]: https://datatracker.ietf.org/doc/html/rfc2315#section-10.3 @@ -229,7 +234,7 @@ Nothing on inputs with invalid padding: 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) + for plaintext p = (p_1, .., p_l) block encryption w/key k enc_k initialization vector IV xor operator + @@ -304,3 +309,4 @@ through the ";admin=true;" substring checker found in > bfcChecker munged True +indicating that the evil substring is present, as desired. diff --git a/docs/s3.md b/docs/s3.md @@ -0,0 +1,77 @@ +### Set 3 + +#### 3.17 + +This one took me some fiddling to get right. As stated in the challenge +text itself, it's easy to get hung up on the idea of decrypting padding +bytes themselves. But the idea is to choose ciphertext byte values so as +to *force* valid padding in a "phantom" plaintext, then using the added +information to recover the actual plaintext bytes (padding bytes or no). + +From the 2.16 answer text, CBC-mode decryption proceeds as follows: + + 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_l) + c_{l-1} + + in plaintext p = (p_1, p_2, .., p_l) + +So, the last plaintext byte can be described by: + + lb(p_l) = lb(dec_k(c_1) + c_{l-1}) (1) + +Say one corrupts `c_{l-1}` (producing `c_{l-1}'`) by perturbing the last +byte, and then submits `(c_{l-1}', c_l)` to the padding oracle. The +padding oracle will internally compute: + + p_l' = dec_k(c_l) + c_{l-1}' + +and then check its padding. We want to *force* the last byte of `p_l'` +to be 0x01, so we require that 1) the padding of `p_l'` validates, and +2) that this forced padding is not 0x0202 or 0x030303 or some other +scheme. We do this repeatedly until the padding validates as desired +(if we are unlucky and have forced some other padding, e.g. 0x0202, we +just treat that as a failure) yielding: + + lb(dec_k(c_l) + c_{l-1}') = 0x01 + lb(dec_k(c_l)) + lb(c_{l-1}') = 0x01 + +so that: + + lb(dec_k(c_l)) = lb(c_{l-1}') + 0x01 + +and thus (using (1)), that: + + lb(p_l) = lb(dec_k(c_l)) + lb(c_{l-1)} + = lb(c_{l-1}') + 0x01 + lb(c_{l}). + +The same is then true for every other byte. For the penultimate byte, +for example, we want to *force* the penultimate byte of `p_l'` to be +0x02, so we also require that the last byte of `p_l'` be 0x02 in order +for its padding validate. Each time we simply do this by manipulating +`c_{l-1}` appropriately. + +`Cryptopals.Block.Attacks.paddingOracle` is a padding oracle, and the +`Cryptopals.Block.Attacks.paddingOracleAttack` function implements the +padding oracle attack (for arbitrary ciphertexts): + + > :{ + ghci| F.for_ [1..10] $ \_ -> putStrLn . show . M.fromJust =<< + ghci| fmap (CU.unpkcs7 . paddingOracleAttack) (paddingOracle gen) + ghci| :} + "000002Quick to the point, to the point, no faking" + "000001With the bass kicked in and the Vega's are pumpin'" + "000000Now that the party is jumping" + "000000Now that the party is jumping" + "000004Burning 'em, if you ain't quick and nimble" + "000005I go crazy when I hear a cymbal" + "000003Cooking MC's like a pound of bacon" + "000002Quick to the point, to the point, no faking" + "000003Cooking MC's like a pound of bacon" + "000004Burning 'em, if you ain't quick and nimble" +