PHDay CTF keygen.exe solution

##########################################################################
# SBoxes used by the crackme (dumped with IDA python)
##########################################################################

WBoxSboxes = [
 [[2, 14, 10, 4, 11, 8, 15, 3, 5, 12, 6, 9, 13, 7, 1, 0],
  [13, 3, 11, 4, 10, 9, 1, 14, 8, 12, 5, 2, 7, 6, 0, 15],
  [4, 14, 8, 12, 6, 9, 11, 10, 2, 15, 5, 1, 3, 7, 0, 13],
  [15, 6, 7, 11, 8, 2, 12, 4, 14, 10, 9, 5, 3, 0, 13, 1],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [4, 5, 8, 11, 7, 10, 9, 6, 14, 12, 13, 2, 1, 3, 15, 0],
  [7, 6, 1, 9, 11, 0, 12, 10, 3, 15, 2, 5, 8, 13, 14, 4],
  [0, 3, 14, 1, 5, 10, 11, 13, 15, 2, 8, 12, 4, 7, 9, 6],
  [2, 14, 10, 4, 11, 8, 15, 3, 5, 12, 6, 9, 13, 7, 1, 0],
  [4, 11, 3, 13, 14, 1, 9, 10, 2, 5, 12, 8, 15, 0, 6, 7],
  [12, 8, 14, 4, 10, 11, 9, 6, 1, 5, 15, 2, 13, 0, 7, 3],
  [2, 8, 4, 12, 6, 15, 11, 7, 0, 3, 1, 13, 10, 14, 5, 9],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [6, 9, 10, 7, 11, 8, 5, 4, 0, 15, 3, 1, 2, 13, 12, 14],
  [5, 2, 15, 3, 4, 14, 13, 8, 9, 1, 6, 7, 10, 12, 0, 11],
  [8, 12, 15, 2, 9, 6, 4, 7, 14, 1, 0, 3, 11, 13, 5, 10]],
 [[2, 14, 10, 4, 11, 8, 15, 3, 5, 12, 6, 9, 13, 7, 1, 0],
  [4, 11, 3, 13, 14, 1, 9, 10, 2, 5, 12, 8, 15, 0, 6, 7],
  [12, 8, 14, 4, 10, 11, 9, 6, 1, 5, 15, 2, 13, 0, 7, 3],
  [2, 8, 4, 12, 6, 15, 11, 7, 0, 3, 1, 13, 10, 14, 5, 9],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [6, 9, 10, 7, 11, 8, 5, 4, 0, 15, 3, 1, 2, 13, 12, 14],
  [5, 2, 15, 3, 4, 14, 13, 8, 9, 1, 6, 7, 10, 12, 0, 11],
  [8, 12, 15, 2, 9, 6, 4, 7, 14, 1, 0, 3, 11, 13, 5, 10],
  [2, 14, 10, 4, 11, 8, 15, 3, 5, 12, 6, 9, 13, 7, 1, 0],
  [0, 15, 7, 6, 5, 2, 8, 12, 1, 14, 10, 9, 11, 4, 13, 3],
  [9, 6, 10, 11, 14, 4, 12, 8, 7, 3, 13, 0, 15, 2, 1, 5],
  [2, 8, 4, 12, 6, 15, 11, 7, 0, 3, 1, 13, 10, 14, 5, 9],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [8, 11, 4, 5, 9, 6, 7, 10, 13, 2, 14, 12, 15, 0, 1, 3],
  [11, 0, 12, 10, 7, 6, 1, 9, 8, 13, 14, 4, 3, 15, 2, 5],
  [1, 14, 3, 0, 13, 11, 10, 5, 12, 8, 2, 15, 6, 9, 7, 4]],
 [[2, 14, 10, 4, 11, 8, 15, 3, 5, 12, 6, 9, 13, 7, 1, 0],
  [0, 15, 7, 6, 5, 2, 8, 12, 1, 14, 10, 9, 11, 4, 13, 3],
  [9, 6, 10, 11, 14, 4, 12, 8, 7, 3, 13, 0, 15, 2, 1, 5],
  [2, 8, 4, 12, 6, 15, 11, 7, 0, 3, 1, 13, 10, 14, 5, 9],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [8, 11, 4, 5, 9, 6, 7, 10, 13, 2, 14, 12, 15, 0, 1, 3],
  [11, 0, 12, 10, 7, 6, 1, 9, 8, 13, 14, 4, 3, 15, 2, 5],
  [1, 14, 3, 0, 13, 11, 10, 5, 12, 8, 2, 15, 6, 9, 7, 4],
  [7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [4, 11, 3, 13, 14, 1, 9, 10, 2, 5, 12, 8, 15, 0, 6, 7],
  [14, 4, 12, 8, 9, 6, 10, 11, 15, 2, 1, 5, 7, 3, 13, 0],
  [7, 11, 15, 6, 12, 4, 8, 2, 9, 5, 14, 10, 13, 1, 3, 0],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [0, 15, 3, 1, 2, 13, 12, 14, 6, 9, 10, 7, 11, 8, 5, 4],
  [13, 8, 4, 14, 15, 3, 5, 2, 0, 11, 10, 12, 6, 7, 9, 1],
  [4, 7, 9, 6, 15, 2, 8, 12, 5, 10, 11, 13, 0, 3, 14, 1]],
 [[7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [4, 11, 3, 13, 14, 1, 9, 10, 2, 5, 12, 8, 15, 0, 6, 7],
  [14, 4, 12, 8, 9, 6, 10, 11, 15, 2, 1, 5, 7, 3, 13, 0],
  [7, 11, 15, 6, 12, 4, 8, 2, 9, 5, 14, 10, 13, 1, 3, 0],
  [13, 15, 11, 5, 9, 10, 2, 7, 8, 12, 14, 1, 6, 4, 0, 3],
  [0, 15, 3, 1, 2, 13, 12, 14, 6, 9, 10, 7, 11, 8, 5, 4],
  [13, 8, 4, 14, 15, 3, 5, 2, 0, 11, 10, 12, 6, 7, 9, 1],
  [4, 7, 9, 6, 15, 2, 8, 12, 5, 10, 11, 13, 0, 3, 14, 1],
  [12, 5, 9, 6, 7, 13, 0, 1, 14, 2, 4, 10, 8, 11, 3, 15],
  [7, 6, 0, 15, 8, 12, 5, 2, 10, 9, 1, 14, 13, 3, 11, 4],
  [7, 3, 13, 0, 15, 2, 1, 5, 9, 6, 10, 11, 14, 4, 12, 8],
  [9, 5, 14, 10, 13, 1, 3, 0, 7, 11, 15, 6, 12, 4, 8, 2],
  [8, 12, 14, 1, 6, 4, 0, 3, 13, 15, 11, 5, 9, 10, 2, 7],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [7, 6, 1, 9, 11, 0, 12, 10, 3, 15, 2, 5, 8, 13, 14, 4],
  [12, 8, 2, 15, 6, 9, 7, 4, 1, 14, 3, 0, 13, 11, 10, 5]],
 [[12, 5, 9, 6, 7, 13, 0, 1, 14, 2, 4, 10, 8, 11, 3, 15],
  [7, 6, 0, 15, 8, 12, 5, 2, 10, 9, 1, 14, 13, 3, 11, 4],
  [7, 3, 13, 0, 15, 2, 1, 5, 9, 6, 10, 11, 14, 4, 12, 8],
  [9, 5, 14, 10, 13, 1, 3, 0, 7, 11, 15, 6, 12, 4, 8, 2],
  [8, 12, 14, 1, 6, 4, 0, 3, 13, 15, 11, 5, 9, 10, 2, 7],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [7, 6, 1, 9, 11, 0, 12, 10, 3, 15, 2, 5, 8, 13, 14, 4],
  [12, 8, 2, 15, 6, 9, 7, 4, 1, 14, 3, 0, 13, 11, 10, 5],
  [7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [10, 11, 9, 6, 12, 8, 14, 4, 13, 0, 7, 3, 1, 5, 15, 2],
  [7, 11, 15, 6, 12, 4, 8, 2, 9, 5, 14, 10, 13, 1, 3, 0],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [9, 1, 6, 7, 10, 12, 0, 11, 5, 2, 15, 3, 4, 14, 13, 8],
  [8, 12, 15, 2, 9, 6, 4, 7, 14, 1, 0, 3, 11, 13, 5, 10]],
 [[7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [10, 11, 9, 6, 12, 8, 14, 4, 13, 0, 7, 3, 1, 5, 15, 2],
  [7, 11, 15, 6, 12, 4, 8, 2, 9, 5, 14, 10, 13, 1, 3, 0],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [9, 1, 6, 7, 10, 12, 0, 11, 5, 2, 15, 3, 4, 14, 13, 8],
  [8, 12, 15, 2, 9, 6, 4, 7, 14, 1, 0, 3, 11, 13, 5, 10],
  [7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [11, 10, 6, 9, 8, 12, 4, 14, 0, 13, 3, 7, 5, 1, 2, 15],
  [11, 7, 6, 15, 4, 12, 2, 8, 5, 9, 10, 14, 1, 13, 0, 3],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [12, 10, 11, 0, 1, 9, 7, 6, 14, 4, 8, 13, 2, 5, 3, 15],
  [5, 10, 11, 13, 0, 3, 14, 1, 4, 7, 9, 6, 15, 2, 8, 12]],
 [[7, 13, 0, 1, 12, 5, 9, 6, 8, 11, 3, 15, 14, 2, 4, 10],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [11, 10, 6, 9, 8, 12, 4, 14, 0, 13, 3, 7, 5, 1, 2, 15],
  [11, 7, 6, 15, 4, 12, 2, 8, 5, 9, 10, 14, 1, 13, 0, 3],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [15, 0, 1, 3, 13, 2, 14, 12, 9, 6, 7, 10, 8, 11, 4, 5],
  [12, 10, 11, 0, 1, 9, 7, 6, 14, 4, 8, 13, 2, 5, 3, 15],
  [5, 10, 11, 13, 0, 3, 14, 1, 4, 7, 9, 6, 15, 2, 8, 12],
  [12, 5, 9, 6, 7, 13, 0, 1, 14, 2, 4, 10, 8, 11, 3, 15],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [11, 10, 6, 9, 8, 12, 4, 14, 0, 13, 3, 7, 5, 1, 2, 15],
  [4, 12, 2, 8, 11, 7, 6, 15, 1, 13, 0, 3, 5, 9, 10, 14],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [9, 6, 7, 10, 8, 11, 4, 5, 15, 0, 1, 3, 13, 2, 14, 12],
  [9, 1, 6, 7, 10, 12, 0, 11, 5, 2, 15, 3, 4, 14, 13, 8],
  [15, 2, 8, 12, 4, 7, 9, 6, 0, 3, 14, 1, 5, 10, 11, 13]],
 [[12, 5, 9, 6, 7, 13, 0, 1, 14, 2, 4, 10, 8, 11, 3, 15],
  [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
  [11, 10, 6, 9, 8, 12, 4, 14, 0, 13, 3, 7, 5, 1, 2, 15],
  [4, 12, 2, 8, 11, 7, 6, 15, 1, 13, 0, 3, 5, 9, 10, 14],
  [4, 6, 3, 0, 12, 8, 1, 14, 10, 9, 7, 2, 15, 13, 5, 11],
  [9, 6, 7, 10, 8, 11, 4, 5, 15, 0, 1, 3, 13, 2, 14, 12],
  [9, 1, 6, 7, 10, 12, 0, 11, 5, 2, 15, 3, 4, 14, 13, 8],
  [15, 2, 8, 12, 4, 7, 9, 6, 0, 3, 14, 1, 5, 10, 11, 13],
  [68, 49, 64, 0, 68, 49, 64, 0, 12, 5, 9, 6, 7, 13, 0, 1],
  [14, 2, 4, 10, 8, 11, 3, 15, 6, 7, 15, 0, 12, 8, 2, 5],
  [9, 10, 14, 1, 3, 13, 4, 11, 10, 11, 9, 6, 12, 8, 14, 4],
  [13, 0, 7, 3, 1, 5, 15, 2, 7, 11, 15, 6, 12, 4, 8, 2],
  [9, 5, 14, 10, 13, 1, 3, 0, 12, 8, 1, 14, 4, 6, 3, 0],
  [15, 13, 5, 11, 10, 9, 7, 2, 7, 10, 9, 6, 4, 5, 8, 11],
  [1, 3, 15, 0, 14, 12, 13, 2, 2, 5, 3, 15, 14, 4, 8, 13],
  [1, 9, 7, 6, 12, 10, 11, 0, 3, 0, 1, 14, 10, 5, 13, 11]]
]

CipherSboxes = [
 [12, 5, 9, 6, 7, 13, 0, 1, 14, 2, 4, 10, 8, 11, 3, 15],
 [6, 7, 15, 0, 12, 8, 2, 5, 9, 10, 14, 1, 3, 13, 4, 11],
 [10, 11, 9, 6, 12, 8, 14, 4, 13, 0, 7, 3, 1, 5, 15, 2],
 [7, 11, 15, 6, 12, 4, 8, 2, 9, 5, 14, 10, 13, 1, 3, 0],
 [12, 8, 1, 14, 4, 6, 3, 0, 15, 13, 5, 11, 10, 9, 7, 2],
 [7, 10, 9, 6, 4, 5, 8, 11, 1, 3, 15, 0, 14, 12, 13, 2],
 [2, 5, 3, 15, 14, 4, 8, 13, 1, 9, 7, 6, 12, 10, 11, 0],
 [3, 0, 1, 14, 10, 5, 13, 11, 2, 15, 12, 8, 7, 4, 6, 9]
]

##########################################################################
# code of keygen.exe translated in python
##########################################################################

# list of nibbles to DWORD
def l2d(l) :
    return reduce(lambda x, y: (x<<4)|y, l[::-1])

# DWORD to list of nibbles
def d2l(d, size = 4) :
    return [int(c, 16) for c in (("%%0%dX"%(2*size))%d)[::-1]]

def rol(l, n) :
    d = l2d(l)
    d = (d << n) | (d >> (32-n))
    d &= 0xFFFFFFFF
    return d2l(d)

# substitution
def subs(l, sbox) :
    return [sbox[v] for v in l]

# sbox inversion
def invSbox(sbox) :
    retval = ["??"]*len(sbox)
    for i,j in enumerate(sbox) :
        retval[j] = i
    return retval

# White Box round
def WBround(block, round) :
    L = block[:8]
    R = block[8:]
    return R + d2l(l2d(rol([WBoxSboxes[round][i][v] for i, v in enumerate(R)], 11)) ^ l2d(L))

# White Box cypher
def WBCypher(block) :
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(7, -1, -1) :
        block = WBround(block, i)
    return block[8:] + block[:8]

# decryption routine round
def dec_round(block, round, k) :
    L = block[:8]
    R = block[8:]
    return R + d2l(l2d(rol([CipherSboxes[i][v] for i, v in enumerate(d2l(k[round] ^ l2d(R)))], 11)) ^ l2d(L))

# decryption routine, we have to find the k which correspond to the white box
def uncypher(block, k) :
    xk = [ord(k[i])**2 + ((ord(k[i+1])**2) << 16) for i in xrange(0, len(k), 2)]

    for i in xrange(8) :
        block = dec_round(block, i, xk)
    for i in xrange(7, -1, -1) :
        block = dec_round(block, i, xk)
    for i in xrange(7, -1, -1) :
        block = dec_round(block, i, xk)
    for i in xrange(7, -1, -1) :
        block = dec_round(block, i, xk)
    return block[8:] + block[:8]

#####################################
# code used to recover the key
#####################################

recoveredK = ["???"]*8

def WBBreakround(block, round) :
    L = block[:8]
    R = block[8:]
    retval = R + d2l(l2d(rol([WBoxSboxes[round][i][v] for i, v in enumerate(R)], 11)) ^ l2d(L))
    Ld = retval[8:]
    Rd = retval[:8]
    recoveredK[round] = l2d([invSbox(CipherSboxes[i])[v] for i, v in enumerate(rol(d2l(l2d(L) ^ l2d(Ld)), 32-11))]) ^ l2d(Rd)
    return retval


def WBBreak(block) :
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(8) :
        block = WBround(block, i)
    for i in xrange(7, -1, -1) :
        block = WBBreakround(block, i)
    return block[8:] + block[:8]

WBBreak(d2l(0, 8))

k = "".join(chr((xk&0xFFFF)**0.5) + chr((xk >> 16)**0.5) for xk in recoveredK)
print k.encode("hex")