commit 195bbec86afbc84ee3451e35a737eda795a9bb88
parent 6cbe4b901a02775ac0d39426cbd61c44eb86f271
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 3 Jun 2023 09:15:54 +0400
More stuff from set 1.
Diffstat:
13 files changed, 376 insertions(+), 67 deletions(-)
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -12,6 +12,7 @@ cabal-version: >= 1.10
library
default-language: Haskell2010
default-extensions:
+ BangPatterns
LambdaCase
OverloadedStrings
RecordWildCards
@@ -19,7 +20,9 @@ library
hs-source-dirs:
lib
exposed-modules:
- Cryptopals.Util
+ Cryptopals.AES
+ , Cryptopals.Util
+ , Cryptopals.Util.ByteString
, Cryptopals.Util.Similarity
build-depends:
base
@@ -27,6 +30,7 @@ library
, base64
, bytestring
, containers
+ , cryptonite
, text
executable fixed-xor
@@ -94,3 +98,43 @@ executable repeating-key-xor
, optparse-applicative
, text
+executable detect-repeating-key-xor-keysize
+ main-is: DetectRepeatingKeyXorKeysize.hs
+ ghc-options: -Wall -O2
+ default-language: Haskell2010
+ hs-source-dirs: src
+ build-depends:
+ base
+ , base64
+ , bytestring
+ , cryptopals
+ , optparse-applicative
+ , psqueues
+ , text
+
+executable rotate
+ main-is: Rotate.hs
+ ghc-options: -Wall -O2
+ default-language: Haskell2010
+ hs-source-dirs: src
+ build-depends:
+ base
+ , base16
+ , bytestring
+ , cryptopals
+ , optparse-applicative
+ , text
+
+executable aes
+ main-is: AES.hs
+ ghc-options: -Wall -O2
+ default-language: Haskell2010
+ hs-source-dirs: src
+ build-depends:
+ base
+ , base16
+ , bytestring
+ , cryptopals
+ , optparse-applicative
+ , text
+
diff --git a/default.nix b/default.nix
@@ -1,5 +1,5 @@
let
- revision = "813836d64";
+ revision = "5717cbc076d996e6c07b16706073f09e021d0b99";
tarball = owner: repo: rev:
builtins.fetchTarball {
diff --git a/docs/s1.md b/docs/s1.md
@@ -167,73 +167,47 @@ so if we want to decrypt the ciphertext we'll need to pipe it through
#### 1.6
- $ INPUTB64=$(< data/s1/q6_input.txt)
- $ INPUTHEX=$(echo $INPUTB64 | ./bin/b642hex)
- $ echo $INPUTB64 | ./bin/score_keysizes 4 10
-
-Top keysizes for average of 4+ groups are roughly 5, 29, 3.
-
-Five doesn't go far:
-
- $ KEYSIZE=5
- $ echo $INPUTHEX | ./bin/rotate $KEYSIZE | parallel -k ./bin/charfreq | less
-
-Twenty-nine does it:
-
- $ KEYSIZE=29
- $ echo $INPUTHEX | ./bin/rotate $KEYSIZE | \
- parallel -k 'echo -n {} | ./bin/break_single_byte_xor -r'
- T (84)
- e (101)
- r (114)
- m (109)
- i (105)
- n (110)
- a (97)
- t (116)
- o (111)
- r (114)
- (32)
- X (88)
- : (58)
- (32)
- B (66)
- r (114)
- i (105)
- n (110)
- g (103)
- (32)
- t (116)
- h (104)
- e (101)
- (32)
- n (110)
- o (111)
- i (105)
- s (115)
- e (101)
-
- $ xxd -r -p <<< "$INPUTHEX" | \
- ./bin/repeating_key_xor "Terminator X: Bring the noise" | \
- xxd -r -p | tail -c +19 | head -2
+First, determining a keysize for a suspected repeating-key XOR'd
+ciphertext; I use an average pairwise normalised Hamming distance:
+
+ $ detect-repeating-key-xor-keysize "$(< data/s1/q6_input.txt)"
+ cryptopals: keysize of 29 yields minimum score of 2.7856894063790736
+
+Then to guess the key itself, one chunks the input into blocks of the
+appropriate size and transposes the result, so that every byte in a
+transposed block has been XOR'd against a single byte. Doing that and
+breaking each block individually yields the key:
+
+ $ input_hex=$(cat data/s1/q6_input.txt | base64 -d | xxd -p | tr -d '\n')
+ $ key=$(rotate 29 $input_hex | \
+ parallel -k 'break-single-byte-xor -l {}' 2> /dev/null | tr -d "\n'")
+ $ echo $key
+ Terminator X: Bring the noise
+
+then use `repeating-key-xor` with the key to recover the plaintext:
+
+ $ repeating-key-xor "$key" --hex "$input_hex" | xxd -r -p | head -2
I'm back and I'm ringin' the bell
A rockin' on the mike while the fly girls yell
#### 1.7
-I like openssl, heck the rules:
+Here we're doing AES-128 decryption in ECB mode.
+
+It's worth using the `openssl` tool just to get a feel for it:
- $ KEY=$(echo -n 'YELLOW SUBMARINE' | xxd -p)
+ $ key=$(echo -n 'YELLOW SUBMARINE' | xxd -p)
$ openssl enc -aes-128-ecb \
- -a -d -K $KEY -nosalt \
+ -a -d -K "$key" -nosalt \
-in data/s1/q7_input.txt | head -2
I'm back and I'm ringin' the bell
A rockin' on the mike while the fly girls yell
-Alternatively, with code:
+The `aes` binary will similarly do the trick:
- $ cat data/s1/q7_input.txt | tr -d '\n' | ./bin/aes_ecb \
- --key "YELLOW SUBMARINE" | head -2
+ $ key=$(echo -n "YELLOW SUBMARINE" | xxd -p)
+ $ ciphertext=$(cat data/s1/q7_input.txt | base64 -d | xxd -p | tr -d '\n')
+ $ aes decrypt "$key" "$ciphertext" | xxd -r -p | head -2
I'm back and I'm ringin' the bell
A rockin' on the mike while the fly girls yell
diff --git a/lib/Cryptopals/AES.hs b/lib/Cryptopals/AES.hs
@@ -0,0 +1,19 @@
+module Cryptopals.AES (
+ encryptEcbAES128
+ , decryptEcbAES128
+ ) where
+
+import qualified Data.ByteString as BS
+import qualified Crypto.Cipher.AES as CAES
+import qualified Crypto.Cipher.Types as CT
+import qualified Crypto.Error as CE
+
+initAES128 :: BS.ByteString -> CAES.AES128
+initAES128 = CE.throwCryptoError . CT.cipherInit
+
+encryptEcbAES128 :: BS.ByteString -> BS.ByteString -> BS.ByteString
+encryptEcbAES128 key = CT.ecbEncrypt (initAES128 key)
+
+decryptEcbAES128 :: BS.ByteString -> BS.ByteString -> BS.ByteString
+decryptEcbAES128 key = CT.ecbDecrypt (initAES128 key)
+
diff --git a/lib/Cryptopals/Util.hs b/lib/Cryptopals/Util.hs
@@ -2,15 +2,21 @@ module Cryptopals.Util (
Hex(..)
, Base64(..)
+ , CUB.chunks
+ , CUB.hamming
, hexToB64
, fixedXor
+ , CUB.nhamming
, CUS.often
- , CUS.score
+ , CUB.panhamming
, repeatingKeyXor
+ , CUB.rotate
+ , CUS.score
, singleByteXor
, CUS.tally
) where
+import qualified Cryptopals.Util.ByteString as CUB
import qualified Cryptopals.Util.Similarity as CUS
import qualified Data.Bits as B
import qualified Data.ByteString as BS
diff --git a/lib/Cryptopals/Util/ByteString.hs b/lib/Cryptopals/Util/ByteString.hs
@@ -0,0 +1,45 @@
+module Cryptopals.Util.ByteString (
+ hamming
+ , nhamming
+ , panhamming
+ , chunks
+ , rotate
+ ) where
+
+import qualified Data.Bits as B
+import qualified Data.ByteString as BS
+import qualified Data.List as L
+import qualified Data.List.NonEmpty as NE
+
+-- | Hamming distance between bytestrings.
+hamming :: BS.ByteString -> BS.ByteString -> Maybe Int
+hamming l r
+ | BS.length l /= BS.length r = Nothing
+ | otherwise = Just (foldr alg 0 (BS.zip l r))
+ where
+ ham a b = B.popCount (B.xor a b)
+ alg = (+) . uncurry ham
+
+-- | Normalized Hamming distance between bytestrings.
+nhamming :: BS.ByteString -> BS.ByteString -> Maybe Double
+nhamming a b =
+ let len = fromIntegral (BS.length a)
+ in fmap (\s -> fromIntegral s / len) (hamming a b)
+
+-- | Average pairwise normalized Hamming distance between bytestrings.
+panhamming:: [BS.ByteString] -> Maybe Double
+panhamming bs = case bs of
+ [] -> Nothing
+ _ -> do
+ ps <- sequence [nhamming h b | (h:t) <- L.tails bs, b <- t]
+ pure $ sum ps / fromIntegral (length ps)
+
+chunks :: Int -> BS.ByteString -> [BS.ByteString]
+chunks size = loop mempty where
+ loop !acc bs
+ | BS.null bs = reverse acc
+ | otherwise = case BS.splitAt size bs of
+ (chunk, rest) -> loop (chunk : acc) rest
+
+rotate :: Int -> BS.ByteString -> [BS.ByteString]
+rotate rows = BS.transpose . chunks rows
diff --git a/lib/Cryptopals/Util/Similarity.hs b/lib/Cryptopals/Util/Similarity.hs
@@ -9,7 +9,7 @@ import Data.Function (on)
import qualified Data.IntMap.Strict as IMS
import qualified Data.List as L
--- | Similarity of the byte encoding to English plaintext. Smaller is better.
+-- | Distance of the encoding from expected English plaintext.
score :: BS.ByteString -> Double
score = mse english . dist
diff --git a/src/AES.hs b/src/AES.hs
@@ -0,0 +1,72 @@
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE RecordWildCards #-}
+
+module Main where
+
+import qualified Cryptopals.AES as AES
+import qualified Data.ByteString.Base16 as B16
+import qualified Data.Char as C
+import qualified Data.Text as T
+import qualified Data.Text.Encoding as TE
+import qualified Data.Text.IO as TIO
+import qualified Options.Applicative as O
+import qualified System.Exit as SE
+import qualified System.IO as SIO
+
+data Operation =
+ Encrypt
+ | Decrypt
+
+data Args = Args {
+ argsOpr :: Operation
+ , argsKey :: T.Text
+ , argsInp :: T.Text
+ }
+
+ops :: O.Parser Args
+ops = Args
+ <$> operationParser
+ <*> O.argument O.str (O.metavar "KEY")
+ <*> O.argument O.str (O.metavar "INPUT")
+
+operationParser :: O.Parser Operation
+operationParser = O.argument op etc where
+ op = O.eitherReader $ \input -> case fmap C.toLower input of
+ "encrypt" -> pure Encrypt
+ "decrypt" -> pure Decrypt
+ _ -> Left ("invalid operation: " <> input)
+
+ etc = O.metavar "OPERATION"
+ <> O.help "{encrypt, decrypt}"
+
+aes :: Args -> IO ()
+aes Args {..} = do
+ let args = do
+ k <- B16.decodeBase16 $ TE.encodeUtf8 argsKey
+ v <- B16.decodeBase16 $ TE.encodeUtf8 argsInp
+ pure (k, v)
+
+ case args of
+ Left e -> do
+ TIO.hPutStrLn SIO.stderr ("cryptopals: " <> e)
+ SE.exitFailure
+
+ Right (k, v) -> do
+ case argsOpr of
+ Encrypt -> TIO.putStrLn . TE.decodeUtf8 . B16.encodeBase16' $
+ AES.encryptEcbAES128 k v
+
+ Decrypt -> TIO.putStrLn . TE.decodeUtf8 . B16.encodeBase16' $
+ AES.decryptEcbAES128 k v
+
+main :: IO ()
+main = do
+ let pars = O.info (O.helper <*> ops) $
+ O.fullDesc
+ <> O.progDesc "AES encryption/decryption"
+ <> O.header "aes"
+
+ args <- O.execParser pars
+
+ aes args
+
diff --git a/src/BreakSingleByteXor.hs b/src/BreakSingleByteXor.hs
@@ -6,6 +6,7 @@ module Main where
import qualified Cryptopals.Util as CU
import qualified Data.ByteString as BS
import qualified Data.ByteString.Base16 as B16
+import qualified Data.Char as C
import Data.List (foldl')
import qualified Data.Text as T
import qualified Data.Text.IO as TIO
@@ -15,10 +16,22 @@ import qualified Options.Applicative as O
import qualified System.Exit as SE
import qualified System.IO as SIO
-data Args = Args { argsInp :: T.Text }
+data Mode =
+ Decrypt
+ | Log
+
+data Args = Args {
+ argsInp :: T.Text
+ , argsMod :: Mode
+ }
ops :: O.Parser Args
-ops = Args <$> O.argument O.str (O.metavar "INPUT")
+ops = Args
+ <$> O.argument O.str (O.metavar "INPUT")
+ <*> O.flag Decrypt Log (
+ O.long "log" <> O.short 'l' <>
+ O.help "log the likely enciphering byte"
+ )
best :: BS.ByteString -> (Word8, Double, BS.ByteString)
best s = foldl' alg (0, CU.score s, s) [32..126] where
@@ -55,7 +68,9 @@ decipher Args {..} = do
)
err $ "cryptopals: result"
- out . TE.decodeUtf8 . B16.encodeBase16' $ b
+ case argsMod of
+ Decrypt -> out . TE.decodeUtf8 . B16.encodeBase16' $ b
+ Log -> out . render $ C.chr (fromIntegral byt)
main :: IO ()
main = do
diff --git a/src/DetectRepeatingKeyXorKeysize.hs b/src/DetectRepeatingKeyXorKeysize.hs
@@ -0,0 +1,69 @@
+{-# LANGUAGE BangPatterns #-}
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE RecordWildCards #-}
+
+module Main where
+
+import qualified Cryptopals.Util as CU
+import qualified Data.ByteString as BS
+import qualified Data.ByteString.Base64 as B64
+import qualified Data.Text as T
+import qualified Data.Text.IO as TIO
+import qualified Data.Text.Encoding as TE
+import qualified Options.Applicative as O
+import qualified System.Exit as SE
+import qualified System.IO as SIO
+
+data Args = Args { argsInp :: T.Text }
+
+ops :: O.Parser Args
+ops = Args <$> O.argument O.str (O.metavar "INPUT")
+
+score :: BS.ByteString -> Maybe (Double, Int)
+score b = loop Nothing 2 where
+ loop acc siz
+ | siz == 40 = acc
+ | otherwise =
+ let sc = CU.panhamming
+ . filter (\s -> BS.length s == siz)
+ . CU.chunks siz
+ $ b
+ in case sc of
+ Nothing -> loop acc (succ siz)
+ Just s ->
+ let nacc = case acc of
+ Nothing -> Just (s, siz)
+ Just (r, _) -> if s < r
+ then Just (s, siz)
+ else acc
+ in loop nacc (succ siz)
+
+guess :: Args -> IO ()
+guess Args {..} = do
+ let err = TIO.hPutStrLn SIO.stderr
+
+ render :: Show a => a -> T.Text
+ render = T.pack . show
+
+ s = B64.decodeBase64Lenient $ TE.encodeUtf8 argsInp
+
+ case score s of
+ Nothing -> do
+ err "cryptopals: couldn't guess keysize"
+ SE.exitFailure
+
+ Just (sc, siz) -> do
+ err ("cryptopals: keysize of " <> render siz <>
+ " yields minimum score of " <> render sc)
+
+main :: IO ()
+main = do
+ let pars = O.info (O.helper <*> ops) $
+ O.fullDesc
+ <> O.progDesc "guess repeating-key-xor'd keysize"
+ <> O.header "detect-repeating-key-xor-keysize"
+
+ args <- O.execParser pars
+
+ guess args
+
diff --git a/src/DetectSingleByteXor.hs b/src/DetectSingleByteXor.hs
@@ -9,7 +9,6 @@ import qualified Data.ByteString.Char8 as B8
import qualified Data.Foldable as F
import Data.Function (on)
import qualified Data.List as L
--- import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import qualified Data.Text.Encoding as TE
import qualified Options.Applicative as O
diff --git a/src/RepeatingKeyXor.hs b/src/RepeatingKeyXor.hs
@@ -10,22 +10,37 @@ import qualified Data.Text.Encoding as TE
import qualified Data.Text.IO as TIO
import qualified Options.Applicative as O
+data Encoding =
+ Utf8
+ | Utf16
+
data Args = Args {
argsKey :: T.Text
, argsInp :: T.Text
+ , argsEnc :: Encoding
}
ops :: O.Parser Args
ops = Args
<$> O.argument O.str (O.metavar "KEY")
<*> O.argument O.str (O.metavar "INPUT")
+ <*> O.flag Utf8 Utf16 (
+ O.long "hex" <>
+ O.help "input is hex-encoded"
+ )
rxor :: Args -> IO ()
rxor Args {..} = do
- let (k, v) = (TE.encodeUtf8 argsKey, TE.encodeUtf8 argsInp)
- res = CU.repeatingKeyXor k v
-
- TIO.putStrLn . TE.decodeUtf8 . B16.encodeBase16' $ res
+ let k = TE.encodeUtf8 argsKey
+ v = case argsEnc of
+ Utf8 -> pure $ TE.encodeUtf8 argsInp
+ Utf16 -> B16.decodeBase16 (TE.encodeUtf8 argsInp)
+
+ case v of
+ Left e -> error "FIXME"
+ Right s ->
+ TIO.putStrLn . TE.decodeUtf8 . B16.encodeBase16' $
+ CU.repeatingKeyXor k s
main :: IO ()
main = do
diff --git a/src/Rotate.hs b/src/Rotate.hs
@@ -0,0 +1,51 @@
+{-# LANGUAGE OverloadedStrings #-}
+{-# LANGUAGE RecordWildCards #-}
+
+module Main where
+
+import qualified Cryptopals.Util as CU
+import qualified Data.ByteString.Base16 as B16
+import qualified Data.Text as T
+import qualified Data.Text.Encoding as TE
+import qualified Data.Text.IO as TIO
+import Data.Foldable (for_)
+import qualified Options.Applicative as O
+import qualified System.Exit as SE
+import qualified System.IO as SIO
+
+data Args = Args {
+ argsSiz :: Int
+ , argsInp :: T.Text
+ }
+
+ops :: O.Parser Args
+ops = Args
+ <$> O.argument O.auto (O.metavar "ROWS")
+ <*> O.argument O.str (O.metavar "INPUT")
+
+rot :: Args -> IO ()
+rot Args {..} = do
+ let args = do
+ v <- B16.decodeBase16 $ TE.encodeUtf8 argsInp
+ pure (argsSiz, v)
+
+ case args of
+ Left e -> do
+ TIO.hPutStrLn SIO.stderr ("cryptopals: " <> e)
+ SE.exitFailure
+
+ Right (s, v) -> do
+ let res = CU.rotate s v
+ for_ res $ TIO.putStrLn . TE.decodeUtf8 . B16.encodeBase16'
+
+main :: IO ()
+main = do
+ let pars = O.info (O.helper <*> ops) $
+ O.fullDesc
+ <> O.progDesc "transpose the target bytes"
+ <> O.header "rotate"
+
+ args <- O.execParser pars
+
+ rot args
+
