# BKPCTF16 – HMAC_CRC

We are given the following implementation of a HMAC where the hash function has been replaced by a CRC function.

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

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:]

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))


We are given two messages PLAIN_1 = "zupe zecret"; PLAIN_2 = "BKPCTF", of which HMAC_1 = hmac(crc, key, bin(PLAIN_1)), where bin() is a binary vectorial representation.
First, we note that the CRC operation is actually interpretable as a simple modular polynomial expression. Also, every binary sequence can be written as a polynomial $\mathbb{F}_2[x] / P(x)$. We use the following mapping: $H(x)$HMAC_1; $M(x)$mesg; $C(x)$, CONST$O(x)$ , OUTER; $I(x)$ , INNER; $P(x)$CRC_POLY and $K(x)$key).

$[M(x)x^{64} + C(X)] \mod P(x).$

Consequently, the HMAC operation can be written as

$H(x) = ([K(x)+O(x)]x^{64} + [K(x)+I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x) \mod P(x).$

Secondly, we note that can move out the $K(x)$ from the expression, i.e.,

$H(x) = \underbrace{([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)}_{\textnormal{Independent of the key}} + K(x)(x^{128}+x^{128+n}) \mod P(x).$

With some simple algebra, we can now determine the key $K(x)$ by rearranging the above equation

$\left(H(X) + ([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)\right)(x^{128}+x^{128+n})^{-1} = K(x) \mod P(x).$

Using Sage, the we can easily do these computations:

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

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

P.<x> = PolynomialRing(GF(2))
I = P.ideal([x^64+x^63+x^62+x^61+x^59+x^58+x^57+x^56+x^55+x^54+x^53+x^52+x^50+x^49+x^46+x^45+x^44+x^43+x^42+x^38+x^37+x^36+x^34+x^33+x^32+x^31+x^30+x^28+x^24+x^21+x^20+x^19+x^13+x^12+x^10+x^8+x^7+x^6+x^5+x^4+x^2+x^1+1])
S = P.quotient_ring(I)
In =  x^61+x^60+x^58+x^57+x^53+x^52+x^50+x^49+x^45+x^44+x^42+x^41+x^37+x^36+x^34+x^33+x^29+x^28+x^26+x^25+x^21+x^20+x^18+x^17+x^13+x^12+x^10+x^9+x^5+x^4+x^2+x^1
Out =  x^62+x^60+x^59+x^58+x^54+x^52+x^51+x^50+x^46+x^44+x^43+x^42+x^38+x^36+x^35+x^34+x^30+x^28+x^27+x^26+x^22+x^20+x^19+x^18+x^14+x^12+x^11+x^10+x^6+x^4+x^3+x^2
M =  x^86+x^85+x^84+x^83+x^81+x^78+x^77+x^76+x^74+x^72+x^70+x^69+x^68+x^62+x^61+x^58+x^56+x^53+x^46+x^45+x^44+x^43+x^41+x^38+x^37+x^34+x^32+x^30+x^29+x^25+x^24+x^22+x^21+x^20+x^17+x^14+x^13+x^10+x^8+x^6+x^5+x^4+x^2
Hmac =  x^63+x^61+x^58+x^56+x^54+x^53+x^52+x^51+x^50+x^48+x^46+x^41+x^40+x^39+x^37+x^29+x^28+x^25+x^23+x^22+x^21+x^20+x^19+x^18+x^17+x^15+x^13+x^12+x^9+x^7+x^2+x^1
CONST = x^63+x^61+x^59+x^57+x^56+x^55+x^53+x^51+x^50+x^48+x^47+x^46+x^44+x^43+x^42+x^41+x^39+x^37+x^35+x^34+x^32+x^31+x^29+x^28+x^27+x^26+x^25+x^23+x^22+x^21+x^19+x^18+x^17+x^16+x^12+x^11+x^10+x^8+x^7+x^6+x^5+x^3+x^1
Y = Hmac + ((Out)*x^64 + ((In)*x^88 + M)*x^64 + CONST)*x^64 + CONST
X = (x^128+x^(128+88))
Xinv = X.xgcd(x^64+x^63+x^62+x^61+x^59+x^58+x^57+x^56+x^55+x^54+x^53+x^52+x^50+x^49+x^46+x^45+x^44+x^43+x^42+x^38+x^37+x^36+x^34+x^33+x^32+x^31+x^30+x^28+x^24+x^21+x^20+x^19+x^13+x^12+x^10+x^8+x^7+x^6+x^5+x^4+x^2+x^1+1)[1]
K = S(Xinv*Y)
Kbin = [K[i] for i in range(0,64)]
Kbin.reverse()
print "The key is", bits_to_hex(Kbin)


and obtain the key 0xae5617703acedc88. Substituting the key into the code, we get the flag BKPCTF{0xd2db2b8b9002841f}.