commit 68413610696fcf046bb1ca04491c6d130f8fe7ce
parent 3e69e92f046e2ed9dcdc18a2e91de7a605f3f63a
Author: Jared Tobin <jared@jtobin.io>
Date: Tue, 15 Aug 2023 22:32:08 -0230
Misc fixes.
Diffstat:
3 files changed, 59 insertions(+), 57 deletions(-)
diff --git a/docs/s5.md b/docs/s5.md
@@ -72,11 +72,11 @@ the initial illustration in the next challenge.
Opening two instances of GHCi, we can run e.g.:
- > bob "3000" dh
+ > bob "3000" dh
in one, and:
- > alice "3000" dh
+ > alice "3000" dh
in the other and watch the logs for fun. Here I'll interleave the
relevant parts of the logs for readability:
@@ -169,8 +169,8 @@ b mod p = 1, as will the shared key from Alice's perspective (since 1 ^
a mod p = 1). Mallory thus needs to forward a 1 as Alice's public key in
order for Bob to agree on the shared key.
-For g = p, Bob computes B = p ^ b mod p = 0, so Mallory can forward a
-p as Alice's public key in order for them to agree on the shared key.
+For g = p, Bob computes B = p ^ b mod p = 0, so Mallory can forward p as
+Alice's public key in order for them to agree on the shared key.
Finally, the case of g = p - 1. Note that for any p > 1 and any even b, we
have (for appropriate coefficients a, c, etc.):
@@ -193,24 +193,30 @@ So Bob's public key will be either 1 or p - 1 depending on whether his
secret key is even or odd. Alice will thus compute:
s = B ^ a mod p
- = 1 } b even or a even
- p - 1 } b odd and a odd.
+ = 1 } b even or a even (p = 3/4)
+ p - 1 } b odd and a odd. (p = 1/4).
-If Mallory thus forwards A = 1 to Bob, we have:
+If Mallory then forwards A = g = p - 1 to Bob, we have:
t = A ^ b mod p
- = 1.
+ = 1 } b even (p = 1/2)
+ = p - 1 } b odd (p = 1/2).
+
+This all yields the following table:
-So, Alice and Bob will agree on the key 1 (i.e., the attack succeeds)
-whenever 'b' is even or 'a' is even, an event that occurs with
-probability 1/2 + 1/2 - 1/4 = 3/4.
+ a
+ even odd
+ even s = 1, t = 1 s = 1, t = 1
+ b
+ odd s = 1, t = p - 1 s = p - 1, t = p - 1
-(Mallory could ensure the attack works every time by forwarding 1's for
-*both* public keys, but that seems against the spirit of the question.)
+such that Alice and Bob will agree on the shared key with probability
+3/4. Mallory also has to choose which shared key value he uses; if he
+uses 1, then the attack succeeds with probability 1/2, and if he uses p
+- 1, then it succeeds with probability 1/4.
Here are the interleaved logs of a successful attack. Start mallory with
-e.g. the `dhngmitm 1` or `dhngmitm p` protocol to perform this attack
-with g = 1 or g = p, or use `dhngmitm'` for the g = p - 1 case:
+e.g. the `dhngmitm 1`, `dhngmitm p`, or `dhngmitm (p - 1)` protocol:
(cryptopals) bob: listening..
(cryptopals) mallory: LiSteNIng..
diff --git a/lib/Cryptopals/DH/Core.hs b/lib/Cryptopals/DH/Core.hs
@@ -10,6 +10,7 @@ module Cryptopals.DH.Core (
, modexp
, genpair
, derivekey
+ , encodekey
) where
import Control.Monad.Primitive
@@ -61,5 +62,14 @@ genpair (Group p g) gen = do
derivekey :: Group -> Keys -> Natural -> BS.ByteString
derivekey (Group p _) Keys {..} pk =
let nat = modexp pk sec p
- in BS.take 16 . BL.toStrict . CS.bytestringDigest $ CS.sha1 (DB.encode nat)
+ in encodekey nat
+
+encodekey :: Natural -> BS.ByteString
+encodekey =
+ BS.take 16
+ . BL.toStrict
+ . CS.bytestringDigest
+ . CS.sha1
+ . DB.encode
+
diff --git a/lib/Cryptopals/DH/Session.hs b/lib/Cryptopals/DH/Session.hs
@@ -18,7 +18,6 @@ module Cryptopals.DH.Session (
, dhmitm
, dhngmitm
- , dhngmitm'
, session
, dance
@@ -153,10 +152,6 @@ dhng = seval ngeval
dhngmitm :: Natural -> Protocol (StateT Sesh IO) (Maybe Command) (Maybe Command)
dhngmitm = seval . malgeval
--- mitm negotiated-group dh evaluation, g = p - 1
-dhngmitm' :: Protocol (StateT Sesh IO) (Maybe Command) (Maybe Command)
-dhngmitm' = seval malgeval'
-
-- diffie-hellman protocol eval
dheval
:: Command
@@ -225,18 +220,26 @@ mitmeval = \case
SendMessage cip -> do
slog $ "rECeIveD CiPHeRTexT " <> B64.encodeBase64 cip
sesh@Sesh {..} <- S.get
- msg <- decrypt cip
- slog $ "DEcRyptEd cIPheRTeXt: \"" <> TE.decodeLatin1 msg <> "\""
+ mmsg <- decryptLenient cip
+ case mmsg of
+ Nothing ->
+ slog "couLdN'T DeCRyPt CiPHertExT"
+ Just msg ->
+ slog $ "DEcRyptEd cIPheRTeXt: \"" <> TE.decodeLatin1 msg <> "\""
slog "reLayINg cIpheRtExt"
pure $ Just (SendMessage cip)
SendTerminal cip -> do
slog $ "reCeiVeD CipHeRtExt " <> B64.encodeBase64 cip
sesh@Sesh {..} <- S.get
- msg <- decrypt cip
- slog $ "DeCrYpteD cIphErteXt: \"" <> TE.decodeLatin1 msg <> "\""
+ mmsg <- decryptLenient cip
+ case mmsg of
+ Nothing ->
+ slog "couLdN'T DeCRyPt CiPHertExT"
+ Just msg ->
+ slog $ "DeCrYpteD cIphErteXt: \"" <> TE.decodeLatin1 msg <> "\""
slog "ReLaYINg CiPHeRTexT"
- pure $ Just (SendTerminal cip)
+ pure (Just (SendTerminal cip))
cmd -> do
slog "RelAyInG coMmaNd"
@@ -309,7 +312,6 @@ malgeval malg = \case
slog "nOt eXPecTinG gRoUp and PublIc KeY"
pure Nothing
- -- only want to send bogus key on the first time
SendPublic pk -> do
slog $ "REceIvED pUBlic keY " <> renderkey pk
slog $ "SeNDing BoGuS kEy " <> renderkey malg
@@ -317,36 +319,6 @@ malgeval malg = \case
cmd -> mitmeval cmd
--- negotiated-group mitm protocol eval, g = p - 1
-malgeval'
- :: Command
- -> StateT Sesh IO (Maybe Command)
-malgeval' = \case
- AckGroup -> do
- slog "rECeiVed aCK"
- slog "ReLaYINg ACk"
- pure (Just AckGroup)
-
- SendParams grp pk -> do
- slog "nOt eXPecTinG gRoUp and PublIc KeY"
- pure Nothing
-
- SendPublic pk -> do
- slog $ "REceIvED pUBlic keY " <> renderkey pk
- sesh@Sesh {..} <- S.get
- case dhKeys of
- Nothing -> do
- S.put sesh {
- dhKeys = Just (Keys 1 1)
- }
- slog $ "SeNDing BoGuS kEy " <> renderkey 1
- pure $ Just (SendPublic 1)
- Just Keys {..} -> do
- slog $ "ReLAyINg pUbliC KeY " <> renderkey pk
- pure $ Just (SendPublic pk)
-
- cmd -> malgeval (p - 1) cmd
-
genGroup :: Natural -> Natural -> StateT Sesh IO Group
genGroup p g = do
sesh <- S.get
@@ -416,6 +388,20 @@ decrypt cip = do
liftIO SE.exitFailure
Just msg -> pure msg
+decryptLenient :: BS.ByteString -> StateT Sesh IO (Maybe BS.ByteString)
+decryptLenient cip = do
+ sesh@Sesh {..} <- S.get
+ case dhKey of
+ Nothing -> do
+ slog "missing shared key"
+ liftIO SE.exitFailure
+ Just k -> do
+ case CU.unpkcs7 (AES.decryptCbcAES128 k cip) of
+ Nothing -> do
+ slog "couldn't decrypt ciphertext"
+ pure Nothing
+ Just msg -> pure (Just msg)
+
renderkey :: Natural -> T.Text
renderkey =
B16.encodeBase16
