BKPCTF 2016

#!/usr/bin/env python
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))

PLAIN_1 = "zupe zecret"
PLAIN_2 = "BKPCTF"

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

if __name__ == "__main__":
  with open("key.txt") as f:
    KEY = to_bits(64, int(f.read().strip("\n"), 16))
  print PLAIN_1, "=>", bits_to_hex(hmac(crc, KEY, str_to_bits(PLAIN_1)))
  print "BKPCTF{" + bits_to_hex(hmac(crc, KEY, str_to_bits(PLAIN_2))) + "}"

Let’s write out the hashing function (hmac-crc):  hash(x,m) := crc( (x ⊕ C1) + crc( (x ⊕ C2) + m ) )  where + is string concat.

We dont have key, but have a (message, hash) pair (“zupe zecret”, 0xa57d43a032feb286), and need to find correct hash for message “BKPCTF”.

The first approach i came up with was brute-forcing, and z3 refused to give me any answer after waiting some hour…

Let’s go deeper, crc function is based on linear combinator of xor, so it’s linear over xor:

 crc(x ⊕ y) = crc(x) ⊕ crc(y),

which’s also mean that

 crc(crc(x ⊕ y)) = crc(crc(x) ⊕ crc(y)) = crc(crc(x)) ⊕ crc(crc(y)).

Back to original hashing function, we can turn string concat into bitwise concat as

x + y = (x<<y.bit_length()) | y

which means our hashing function can be turned into pure integer operation form (note that this version of crc returns 64 bit data):

hash(x,m) := crc( (x ⊕ C1)<<64 | crc( (x ⊕ C2) << m.bit_length() | m ) )

As crc is linear over xor, that form can be rewritten as:

hash(x,m) := crc(x<<64) ⊕ crc(crc(x<<m.bit_length())) ⊕ f(m)

Where f(m) is independent from x, and can be calculated by:

f(m) := crc(x<<64) ⊕ crc(crc(x<<m.bit_length())) ⊕ hash(x,m)

Let’s try if it’s constant:

def f(x,m):
  return xor(xor(crc(x+[0]*64),crc(crc(x+[0]*(len(m))))),hmac(crc,x,m))
  
print bits_to_hex(f(to_bits(64,0x273846),str_to_bits(PLAIN_1)))
print bits_to_hex(f(to_bits(64,0x27384633),str_to_bits(PLAIN_1)))
print bits_to_hex(f(to_bits(64,0xdeadbeef),str_to_bits(PLAIN_1)))

0xad441373f3df7919
0xad441373f3df7919
0xad441373f3df7919

So the constant for PLAIN_1 is 0xad441373f3df7919, or crc(x<<64) ⊕ crc(crc(x<<m.bit_length())) == 0xa57d43a032feb286 ⊕ 0xad441373f3df7919 == !

Now, as the LHS is linear over xor, we can solve for x by bits.

Let’s say g(x) is a linear function over xor, then g(x) = x0*g(2^0)+x1*g(2^1)+x2*g(2^2), where xi is bit i of x, so to solve for x from g(x), we just need to find x0, x1, x2,…

Ok, let’s calculate array {g(2^i)}:

print map(lambda x: int(x[2:],16)^0xad441373f3df7919,[bits_to_hex(hmac(crc, to_bits(64, 2**i), str_to_bits(PLAIN_1))) for i in range(64)])

[6834908643740050077L, 8918261360326614375L, 3600904948819878547L, 11925816451771342203L, 7098953563970525020L, 250491143874901733L, 13871981502125061527L, 12141935756842272388L, 8684960005792719010L, 3998826113598822681L, 12145552072860297839L, 8691349026213935476L, 3984360580943489717L, 12170521405071002935L, 8667819726527657924L, 3955397618321405909L, 12373709570274539511L, 9148772311635821124L, 4295619248599194837L, 12775235449187295735L, 5409676984928710212L, 5789065119148442837L, 7412147678370845175L, 849648730292190131L, 15124753415683977019L, 9965726379648136156L, 4403455869246736914L, 13567263759751040121L, 5843346184221062488L, 7232655499200574189L, 1067334037898706311L, 15847930004167435091L, 11410109179131964172L, 1528755289798589362L, 17014177992982769465L, 17418665637690586072L, 14623638097115056666L, 13575463204758878622L, 5858618864078233238L, 7271915590215853425L, 1127839958837695167L, 15653736043036081443L, 11240125514458011628L, 2197594243193422450L, 18054418212176223417L, 15896248787898488024L, 10426727587354133530L, 639743797107778974L, 15542294092789453665L, 9719943529612364648L, 2616260629129296762L, 10298979513560477353L, 3772943349561078008L, 12594504273370790317L, 8365397508198080240L, 3341473552091702717L, 11154974181608723239L, 2025021915423886308L, 18321857654312619925L, 15352253859363582592L, 9483132146532092074L, 3365100990727388414L, 11175275768288584097L, 2282081819746938600L]

Solving it using SAGE:

from sage.all import *

A = [6834908643740050077L, 8918261360326614375L, 3600904948819878547L, 11925816451771342203L, 7098953563970525020L, 250491143874901733L, 13871981502125061527L, 12141935756842272388L, 8684960005792719010L, 3998826113598822681L, 12145552072860297839L, 8691349026213935476L, 3984360580943489717L, 12170521405071002935L, 8667819726527657924L, 3955397618321405909L, 12373709570274539511L, 9148772311635821124L, 4295619248599194837L, 12775235449187295735L, 5409676984928710212L, 5789065119148442837L, 7412147678370845175L, 849648730292190131L, 15124753415683977019L, 9965726379648136156L, 4403455869246736914L, 13567263759751040121L, 5843346184221062488L, 7232655499200574189L, 1067334037898706311L, 15847930004167435091L, 11410109179131964172L, 1528755289798589362L, 17014177992982769465L, 17418665637690586072L, 14623638097115056666L, 13575463204758878622L, 5858618864078233238L, 7271915590215853425L, 1127839958837695167L, 15653736043036081443L, 11240125514458011628L, 2197594243193422450L, 18054418212176223417L, 15896248787898488024L, 10426727587354133530L, 639743797107778974L, 15542294092789453665L, 9719943529612364648L, 2616260629129296762L, 10298979513560477353L, 3772943349561078008L, 12594504273370790317L, 8365397508198080240L, 3341473552091702717L, 11154974181608723239L, 2025021915423886308L, 18321857654312619925L, 15352253859363582592L, 9483132146532092074L, 3365100990727388414L, 11175275768288584097L, 2282081819746938600L]
b = 0xa57d43a032feb286^0xad441373f3df7919
m=[]
for i in range(64):
  for a in A:
    m.append(int((a>>i)&1))
  m.append(int((b>>i)&1))
m = Matrix(GF(2),64,65,m)
mr=m.rref()
#print mr.str()
print mr[:,64].transpose().str()

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]

Um, seems wrong… Let’s relook at the crc function…

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

Found it! This crc function is padded with CONST, we just need to nullize it and change function f above.

def _crc(mesg):
  mesg += [0]*64
  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 f(x,m):
 return xor(xor(_crc(x+[0]*64),_crc(_crc(x+[0]*(len(m))))),hmac(crc,x,m))

The constants now is 0xef6bbf832c7eced2, regenerate the {g(2^i)} array, we obtain:

A = [2086809031724160342, 4173618063448320684, 8347236126896641368, 16694472253793282736L, 2354010789588066455, 4708021579176132910, 9416043158352265820L, 16910874547544338767L, 4226771103552264041, 8453542207104528082, 16907084414209056164L, 4229569526062812863, 8459139052125625726, 16918278104251251452L, 4208021141449359375, 8416042282898718750, 16832084565797437500L, 4384635772785538447, 8769271545571076894, 17538543091142153788L, 665587708229949839, 1331175416459899678, 2662350832919799356, 5324701665839598712, 10649403331679197424L, 14439371256774722583L, 9165840333751074265, 18331680667502148530L, 1384875121671455379, 2769750243342910758, 5539500486685821516, 11079000973371643032L, 15886295027533749447L, 6275931173970513017, 12551862347941026034L, 12940008229072012307L, 9862379257203277265L, 18323483507405901397L, 1396769139689302365, 2793538279378604730, 5587076558757209460, 11174153117514418920L, 15695992938220920871L, 6652028455910995385, 13304056911821990770L, 11436186450250294035L, 15176147297687040977L, 5390667367170691669, 10781334734341383338L, 14180570601802398883L, 7377318259839126705, 14754636519678253410L, 8535309807767455539, 17070619615534911078L, 3906996125356534075, 7813992250713068150, 15627984501426136300L, 6788611577661193263, 13577223155322386526L, 10890132138416260427L, 13958192917995831137L, 7826290186278357813, 15652580372556715626L, 6738574311101372707]
b = 0xa57d43a032feb286^0xef6bbf832c7eced2

And the output now is:

[0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1]

So the key in binary form is 1010111001010110000101110111000000111010110011101101110010001000. Let’s calculate the hash now!

print bits_to_hex(hmac(crc, to_bits(64, 0b1010111001010110000101110111000000111010110011101101110010001000), str_to_bits(PLAIN_2)))

0xd2db2b8b9002841f

And here’s the flag: BKPCTF{0xd2db2b8b9002841f}!