cryptopals

s3.md (10938B)

---

 ### 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 use 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 to 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"
 
 #### 3.18
 
 CTR mode is trivial; the only thing to get right is really the specified
 counter format. `Cryptopals.AES.decryptCtrAES128` (or its synonym,
 `encryptCtrAES128`) can be used to retrieve our desired plaintext:
 
     > let Right cip = B64.decodeBase64 "L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ=="
     > decryptCtrAES128 0 "YELLOW SUBMARINE" cip
     "Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby "
 
 You can get at this from the command line via the 'ctr' arg to the 'aes'
 binary:
 
     $ ct=$(echo "L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==" | base64 -d | xxd -p | tr -d '\n')
     $ key=$(echo -n "YELLOW SUBMARINE" | xxd -p)
     $ aes decrypt ctr --nonce 0 "$key" "$ct" | xxd -r -p
     Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby
 
 #### 3.19 (and 3.20)
 
 I used the same approach as was done in question 1.6, taking the
 first 16 bytes of each ciphertext and then transposing them such that
 each "block" has been single-byte XOR'd by something. Using a similar
 scoring routine (see `Cryptopals.Block.Attacks.rnBest`) and some manual
 fiddling, one can recover the keystream without much difficulty. Finding
 the first 16 bytes exposes enough of the plaintexts that the remaining
 bytes can be completed by hand, though I bailed out after I got the
 gist of it:
 
     > let ks = BS.pack $ fmap (\(a, _, _) -> a) . rnBest) rnrotated
     > -- the resulting keystream needed some manual patching, but
     > -- results like "eighteeoth-centu" make it easy to do.
     > take 4 $ fmap (CU.fixedXor ks) rnscrypted
     ["I have met them ","Coming with vivi","From counter or ","Eighteenth-centu"]
 
 (It turns out this is the way one is supposed to solve 3.20 too.  Whoops!)
 
 #### 3.21
 
 `Cryptopals.Stream.RNG.MT19937` implements the Mersenne Twister
 (MT19937) PRNG in standard return-the-generator fashion:
 
     > let gen = seed 42
     > tap 3 gen
     > ([1608637542,3421126067,4083286876],<MT19937.Gen>)
 
 The only annoying thing about this problem was finding a test vector
 to check the implementation against. I used the outputs on [this
 guy's](https://create.stephan-brumme.com/mersenne-twister/) page;
 the implementations he cites return signed 32-bit integers, but I
 use (unsigned) Word32. One can convert results to e.g. Int32 with
 fromIntegral to verify.
 
 There's also a binary:
 
     $ mt19937 42 3
     1608637542
     3421126067
     4083286876
 
 (N.b., the [original
 paper](http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/ARTICLES/mt.pdf) on
 the Mersenne Twister is very well-written and readable.)
 
 #### 3.22
 
 After the fourth or fifth time my children woke me up in the middle of
 the night, I decided to just get up and pick at this stuff. I kicked off
 this business somewhere around 5-6am:
 
     $ sleep $(shuf -i 40-1000 -n 1); ts=$(date +%s); \
       sleep $(shuf -i 40-1000 -n 1); mt19937 $ts 1
     1133750118
 
 and then lay down again and fell asleep for a few hours. Using [this
 timestamp calculator](https://www.unixtimestamp.com/) after the fact,
 the timestamp is probably somewhere in the range of about \[1690702400,
 1690708000\].  So, using:
 
     #!/usr/bin/env bash
     declare -i i
     i=1690702400
     while (($i < 1690708000)); do
       val=$(mt19937 $i 1)
       if (($val == 1133750118)); then
         echo "seed is $i"
         exit
       else
         i+=1
       fi
     done
 
 we get:
 
     $ ./crackmt.sh
     seed is 1690706100
 
 So, via the same timestamp calculator, it was seeded at Sun Jul 30 2023
 06:05:00 GMT-0230 (heure d’été de Terre-Neuve).
 
 #### 3.23
 
 A Mersenne Twister outputs elements of its internal state transformed
 by a linear tempering map. The state is perturbed every 624 iterations
 (the "twist"), but if we have all 624 outputs generated from a constant
 internal state, that state can be recovered by running the outputs
 through the inverse tempering map.
 
 The tempering transform (in Cryptopals.Stream.RNG.MT19937) can be
 expressed by:
 
     temper :: Word32 -> Word32
     temper = e4 . e3 . e2 . e1 where
       e1 = rs u
       e2 = ls s b
       e3 = ls t c
       e4 = rs l
 
 and its inverse by:
 
     untemper :: Word32 -> Word32
     untemper = n1 . n2 . n3 . n4 where
       n1 = rsinv u
       n2 = lsinv s b
       n3 = lsinv t c
       n4 = rsinv l
 
 given the following salad of internal functions (you either know how to invert
 an xorshift operation or you don't):
 
     ls :: Word32 -> Word32 -> Word32 -> Word32
     ls s m a = a `B.xor` (B.shiftL a (fi s) .&. m)
 
     rs :: Word32 -> Word32 -> Word32
     rs s a = a `B.xor` B.shiftR a (fi s)
 
     lsinv :: Word32 -> Word32 -> Word32 -> Word32
     lsinv s bm = loop 0 where
       loop j !b
         | j >= fi w = b
         | otherwise =
             let m = mask j (min (fi w - 1) (j + fi s - 1))
                 x = ((m .&. b) `B.shiftL` fi s) .&. bm
             in  loop (j + fi s) (b `B.xor` x)
 
     rsinv :: Word32 -> Word32 -> Word32
     rsinv s = loop (fi w - 1) where
       loop j !b
         | j <= 0    = b
         | otherwise =
             let m = mask (max 0 (j - fi s + 1)) j
                 x = (m .&. b) `B.shiftR` fi s
             in  loop (j - fi s) (b `B.xor` x)
 
     mask :: B.Bits b => Int -> Int -> b
     mask l h = loop l B.zeroBits where
       loop j !b
         | j > h = b
         | otherwise =
             loop (succ j) (B.setBit b j)
 
 So we can run a generator for 624 iterations, capture the outputs, and
 untemper them to recover the internal state for those 624 iterations
 (with the caveat that the outputs we need to observe must occur absent
 any intermediate twists of the internal state):
 
     > let gen = seed 42
     > let (bs, g) = tap 624 gen
     > let cloned = Gen 624 (VU.fromList . fmap untemper $ bs)
     > fst (tap 3 g)
     [108880612,791707097,4134543476]
     > fst (tap 3 cloned)
     [108880612,791707097,4134543476]
 
 As stated in sec 1.6 of the original Mersenne Twister paper, the key
 to hardening the PRNG is to pass the outputs through a secure hash
 function.
 
 #### 3.24
 
 The first challenge here is to recover the stream cipher's seed from
 some ciphertext, given a (mostly-) known plaintext. The issue is that
 at 16 bits the seed is tiny, and so it can be easily be brute-forced by
 just iterating through the possible word values:
 
     mtCipherAttack :: BS.ByteString -> Word16
     mtCipherAttack cip = loop 0 where
       l = BS.length cip
       t = BS.replicate 14 65
       loop j
         | j > (maxBound :: Word16) = error "impossible seed"
         | otherwise =
             let g  = MT.seed (fromIntegral j)
                 bs = keystream l g
                 pt = BS.drop (l - 14) (bs `CU.fixedXor` cip)
             in  if   pt == t
                 then j
                 else loop (succ j)
 
 Running it on some ciphertext I created reveals the seed used in a
 minute or two:
 
     > B16.encodeBase16 ciphertext
     "df2c20f5025fed9e86a986e47d8bee063213afc1"
     > mtCipherAttack ciphertext
     50000
 
 The token seeded by system time is also trivial to crack, since we can
 just generate a seed from the current time and check the result directly:
 
     pwntToken :: IO T.Text
     pwntToken = do
       s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
       let g = MT.seed s
       pure $ B64.encodeBase64 (keystream 16 g)
 
     notPwntToken :: IO T.Text
     notPwntToken = do
       g  <- MWC.createSystemRandom
       bs <- fmap BS.pack $ replicateM 16 (MWC.uniformR (32, 126) g)
       pure $ B64.encodeBase64 bs
 
     isPwnt :: T.Text -> IO Bool
     isPwnt token = do
       s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
       let g = MT.seed s
           ks = keystream 16 g
       pure $ token == B64.encodeBase64 ks
 
 (N.b., 'notPwntToken' uses /dev/random or /dev/urandom to generate a
 seed, instead of the system time.)
 
 Some examples:
 
     > pwntToken
     "2Pi2LO0cn3XXyw1xwrLlHQ=="
     > pwntToken
     "WqPvmtGTfc3QkhVs78uOqQ=="
     > notPwntToken
     "V0codSgtXyNvLSJ4XjNyNQ=="
     > notPwntToken
     "STA3ZnxVe1tQW0Q4TF0pbg=="
     > pwntToken >>= isPwnt
     True
     > notPwntToken >>= isPwnt
     False