commit aa6ded6c8e43f148549baa8565a970b165767854
parent 75e926d4f7badeeb7a0bcd6924721ca4770aba78
Author: Jared Tobin <jared@jtobin.io>
Date: Fri, 11 Aug 2023 23:46:12 -0230
Add 4.32.
Diffstat:
6 files changed, 142 insertions(+), 16 deletions(-)
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -41,6 +41,7 @@ library
, bytestring
, containers
, cryptonite
+ , HTTP
, mwc-random
, primitive
, text
diff --git a/docs/s4.md b/docs/s4.md
@@ -345,7 +345,7 @@ hammering the server with different MACs until it reports verification.
So, boot up the server via 'node index.js' and elsewhere do:
- $ .etc/crackhmac.sh "secrets.csv"
+ $ ./crackhmac.sh "secrets.csv"
present MAC guess: 0000000000000000000000000000000000000000
working on next byte (hexstring index 0)..
found byte b0
@@ -364,7 +364,7 @@ the loop in case the next byte can't be found due to timing weirdness.
Append as arguments the index we were working on, the time in seconds
the last comparison took, and the key we've extracted thus far, e.g.:
- $ ./etc/crackhmac.sh "secrets.csv" 20 "0.57" "b094e8b74021e638ca4a"
+ $ ./crackhmac.sh "secrets.csv" 20 "0.57" "b094e8b74021e638ca4a"
I probably shouldn't have chosen to do this with the shell, in
hindsight, and I can immediately think of a better way to handle the
@@ -378,10 +378,59 @@ secret MAC:
And we can check our result manually to see HTTP status code 200 (the
'safe' query parameter determines whether we do a sane comparison or
-this insane bytewise sleep comparison):
+this insane bytewise sleep thingy):
+ $ file="secrets.csv"
$ hmac="b094e8b74021e638ca4a65a9ac466cc7fde35c03"
$ curl -o /dev/null --silent -Iw "%{http_code}\n" \
- "localhost:3000/hmac?safe=false&file=secrets.csv&signature=$hmac"
+ "localhost:3000/hmac?safe=false&file=$file&signature=$hmac"
200
+#### 4.32
+
+Here we do the same thing as in the last challenge, but now it's harder.
+
+> I probably shouldn't have chosen to do this with the shell, in
+> hindsight, and I can immediately think of a better way to handle the
+> timing variation.
+
+This is where we atone for our previous hacky bash scripts and write
+something a little more l33t. In this case we'll loop over bytes a
+few times each, collect timings, and then choose byte values on a
+statistical basis.
+
+Cryptopals.MAC.Attacks implements a few functions for poking the server,
+gathering timing samples, and choosing byte values. The thing that
+required the most fiddling was selecting the number of samples to take
+for each byte. A size of three didn't cut it, five often but not always
+cut it, and ten seemed to usually cut it, all using a boring average to
+aggregate the samples. Then I reckoned I could try taking less samples,
+but compare a more robust statistic for central tendency -- i.e., the
+median -- and that indeed worked really well. I converged on using seven
+samples, so that the median could be calculated by merely plucking out
+the middle sorted element. As a rule, the median is awesome.
+
+With that all in place, let's crack us a HMAC for the provided "file."
+We get periodic updates as more bytes are found:
+
+ > mac <- crackHmac "secrets.csv"
+ current guess: "34"
+ current guess: "34ad"
+ current guess: "34ade1"
+ current guess: "34ade1f0"
+ [..]
+
+when all is said and done, we recover our MAC:
+
+ > B16.encodeBase16 mac
+ 34ade1f0a9c49af9bea5dea3f949b4b07582ba0d
+
+and can verify it validates properly for our "file":
+
+ $ file="secrets.csv"
+ $ hmac="34ade1f0a9c49af9bea5dea3f949b4b07582ba0d"
+ $ curl -o /dev/null --silent -Iw "%{http_code}\n" \
+ "localhost:3000/hmac?safe=true&file=$file&signature=$hmac"
+ 200
+
+A HTTP 200 status code, as expected.
diff --git a/etc/crackhmac.sh b/etc/crackhmac.sh
@@ -1,9 +1,11 @@
#!/usr/bin/env bash
fil=$1
-lidx=$2
-llas=$3
-lgot=$4
+
+# use these if one needs to resume a broken loop
+lidx=$2 # byte idx to start at
+llas=$3 # time the last comparison took
+lgot=$4 # MAC we've guessed thus far
if [[ -z "$fil" ]]; then
echo "no file specified. bailing out.."
@@ -12,11 +14,10 @@ fi
if [[ -z "$lidx" ]]; then
lidx=0
- lgot=""
llas=0.049
+ lgot=""
fi
-# resume broken loop
sup=$((39 - $lidx))
sig="$lgot""$(printf '0%.0s' $(seq 0 $sup))"
@@ -54,9 +55,8 @@ for j in $(seq $lidx 2 38); do
dif=$(echo "$tim - $las" | bc -l)
if (($try == 500)); then
- lon=$(echo "$dif > 0.05" | bc -l) # XX need more reliable condition
+ lon=$(echo "$dif > 0.05" | bc -l)
if (( $lon == 1 )); then
- echo "dif: $dif"
got="$got""$byt"
sig="$got""$etc"
las=$tim
diff --git a/etc/hmac/hmac.js b/etc/hmac/hmac.js
@@ -50,7 +50,7 @@ const hmac_sha1 = (k, m) => {
const verify_hmac_sha1 = (key, msg, mac) =>
hmac_sha1(key, msg) == mac
-async function insecure_compare(key, msg, mac) {
+async function insecure_compare(key, msg, mac, del) {
const bcal = Buffer.from(hmac_sha1(key, msg), 'hex')
const bmac = Buffer.from(mac, 'hex')
@@ -60,7 +60,7 @@ async function insecure_compare(key, msg, mac) {
if (bcal[idx] != bmac[idx]) {
return false
}
- await new Promise(r => setTimeout(r, 50))
+ await new Promise(r => setTimeout(r, del))
}
return true
diff --git a/etc/hmac/index.js b/etc/hmac/index.js
@@ -13,15 +13,17 @@ app.get('/', (req, res) => {
app.get('/hmac', async (req, res) => {
const saf = req.query.safe
+ const del = req.query.delay
const fil = req.query.file
const sig = req.query.signature
const msg = Buffer.from(fil).toString('hex')
const safe = saf == "true"
+ const wat = parseInt(del, 10)
const valid = safe
? hmac.verify_hmac_sha1(sec, msg, sig)
- : await hmac.insecure_compare(sec, msg, sig)
+ : await hmac.insecure_compare(sec, msg, sig, wat)
if (valid) {
res.status(200).send({ 'HTTP': 200 })
diff --git a/lib/Cryptopals/MAC/Attacks.hs b/lib/Cryptopals/MAC/Attacks.hs
@@ -3,16 +3,24 @@
module Cryptopals.MAC.Attacks where
import qualified Control.Monad.Trans.Reader as R
-import qualified Data.ByteString.Lazy as BSL
-import qualified Data.ByteString.Lazy.Char8 as BL8
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.Base16 as B16
+import qualified Data.ByteString.Char8 as B8
+import qualified Data.ByteString.Lazy as BSL
+import qualified Data.ByteString.Lazy.Char8 as BL8
+import qualified Data.IntMap.Strict as IMS
+import qualified Data.List as L
+import qualified Data.Text as T
+import qualified Data.Time as TI
import qualified Cryptopals.MAC as CM
import qualified Cryptopals.Digest.Pure.MD4 as M
import qualified Cryptopals.Digest.Pure.SHA as S
import GHC.Word (Word8, Word32, Word64)
+import qualified Network.HTTP as H
+import Numeric (showHex)
import qualified System.Random.MWC as MWC
data SHA1Registers = SHA1Registers !Word32 !Word32 !Word32 !Word32 !Word32
@@ -157,3 +165,69 @@ leamd4 input mac addl = loop 0 where
k <- R.ask
pure $ CM.verifymd4mac k mac msg
+-- timing attack on HMAC-SHA1
+
+hmacValidates :: BS.ByteString -> BS.ByteString -> IO Bool
+hmacValidates fil sig = do
+ let f = B8.unpack fil
+ s = T.unpack . B16.encodeBase16 $ sig
+ res <- H.simpleHTTP . H.getRequest $
+ "http://localhost:3000/hmac?safe=false&delay=5&file=" <> f <> "&" <>
+ "signature=" <> s
+ cod <- H.getResponseCode res
+ pure $ cod == (2, 0, 0)
+
+collect
+ :: BS.ByteString -- message
+ -> Int -- number of samples
+ -> BS.ByteString -- got so far
+ -> BS.ByteString -- remaining
+ -> IO (IMS.IntMap [TI.NominalDiffTime])
+collect !fil sam pre etc = loop mempty 0 0 where
+ loop !acc cyc b
+ | cyc == sam = pure acc
+ | otherwise = do
+ let !can = pre <> BS.cons b etc
+ org <- TI.getCurrentTime
+ cod <- hmacValidates fil can
+ end <- TI.getCurrentTime
+ let dif = TI.diffUTCTime end org
+ nac = IMS.alter (add dif) (fromIntegral b) acc
+ sik | b == 255 = succ cyc
+ | otherwise = cyc
+ loop nac sik (b + 1)
+
+ add d ma = case ma of
+ Nothing -> Just (d : [])
+ Just a -> Just (d : a)
+
+crackByte
+ :: BS.ByteString
+ -> BS.ByteString
+ -> BS.ByteString
+ -> IO Word8
+crackByte fil pre etc = do
+ samples <- collect fil 7 pre etc
+ let ver = fmap med samples
+ chu = IMS.foldlWithKey'
+ (\acc k v -> if v > snd acc then (k, v) else acc)
+ (256, 0)
+ ver
+ pure $ fromIntegral (fst chu)
+
+crackHmac :: BS.ByteString -> IO BS.ByteString
+crackHmac fil = loop mempty (BS.replicate 20 0) where
+ loop !acc sig = case BS.uncons sig of
+ Nothing -> pure acc
+ Just (_, t) -> do
+ byt <- crackByte fil acc t
+ let nex = BS.snoc acc byt
+ putStrLn $ "current guess: " <> show (B16.encodeBase16 nex)
+ loop nex t
+
+avg :: (Foldable f, Fractional a) => f a -> a
+avg l = sum l / fromIntegral (length l)
+
+-- -- hacky median for container with known length 7
+med :: Ord a => [a] -> a
+med l = L.sort l !! 3
