ångstromCTF 2019 | MAC Forgery - crypto-writeup-public

#angstromCTF2019

CBC-MAC is so overrated. This new scheme supports variable lengths and multiple tags per message.

nc 54.159.113.26 19002

import binascii
import socketserver

from cbc_mac import CBC_MAC
from secret import flag, key

welcome = b"""\
If you provide a message (besides this one) with
a valid message authentication code, I will give
you the flag."""

cbc_mac = CBC_MAC(key)


def handle(self):
    iv, t = cbc_mac.generate(welcome)
    self.write(welcome)
    self.write(b"MAC: %b" % binascii.hexlify(iv + t))

    m = binascii.unhexlify(self.query(b"Message: "))
    mac = binascii.unhexlify(self.query(b"MAC: "))
    assert len(mac) == 32
    iv = mac[:16]
    t = mac[16:]

    if m != welcome and cbc_mac.verify(m, iv, t):
        self.write(flag)


class RequestHandler(socketserver.BaseRequestHandler):

    handle = handle

    def read(self, until=b"\n"):
        out = b""
        while not out.endswith(until):
            out += self.request.recv(1)
        return out[: -len(until)]

    def query(self, string=b""):
        self.write(string, newline=False)
        return self.read()

    def write(self, string, newline=True):
        self.request.sendall(string)
        if newline:
            self.request.sendall(b"\n")


class Server(socketserver.ForkingTCPServer):

    allow_reuse_address = True

    def handle_error(self, request, client_address):
        pass


port = 3000
server = Server(("0.0.0.0", port), RequestHandler)
server.serve_forever()

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from Crypto.Util.strxor import strxor

split = lambda s, n: [s[i:i+n] for i in range(0, len(s), n)]

class CBC_MAC:

    BLOCK_SIZE = 16

    def __init__(self, key):
        self.key = key

    def next(self, t, m):
        return AES.new(self.key, AES.MODE_ECB).encrypt(strxor(t, m))

    def mac(self, m, iv):
        m = pad(m, self.BLOCK_SIZE)
        m = split(m, self.BLOCK_SIZE)
        m.insert(0, long_to_bytes(len(m), self.BLOCK_SIZE))
        t = iv
        for i in range(len(m)):
            t = self.next(t, m[i])
        return t

    def generate(self, m):
        iv = get_random_bytes(self.BLOCK_SIZE)
        return iv, self.mac(m, iv)

    def verify(self, m, iv, t):
        return self.mac(m, iv) == t

平文 $M$ と、それのMACハッシュ $C = MAC(M)$ が与えられるので、 $M \ne M'$ かつ $C = MAC(M')$ となるような $M'$ を求める問題。

ハッシュのとり方はこんな感じ

* $IV$ と $M_i$ を用意する。

$M_0 = len(M)$
各ブロックについて、前のブロックとxorをとってからAES_CBCで暗号化。最後のブロックをMACとする

要するにAESのCBCモードなんだけど先頭ブロックがちょっと特異って感じ。

ここで平文に新しいブロック $M_{n+1}$ を追加することを考える。プログラムと同じ変数を使うと、 $t_{n+1} = E(M_{n+1} \oplus t_n)$ ということになる。今 $t_n$ だけはわかっているので、 $M_{n+1} = M_0 \oplus t_n \oplus IV$ とすると、 $M_{n+1} \oplus t_n = M_0 \oplus IV$ となることがわかる。あとは $M_{n+i} = M_{i-1}$ という対応でN-1ブロック追加すれば、最終的に $t_{2n} = t_n$ になりそう。

唯一の問題点はブロックの総数が変わると $M_0$ が変わることだけど、ここは $IV$ を操作して回避できる。

一個目のメッセージにはPaddingがつくけど2個目のメッセージにパディングをつけちゃいけないことに気が付かなくて嵌った。

from ptrlib.pwn.sock import Socket
from binascii import hexlify
from cbc_mac import CBC_MAC, split, pad


def unpad(xs):
    return xs[: -xs[-1]]


welcome = pad(
    b"""\
If you provide a message (besides this one) with
a valid message authentication code, I will give
you the flag.""",
    16,
)
ms = split(welcome, 16)

sock = Socket("localhost", 3000)
_ = sock.recvuntil("MAC: ")
mac = sock.recvline().decode()
iv, t = int(mac[:32], 16), int(mac[32:], 16)

new_iv = (len(ms) * 2 + 1) ^ len(ms) ^ iv
ps = ms[:]
ps.insert(0, (len(ms) ^ t ^ iv).to_bytes(16, "big"))  # M0 ^ t ^ IV

message = hexlify(unpad(b"".join(ms + ps)))
mac = hexlify(new_iv.to_bytes(16, "big") + t.to_bytes(16, "big"))
sock.sendlineafter("Message: ", message)
sock.sendlineafter("MAC: ", mac)

print(sock.recvline())

actf{initialization_vectors_were_probably_a_bad_idea}