commit 245f756a723fae2cd493a0f6cbf46d5004d21fee
parent 9b00748ce1fc78a38de6e8546200847a74b66463
Author: Jared Tobin <jared@jtobin.ca>
Date: Fri, 5 May 2017 21:09:39 +1200
Misc updates.
Diffstat:
14 files changed, 203 insertions(+), 2 deletions(-)
diff --git a/README.md b/README.md
@@ -5,3 +5,69 @@
Matasano's [cryptopals challenges](http://cryptopals.com/), implemented mainly
in [Rust](https://www.rust-lang.org) and [Haskell](https://haskell-lang.org/).
+## Problems
+
+To check some of these you can use the following general pattern:
+
+ $ SOLUTION = $(whatever)
+ $ diff <(echo $SOLUTION) /path/to/golden/output
+
+This is illustrated for 1.1.
+
+### Set 1
+
+#### 1.1
+
+ $ SOLUTION=$(cat data/s1/q1_input.txt | ./bin/hex2b64)
+ $ diff <(echo $SOLUTION) data/s1/q1_output.txt
+
+#### 1.2
+
+ $ ./bin/fixed_xor $(< data/s1/q2_input.txt) $(< data/s1/q2_against.txt)
+ 746865206b696420646f6e277420706c6179
+
+#### 1.3
+
+ $ ./bin/charfreq $(cat data/s1/q3_input.txt)
+ original: 1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
+ byte (frequency)
+ ----------------
+ 120 (6)
+ 55 (5)
+ 54 (3)
+ 49 (2)
+ 27 (2)
+
+ $ cat data/s1/q3_input.txt | ./bin/single_byte_xor 120
+ original: 1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
+
+ xored with: 120 (x)
+ decrypted: cOOKINGmcSLIKEAPOUNDOFBACON
+
+#### 1.4
+
+ $ parallel -a data/s1/q4_input.txt ./bin/charfreq | less
+ $ # look for strings w/high-frequency bytes
+ $ INPUT=7b5a4215415d544115415d5015455447414c155c46155f4058455c5b523f
+ $ HIGH_FREQ_BYTE=21
+ $ echo $INPUT | ./bin/single_byte_xor $HIGH_FREQ_BYTE
+ original: 7b5a4215415d544115415d5015455447414c155c46155f4058455c5b523f
+
+ xored with: 21 ()
+ decrypted: nOWTHATTHEPARTYISJUMPING*
+
+#### 1.5
+
+ $ echo -n $(cat data/s1/q5_input.txt) | ./bin/repeating_key_xor ICE | fold -w 74
+ original:
+ Burning 'em, if you ain't quick and nimble I go crazy when I hear a cymbal
+ xored with: ICE
+ result:
+ 0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a2622632427276527
+ 2a282b2f20690a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f
+
+
+#### 1.6
+
+ $ INPUT=$(cat data/s1/q6_input.txt | ./bin/b642hex)
+
diff --git a/data/s1/q1_input.txt b/data/s1/q1_input.txt
@@ -0,0 +1 @@
+49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d
diff --git a/data/s1/q1_output.txt b/data/s1/q1_output.txt
@@ -0,0 +1 @@
+SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t
diff --git a/data/s1/q2_against.txt b/data/s1/q2_against.txt
@@ -0,0 +1 @@
+686974207468652062756c6c277320657965
diff --git a/data/s1/q2_input.txt b/data/s1/q2_input.txt
@@ -0,0 +1 @@
+1c0111001f010100061a024b53535009181c
diff --git a/data/s1/q2_output.txt b/data/s1/q2_output.txt
@@ -0,0 +1 @@
+746865206b696420646f6e277420706c6179
diff --git a/etc/data/3.txt b/data/s1/q3_input.txt
diff --git a/etc/data/s1c4.dat b/data/s1/q4_input.txt
diff --git a/etc/data/s1c5.txt b/data/s1/q5_input.txt
diff --git a/etc/data/6.txt b/data/s1/q6_input.txt
diff --git a/lib/hex2b64/README.md b/lib/hex2b64/README.md
@@ -0,0 +1,7 @@
+# hex2b64
+
+Convert hex-encoded strings to base64-encoded strings.
+
+```
+$ echo '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d' | cargo run
+```
diff --git a/lib/rotate/Rotate.hs b/lib/rotate/Rotate.hs
@@ -25,7 +25,7 @@ main = do
Nothing -> hPutStrLn stderr "rotate: invalid keysize"
Just size -> do
bs <- B8.getContents
- let flipped = B.transpose $ chunks size (B8.filter (/= '\n') bs)
+ let flipped = B.transpose $ chunks size bs
mapM_ B8.putStrLn flipped
_ -> putStrLn "USAGE: echo FOO | ./rotate KEYSIZE"
diff --git a/lib/single_byte_xor/src/main.rs b/lib/single_byte_xor/src/main.rs
@@ -10,7 +10,7 @@ fn main() {
let args: Vec<String> = env::args().collect();
if args.len() != 2 {
- println!("USAGE: echo FOO | ./single_byte_xor BYTE");
+ println!("USAGE: echo HEX | ./single_byte_xor BYTE");
return ()
}
diff --git a/src/s1c6.hs b/src/s1c6.hs
@@ -0,0 +1,123 @@
+{-# OPTIONS_GHC -Wall #-}
+{-# LANGUAGE BangPatterns #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE TypeOperators #-}
+
+import Control.Error
+import Data.Bits
+import qualified Data.ByteString as B
+import qualified Data.ByteString.Char8 as B8
+import qualified Data.ByteString.Base16 as B16
+import qualified Data.ByteString.Base64 as B64
+import qualified Data.IntPSQ as PSQ
+import qualified Data.Map.Strict as MS
+import GHC.Word
+import System.IO
+
+-- | Hamming distance between bytestrings.
+--
+-- Returns Nothing if bytestrings are of unequal length.
+distance :: B.ByteString -> B.ByteString -> Maybe Int
+distance s0 s1
+ | B.length s0 /= B.length s1 = Nothing
+ | otherwise = Just (foldr alg 0 (B.zip s0 s1))
+ where
+ hamming a b = popCount (xor a b)
+ alg = (+) . uncurry hamming
+
+-- | Score a keysize applied to a bytestring.
+score :: Fractional a => B.ByteString -> Int -> Maybe a
+score text size = do
+ let (chunk0, rest) = B.splitAt size text
+ chunk1 = B.take size rest
+ hamming <- distance chunk0 chunk1
+ return $ fromIntegral hamming / fromIntegral size
+
+-- | More meticulously score a keysize applied to a bytestring.
+altScore :: Fractional a => B.ByteString -> Int -> Maybe a
+altScore text size = do
+ let chunked = chunks size text
+ leading = take 4 chunked
+
+ chunk0 <- atMay leading 0
+ chunk1 <- atMay leading 1
+ chunk2 <- atMay leading 2
+ chunk3 <- atMay leading 3
+
+ hamming0 <- distance chunk0 chunk1
+ hamming1 <- distance chunk0 chunk2
+ hamming2 <- distance chunk0 chunk3
+
+ let dsum = hamming0 + hamming1 + hamming2
+
+ return $ fromIntegral dsum / (3 * fromIntegral size)
+
+-- | Score keysizes 2-40 over a given bytestring.
+scoreKeysizes
+ :: (B.ByteString -> Int -> Maybe Double)
+ -> B.ByteString
+ -> PSQ.IntPSQ Double ()
+scoreKeysizes scorer text = loop PSQ.empty 2 where
+ plain = B64.decodeLenient text
+ loop !acc size
+ | size == 40 = acc
+ | otherwise = case score plain size of
+ Nothing -> acc
+ Just prio ->
+ let nacc = PSQ.insert size prio () acc
+ in loop nacc (succ size)
+
+-- | Return the best (smallest) n keys from a queue, by key..
+best :: Ord p => Int -> PSQ.IntPSQ p v -> [(Int, p)]
+best = loop mempty where
+ loop !acc idx queue
+ | idx <= 0 = reverse acc
+ | otherwise = case PSQ.minView queue of
+ Nothing -> reverse acc
+ Just (key, prio, _, rest) ->
+ let nacc = (key, prio) : acc
+ in loop nacc (pred idx) rest
+
+-- | Split a bytestring into chunks.
+chunks :: Int -> B.ByteString -> [B.ByteString]
+chunks size = loop mempty where
+ loop !acc bs
+ | B.null bs = reverse acc
+ | otherwise = case B.splitAt size bs of
+ (chunk, rest) -> loop (chunk : acc) rest
+
+tally :: Ord a => [a] -> MS.Map a Int
+tally = loop MS.empty where
+ loop !acc [] = acc
+ loop !acc (x:xs) =
+ let nacc = case MS.lookup x acc of
+ Nothing -> MS.insert x 1 acc
+ Just count -> MS.update (Just . succ) x acc
+ in loop nacc xs
+
+mostFrequent :: MS.Map a Int -> Maybe a
+mostFrequent ms = case MS.toList ms of
+ [] -> Nothing
+ ((k, v):xs) -> Just (loop k v xs)
+ where
+ loop mk _ [] = mk
+ loop mk mv ((k, v):xs) = case compare v mv of
+ GT -> loop k v xs
+ _ -> loop mk mv xs
+
+main :: IO ()
+main = do
+ raw <- B.readFile "etc/data/6.txt"
+ let mdecoded = B64.decode (B8.filter (/= '\n') raw)
+
+ case mdecoded of
+ Left msg -> hPutStrLn stderr msg
+ Right decoded -> do
+ let hexed = B16.encode decoded
+ chunked = chunks 3 hexed
+ rotated = B.transpose chunked
+ unpacked = fmap B.unpack rotated
+
+ return ()
+
+ return ()
