Mar
07

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

 : 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”?

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}.