Skip to content

Instantly share code, notes, and snippets.

@KWMalik
Forked from supki/Main.hs
Created July 30, 2012 20:04
Show Gist options
  • Save KWMalik/3209711 to your computer and use it in GitHub Desktop.
Save KWMalik/3209711 to your computer and use it in GitHub Desktop.
Cryptography coursera class exercise #4.
{-# 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"
@KWMalik
Copy link
Author

KWMalik commented Jul 31, 2012

% 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

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment