commit 75e926d4f7badeeb7a0bcd6924721ca4770aba78
parent 5d9609ffc97c122cc23fc80cae24ce9de5f5fb89
Author: Jared Tobin <jared@jtobin.io>
Date: Fri, 11 Aug 2023 19:33:37 -0230
Add 4.31.
Diffstat:
6 files changed, 294 insertions(+), 1 deletion(-)
diff --git a/.gitignore b/.gitignore
@@ -1,4 +1,6 @@
.cabal-sandbox
cabal.sandbox.config
dist-newstyle
+node_modules
+package-lock.json
*swp
diff --git a/docs/s4.md b/docs/s4.md
@@ -295,7 +295,8 @@ access to a verifying oracle:
k <- R.ask
pure $ CM.verifymd4mac k mac msg
-and let's give it a whirl:
+Again, 'md4' is a modified implementation allowing us to resume from an
+arbitrary state and use devious padding. Let's give it a whirl:
> k <- key
> let mac = CM.md4mac k raw
@@ -305,3 +306,82 @@ and let's give it a whirl:
> CM.verifymd4mac k forged evil
True
+#### 4.31
+
+For this exercise we'll switch it up and write some JavaScript. etc/hmac
+contains some JS HMAC utilities (in hmac.js) and a tiny express.js app
+(in index.js) that will verify messages and MACs it receives via query
+parameters.
+
+HMAC (Hash-based MAC) is not vulnerable to length-extension attacks
+due the presence of multiple (at least two, and potentially more)
+enveloping calls to the hash function when creating the MAC. Ferguson et
+al. recommended a similar approach in *Cryptography Engineering* when
+dealing with Merkle-Damgård hash functions, in which, for hash function
+h and message m, instead of using h(m) one uses h(h(m) || m). The HMAC
+construction, which goes:
+
+ hmac(k, m) = h((k' + 0x5c) || h((k' + 0x36) || m))
+
+for:
+
+ k' = { h(k) for k > block size
+ { k otherwise
+
+where + is single-byte XOR and || is concatenation, is more or less the
+same idea, except.. moreso.
+
+Anyway. The idea here is that we have a webserver that does
+byte-at-a-time comparison with the supplied MAC, sleeping a little
+per byte verified and bailing out early if equality isn't found. So,
+we start guessing MACs by working on one byte at a time and checking
+whether the server takes appreciably longer to reject what we supply.
+If it does, then we probably know that we've matched the value for that
+byte, and so we move onto the next one, repeating the same procedure.
+
+The server does what is expected of us. etc/crackhmac.sh is a
+particularly-hacky bash script that calls curl in the requisite loop,
+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"
+ present MAC guess: 0000000000000000000000000000000000000000
+ working on next byte (hexstring index 0)..
+ found byte b0
+ present MAC guess: b000000000000000000000000000000000000000
+ working on next byte (hexstring index 2)..
+ found byte 94
+ present MAC guess: b094000000000000000000000000000000000000
+ working on next byte (hexstring index 4)..
+ found byte e8
+ present MAC guess: b094e80000000000000000000000000000000000
+ working on next byte (hexstring index 6)..
+ [..]
+
+N.b., the script is sort of janky, so there are facilities for resuming
+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"
+
+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. But in any case, after a while we should recover the
+secret MAC:
+
+ working on next byte (hexstring index 38)..
+ succeeded
+ file: secrets.csv
+ hmac: b094e8b74021e638ca4a65a9ac466cc7fde35c03
+
+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):
+
+ $ hmac="b094e8b74021e638ca4a65a9ac466cc7fde35c03"
+ $ curl -o /dev/null --silent -Iw "%{http_code}\n" \
+ "localhost:3000/hmac?safe=false&file=secrets.csv&signature=$hmac"
+ 200
+
diff --git a/etc/crackhmac.sh b/etc/crackhmac.sh
@@ -0,0 +1,81 @@
+#!/usr/bin/env bash
+
+fil=$1
+lidx=$2
+llas=$3
+lgot=$4
+
+if [[ -z "$fil" ]]; then
+ echo "no file specified. bailing out.."
+ exit 1
+fi
+
+if [[ -z "$lidx" ]]; then
+ lidx=0
+ lgot=""
+ llas=0.049
+fi
+
+# resume broken loop
+sup=$((39 - $lidx))
+sig="$lgot""$(printf '0%.0s' $(seq 0 $sup))"
+
+hos="localhost:3000"
+got="$lgot"
+
+attempt() {
+ local res=$(curl -o /dev/null --silent -Iw "%{http_code}\n" "$1")
+ echo "$res"
+}
+
+weld() {
+ echo "$hos""/hmac?safe=false&file=""$fil""&signature=""$1"
+}
+
+las="$llas"
+
+for j in $(seq $lidx 2 38); do
+ etc="${sig:$((j+2))}"
+
+ echo "present MAC guess: $sig"
+ echo "working on next byte (hexstring index $j).."
+
+ for b in {0..255}; do
+ byt=$(printf "%02x" $b)
+
+ can="$got""$byt""$etc"
+ url=$(weld $can)
+
+ org=$(date +%s.%N)
+ try=$(attempt $url)
+ end=$(date +%s.%N)
+
+ tim=$(echo "$end - $org" | bc -l)
+ dif=$(echo "$tim - $las" | bc -l)
+
+ if (($try == 500)); then
+ lon=$(echo "$dif > 0.05" | bc -l) # XX need more reliable condition
+ if (( $lon == 1 )); then
+ echo "dif: $dif"
+ got="$got""$byt"
+ sig="$got""$etc"
+ las=$tim
+ echo "found byte $byt"
+ break
+ elif (($b == 255)); then
+ echo "couldn't find byte value. bailing out.."
+ echo "got: $got"
+ echo "tim: $tim"
+ exit 1
+ fi
+ elif (($try == 200)); then
+ echo "succeeded"
+ echo "file: $fil"
+ echo "hmac: $sig"
+ exit 0
+ else
+ echo "something really weird happened.."
+ fi
+ done
+done
+
diff --git a/etc/hmac/hmac.js b/etc/hmac/hmac.js
@@ -0,0 +1,74 @@
+const sha1 = require('js-sha1')
+const crypto = require('crypto')
+
+// hmac utils /////////////////////////////////////////////////////////////////
+
+const buf2hex = buf =>
+ Buffer.from(buf).toString('hex')
+
+const hex2buf = hex =>
+ Buffer.from(hex, 'hex')
+
+const bufs2buf = (a, b) =>
+ Buffer.concat([a, b])
+
+// returns hex
+const gen_key = () => {
+ const arr = crypto.getRandomValues(new Uint8Array(16))
+ return buf2hex(arr)
+}
+
+// expects hex, returns hex
+const pad = (hex, siz) =>
+ hex.padEnd(siz, '0')
+
+// expects buffer, returns hex
+const compute_sized_key = (key, hash, siz) =>
+ key.length > siz ?
+ hash(key) :
+ key.length < siz ?
+ pad(buf2hex(key), siz * 2) : // bytes, not length
+ buf2hex(key)
+
+// expects hex, returns hex
+const hmac_sha1 = (k, m) => {
+ const bk = hex2buf(k)
+ const bm = hex2buf(m)
+
+ const sized_key = hex2buf(compute_sized_key(bk, sha1, 64))
+
+ const okey_pad = sized_key.map(x => x ^ 0x5c)
+ const ikey_pad = sized_key.map(x => x ^ 0x36)
+
+ const inner = bufs2buf(ikey_pad, bm)
+ const hinner = hex2buf(sha1(inner))
+ const outer = bufs2buf(okey_pad, hinner)
+
+ return sha1(outer)
+}
+
+const verify_hmac_sha1 = (key, msg, mac) =>
+ hmac_sha1(key, msg) == mac
+
+async function insecure_compare(key, msg, mac) {
+ const bcal = Buffer.from(hmac_sha1(key, msg), 'hex')
+ const bmac = Buffer.from(mac, 'hex')
+
+ const idxs = Array(bcal.length).fill().map((el, idx) => idx)
+
+ for await (const idx of idxs) {
+ if (bcal[idx] != bmac[idx]) {
+ return false
+ }
+ await new Promise(r => setTimeout(r, 50))
+ }
+
+ return true
+}
+
+module.exports = {
+ gen_key,
+ hmac_sha1,
+ verify_hmac_sha1,
+ insecure_compare
+}
diff --git a/etc/hmac/index.js b/etc/hmac/index.js
@@ -0,0 +1,44 @@
+const express = require('express')
+const hmac = require('./hmac')
+
+// web app ////////////////////////////////////////////////////////////////////
+
+const sec = hmac.gen_key()
+
+const app = express()
+
+app.get('/', (req, res) => {
+ res.send('waiting to do something cool..')
+})
+
+app.get('/hmac', async (req, res) => {
+ const saf = req.query.safe
+ const fil = req.query.file
+ const sig = req.query.signature
+
+ const msg = Buffer.from(fil).toString('hex')
+ const safe = saf == "true"
+
+ const valid = safe
+ ? hmac.verify_hmac_sha1(sec, msg, sig)
+ : await hmac.insecure_compare(sec, msg, sig)
+
+ if (valid) {
+ res.status(200).send({ 'HTTP': 200 })
+ } else {
+ res.status(500).send({ 'HTTP': 500 })
+ }
+
+})
+
+const port = 3000
+
+app.listen(port, () => {
+ console.log(`server listening on ${port}`)
+})
+
+console.log('server generated the following key:')
+console.log(`${sec}`)
+console.log('for dev convenience, hmac for \'secrets.csv\' is:')
+console.log(`${hmac.hmac_sha1(sec, Buffer.from('secrets.csv').toString('hex'))}`)
+
diff --git a/etc/hmac/package.json b/etc/hmac/package.json
@@ -0,0 +1,12 @@
+{
+ "name": "hmac",
+ "version": "0.1.0",
+ "description": "cryptopals challenge 4.30",
+ "main": "index.js",
+ "author": "jtobin",
+ "license": "MIT",
+ "dependencies": {
+ "express": "^4.18.2",
+ "js-sha1": "^0.6.0"
+ }
+}
