commit fea928f39845e649cc2a49df9b4936c82bf6c72d
parent 1d977eaa83faa35b61974be124c56ef2c10f6400
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 29 Jul 2023 00:40:24 -0230
Add 3.19, 3.20.
Diffstat:
4 files changed, 122 insertions(+), 0 deletions(-)
diff --git a/docs/s3.md b/docs/s3.md
@@ -77,6 +77,8 @@ padding oracle attack (for arbitrary ciphertexts):
#### 3.18
+(FIXME, add binaries for these.)
+
CTR mode is trivial; the only thing to get right is really the specified
counter format. `Cryptopals.AES.decryptCtrAES128` (or its synonym,
`encryptCtrAES128`) can be used to retrieve our desired plaintext:
@@ -85,4 +87,23 @@ counter format. `Cryptopals.AES.decryptCtrAES128` (or its synonym,
> decryptCtrAES128 0 "YELLOW SUBMARINE" cip
"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby "
+#### 3.19 (and 3.20)
+
+I used the same approach as was done in question 1.6, taking the
+first 16 bytes of each ciphertext and then transposing them such that
+each "block" has been single-byte XOR'd by something. Using a similar
+scoring routine (see `Cryptopals.Block.Attacks.rnBest`) and some manual
+fiddling, one can recover the keystream without much difficulty. Finding
+the first 16 bytes exposes enough of the plaintexts that the remaining
+bytes can be completed by hand, though I bailed out after I got the
+gist of it:
+
+ > let ks = BS.pack $ fmap (\(a, _, _) -> a) . rnBest) rnrotated
+ > -- the resulting keystream needed some manual patching, but
+ > -- results like "eighteeoth-centu" make it easy to do.
+ > take 4 $ fmap (CU.fixedXor ks) rnscrypted
+ ["I have met them ","Coming with vivi","From counter or ","Eighteenth-centu"]
+
+(It turns out this is the way one is supposed to solve 3.20 too. Whoops!)
+
diff --git a/lib/Cryptopals/Block/Attacks.hs b/lib/Cryptopals/Block/Attacks.hs
@@ -15,6 +15,8 @@ import qualified Data.ByteString.Base16 as B16
import qualified Data.ByteString.Base64 as B64
import qualified Data.HashMap.Strict as HMS
import qualified Data.List as L
+import qualified Data.Maybe as M
+import qualified Data.Set as S
import qualified Data.Text as T
import qualified Data.Text.Encoding as TE
import GHC.Word (Word8)
@@ -288,3 +290,72 @@ poAttackBlock tol tar = byte tol tar mempty mempty where
| poValidate (BS.snoc bs (b + 1) <> etc) -> True
| otherwise -> False
+-- CTR reused-nonce
+
+rninputs :: [BS.ByteString]
+rninputs = [
+ "SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ=="
+ , "Q29taW5nIHdpdGggdml2aWQgZmFjZXM="
+ , "RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ=="
+ , "RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4="
+ , "SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk"
+ , "T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA=="
+ , "T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ="
+ , "UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA=="
+ , "QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU="
+ , "T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl"
+ , "VG8gcGxlYXNlIGEgY29tcGFuaW9u"
+ , "QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA=="
+ , "QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk="
+ , "QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg=="
+ , "QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo="
+ , "QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4="
+ , "VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA=="
+ , "SW4gaWdub3JhbnQgZ29vZCB3aWxsLA=="
+ , "SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA=="
+ , "VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg=="
+ , "V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw=="
+ , "V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA=="
+ , "U2hlIHJvZGUgdG8gaGFycmllcnM/"
+ , "VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w="
+ , "QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4="
+ , "VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ="
+ , "V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs="
+ , "SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA=="
+ , "U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA=="
+ , "U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4="
+ , "VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA=="
+ , "QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu"
+ , "SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc="
+ , "VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs"
+ , "WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs="
+ , "SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0"
+ , "SW4gdGhlIGNhc3VhbCBjb21lZHk7"
+ , "SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw="
+ , "VHJhbnNmb3JtZWQgdXR0ZXJseTo="
+ , "QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4="
+ ]
+
+rncrypted :: [BS.ByteString]
+rncrypted = fmap (enc . B64.decodeBase64Lenient) rninputs where
+ enc = AES.encryptCtrAES128 0 "YELLOW SUBMARINE"
+
+rnscrypted :: [BS.ByteString]
+rnscrypted = fmap (BS.take 16) rncrypted
+
+rnrotated :: [BS.ByteString]
+rnrotated = CU.rotate 16 (BS.concat rnscrypted)
+
+-- FIXME replace Cryptopals.Util.best with this?
+rnBest :: BS.ByteString -> (Word8, Double, BS.ByteString)
+rnBest s = loop (0, 1 / 0, s) 0 where
+ loop acc@(_, asc, _) b
+ | b == 255 = acc
+ | otherwise =
+ let xo = CU.singleByteXor b s
+ in case CU.scoreAlt xo of
+ Nothing -> loop acc (succ b)
+ Just sc
+ | sc < asc -> loop (b, sc, xo) (succ b)
+ | otherwise -> loop acc (succ b)
+
diff --git a/lib/Cryptopals/Util.hs b/lib/Cryptopals/Util.hs
@@ -11,8 +11,10 @@ module Cryptopals.Util (
, CUB.rotate
, roundUpToMul
, CUS.score
+ , CUS.scoreAlt
, singleByteXor
, CUS.tally
+ , CUS.gtally
, unpkcs7
) where
diff --git a/lib/Cryptopals/Util/Similarity.hs b/lib/Cryptopals/Util/Similarity.hs
@@ -1,18 +1,29 @@
module Cryptopals.Util.Similarity (
score
+ , scoreAlt
, tally
+ , gtally
, often
+ , mse
+ , mseAlt
+ , english
+ , dist
) where
import qualified Data.ByteString as BS
+import qualified Data.Foldable as F
import Data.Function (on)
import qualified Data.IntMap.Strict as IMS
import qualified Data.List as L
+import qualified Data.Map.Strict as MS
-- | Distance of the encoding from expected English plaintext.
score :: BS.ByteString -> Double
score = mse english . dist
+scoreAlt :: BS.ByteString -> Maybe Double
+scoreAlt = mseAlt english . dist
+
mse :: IMS.IntMap Double -> IMS.IntMap Double -> Double
mse ref tar =
let res = IMS.foldlWithKey' alg mempty ref
@@ -23,6 +34,17 @@ mse ref tar =
Nothing -> acc
Just tal -> IMS.insert key ((tal - val) ^ 2) acc
+mseAlt :: IMS.IntMap Double -> IMS.IntMap Double -> Maybe Double
+mseAlt ref tar = case F.foldlM alg mempty (IMS.toList tar) of
+ Nothing -> Nothing
+ Just res -> pure $
+ let siz = IMS.size res
+ in IMS.foldl' (\acc val -> acc + val / fromIntegral siz) 0 res
+ where
+ alg acc (key, val) = case IMS.lookup key ref of
+ Nothing -> Nothing
+ Just tal -> pure (IMS.insert key ((tal - val) ^ 2) acc)
+
dist :: BS.ByteString -> IMS.IntMap Double
dist = normalize . tally
@@ -35,6 +57,12 @@ tally = BS.foldl' alg mempty where
| IMS.member byt acc = IMS.adjust succ byt acc
| otherwise = IMS.insert byt 1 acc
+gtally :: Ord a => [a] -> MS.Map a Int
+gtally = L.foldl' alg mempty where
+ alg acc val
+ | MS.member val acc = MS.adjust succ val acc
+ | otherwise = MS.insert val 1 acc
+
normalize :: IMS.IntMap Int -> IMS.IntMap Double
normalize m =
let siz = fromIntegral $ IMS.foldl' (+) 0 m
