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"

% time runhaskell Main.hs
"The Magic Words are Squeamish Ossifrage\t\t\t\t\t\t\t\t\t"
runhaskell Main.hs 17.64s user 4.23s system 2% cpu 15:31.76 total

Hi! I just found via googling for instrctive material to solve the problem. Although I have implemented a variant of the padding oracle algorithm, I am still at a loss in what to send to the server. I liked your implementation (which seems wayyyy better than mine), and I was wondering if you could help me in this regard. I have my code in python and am still looking at the approach of a dict. attack, reading ciphers from a file. Can you share your ciphertext.dat file with me, which I may look into for insight into what is being sent; I am still very confused what it means to send arbitrary ciphertexts. Thanks for sharing the answer, which will be handy for comparison, although I'll only submit my answer if I generate it by my code, else I'll not submit it. I look forward to hearing from you in this regard in a positive. Thanks and Regards.
-- Bace

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.