Boston Key Party CTF 2016 – HMAC-CRC (Crypto 5pts)

[3] : hmac_crc – 5 – 36 solves : crypto: We’re trying a new mac here at BKP—HMAC-CRC. The hmac (with our key) of “zupe zecret” is ‘0xa57d43a032feb286’. What’s the hmac of “BKPCTF”?

hmac-task.py

Summary: breaking HMAC-CRC (again)

CRC_POLY = to_bits(65, (2**64) + 0xeff67c77d13835f7)
CONST = to_bits(64, 0xabaddeadbeef1dea)
 
def crc(mesg):
  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:]
 
def hmac(h, key, mesg):
  return h(xor(key, OUTER) + h(xor(key, INNER) + mesg))

This challenge is similar to MMACTF Motto Mijikai Address. Given one plaintext and its HMAC-CRC, we need to forge HMAC-CRC for another plaintext. Recall that

$$HMAC{–}CRC(m, k) = CRC( [K \oplus opad] || CRC ( [K \oplus ipad] || m)),$$

where $opad$ and $ipad$ are some constant strings. Recall also that CRC is a multiplication of polynomials modulo the CRC polynomial $P(x)$ and is affine over $GF(2)$. Note that when the message $m$ is fixed, HMAC-CRC is affine function of $k$. Moreover, composition of two CRCs is still a multiplication by a polynomial (plus some independent terms, which we consider constant when $m$ is fixed). We can write

$$HMAC{–}CRC(m, k) = (q_m(x) \oplus r_m(x)k(x)) \mod P(x),$$

where $q_m(x),r_m(x)$ are some polynomials depending on $m$. We could find the polynomials by carefully writing down the equation for HMAC. But we can do it easier using the following differentials:

$$HMAC{–}CRC(m, 0) \oplus HMAC{–}CRC(m, 1) = r_m(x) \mod P(x).$$

Then we can use known $HMAC{–}CRC(m, k)$:

$$HMAC{–}CRC(m, 0) \oplus HMAC{–}CRC(m, k) = (r_m(x) k(x)) \mod P(x).$$

And then we can hopefully invert $r_m(x)$ and recover $k$.

Here’s Sage code for that:

from sage.all import *
 
def ntopoly(npoly):
    return sum(c*X**e
        for e, c in enumerate(Integer(npoly).bits()))
 
def polyton(poly):
    return sum(int(poly[i])*(1 << i)
        for i in xrange(poly.degree() + 1))
 
X = GF(2).polynomial_ring().gen()
 
N = 64
poly = ntopoly(0xeff67c77d13835f7 + 2**64)
 
m = "zupe zecret"
hmac = 0xa57d43a032feb286
 
# obtain from running hmac-task on m = "zupe secret"
hmac0 = 0xef6bbf832c7eced2
hmac1 = 0xf39e6a4125801b84
 
r = ntopoly(hmac1 ^^ hmac0)
kr = ntopoly(hmac ^^ hmac0)
g = gcd(poly, r)
assert g == 1
 
K = (kr * inverse_mod(r, poly)) % poly
 
print "K: 0x%x" % polyton(K)

We obtain K = 0xae5617703acedc88. Plugging it in hmac-task.py, we get the flag: BKPCTF{0xd2db2b8b9002841f}.