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))
c = Q((0xabaddeadbeef1dea).bits())
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)
CONST = to_bits(64, 0xabaddeadbeef1dea)
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:
KEY = to_bits(64, int(f.read().strip("\n"), 16))
print PLAIN_1, "=>", bits_to_hex(hmac(crc, KEY, str_to_bits(PLAIN_1)))
print "BKPCTF{" + bits_to_hex(hmac(crc, KEY, str_to_bits(PLAIN_2))) + "}"