# Boston Key Party 2016: HMAC_CRC

This was a challenge in last years Boston Key Party CTF, which we did not solve during the competition. While talking about a different challenge involving a CRC checksum today, this challenge came to my mind and now I was able to solve it.

We were given a python source code (see appendix), which implement the HMAC construction using a 64 bit CRC as hash function.

They also gave us the MAC $$h_1 = HMAC\_CRC(k, m_1)$$ of the string $$m_1 = \texttt{"zupe zecret"}$$. The task was to find a valid MAC $$h_2$$ for $$m_2 = \texttt{"BKPCTF"}$$ while the key $$k$$ was not given.

The MAC over a message $$m$$ with key $$k$$ is computed as follows ($$opad$$ and $$ipad$$ are known constants).

\begin{equation*} HMAC\_CRC(k, m) = CRC((k \oplus opad) \parallel CRC((k \oplus ipad) \parallel m)) \end{equation*}

The CRC function is defined with a constant $$c$$ and a polynomial $$p \in GF(2)[X]$$. It appends $$c$$ to the input interprets the result as a polynomial over the field $$GF(2)$$. The hash is this polynomial modulo $$p$$:

\begin{equation*} CRC(m) = m \cdot X^{64} + c \bmod p \end{equation*}

The following computations are done modulo $$p$$, that is in the quotient ring $$GF(2)[X] / (p)$$, which is a field since $$p$$ is irreducible. The complete calculation can be expressed as

\begin{equation*} HMAC\_CRC(k, m) = \Big( (k + opad) \cdot X^{64} + \big( ((k + ipad) \cdot X^{|m|} + m) \cdot X^{64} + c \big) \Big) \cdot X^{64} + c \end{equation*}

This can be expanded and reordered as

\begin{equation*} HMAC\_CRC(k, m) = k \cdot (X^{128 + |m|} + X^{128}) + ipad \cdot X^{128 + |m|} + (m + opad) \cdot X^{128} + c \cdot X^{64} + c \end{equation*}

and solved by $$k$$ to calculate the key:

\begin{equation*} k = \frac{ HMAC\_CRC(k, m) - ipad \cdot X^{128 + |m|} - (m + opad) \cdot X^{128} - c \cdot X^{64} - c } {(X^{128 + |m|} + X^{128})} \end{equation*}

With the recovered key we can compute the MAC on the second string flag: $$HMAC\_CRC(k, \texttt{"BKPCTF"}) = \mathrm{d2db2b8b9002841f}$$ and get the flag: BKPCTF{d2db2b8b9002841f}.

## Appendix

The Sage script to solve the challenge:

solve.sage

#!/usr/bin/env sage

def poly2num(p):
return Integer(''.join(str(b) for b in p.list()[::- 1]), 2)

def to_bits(length, N):
return [int(i) for i in bin(N)[2:].zfill(length)]

def str2bits(s):
return [b for i in s for b in to_bits(8, ord(i))]

PLAIN_1 = "zupe zecret"
PLAIN_2 = "BKPCTF"

R.<x> = GF(2)[]
p = R(((2**64) + 0xeff67c77d13835f7).bits())
Q = R.quotient(R.ideal(p))

i = Q(((0x36).bits() + [0, 0]) * 8)
o = Q(((0x5c).bits() + [0]) * 8)

def crc(msg):
return msg*x^64 + c

def hmac(key, msg, msg_len):
return crc((key + o)*x^64 + crc((key + i)*x^msg_len + msg))

m1 = Q(str2bits(PLAIN_1)[::-1])
m2 = Q(str2bits(PLAIN_2)[::-1])
h1 = Q((0xa57d43a032feb286).bits())

k = (h1 - i*x^(len(PLAIN_1)*8 + 128) - (o + m1)*x^128 - c*x^64 - c) / (x^(len(PLAIN_1)*8 + 128) + x^128)
print("k = {}".format(hex(poly2num(k))))
h2 = hmac(k, m2, len(PLAIN_2)*8)
print("hmac(k, \"{}\") = {}".format(PLAIN_2, hex(poly2num(h2))))
print("BKPCTF{{{h2:x}}}".format(h2=poly2num(h2)))


The given source code:

hmac_crc.py

#!/usr/bin/env python2
def to_bits(length, N):
return [int(i) for i in bin(N)[2:].zfill(length)]

def from_bits(N):
return int("".join(str(i) for i in N), 2)

CRC_POLY = to_bits(65, (2**64) + 0xeff67c77d13835f7)

def crc(mesg, x=True):
if x:
mesg += CONST
shift = 0
while shift < len(mesg) - 64:
if mesg[shift]:
for i in range(65):
mesg[shift + i] ^= CRC_POLY[i]
shift += 1
return mesg[-64:]

INNER = to_bits(8, 0x36) * 8
OUTER = to_bits(8, 0x5c) * 8

def xor(x, y):
return [g ^ h for (g, h) in zip(x, y)]

def hmac(h, key, mesg):
return h(xor(key, OUTER) + h(xor(key, INNER) + mesg))

PLAIN_1 = "zupe zecret"
PLAIN_2 = "BKPCTF"

def str_to_bits(s):
return [b for i in s for b in to_bits(8, ord(i))]

def bits_to_hex(b):
return hex(from_bits(b)).rstrip("L")

if __name__ == "__main__":
with open("key.txt") as f: