Boston Key Party 2016: HMAC

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))) + "}"

CInsects

Boston Key Party 2016: HMAC_CRC

Appendix