Cryptography coursera class exercise #4.

Main.hs

{-# LANGUAGE UnicodeSyntax #-}
module Main where

import Control.Applicative ((<$>))
import Control.Monad (foldM, join)
import qualified Data.Bits as Bits
import Data.List (genericReplicate, inits)
import Data.Monoid ((<>))
import Data.Word (Word8)
import Text.Printf (printf)

import Data.ByteString (ByteString)
import qualified Data.ByteString as B
import qualified Network.Curl as C


randomByteString ∷ ByteString
randomByteString = B.replicate 16 57


main ∷ IO ()
main =
  do cipher ← B.readFile "ciphertext.dat"
     plainText ← decrypt cipher
     print plainText


decrypt ∷ ByteString → IO ByteString
decrypt cipher = B.concat . map (B.pack . B.zipWith Bits.xor randomByteString) <$> mapM decryptitionRound (ciphers cipher)
 where
  ciphers = map B.concat . drop 2 . inits . chunk 16



decryptitionRound ∷ ByteString → IO ByteString
decryptitionRound cipher = foldM (bruteforceByte cipher) (B.replicate 16 0) paddings
 where
  paddings = map (B.pack . reverse . take 16 . (<> repeat 0) . join genericReplicate) [1..16]


bruteforceByte ∷ ByteString → ByteString → ByteString → IO ByteString
bruteforceByte cipher acc padding = go 0
 where
  paddedCipher = cipher `xor` padding `xor` acc `xor` randomByteString
  go n =
    do let guess = pretty $ paddedCipher `xor` fromWord8 (B.length $ B.dropWhile (== 0) acc) n
       r ← C.withCurlDo $ C.curlGetResponse_
         ("http://crypto-class.appspot.com/po?er=" <> guess)
         [] ∷ IO (C.CurlResponse_ [(String, String)] ByteString)
       case C.respStatus r of
         403 → go (n + 1)
         _ → return (addByte n acc)


addByte ∷ Word8 → ByteString → ByteString
addByte n xs = B.replicate (16 - t - 1) 0 <> B.cons n ys
 where
  ys = B.dropWhile (== 0) xs
  t = B.length ys


xor ∷ ByteString → ByteString → ByteString
xor x y = B.concat as <> B.pack (B.zipWith Bits.xor c y) <> b
 where
  (as,c,b) = split $ chunk 16 x


fromWord8 ∷ Int → Word8 → ByteString
fromWord8 t n = B.pack $ replicate (16 - t - 1) 0 ++ n : replicate t 0


pretty ∷ ByteString → String
pretty = concatMap (printf "%02x") . B.unpack


chunk ∷ Int → ByteString → [ByteString]
chunk n bs
  | B.length bs <= n = [bs]
  | otherwise = B.take n bs : chunk n (B.drop n bs)


split ∷ [α] → ([α], α, α)
split = go []
 where
  go as [x,y] = (reverse as, x, y)
  go as (x:xs) = go (x:as) xs
  go _ _ = error "Main.split: [_]/empty list"

ciphertext.dat is not very interesting since it just contains given ciphertext (f20bdba6ff29eed7b046d1df9fb7000058b1ffb4210a580f748b4ac714c001bd4a61044426fb515dad3f21f18aa577c0bdf302936266926ff37dbf7035d5eeb4) in binary.
You don't need to do any smart dictionary attacks or prepare sophisticated ciphertexts in file to solve the problem, bruteforce is enough. The key idea is to guess byte after byte given different oracle's responses on different kinds of problems. Simple example for one last byte is given in lecture slides (page 50-51).

Hi
Just found this looking at Haskell implementations! I might commend this; a much optimized implementation than my own version, implemented in Java. Thanks for sharing! I found it to be quite instructive and useful from both learning and skills development standpoints.

@KWMalik You're welcome. Note that this code snippet isn't really meant to be optimized, I'm sure some cleverer algorithm exists.

I'm sure, as noted by my CS collegefellows here at Cambridge (I'm currently diversifying into management). I merely put in an implementation to get the work done, not really concerned with optimizing either, but the program took way too long for comfort. In the end, didn't really mind as it got the job done. Regarding this, it was clever for me, as I am just starting out with Haskell and Ruby; quite a way to go even before I reach this level of coding in hs, so to speak. Best Regards, Khurram

Hello!
This gist violates coursera honor code: https://www.coursera.org/about/terms/honorcode

I will not make solutions to homework, quizzes or exams available to anyone else.
This includes both solutions written by me, as well as any official solutions provided by the course staff.