BKP-2016-hmac_crc-solve.py

'''
https://ctftime.org/task/2108

In the challenge, 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”? 

'''
from sage.all import *

X = GF(2).polynomial_ring().gen()
N = 64

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


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

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


PLAIN_1 = "zupe zecret"
PLAIN_2 = "BKPCTF"

hmack = 0xa57d43a032feb286

# obtain from running hmac-task on m = "zupe secret"
key0 = to_bits(64, 0)
key1 = to_bits(64, 1)
hmac0 = int(bits_to_hex(hmac(crc, key0, str_to_bits(PLAIN_1))), 16)
hmac1 = int(bits_to_hex(hmac(crc, key1, str_to_bits(PLAIN_1))), 16)

poly = ntopoly(0xeff67c77d13835f7 + 2**64)
r = ntopoly(hmac1 ^ hmac0)
kr = ntopoly(hmack ^ hmac0)
g = gcd(poly, r)
assert g == 1

K = (kr * inverse_mod(r, poly)) % poly
print "K: 0x%x" % polyton(K)

KEY = to_bits(64, polyton(K))
print "BKPCTF{" + bits_to_hex(hmac(crc, KEY, str_to_bits(PLAIN_2))) + "}"