cryptopals

s4.md (16759B)

---

 ### Set 4
 
 #### 4.25
 
 If we can control the offset and plaintext input, then we can ask
 the oracle to encrypt a plaintext with the same length of the
 ciphertext at offset 0. *Et voilà*, there's our keystream, which we
 can just xor with the original ciphertext in order to decrypt it.
 Cryptopals.Stream.Attacks.rawrCtrAttack implements such an "attack":
 
     rawrCtrAttack :: IO BS.ByteString
     rawrCtrAttack = do
       cip <- rawrCtrOracle (maxBound :: Int) mempty
       let l = BS.length cip
           p = BS.replicate l 65
 
       new <- rawrCtrOracle 0 p
       let ks = new `CU.fixedXor` p
 
       pure $ ks `CU.fixedXor` cip
 
 which gives the expected plaintext:
 
     > fmap (BS.take 33) rawrCtrAttack
     "I'm back and I'm ringin' the bell"
 
 #### 4.26
 
 After making the necessary adjustments, we can generate an analogous
 ciphertext via:
 
     > -- Cryptopals.Stream.Attacks.bfcEncrypter
     > let cip = bfcEncrypter "AAAAA!admin!true"
 
 Encoded as hex, this one looks like:
 
     911197ace68288173aeea79803ba30ff comment1=cooking
     7a45f6350fefac4ff9b4f1277500e130 %20MCs;userdata=
     843d67e24f8af8305928b16352b943e9 AAAAA!admin!true
     39e33d0551e309a752c2bb658a8ba9ee ;comment=%20like
     dda6c8de9da59acc48f4d83f0d63fb8b %20a%20pound%20o
     4969b8aac52e78b701c8da0f253efe59 fbacon__________
 
 Here we want to target the desired bytes themselves, not the bytes in
 a previous block as was done for the attack on CBC mode. Since we know
 the ciphertext and plaintext byte values, we can trivially recover the
 keystream at those bytes (i.e. at indices 37 and 43). Then it's just a
 matter of replacing the ciphertext bytes by the keystream bytes XOR'd by
 the desired plaintext:
 
     > -- Cryptopals.Stream.Attacks.bfcEncrypter
     > let cip = bfcEncrypter "AAAAA!admin!true"
     > :{
     ghci| let munge cip = loop 0 mempty cip where
     ghci|       p = fi (C.ord '!')
     ghci|       s = fi (C.ord ';')
     ghci|       e = fi (C.ord '=')
     ghci|       loop j acc !bs = case BS.uncons bs of
     ghci|         Nothing -> acc
     ghci|         Just (b, etc)
     ghci|           | j == 37 -> let c = BS.index cip j
     ghci|                            k = c `B.xor` p
     ghci|                            vil = k `B.xor` s
     ghci|                            nex = BS.snoc acc vil
     ghci|                        in  loop (succ j) nex etc
     ghci|           | j == 43 -> let c = BS.index cip j
     ghci|                            k = c `B.xor` p
     ghci|                            vil = k `B.xor` e
     ghci|                            nex = BS.snoc acc vil
     ghci|                        in  loop (succ j) nex etc
     ghci|           | otherwise -> loop (succ j) (BS.snoc acc b) etc
     ghci| :}
     > let munged = munge cip
     > bfcChecker cip
     False
     > bfcChecker munged
     True
 
 #### 4.27
 
 This one works exactly as advertised. The ivl{en, de}cryptCbcAES128
 functions in Cryptopals.Block.Attacks will {en, de}crypt inputs in CBC
 mode using identical key and IV's, and ivlVerifier serves as the desired
 oracle.
 
 First, assembling the nasty ciphertext:
 
     > let b = "YELLOW SUBMARINE"
     > B16.encodeBase16 consistentKey
     "d18a7e96a50f45cb9b928e502c2b310d"
     > let cip = ivlEncryptCbcAES128 consistentKey (b <> b <> b)
     > let cs = CU.chunks 16 cip
     > let mcip = cs !! 0 <> BS.replicate 16 0 <> cs !! 0
 
 And now recovering the key:
 
     > let Left mpay = ivlVerifier mcip
     > let ps = CU.chunks 16 mpay
     > B16.encodeBase16 $ (ps !! 0) `CU.fixedXor` (ps !! 2)
     "d18a7e96a50f45cb9b928e502c2b310d"
 
 As for how this works: refer back to the omnipresent CBC-mode decryption
 scheme from 2.16 (here modified):
 
     for ciphertext                    c = (c_1, c_2, c_3)
         block decryption w/key k      dec_k
         xor operator                  +
 
     let p_1 = dec_k(c_1) + k
         p_2 = dec_k(c_2) + c_1
         p_3 = dec_k(c_3) + c_2
 
     in  plaintext                     p = (p_1, p_2, p_3)
 
 So if we provide the modified `c = (c_1, 0, c_1)`, decryption will give us:
 
     p_1' = dec_k(c_1) + k
     p_2' = dec_k(0) + c_1
     p_3' = dec_k(c_1) + 0
 
 such that, trivially:
 
     p_1' + p_3' = dec_k(c_1) + k + dec_k(c_1) + 0
                 = k.
 
 #### 4.28
 
 Using the SHA1 (Secure Hashing Algorithm) implementation from the 'sha'
 package under the hood, Cryptopals.MAC.sha1mac implements the desired
 MAC (i.e. message authentication code):
 
     > let mac = sha1mac "YELLOW SUBMARINE" "question 4.28"
     > B16.encodeBase16 . BSL.toStrict $ mac
     "45b5bb1ab02988df4609ff1227c90fe997236719"
 
 verifysha1mac verifies a MAC given a key and message:
 
     > verifysha1mac "YELLOW SUBMARINE" mac "question 4.28"
     True
 
 and we obviously can't tamper with anything without the MAC failing to
 verify:
 
     > verifysha1mac "YELLOW SUBMARINE" mac "question 4.29"
     False
 
 #### 4.29
 
 So, length extension on SHA-1. A preliminary note: "MD
 padding" refers to Merkle-Damgård compliant padding, described
 [here](https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_constru
 ction) and concretely elaborated on in
 [RFC1321](http://www.faqs.org/rfcs/rfc1321.html), section 3.1, and
 [RFC3174](http://www.faqs.org/rfcs/rfc3174.html), section 4. The latter
 contains the TLDR summary:
 
 > The purpose of message padding is to make the total length of a padded
 > message a multiple of 512. SHA-1 sequentially processes blocks of
 > 512 bits when computing the message digest. The following specifies
 > how this padding shall be performed. As a summary, a "1" followed by
 > m "0"s followed by a 64- bit integer are appended to the end of the
 > message to produce a padded message of length 512 * n. The 64-bit
 > integer is the length of the original message.
 
 The crux of this attack is that, like the Mersenne Twister, the SHA1
 algorithm (indeed, every SHA algorithm) maintains internal state.
 In the Mersenne Twister we use the state and temper it ("twisting"
 occasionally) to produce outputs; in SHA1, the output on termination
 of the (padded) input *is* the internal state, i.e. five 32-bit words,
 glued together. Any hash output thus corresponds to the internal state
 of the algorithm at the end of some (padded) input.
 
 Here, as the attacker, we know the message -- but not the key -- used
 to produce the MAC, and we know the MAC itself. The MAC corresponds
 to the internal state of SHA1 when we finished hashing the original
 `key <> message` input, padded to a multiple of 512 bits. So, we can
 reinitialise SHA1 with that state and continue hashing further input,
 the goal being to produce a MAC that verifies for an arbitrary extension
 of the original message without knowledge of the secret key.
 
 (N.b., two things in this challenge drove me crazy. The first was
 getting the padding right everywhere, something which broke my brain
 for awhile until things eventually slotted into place. The second was a
 really, really stupid error, in which I accidentally treated a 40-byte
 UTF8-encoded hex string as a 20-byte bytestring, messing up the internal
 state of SHA1 whenever I'd restore it from an output. That was annoying
 to track down.)
 
 *Alors*. Various functions in Cryptopals.MAC.Attacks will be employed to
 forge a MAC from another MAC. First, as recommended, let's hack together
 something to grab a key from /usr/share/dict:
 
     key :: IO BSL.ByteString
     key = do
       gen <- MWC.createSystemRandom
       idx <- MWC.uniformR (0, 235885) gen
       dict <- BL8.readFile "/usr/share/dict/words"
       let ls = BL8.lines dict
       pure $ ls !! idx
 
 and then grab one and produce a mac ('raw' is the given input text):
 
     > k <- key
     > let mac = CM.sha1mac k raw
 
 Now, the evil message for which we will forge a MAC. This evil message
 must include the *original* padding of the 'key + message' input used to
 produce the MAC, since SHA1 stopped hashing on completion of pad(key +
 message). All we know is that the message length is at least the same as
 'raw', and, for nontrivial keys, is strictly more.
 
 Similarly, to verify integrity, one computes sha1(key + message) and
 checks that it equals the provided MAC. I.e., for an evil message and
 forged MAC, one checks that:
 
     sha1(key + evil) == forged
 
 SHA1 will terminate at pad(key + evil), which includes the total
 message length of 'key + evil'. So we must ensure that our resumed
 length-extension hash uses this padding.
 
 As best I can tell, in order to guess productively at the key length
 used to construct the original MAC, we need access to an oracle that
 can validate message/MAC pairs for us. A sort of wonky way to simulate
 this is via the following 'leasha1' procedure that, while interacting with
 something that needs a key, doesn't make use of a key itself:
 
     leasha1
       :: BSL.ByteString
       -> BSL.ByteString
       -> BSL.ByteString
       -> R.Reader BSL.ByteString (BSL.ByteString, BSL.ByteString)
     leasha1 input mac addl = loop 0 where
       loop j = do
         let len = fromIntegral $ BSL.length input
             evil = pad (len + j) input <> addl
             rs   = inject mac
             p    = fromIntegral (BSL.length evil) + j
             forged = sha1 rs p addl
         validates <- oracleValidates evil forged
         if   validates
         then pure (evil, forged)
         else loop (succ j)
 
       oracleValidates msg mac = do
         k <- R.ask
         pure $ CM.verifysha1mac k mac msg
 
 'sha1' here calls the modified SHA1 allowing us to 1) initialize its
 internal state from the provided registers, and 2) use the specified
 message length for padding, instead of calculating it from the provided
 bytestring.
 
 So, with all that, let's *cackles* forge the evil message and a MAC that
 will validate for it. 'mal' is the malicious text ";admin=true":
 
     > let (evil, forged) = R.runReader (leasha1 raw mac mal) k
     > evil
     "comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20ba
     con\128\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL
     \NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NUL\NU
     L\NUL\NUL\NUL\STX\176;admin=true"
     > B16.encodeBase16 . BSL.toStrict $ forged
     "0ad748ec8eef1a0b510b01b8f9ff692cf050bd15"
     > CM.verifysha1mac k forged evil
     True
 
 #### 4.30
 
 I grabbed and proceeded to butcher [this
 guy's](https://github.com/mfeyg/md4/tree/master) MD4 implementation. He
 evidently likes to keep me on my toes by doing everything little-endian;
 after making sure everything conforms to that, the story is exactly the
 same as the last challenge. Here's the length extension attack that uses
 access to a verifying oracle:
 
     leamd4
       :: BSL.ByteString
       -> BSL.ByteString
       -> BSL.ByteString
       -> R.Reader BSL.ByteString (BSL.ByteString, BSL.ByteString)
     leamd4 input mac addl = loop 0 where
       loop j = do
         let len = fromIntegral $ BSL.length input
             evil = padle (len + j) input <> addl
             rs   = injectMd4 mac
             p    = fromIntegral (BSL.length evil) + j
             forged = md4 rs p addl
         validates <- oracleValidates evil forged
         if   validates
         then pure (evil, forged)
         else loop (succ j)
 
       oracleValidates msg mac = do
         k <- R.ask
         pure $ CM.verifymd4mac k mac msg
 
 Again, 'md4' is a modified implementation allowing us to resume from an
 arbitrary state and use devious padding. Let's give it a whirl:
 
     > k <- key
     > let mac = CM.md4mac k raw
     > let (evil, forged) = R.runReader (leamd4 raw mac mal) k
     > B16.encodeBase16 . BSL.toStrict $ forged
     "289e55e2fd99091f1b4e09e1ac4167f3"
     > CM.verifymd4mac k forged evil
     True
 
 #### 4.31
 
 For this exercise we'll switch it up and write some JavaScript. etc/hmac
 contains some JS HMAC utilities (in hmac.js) and a tiny express.js app
 (in index.js) that will verify messages and MACs it receives via query
 parameters.
 
 HMAC (Hash-based MAC) is not vulnerable to length-extension attacks
 due the presence of multiple (at least two, and potentially more)
 enveloping calls to the hash function when creating the MAC. Ferguson et
 al. recommended a similar approach in *Cryptography Engineering* when
 dealing with Merkle-Damgård hash functions, in which, for hash function
 h and message m, instead of using h(m) one uses h(h(m) || m). The HMAC
 construction, which goes:
 
     hmac(k, m) = h((k' + 0x5c) || h((k' + 0x36) || m))
 
 for:
 
     k' = { h(k)   for k > block size
          { k      otherwise
 
 where + is single-byte XOR and || is concatenation, is more or less the
 same idea, except.. moreso.
 
 Anyway. The idea here is that we have a webserver that does
 byte-at-a-time comparison with the supplied MAC, sleeping a little
 per byte verified and bailing out early if equality isn't found. So,
 we start guessing MACs by working on one byte at a time and checking
 whether the server takes appreciably longer to reject what we supply.
 If it does, then we probably know that we've matched the value for that
 byte, and so we move onto the next one, repeating the same procedure.
 
 The server does what is expected of it. etc/crackhmac.sh is a
 particularly-hacky bash script that calls curl in the requisite loop,
 hammering the server with different MACs until it reports verification.
 
 So, boot up the server via 'node index.js' and elsewhere do:
 
     $ ./crackhmac.sh "secrets.csv"
     present MAC guess: 0000000000000000000000000000000000000000
     working on next byte (hexstring index 0)..
     found byte b0
     present MAC guess: b000000000000000000000000000000000000000
     working on next byte (hexstring index 2)..
     found byte 94
     present MAC guess: b094000000000000000000000000000000000000
     working on next byte (hexstring index 4)..
     found byte e8
     present MAC guess: b094e80000000000000000000000000000000000
     working on next byte (hexstring index 6)..
     [..]
 
 N.b., the script is sort of janky, so there are facilities for resuming
 the loop in case the next byte can't be found due to timing weirdness.
 Append as arguments the index we were working on, the time in seconds
 the last comparison took, and the MAC we've extracted thus far, e.g.:
 
     $ ./crackhmac.sh "secrets.csv" 20 "0.57" "b094e8b74021e638ca4a"
 
 I probably shouldn't have chosen to do this with the shell, in
 hindsight, and I can immediately think of a better way to handle the
 timing variation. But in any case, after a while we should recover the
 secret MAC:
 
     working on next byte (hexstring index 38)..
     succeeded
     file: secrets.csv
     hmac: b094e8b74021e638ca4a65a9ac466cc7fde35c03
 
 And we can check our result manually to see HTTP status code 200 (the
 'safe' query parameter determines whether we do a sane comparison or
 this insane bytewise sleep thingy):
 
     $ file="secrets.csv"
     $ hmac="b094e8b74021e638ca4a65a9ac466cc7fde35c03"
     $ curl -o /dev/null --silent -Iw "%{http_code}\n" \
         "localhost:3000/hmac?safe=false&file=$file&signature=$hmac"
     200
 
 #### 4.32
 
 Here we do the same thing as in the last challenge, but now it's harder.
 
 > I probably shouldn't have chosen to do this with the shell, in
 > hindsight, and I can immediately think of a better way to handle the
 > timing variation.
 
 This is where we atone for our previous hacky bash scripts and write
 something a little more l33t. In this case we'll loop over bytes a
 few times each, collect timings, and then choose byte values on a
 statistical basis.
 
 Cryptopals.MAC.Attacks implements a few functions for poking the server,
 gathering timing samples, and choosing byte values. The thing that
 required the most fiddling was selecting the number of samples to take
 for each byte. A size of three didn't cut it, five often but not always
 cut it, and ten seemed to usually cut it, all using a boring average to
 aggregate the samples. Then I reckoned I could try taking less samples,
 but compare a more robust statistic for central tendency -- i.e., the
 median -- and that indeed worked really well. I converged on using seven
 samples, so that the median could be calculated by merely plucking out
 the middle sorted element. As a rule, the median is awesome.
 
 With that all in place, let's crack us a HMAC for the provided "file."
 We get periodic updates as more bytes are found:
 
     > mac <- crackHmac "secrets.csv"
     current guess: "34"
     current guess: "34ad"
     current guess: "34ade1"
     current guess: "34ade1f0"
     [..]
 
 when all is said and done, we recover our MAC:
 
     > B16.encodeBase16 mac
     34ade1f0a9c49af9bea5dea3f949b4b07582ba0d
 
 and can verify it validates properly for our "file":
 
     $ file="secrets.csv"
     $ hmac="34ade1f0a9c49af9bea5dea3f949b4b07582ba0d"
     $ curl -o /dev/null --silent -Iw "%{http_code}\n" \
         "localhost:3000/hmac?safe=true&file=$file&signature=$hmac"
     200
 
 A HTTP 200 status code, as expected.