commit 64357d513f00456eab1de95b0917fe73ba37aff2
parent d6300a6ddf03e6ff84b49cddaed8b907a45a11c3
Author: Jared Tobin <jared@jtobin.io>
Date: Tue, 1 Aug 2023 22:24:59 -0230
Finish set 3.
Diffstat:
5 files changed, 163 insertions(+), 13 deletions(-)
diff --git a/.ghci b/.ghci
@@ -1,5 +1,7 @@
:set prompt "> "
:set -XOverloadedStrings
+import qualified Data.Binary.Get as BG
+import qualified Data.Binary.Put as BP
import qualified Data.Bits as B
import qualified Data.ByteString as BS
import qualified Data.ByteString.Lazy as BSL
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -26,6 +26,7 @@ library
, Cryptopals.Util
, Cryptopals.Util.ByteString
, Cryptopals.Util.Similarity
+ , Cryptopals.Stream.Attacks
, Cryptopals.Stream.RNG
, Cryptopals.Stream.RNG.MT19937
build-depends:
@@ -39,6 +40,7 @@ library
, mwc-random
, primitive
, text
+ , time
, unordered-containers
, vector
diff --git a/docs/s3.md b/docs/s3.md
@@ -112,7 +112,7 @@ gist of it:
(MT19937) PRNG in standard return-the-generator fashion:
> let gen = seed 42
- > bytes 3 gen
+ > tap 3 gen
> ([1608637542,3421126067,4083286876],<MT19937.Gen>)
The only annoying thing about this problem was finding a test vector
@@ -172,8 +172,8 @@ So, via the same timestamp calculator, it was seeded at Sun Jul 30 2023
#### 3.23
A Mersenne Twister outputs elements of its internal state transformed
-by a tempering map. The state is perturbed every 624 iterations (the
-"twist"), but if we have all 624 outputs generated from a constant
+by a linear tempering map. The state is perturbed every 624 iterations
+(the "twist"), but if we have all 624 outputs generated from a constant
internal state, that state can be recovered by running the outputs
through the inverse tempering map.
@@ -187,7 +187,7 @@ expressed by:
e3 = ls t c
e4 = rs l
-and the inverse transform by:
+and its inverse by:
untemper :: Word32 -> Word32
untemper = n1 . n2 . n3 . n4 where
@@ -196,7 +196,8 @@ and the inverse transform by:
n3 = lsinv t c
n4 = rsinv l
-given the following salad of internal functions:
+given the following salad of internal functions (you either know how to invert
+an xorshift operation or you don't):
ls :: Word32 -> Word32 -> Word32 -> Word32
ls s m a = a `B.xor` (B.shiftL a (fi s) .&. m)
@@ -235,11 +236,83 @@ untemper them to recover the internal state for those 624 iterations
any intermediate twists of the internal state):
> let gen = seed 42
- > let (bs, g) = bytes 624 gen
+ > let (bs, g) = tap 624 gen
> let cloned = Gen 624 (VU.fromList . fmap untemper $ bs)
- > fst (bytes 3 g)
+ > fst (tap 3 g)
[108880612,791707097,4134543476]
- > fst (bytes 3 cloned)
+ > fst (tap 3 cloned)
[108880612,791707097,4134543476]
+As stated in sec 1.6 of the original Mersenne Twister paper, the key
+to hardening the PRNG is to pass the outputs through a secure hash
+function.
+
+#### 3.24
+
+The first challenge here is to recover the stream cipher's seed from
+some ciphertext, given a (mostly-) known plaintext. The issue is that
+at 16 bits the seed is tiny, and so it can be easily be brute-forced by
+just iterating through the possible word values:
+
+ mtCipherAttack :: BS.ByteString -> Word16
+ mtCipherAttack cip = loop 0 where
+ l = BS.length cip
+ t = BS.replicate 14 65
+ loop j
+ | j > (maxBound :: Word16) = error "impossible seed"
+ | otherwise =
+ let g = MT.seed (fromIntegral j)
+ bs = keystream l g
+ pt = BS.drop (l - 14) (bs `CU.fixedXor` cip)
+ in if pt == t
+ then j
+ else loop (succ j)
+
+Running it on some ciphertext I created reveals the seed used in a
+minute or two:
+
+ > B16.encodeBase16 ciphertext
+ "df2c20f5025fed9e86a986e47d8bee063213afc1"
+ > mtCipherAttack ciphertext
+ 50000
+
+The token seeded by system time is also trivial to crack, since we can
+just generate a seed from the current time and check the result directly:
+
+ pwntToken :: IO T.Text
+ pwntToken = do
+ s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
+ let g = MT.seed s
+ pure $ B64.encodeBase64 (keystream 16 g)
+
+ notPwntToken :: IO T.Text
+ notPwntToken = do
+ g <- MWC.createSystemRandom
+ bs <- fmap BS.pack $ replicateM 16 (MWC.uniformR (32, 126) g)
+ pure $ B64.encodeBase64 bs
+
+ isPwnt :: T.Text -> IO Bool
+ isPwnt token = do
+ s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
+ let g = MT.seed s
+ ks = keystream 16 g
+ pure $ token == B64.encodeBase64 ks
+
+(N.b., 'notPwntToken' uses /dev/random or /dev/urandom to generate a
+seed, instead of the system time.)
+
+Some examples:
+
+ > pwntToken
+ "2Pi2LO0cn3XXyw1xwrLlHQ=="
+ > pwntToken
+ "WqPvmtGTfc3QkhVs78uOqQ=="
+ > notPwntToken
+ "V0codSgtXyNvLSJ4XjNyNQ=="
+ > notPwntToken
+ "STA3ZnxVe1tQW0Q4TF0pbg=="
+ > pwntToken >>= isPwnt
+ True
+ > notPwntToken >>= isPwnt
+ False
diff --git a/lib/Cryptopals/Stream/Attacks.hs b/lib/Cryptopals/Stream/Attacks.hs
@@ -0,0 +1,74 @@
+module Cryptopals.Stream.Attacks where
+
+import Control.Monad
+import qualified Control.Monad.ST as ST
+import qualified Data.Binary.Put as BP
+import qualified Data.ByteString as BS
+import qualified Data.ByteString.Base64 as B64
+import qualified Data.ByteString.Lazy as BSL
+import qualified Data.Text as T
+import qualified Data.Time.Clock.System as TS
+import qualified Cryptopals.Stream.RNG.MT19937 as MT
+import qualified Cryptopals.Util as CU
+import GHC.Word (Word16, Word8)
+import qualified System.Random.MWC as MWC
+
+keystream :: Int -> MT.Gen -> BS.ByteString
+keystream nb g =
+ let l = nb `quot` 4 + nb `rem` 4
+ ws = fst (MT.tap l g)
+ in BS.take nb . BSL.toStrict . BP.runPut $ loop ws
+ where
+ loop bs = case bs of
+ [] -> pure ()
+ (h:t) -> do
+ BP.putWord32le h
+ loop t
+
+encryptMT19937 :: Word16 -> BS.ByteString -> BS.ByteString
+encryptMT19937 s pt = pt `CU.fixedXor` bs where
+ g = MT.seed (fromIntegral s)
+ bs = keystream (BS.length pt) g
+
+decryptMT19937 :: Word16 -> BS.ByteString -> BS.ByteString
+decryptMT19937 = encryptMT19937
+
+ciphertext :: BS.ByteString
+ciphertext = encryptMT19937 50000 $ ST.runST $ do
+ g <- MWC.create
+ n <- MWC.uniformR (1, 10) g
+ bs <- fmap BS.pack $ replicateM n (MWC.uniformR (32, 126) g)
+ pure (bs <> BS.replicate 14 65)
+
+mtCipherAttack :: BS.ByteString -> Word16
+mtCipherAttack cip = loop 0 where
+ l = BS.length cip
+ t = BS.replicate 14 65
+ loop j
+ | j > (maxBound :: Word16) = error "impossible seed"
+ | otherwise =
+ let g = MT.seed (fromIntegral j)
+ bs = keystream l g
+ pt = BS.drop (l - 14) (bs `CU.fixedXor` cip)
+ in if pt == t
+ then j
+ else loop (succ j)
+
+pwntToken :: IO T.Text
+pwntToken = do
+ s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
+ let g = MT.seed s
+ pure $ B64.encodeBase64 (keystream 16 g)
+
+notPwntToken :: IO T.Text
+notPwntToken = do
+ g <- MWC.createSystemRandom
+ bs <- fmap BS.pack $ replicateM 16 (MWC.uniformR (32, 126) g)
+ pure $ B64.encodeBase64 bs
+
+isPwnt :: T.Text -> IO Bool
+isPwnt token = do
+ s <- fmap (fromIntegral . TS.systemSeconds) TS.getSystemTime
+ let g = MT.seed s
+ ks = keystream 16 g
+ pure $ token == B64.encodeBase64 ks
diff --git a/lib/Cryptopals/Stream/RNG/MT19937.hs b/lib/Cryptopals/Stream/RNG/MT19937.hs
@@ -2,10 +2,9 @@ module Cryptopals.Stream.RNG.MT19937 (
Gen
, seed
, extract
- , bytes
+ , tap
- , temper
- , untemper
+ , clone
) where
import qualified Control.Monad.ST as ST
@@ -48,8 +47,8 @@ data Gen = Gen !Word32 !(VU.Vector Word32)
instance Show Gen where
show Gen {} = "<MT19937.Gen>"
-bytes :: Int -> Gen -> ([Word32], Gen)
-bytes = loop mempty where
+tap :: Int -> Gen -> ([Word32], Gen)
+tap = loop mempty where
loop !acc j gen
| j == 0 = (reverse acc, gen)
| otherwise =
