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

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), CONSTO(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}.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s