cryptopals

commit e05cd6e0f14a480fe3795bff9327526c678f88c6
parent d5a38f561b7ed8fd812e6bf7675d826a781f5183
Author: Jared Tobin <jared@jtobin.io>
Date:   Sat, 26 Aug 2023 23:58:51 -0230

Add 6.46.

Diffstat:
M
docs/s6.md
 | 
33
+++++++++++++++++++++++++++++++++
M
lib/Cryptopals/RSA/Attacks.hs
 | 
26
++++++++++++++++++++++++++

2 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/docs/s6.md b/docs/s6.md
@@ -261,3 +261,36 @@ parameters in which g = p + 1:
 
 Bad group!
 
+#### 6.46
+
+This one is super fun, as advertised, and another good illustration of
+how the slightest information leak can compromise an otherwise secure
+cryptographic scheme.
+
+Cryptopals.RSA.Attacks.parityOracle implements the oracle, and
+parityAttack the loop:
+
+    parityOracle :: BS.ByteString -> Bool
+    parityOracle cip =
+      let msg = decrypt (sec consistentKey) cip
+      in  B.testBit (roll msg) 0
+
+    parityAttack :: Key -> BS.ByteString -> IO BS.ByteString
+    parityAttack (Pub e n) cip = loop 0 n (roll cip) where
+      loop i j c
+        | j == i || j - i == 1 = pure (unroll j)
+        | otherwise = do
+            B8.putStrLn (unroll j)
+            let d = (c * DH.modexp 2 e n) `mod` n
+            if   parityOracle (unroll d)
+            then loop (i + (j - i) `quot` 2) j d
+            else loop i (j - (j - i) `quot` 2) d
+
+For 'mystery' our base64-encoded input, we get (via our "Hollywood
+decryption"):
+
+    > let cip = encrypt (pub consistentKey) (B64.decodeBase64Lenient mystery)
+    > parityAttack (pub consistentKey) cip
+    [..]
+    "That's why I found you don't play around with the Funky Cold Medin\\"
+
diff --git a/lib/Cryptopals/RSA/Attacks.hs b/lib/Cryptopals/RSA/Attacks.hs
@@ -10,6 +10,7 @@ import Control.Monad.Trans.State
 import qualified Cryptopals.DH as DH
 import Cryptopals.RSA
 import qualified Cryptopals.Digest.Pure.SHA as CS
+import qualified Data.Bits as B
 import qualified Data.ByteString as BS
 import qualified Data.ByteString.Base16 as B16
 import qualified Data.ByteString.Char8 as B8
@@ -127,3 +128,28 @@ forge mod msg =
   let f = fencode mod msg
   in  unroll $ R.integerCubeRoot (roll f) + 1
 
+-- parity attack
+
+consistentKey :: Keypair
+consistentKey = Keypair {
+    sec = Sec 17123352828014333155624438024036760971684155055395178750326166116221921534834757334258805831433671108747515574930784033716009753162288853697798226497143603784063672293784689339725292980717759302559416192505022202607060043180747993307152813641965271101487768850534996446308519974161336757521350033549104638323502861457159133823648406287066941450810841565848911430015280485845523895713183178201477186740322834886881520321163855222966200390877773389398001466822114489027189069065611644814402176315409188376507981912063223328698296264072987777394439869807029983108333829414790214696124608366420616926584028341835718008171 25685029242021499733436657036055141457526232583092768125489249174332882302252136001388208747150506663121273362396176050574014629743433280546697339745715405676095508440677034009587939471076638953839124288757533303910590064771121989960729220462947906652231653275802494669462779961242005136282025050323656957485575104768964364403120315473688233575506565199853941740698324759332741496556795318816219056943528386602087313223192513906581768759460447708758904161995531418020160091893731652698334419244087283089646693366368274960752450233540634283787034263316102286260474903106332924146000298152373432597583736507887518612367
+  , pub = Pub 3 25685029242021499733436657036055141457526232583092768125489249174332882302252136001388208747150506663121273362396176050574014629743433280546697339745715405676095508440677034009587939471076638953839124288757533303910590064771121989960729220462947906652231653275802494669462779961242005136282025050323656957485575104768964364403120315473688233575506565199853941740698324759332741496556795318816219056943528386602087313223192513906581768759460447708758904161995531418020160091893731652698334419244087283089646693366368274960752450233540634283787034263316102286260474903106332924146000298152373432597583736507887518612367
+  }
+
+-- true if odd
+parityOracle :: BS.ByteString -> Bool
+parityOracle cip =
+  let msg = decrypt (sec consistentKey) cip
+  in  B.testBit (roll msg) 0
+
+parityAttack :: Key -> BS.ByteString -> IO BS.ByteString
+parityAttack (Pub e n) cip = loop 0 n (roll cip) where
+  loop i j c
+    | j == i || j - i == 1 = pure (unroll j)
+    | otherwise = do
+        B8.putStrLn (unroll j)
+        let d = (c * DH.modexp 2 e n) `mod` n
+        if   parityOracle (unroll d)
+        then loop (i + (j - i) `quot` 2) j d
+        else loop i (j - (j - i) `quot` 2) d
+