Wednesday, 9 November 2016

Flare-on Challenge 2016 Write-up


The Flare-on challenge is an annual CTF style challenge with a focus on reverse engineering. Official solutions have already been published, besides that there are other writeups available too, hence I will just skim through the parts.

Challenge #1

The first was simple. This is base64 encoding with a custom charset. This online tool does the job.
Flag: sh00ting_phish_in_a_barrel@flare-on.com

Fig 1: Challenge 1

Challenge #2 - DudeLocker

This is a file encrypting ransomware. An encrypted file (BusinessPapers.doc) is provided, the task is to decrypt it. As the encryption key is hardcoded in the binary, I simply changed the CryptEncrypt call to CryptDecrypt by modifying the IAT. This decrypts the file giving the following image.
flag: cl0se_t3h_f1le_0n_th1s_One@flare-on.com 

Fig 2: Challenge 2

Challenge #3 - Unknown

The challenge is named unknown, we need to find it proper name. This can be found from the embedded pdb file path debug information. The binary implements a custom md5 hash algorithm which is used to calculate a table from the command line argument and the executable path. Since we already know the proper path, the command line argument can simply be brute forced giving us the flag Ohs0pec1alpwd@flare-on.com 
sss = map(ord, list('__FLARE On!'))

target = [0xEE613E2F, 0xDE79EB45, 0xAF1B2F3D, 0x8747BBD7, 
0x739AC49C, 0xC9A4F5AE, 0x4632C5C1, 0xA0029B24, 0xD6165059, 
0xA6B79451, 0xE79D23BA, 0x8AAE92CE, 0x85991A18, 0xFEE05899, 
0x430C7994, 0x1AB9F36F, 0x70C42481, 0x05BD27CF, 0xC4FF6E6F, 
0x5A77847C, 0xDD9277B3, 0x25843CFF, 0x5FDCA944, 0x8EE42896, 
0x2AE961C7, 0xA77731DA]

def charsprod(li):
 prod = 0
 for i in xrange(len(li)):
  prod = ((prod*37)&0xFFFFFFFF) + li[i] 
 return prod

email = ''

for i in xrange(26):
 sss[1] = ord('`') + i
 for j in xrange(1, 256):
  sss[0] = j
  if charsprod(sss) == target[i]:
   email += chr(j)
   break

print email


Challenge #4 - flareon2016challenge

A dll is provided which exports 51 functions by ordinals. Among them functions 1 to 48 & 51 changes the global state in someway or the other and must be called first. Ordinal 50 makes call to Beep and also tries to decrypt some piece of data. The task is to calls the functions in proper order so that the decryption may succeed. Additionally these  functions return an integer byte value indicating the ordinal of the next function that must be called. We can use the return values to build up the call chain order using the following script.
import ctypes

dll = ctypes.windll.LoadLibrary('flareon2016challenge')
call_chain = {}

for i in range(1, 49):
 retval = dll[i]()
 call_chain[i] = retval

print sorted(call_chain.values())
# missing is ordinal 30, should be called first

The call chain table thus found has no entry for ordinal 30, hence that is the function to be called first. After calling the functions in the correct order, an embedded executable is decrypted which just makes a series of calls to the Beep function. Setting a logging breakpoint on Beep allows us to recover the parameters passed. Calling export 50 using the same parameters gives us the flag: f0ll0w_t3h_3xp0rts@flare-on.com 
import sys
import ctypes
import os

params =[(440, 500), (440, 500), (440, 500), (349, 350) , (523, 150), (440, 500), (349, 350), (523, 150), (440, 1000), (659, 500), 
(659, 500), (659, 500), (698, 350), (523, 150), (415, 500), (349, 350), (523, 150), (440 , 1000)]

dll = ctypes.cdll.LoadLibrary('flareon2016challenge')

# call first function
retval = dll[30]()

# do not call last function
while retval != 51:
 retval = dll[retval]()

# call last func
dll[51]()

for p in params:
 dll[50](p[0], p[1])

Challenge #5 - smokestack

The provided executable is a stack based virtual machine. It takes in an argument, and prints the flag if it is correct. I reimplemented the vm in python and brute forced the flag A_p0p_pu$H_&_a_Jmp@flare-on.com
instructions = [0, 33, 2, 0, 145, 8, 0, 22, 0, 12, 9, 10, 11, 0, 0,
12, 2, 12, 0, 0, 29, 10, 11, 0, 0, 99, 2, 12, 0, 0,
24, 6, 0, 84, 8, 0, 51, 0, 41, 9, 10, 11, 0, 0, 44,
2, 12, 0, 0, 61, 10, 0, 14, 1, 11, 0, 0, 89, 2, 12,
0, 11, 0, 0, 0, 12, 1, 0, 9, 12, 0, 11, 1, 0, 2, 2,
12, 1, 11, 0, 0, 1, 3, 12, 0, 11, 0, 0, 0, 8, 0, 71,
0, 96, 9, 10, 12, 0, 11, 1, 3, 0, 93, 8, 0, 124, 0,
110, 9, 10, 11, 0, 0, 7, 3, 12, 0, 0, 91, 12, 1, 0,
135, 10, 0, 54, 12, 1, 11, 0, 11, 1, 2, 12, 1, 11, 1,
0, 88, 2, 6, 0, 249, 8, 0, 160, 0, 150, 9, 10, 11, 0,
0, 77, 6, 12, 0, 0, 174, 10, 0, 803, 0, 299, 3, 12,
1, 11, 0, 11, 1, 2, 12, 1, 12, 1, 11, 1, 11, 1, 0, 1,
3, 12, 1, 0, 3, 2, 11, 1, 0, 0, 8, 0, 178, 0, 199, 9,
10, 7, 0, 65143, 8, 0, 216, 0, 209, 9, 10, 11, 0, 0,
88, 2, 12, 0, 0, 3, 4, 0, 140, 2, 0, 24724, 8, 0, 238,
0, 231, 9, 10, 11, 0, 0, 231, 2, 12, 0, 11, 1, 2, 0,
12, 6, 0, 116, 8, 0, 263, 0, 253, 9, 10, 11, 0, 0, 9,
3, 12, 0, 0, 285, 10, 0, 10, 12, 1, 11, 1, 0, 1, 3,
12, 1, 11, 1, 0, 0, 8, 0, 267, 0, 285, 9, 10, 0, 6,
5, 0, 7616, 8, 0, 307, 0, 297, 9, 10, 11, 0, 0, 113,
2, 12, 0, 0, 317, 10, 11, 0, 0, 119, 2, 12, 0, 0, 317,
10, 0, 22, 2, 0, 14, 3, 0, 97, 8, 0, 339, 0, 332, 9,
10, 11, 0, 0, 44, 3, 12, 0, 12, 1, 11, 1, 0, 8492, 11,
1, 0, 1, 3, 12, 1, 0, 7, 3, 11, 1, 0, 0, 8, 0, 345,
0, 366, 9, 10, 0, 458, 6, 0, 8181, 8, 0, 385, 0, 378,
9, 10, 11, 0, 0, 18, 2, 12, 0, 13]

stack = []
sp = ctx1 = ctx2 = 0

def push(value):
 global sp
 sp += 1
 stack[sp] = value & 0xFFFF

def pop():
 global sp
 sp -= 1
 return stack[sp + 1]

def init_vm():
 global stack, sp, ctx1, ctx2
 stack = [ord(ch) for ch in 'kYwxCbJoLp']
 stack += [0,0,0,0]
 sp = 9
 ctx1 = ctx2 = 0

def exec_vm():
 global ctx1, ctx2
 ip = 0

 while ip < 386:
  #print 'loc_%d' %ip
  opcode = instructions[ip]
  
  if opcode == 0: # ins_load
   operand = instructions[ip + 1]
   push(operand)
   ip += 2

  elif opcode == 1: # ins_dec_sp
   pop()
   ip += 1

  elif opcode == 2: # ins_add
   v0 = pop()
   v1 = pop()
   push(v0 + v1)
   ip += 1

  elif opcode == 3: # ins_sub
   v0 = pop()
   v1 = pop()
   push(v1 - v0)
   ip += 1  

  elif opcode == 4: # ins_rotr
   v0 = pop()
   v1 = pop();
   push((v1 << (16 - v0)) | (v1 >> v0))
   ip += 1

  elif opcode == 5: # ins_rotl
   v0 = pop()
   v1 = pop();
   push((v1 >> (16 - v0)) | (v1 << v0))
   ip += 1

  elif opcode == 6: # ins_xor
   v0 = pop()
   v1 = pop();
   push(v1 ^ v0)
   ip += 1

  elif opcode == 7: # ins_not
   v0 = pop()
   push(~v0)
   ip += 1  

  elif opcode == 8: # ins_cmp
   v0 = pop()
   if v0 == pop():
    push(1)
   else:
    push(0)
   ip += 1    

  elif opcode == 9: # ins_cload
   v1 = pop()
   v0 = pop()
   if 1 == pop():
    push(v1)
   else:
    push(v0)
   ip += 1 

  elif opcode == 10: # ins_jmp
   ip = pop()

  elif opcode == 11: # ins_load_ctx
   operand = instructions[ip + 1]
   if operand == 0:
    push(ctx1)
   elif operand == 1:
    push(ctx2)
   ip += 2

  elif opcode == 12: # ins_set_ctx
   operand = instructions[ip + 1]
   v1 = pop()
   if operand == 0:
    ctx1 = v1
   elif operand == 1:
    ctx2 = v1
   ip += 2 

  elif opcode == 13: # ins_inc_ip
   ip += 1    


def main():
 global stack
 start = ord('A') - 1
 end = ord('z') + 1

 for pos in range(10):
  ret_vals = [None for i in xrange(start, end)]
  for i in range(start, end):
   init_vm()
   stack[pos] = i
   exec_vm()
   ret_vals[i-start] = tuple([i, ctx1])

  for e in ret_vals:
   if e[1] != ret_vals[0][1]:
    print chr(e[0]),
    break 


if __name__ == '__main__':
 main()

Challenge #6 - khaki

The challenge presents a piece of obfuscated python bytecode and by far this is best challenge. The file provided is a py2exe'd executable which can be easily unpacked to get the embedded pyc file. This pyc is obfuscated and cannot be easily decompiled. The reason for this is it has been sprinkled with NOPs , two POP_TOP, two ROT_TWO, and three ROT_THREE instructions. I developed a peephole optimizer to remove these instructions and make the file decompile-able using the bytecode-graph library developed by fireeye.
import bytecode_graph
import marshal
import opcode

def remove_nops(bcg, nodes):
 for i in xrange(len(nodes) - 1):
  node = nodes[i]
  if node.opcode == opcode.opmap['NOP']:
   bcg.delete_node(node)
   return True
 return False


def peephole_load_const(bcg, nodes):
 for i in xrange(len(nodes) - 1):
  node = nodes[i]
  # Peephole optimization (remove sequence of load and pop instructions)  
  if node.opcode == opcode.opmap['LOAD_CONST'] and nodes[i+1].opcode == opcode.opmap['POP_TOP']:
   bcg.delete_node(node)
   bcg.delete_node(nodes[i+1])
   return True
 return False   

def peephole_rot_two(bcg, nodes):
 for i in xrange(len(nodes) - 1):
  node = nodes[i]

  # Peephole optimization (remove two consecutive ROT_TWO)  
  if node.opcode == opcode.opmap['ROT_TWO'] and nodes[i+1].opcode == opcode.opmap['ROT_TWO']:
   bcg.delete_node(node)
   bcg.delete_node(nodes[i+1])
   return True
 return False

def peephole_rot_three(bcg, nodes):
 for i in xrange(len(nodes) - 2):
  node = nodes[i]

  # Peephole optimization (remove two consecutive ROT_THREE)  
  if node.opcode == opcode.opmap['ROT_THREE'] and nodes[i+1].opcode == opcode.opmap['ROT_THREE'] and nodes[i+2].opcode == opcode.opmap['ROT_THREE']:
   bcg.delete_node(node)
   bcg.delete_node(nodes[i+1]) 
   bcg.delete_node(nodes[i+2]) 
   return True

 return False  


def main():
 pyc_file = open('poc.pyc', 'rb').read()
 pyc = marshal.loads(pyc_file[8:])
 bcg = bytecode_graph.BytecodeGraph(pyc)

 nodes = [x for x in bcg.nodes()]

 while remove_nops(bcg, nodes) == True:
  nodes = [x for x in bcg.nodes()]

 while peephole_load_const(bcg, nodes) == True:
  nodes = [x for x in bcg.nodes()]
 
 while peephole_rot_two(bcg, nodes) == True:
  nodes = [x for x in bcg.nodes()]


 while peephole_rot_three(bcg, nodes) == True:
  nodes = [x for x in bcg.nodes()]

 deobf_code = bcg.get_code()
 f = open('poc-deobf.pyc', 'wb')
 f.write('\x03\xf3\x0d\x0a\0\0\0\0')
 marshal.dump(deobf_code, f)
 f.close()


if __name__ == '__main__':
 main()

Using this we can obtain the following deobfuscated code.
# Embedded file name: poc.py
import sys, random
__version__ = 'Flare-On ultra python obfuscater 2000'
target = random.randint(1, 101)
count = 1
error_input = ''
while True:
    print '(Guesses: %d) Pick a number between 1 and 100:' % count,
    input_num = sys.stdin.readline()
    try:
        input_num = int(input_num, 0)
    except:
        error_input = input_num
        print 'Invalid input: %s' % error_input
        continue

    if target == input_num:
        break
    if input_num < target:
        print 'Too low, try again'
    else:
        print 'Too high, try again'
    count += 1

if target == input_num:
    win_msg = 'Wahoo, you guessed it with %d guesses\n' % count
    sys.stdout.write(win_msg)
if count == 1:
    print 'Status: super guesser %d' % count
    #sys.exit(1)
if count > 25:
    print 'Status: took too long %d' % count
    sys.exit(1)
else:
    print 'Status: %d guesses' % count

if error_input != '':
    tmp = ''.join((chr(ord(x) ^ 66) for x in error_input)).encode('hex')
    if tmp != '312a232f272e27313162322e372548':
        sys.exit(0)
    stuffs = [67,139,119,165,232,86,207,61,
    import hashlib
    stuffer = hashlib.md5(win_msg + tmp).digest()
    for x in range(len(stuffs)):
        print chr(stuffs[x] ^ ord(stuffer[x % len(stuffer)])),

    print

Another python script to brute force the flag.
import hashlib

for i in xrange(100):
 win_msg = 'Wahoo, you guessed it with %d guesses\n' %i
 tmp = '312a232f272e27313162322e372548'

 stuffs = [67,139,119,165,232,86,207,61,79,67,45,58,230,190,181,74,65,148,71,243,246,67,142,60,61,92,58,115,240,226,171]
 stuffer = hashlib.md5(win_msg + tmp).digest()

 s = ''
 for x in range(len(stuffs)):
  s += chr(stuffs[x] ^ ord(stuffer[x % len(stuffer)]))
 if s.endswith('.com'):
  print s
  break
Flag 1mp0rt3d_pygu3ss3r@flare-on.com

Challenge #7 - hashes

The challenge is a x86 ELF (linux binary) developed in the go language. However unlike the standard go compiler gc, this has been compiled with gccgo and requires libgo.so.7 in order to be able to run. Now my local linux vm is ubuntu 14.04 and libgo7 is only available for ubuntu 16.04 and above. However I was not willing to download and install a complete new distro just for running this single binary. Hence a workaround was necessary. I powered on cloud9 vm, wgetted the deb directly bypassing the package manager. Although dpkg could not install the package, I got the much needed file libgo.so.7. Using it I could debug the binary in my local ubuntu 14.04 vm.

Fig 7 - Satisfying the dependencies
With that out of the picture, the objective of the challenge is to crack the SHA1 hash of the flag applied three times recursively. Since we know, that the flag ends in @flare-on.com, all that is required is to bruteforce the first few characters. Taking the good boy message "You have hashed the hashes" as a cue, I quickly brute forced the flag h4sh3d_th3_h4sh3s@flare-on.com

Challenge #8 - chimera

The name of the challenge immediately reminded me of the movie Mission: Impossible II wherein IMF agent Ethan Hunt must track and destroy a biological weapon Chimera along with its anti-dote Bellerophon and prevent it from being misused. While the actual challenge had nothing to do with the movie but certainly it was equally engrossing. Instead of the chimera virus, here we have an PE executable with a the relevant code hidden up the sleeves in the DOS stub. Once this is figured out, all that is left to disassemble the obfuscated 16 bit code to understand its workings. Dosbox along with its debugger proved much helpful in solving this problem. To get the flag I used the following script.
table = [255, 21, 116, 32, 64, 0, 137, 236, 93, 195, 66, 70,
192, 99, 134, 42, 171, 8, 191, 140, 76, 37, 25, 49,
146, 176, 173, 20, 162, 182, 103, 221, 57, 216, 95,
63, 123, 92, 194, 178, 246, 46, 117, 155, 97, 148, 207,
206, 106, 152, 80, 242, 91, 240, 69, 48, 14, 56, 235,
59, 108, 102, 127, 36, 61, 223, 136, 151, 185, 179,
241, 203, 131, 153, 26, 13, 239, 177, 3, 85, 158, 154,
122, 16, 224, 54, 232, 211, 228, 50, 193, 120, 7, 183,
107, 199, 112, 201, 44, 160, 145, 53, 109, 254, 115,
94, 244, 164, 217, 219, 67, 105, 245, 141, 238, 68,
125, 72, 181, 220, 75, 2, 161, 227, 210, 166, 33, 62,
47, 163, 215, 187, 132, 90, 251, 143, 18, 28, 65, 40,
197, 118, 89, 156, 247, 51, 6, 39, 10, 11, 175, 113,
22, 74, 233, 159, 79, 111, 226, 15, 190, 43, 231, 86,
213, 83, 121, 45, 100, 23, 149, 167, 189, 124, 29, 88,
147, 165, 101, 248, 24, 19, 234, 188, 229, 243, 55,
4, 150, 168, 30, 1, 41, 130, 81, 60, 104, 31, 142, 218,
138, 5, 34, 114, 73, 250, 135, 169, 84, 98, 198, 170,
9, 180, 253, 214, 209, 172, 133, 17, 71, 58, 157, 230,
77, 27, 204, 82, 128, 35, 252, 237, 139, 126, 96, 205,
110, 87, 186, 222, 174, 202, 196, 119, 12, 78, 212,
208, 200, 225, 184, 249, 38, 144, 129, 52]

target = [56, 225, 74, 27, 12, 26, 70, 70, 10, 150, 41, 115, 115, 164, 105, 3, 0, 27, 168, 248, 184, 36, 22, 214, 9, 203]

flag = map(ord, list('A'*26))

def rol(n):
 b = (n >> 7) & 1
 n = ((n << 1) | b) & 0xFF
 return n

def ror(n):
 b = n & 1
 n = ((n >> 1) | (b << 7)) & 0xFF
 return n 


def calc():
 for i in xrange(len(flag)-1, -1, -1):
  if i == len(flag) - 1:
   v1 = rol(rol(rol(0x97)))
  else:
   v1 = rol(rol(rol(flag[i+1])))

  v2 = table[v1]
  v2 = table[v2]

  flag[i] ^= v2  

 for i in xrange(len(flag)):
  if i == 0:
   flag[i] ^= 0xC5
  else:
   flag[i] ^= flag[i-1]

 print map(hex, flag)


def reverse():
 for i in xrange(len(target)-1, -1, -1):
  if i == 0:
   target[i] ^= 0xC5
  else:
   target[i] ^= target[i-1]

 for i in xrange(len(target)-1, -1, -1):
  if i == len(target) - 1:
   v1 = rol(rol(rol(0x97)))
  else:
   v1 = rol(rol(rol(save)))

  v2 = table[v1]
  v2 = table[v2]
  save = target[i]
  target[i] ^= v2 

 print ''.join(map(chr, target))


if __name__ == '__main__':
 reverse()
flag retr0_hack1ng@flare-on.com 


Challenge #9 - GUI

The challenge consists of a .net executable with ConfuserEx thrown in for a change. DnSpy along with NoFuserEx is sufficient to extract all the necessary strings for reconstructing back the shared secret.

Share:1-d8effa9e8e19f7a2f17a3b55640b55295b1a327a5d8aebc832eae1a905c48b64
Share:2-f81ae6f5710cb1340f90cd80d9c33107a1469615bf299e6057dea7f4337f67a3
Share:3-523cb5c21996113beae6550ea06f5a71983efcac186e36b23c030c86363ad294
Share:4-04b58fbd216f71a31c9ff79b22f258831e3e12512c2ae7d8287c8fe64aed54cd
Share:5-5888733744329f95467930d20d701781f26b4c3605fe74eefa6ca152b450a5d3
Share:6-a003fcf2955ced997c8741a6473d7e3f3540a8235b5bac16d3913a3892215f0a

Flag Shamir_1s_C0nfused@flare-on.com

Challenge #10 - flava

This was the final challenge, and is composed of many sub challenges. The first part requires to get through three layers of obfuscated javascript with an obfuscated Diffie Hellman (courtesy of Angler EK) for more distress. So unless, one figures out what the heck is with all the obfuscated javascript it is a dead end. Even if one manages to guess that, breaking the Diffie Hellman is more pain. Luckily, Kaspersky researches have already done the hard work before and it requires a bit of Googling to locate the code necessary to break the diffie hellman.
After three layers of javascript there are three more layers of actionscript. While the first layer is straightforward the second and third layers are obfuscated. The challenge in this part is to identify that the RC4 key is reused.  Once we know that, we can simply xor the plain text and ciphertext to get the keystream, and xor the resultant keystream with the second ciphertext to get back the plain text. The third actionscript layer simply prints the flag angl3rcan7ev3nprim3@flare-on.com

Final Words

Overall, the challenges this year were certainly more difficult than those of the preceding year. Some parts required bruteforcing hashes and guesswork which I detest. Another point of notice is that there were no 64 bit binaries. There were also no challenges involving kernel drivers. Finally, I would like to extend my thanks to everyone who helped me through the course of the challenges.

Monday, 7 November 2016

Hack the Vote 2016 CTF - APTeaser writeup


Just for fun I decided to have a go at the Hack the Vote 2016 CTF, particularly the reversing challenges on Windows. There were two of them APTeaser & Trumpervisor. I managed to solve the first. I did try the second but it involved reversing a Win 10 kernel driver implementing a hypervisor using the Intel Virtualization Extensions (VT-x). Anyway, here is a somewhat detailed writeup for the first.

Initial Analysis

The provided file is a pcapng. Opening it in fiddler, reveals an interesting http request for a supposed pdf file on the domain important.documents.trustme, but as indicated from the Content-Type the response is actually an executable.

Serving an executable when all I want is a pdf
Fig 1: Serving an executable when all I want is a pdf
This can be further verified in wireshark as shown in Fig 2.

Cross checking in wireshark
Fig 2: Cross checking in wireshark
We can save the response to a new file for further analysis. As expected the the file has a pdf icon and a dual extension to pass off as an innocuous pdf, waiting to be clicked.

Fig 3: An exe with a pdf icon and dual extensions

Dissecting the executable

The executable in question is a screen grabber. It takes screenshot of the desktop at regular intervals, saves to a jpeg file, "encrypts" the file, and sends it to a remove server. We can decompile it in hex-rays to get the following pseudo code.
int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v4; // [sp+0h] [bp-2Ch]@1
  int v5; // [sp+10h] [bp-1Ch]@1
  int x; // [sp+14h] [bp-18h]@1
  int y; // [sp+18h] [bp-14h]@1
  int x1; // [sp+1Ch] [bp-10h]@1
  int y1; // [sp+20h] [bp-Ch]@1
  SOCKET sock; // [sp+24h] [bp-8h]@2
  int i; // [sp+28h] [bp-4h]@1

  sub_401BF0(0, 0, 0);
  GdiplusStartup(&v5, &v4, 0);
  x1 = 0;
  y1 = 0;
  x = GetSystemMetrics(SM_CXSCREEN);
  y = GetSystemMetrics(SM_CYSCREEN);
  i = 0;
  do
  {
    sock = create_socket();
    if ( sock == SOCKET_ERROR )
    {
      ++i;
      Sleep(300u);
    }
    else
    {
      i = 0;
      take_screenshot(x1, y1, x - x1, y - y1);
      send_file(sock, "a");
      destroy_socket(sock);
    }
  }
  while ( i < 5 );
  GdiplusShutdown(v5);
  return 0;
}

As shown in the preceding snippet, it takes screencaps at regular intervals, and retrying for 5 times if socket creation fails. To get a better overview of the network traffic, we can analyse it using FakeNet-NG an excellent dynamic network analysis tool from Fireeye.

A quick overview of the network traffic

FakeNet-NG capturing the outbound requests
Fig 4: FakeNet-NG capturing the outbound requests
FakeNet-NG is an immensely helpful tool for dealing with malware/apps that uses the internet for communication. While tools like wireshark can only capture the traffic, fakenet additionally, also has the ability to mimic/emulate/tamper the responses via custom listeners implemented as plugins. On this particular sample, it has redirected an outbound request to 128.213.48.117:27015 to its default tcp listeners. Additionally, the name/pid of the application that initiated the request is also shown. The next point of interest the data that is actually being sent. It starts with the hex bytes 80 F4 FF E0. Now, a jpeg starts with FF D8 FF E0. Similarly the next 4 bytes, 43 4F 4A 46 bear strong resemblance to the true jpg header bytes xx xx 4A 46. From this, it can be easily deduced that a jpeg is being sent after applying some sort of "encryption" on the first two bytes of each dword.

The encryption algorithm

The encrypting functionality is implemented in the function send-file and is the subject of further analysis. The snippet of code that deals with the encryption is as follows.

  completed = 0;
  blocksize = 0;
  while ( completed < filesize )
  {
    seed = get_time(0);
    srand(seed);
    if ( filesize - completed < 2048 )
      blocksize = filesize - completed;
    else
      blocksize = 2048;
    for ( i = 0; i < blocksize / 4; ++i )
    {
      randnum = rand();
      if ( !i )
      {
        xored_val = randnum ^ *(jpeg_buf + completed);
        v4 = std::basic_ostream<char,std::char_traits<char>>::operator<<(std::cerr, randnum, sub_403880, " ", *(jpeg_buf + completed), " ");
        v5 = std::basic_ostream<char,std::char_traits<char>>::operator<<(v4);
        v6 = sub_401040(v5, xored_val);
        v7 = std::basic_ostream<char,std::char_traits<char>>::operator<<(v6, sub_401680, v13, *&v14, v15, v16);
        v9 = sub_401040(v7, v8);
        v11 = std::basic_ostream<char,std::char_traits<char>>::operator<<(v9, v10, *&v14, v15, v16, v17);
        std::basic_ostream<char,std::char_traits<char>>::operator<<(v11);
      }
      *(jpeg_buf + 4 * i + completed) ^= randnum;
    }
    send(sock, jpeg_buf + completed, blocksize, 0);
    completed += blocksize;
    Sleep(Seed * completed % 3600);
  }

The code initializes the random number using the current time as a seed to the function srand. Then it begins to xor the jpeg 4 bytes at a time with the generated random number in blocks of 2048 bytes, i.e it uses a new random number after every 2048 bytes. The range of the function rand lies between 0 and 32767 (0x7FFF). The upper two bytes are always zero. This explains the reason behind the fact that for every 4 bytes of the encrypted data, 2 bytes were always left unencrypted, as was found in fakenet.

Breaking the crypto

To break the crypto, we need to predict the generated random number, which depends on the seed used. The seed in turn is just the current time in epochs. Now each captured packet has a timestamp, we can use that value as a seed to srand to regenerate the exact same sequence of random numbers.

First we need to get the timestamps of the relevant packets. This can be done by setting a filter and exporting the resultant packets to a new pcap file as shown in Fig. 5
Fig 5: Applying a display filter in wireshark
Then a python script to get the timestamps and to carve out the jpeg.
import pyshark
import cStringIO

cap = pyshark.FileCapture('filtered.pcap')
buf = cStringIO.StringIO()
rand_seeds = []

for pkt in cap:
    buf.write(pkt.data.data.decode('hex')) # pkt.layers[3].data
    rand_seeds.append(int(float(pkt.frame_info.time_epoch))) 

open('encrypted.jpg', 'wb').write(buf.getvalue())
print rand_seeds

Once we have the encrypted jpeg and the seed values, we can create the decrypter in C.
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

void main()
{
 int rand_seeds[] = {1460329071, 1460329074, 1460329077, 1460329080, 1460329084, 
  1460329084, 1460329087, 1460329090, 1460329091, 1460329093, 1460329096, 
  1460329100, 1460329102, 1460329105, 1460329109, 1460329111, 1460329112, 
  1460329114, 1460329115, 1460329117, 1460329121, 1460329121, 1460329123, 
  1460329125, 1460329128, 1460329131, 1460329133, 1460329135, 1460329136, 
  1460329140, 1460329141, 1460329142, 1460329145, 1460329148, 1460329150, 
  1460329154, 1460329154, 1460329154, 1460329158, 1460329158, 1460329160, 
  1460329161, 1460329161, 1460329165, 1460329165, 1460329167, 1460329168, 
  1460329170, 1460329171, 1460329172, 1460329173, 1460329174, 1460329175, 
  1460329178, 1460329180, 1460329182, 1460329182, 1460329184, 1460329185, 
  1460329186, 1460329187, 1460329190, 1460329191, 1460329192, 1460329194, 
  1460329197, 1460329197, 1460329198, 1460329199, 1460329200, 1460329202, 
  1460329202, 1460329203, 1460329203, 1460329205, 1460329207, 1460329210, 
  1460329210, 1460329213, 1460329215, 1460329217, 1460329218, 1460329220, 
  1460329220, 1460329222, 1460329225, 1460329227, 1460329230, 1460329232, 
  1460329234};

 FILE *inf = fopen("encrypted.jpg", "rb");
 FILE *outf = fopen("decrypted.jpg", "wb");
 fseek(inf, 0, SEEK_END);
 long size = ftell(inf);
 rewind(inf);

 for (int i = 0; i < 90; i++)
 {
  srand(rand_seeds[i]);
  for (int j = 0; j < (size < 2048?size/4:2048/4); j++)
  {
   unsigned int data;
   fread(&data, 4, 1,  inf);
   data ^= rand();
   fwrite(&data, 4, 1, outf);
  }
  size -= 2048;
 }
 getch();
}

Running this we get the decrypted jpeg as shown in Fig 6. The flag is flag{1_n33d_my_t00Lb4r5}.

Fig 6: The flag


Sunday, 30 October 2016

A punched card reader in javascript

While trying out the Ektoparty CTF 2016 there was a challenge which requires to decode a series of punched card images. A punched card looks like this

A Punched Card
Fig 1: A sample punch card
The small white blocks denote the punch. All of the card images were specifically generated by an online service - Card punch. However, on searching for a tool which reads such images, I found nothing, hence I developed a small web app which can read in these punched card images. Please do note the card image must have an exact dimensions of 588 x 264 or else the tool wont work. You can try out the tool here or below. The source is on github.

Wednesday, 7 September 2016

Pyinstaller Extractor updated to v1.6

PyInstaller Extractor is a tool to extract the contents of a windows executable file created by pyinstaller. This weekend I updated the tool to version 1.6. The new features which were incorporated include

  • Support for extracting pyinstaller 3.2
  • Extractor would now use a random name for extracting unnamed files within the CArchive
  • Preliminary support for handling encrypted pyz archives
The features are explained below.

Support for extracting pyinstaller 3.2

There has not been any format changes between pyinstaller 3.2 and the earlier versions. The previous versions works as is for pyinstaller 3.2

Handling unnamed files within CArchive

A Pyinstaller exe file can be visualized as of two nested archives. The outer layer is called CArchive. It is called so as it handled by C code i.e. the decompression of the layer is handled by a native stub written in C. The CArchive in turn contain another archive called PYZArchive along with other files. The PYZArchive is usually zlib compressed and is handled by python code and hence the reason for its name.

The CArchive usually contains the main script along with necessary dll files and python extension modules (pyd files). When running an pyinstaller exe, all dll and pyd files are written to a temporary directory to facilitate loading. (This behaviour is noticeably different from py2exe which loads dlls from memory.) The main script is never written to disk and hence it is possible to remove its name. If such is the case then the earlier versions of extractor would fail. The current version 1.6 will use a random name if it finds any unnamed files.

This feature has mainly been inspired while working on the PAN LabyREnth challenge (Threat #7).

Preliminary support for handling encrypted pyz archives

The files within the PYZ archive can be encrypted too. If such is the case, the tool would dump those files as is without attempting to process them. Previously the tool would fail trying to decompress encrypted data.

That's it. I would make a separate post to demonstrate how to extract encrypted pyz archives. It isn't difficult as the key to decrypt is present right in the CArchive.

Saturday, 20 August 2016

LabyREnth CTF WriteUp - Random track


Attempting the Labyrenth challenges was an interesting experience. I completed three tracks - Windows, Docs & Random, and the others were left halfway. Among all the tracks, the random track was more interesting particularly due to the last python challenge.

Level 1 - Java

The challenge consists of a jar file. So it seems, we have to reverse java bytecode. The interesting thing is the jar will only run with Java 9 (currently in beta) as it uses StringConcatFactory. Attempting to decompile the file with Jad, Procyon, or CFR fails. This is due the fact it uses a new opcode InvokeDynamic. This is a fairly new opcode and as of now, the java compiler does not emit this opcode. It exists to support other dynamic languages running on the JVM. 

Only krakatau was able to decompile the file proper, although it too doesn't handle the InvokeDynamic opcode.
public class omg {
    String username;
    String levelFlag;
    
    public omg(String s)
    {
        super();
        this.levelFlag = "W5SSA2DPOBSSA6LPOUQGK3TKN54SA5DINFZSASTBOZQSAYLQOAQGC4ZAO5QXE3JNOVYC4ICUNBSSA4TFON2CA53JNRWCAYTFEBWXKY3IEBWW64TFEBZWK6DDNF2GS3THEEQFI2DFEBTGYYLHEBUXGICQIFHHWRBQL5MTA5K7IV3DG3S7IJQXGZJTGJ6Q!";
        this.username = s;
        if (s.contains((CharSequence)(Object)"-isDrunk"))
        {
            String[] a = s.split("-");
            int i = a[1].charAt(2);
            int i0 = Character.toUpperCase((char)i);
            int i1 = (char)(i0 ^ 15);
            this.levelFlag = /*invokedynamic*/null;
            StringBuilder a0 = new StringBuilder(this.levelFlag);
            int i2 = 0;
            while(i2 < 4)
            {
                Object[] a1 = new Object[1];
                int i3 = a[1].charAt(a[1].length() - 1);
                int i4 = (short)i3;
                a1[0] = Short.valueOf((short)i4);
                int i5 = (char)(Integer.parseInt(String.format("%04x", a1), 16) ^ 166);
                a0.append((char)i5);
                i2 = i2 + 1;
            }
            System.out.println(a0.toString());
            this.levelFlag = a0.toString();
        }
        else
        {
            int i6 = 0;
            while(i6 < s.length() / 2)
            {
                String s0 = this.levelFlag;
                int i7 = s.charAt(i6);
                int i8 = s.charAt(s.length() - 1);
                this.levelFlag = s0.replace((char)i7, (char)i8);
                i6 = i6 + 1;
            }
        }
    }
    
    public String getLevelFlag()
    {
        return this.levelFlag;
    }
    
    public static void main(String[] a)
    {
        omg a0 = new omg(System.getenv("Admin"));
        System.out.println(/*invokedynamic*/null);
    }
}
There is a whole bunch of decoy code. The actual flag  can be found by base32 decoding the levelFlag: 

W5SSA2DPOBSSA6LPOUQGK3TKN54SA5DINFZSASTBOZQSAYLQOAQGC4ZAO5QXE3JNOVYC4ICUNBSSA4TFON2CA53JNRWCAYTFEBWXKY3IEBWW64TFEBZWK6DDNF2GS3THEEQFI2DFEBTGYYLHEBUXGICQIFHHWRBQL5MTA5K7IV3DG3S7IJQXGZJTGJ6Q

Fig 1: Level 1 flag
This gives our flag: PAN{D0_Y0u_Ev3n_Base32}


Level 2 - Regex

This challenge looks scary at first sight. A regular expression is given. Our task is to find a string that does not match the regex. Netcatting the string to 52.27.101.106 would give the flag.

Fig 2: That looks scary, doesn't it?
The regex seems to match everything ever thrown at it. It has 625 clauses making it unfit for manual analysis. A regex debugger like RegexBuddy or regex101 is handy for such situations.

Lets look at the clause 1: .*[^0mglo8sc1enC3].*

This matches a single character unlimited number of times followed by a character which is not in the negation list, finally followed by a character unlimited number of times. Hence any string consisting of only characters present in the negation list will not match this clause.

Clause 2: .{,190}
Clause 3: .{192,}

The 2nd clause matches any string of length 190 or lower. The 3rd clause matches any string of length 192 or above. Combining these two clauses, for a non match our string should exactly 191 characters drawn from the list in clause 1.

The remaining clauses worth of interest is clause 124 and 341.
Clause 124
Fig 3: Clause 124
Clause 341
Fig 4: Clause 341
Clause 124 matches a string of length 190 chars followed by one of e0nlCo3c8. Similarly clause 341 matches a string of length 190 followed by one of mg1.

Combining the above clauses the string which does not match the regex consists of 190 g followed by a solitary s.
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggs

Netcatting this to 52.27.101.106 gives the flag PAN{th4t5_4_pr311y_dum8_w4y_10_us3_r3g3x}

Fig 5: Level 2 flag

Level 3 - Pcap

A pcap file is provided. Loading it in Wireshark reveals something interesting with the tcp sequence number of the SYN packets. The sequence numbers starts with PK\03\04 which is also the magic signature for zip files. We can set a display filter will only display the SYN packets. The same can be used to save the filtered packets to a new pcap file.

ZIP signature in tcp sequence number
Fig 6: ZIP signature in tcp sequence number
To assemble zip file by combining the sequence number, we can use scapy.
from scapy.all import *
from binascii import unhexlify
import cStringIO

def main():
    buf = cStringIO.StringIO()
    with PcapReader('SYN-filtered.pcap') as pcap_reader:
        for pkt in pcap_reader:                                 
                buf.write(unhexlify(format(pkt.seq, 'x').zfill(8)))
    open('extracted.zip', 'wb').write(buf.getvalue())   
            
if __name__ == '__main__':
    main()

This creates a new file extracted.zip. This zip contains 853 files each containing base64 encoded text.

Contents of zip file
Fig 7: Contents of zip file
Our task is to join the files in the correct order to form a huge base64 text blob. Decoding that text blob should give us our flag. The padding character used in base64 is =. Grepping for the = character within the extracted BIN files gives one hit 339.bin. This should therefore be the last file in the combined blob.
339.bin
Fig 8: 339.bin
The other point to note is that the contents of the files overlap as in Fig 9 showing the overlapped part of 531.bin with 339.bin.

Overlapped part
Fig 9: Overlapped part
We can write a python script which would find the order of assembling the files by searching for the overlapped part.
import re

def findMatch(dct, txt):
    for i in xrange(len(txt)-1, 0, -1):
        reg = re.compile(re.escape(txt[0:i])+'$')

        for key in dct.keys():
            if reg.search(dct[key]):
                return (key, i)

    return (None, -1)


def main():
    contents = dict()

    for i in xrange(853):
        fname = '%d.txt' %i
        txt = open(fname).read()
        contents[fname] = txt

    nm = '339.txt'
    print nm

    while True:
        txt = contents[nm]
        result, matchlen = findMatch(contents, txt)

        if result == None:
            break
            
        print result, matchlen
        del contents[nm] 
        nm = result


if __name__ == '__main__':
    main()
Running this gives the order of joining the files in reverse i.e the first line (339.txt) is the last file and the line (659.txt) is the first file. Each line contains two comma separated values. The second value is the number of overlapping characters. The full list is available as a gist.

Based on the join order, another python script can assemble the files.
f = open('combined.txt', 'w')
lines = open('random-lev3-joinorder.txt', 'r').readlines()

try:
    for line in reversed(lines):
        fname, matchlen = line.split(' ')
        matchlen = int (matchlen)

        txt = open(fname, 'r').read()
        f.write(txt[0:len(txt)-matchlen])

except:
    f.write(open('339.txt', 'r').read()) # last file has no overlap

f.close()
The assembled file, combined.txt is a base64 text blob. Decoding it results in a zip file. The zip file has several images within.
One of them troll_cloud.png contains the flag:  PAN{YouDiD4iT.GREATjob}
Level 3 flag
Fig 10: Level 3 flag

Level 4 - PHP

The challenge consists of solving a maze. The maze is coded in PHP and is additionally heavily obfuscated. For running this, I had to set up wamp server in my windows virtual machine. The actual php code which we are after is dynamically generated and eval'd. Getting around this obfuscation was easy as PHP was configured with display errors to be true. This made it to spit out the eval'd php code as a warning message.

Dynamically generated php code
Fig 11: Dynamically generated php code
To copy the de-obfuscated php code, we need to use a tool like fiddler. We cannot directly copy the php code from the warning message as the characters are not escaped properly. The deobfuscated source can be found here. From this point it is a matter of manual source code analysis to find the correct path for solving the maze. Solving the maze gives the flag:
 PAN{Life is a maze of complications. Also, puppets are sometimes involved. Deal with it.}

Fig 12: Level  4 flag

Level 5 - Python

Level 5 challenge - Crack APT Maker Pro
Fig 13: Level 5 challenge - Crack APT Maker Pro
This the final challenge in the Random track and is the most interesting. As the description of the challenge points out we really "have to be a snake charmer to crack the newest version of APT Maker Pro". The file is a 720 KB python script which contains a zlib compressed marshalled code object which is dynamically executed by the exec statement as shown in Fig 14.

Dynamically executed payload
Fig 14: Dynamically executed payload
To proceed, we need the decompiled payload from the compressed code object. This is easy and my tool Easy Python Decompiler is sufficient for the task. First, decompress the zlib data into a new file, add the python magic header 03 F3 0D 0A 00 00 00 00 at the beginning, and finally feed it to the decompiler to get our decompiled source as shown in Fig 15.

Decompiled payload
Fig 15: Decompiled payload
However that is not all. The decompiled payload contains a base64 encoded, zlib compressed code object which is executed by the exec statement just like the previous case. In addition to this there is a piece of RC4 encrypted data labelled as malware as shown in Fig 16. Thus the actual challenge is to find the correct RC4 decryption key. To find the key, we need to inspect the second level payload just found.
Fig 16: The malware blob
The difficulty at this stage increases rapidly. We cannot decompile the second level payload as it has been obfuscated. A deep knowledge about CPython internals is necessary to proceed forward. As I said, the payload is no longer decompilable, hence we need to inspect it manually. Let's inspect the code object.
>>> import marshal
>>> f = open('level2.pyc', 'rb')
>>> f.seek(8)
>>> co = marshal.load(f)
>>> co.co_consts
(<code object verify_license at 00AAB2F0, file "", line -1>, None)
The code object contains another nested code object verify_license which sounds interesting. Lets dump it to a new file.
>>> of = open('level3.pyc', 'wb')
>>> of.write('\x03\xF3\x0D\x0A' + '\x00' * 4)
>>> marshal.dump(co.co_consts[0], of)
>>> of.close()

Now we need to analyze 3rd level payload level3.pyc. Similar to level2.pyc this is too obfuscated and undecompileable. Lets run some preliminary analysis.
>>> f = open('level3.pyc', 'rb')
>>> f.seek(8)
>>> co=marshal.load(f)
>>> len(co.co_consts)
37173
>>> len(co.co_names)
37124
>>> len(co.co_code)
144060
That's more than 37k constants and names!. In addition the size of bytecode instructions that gets actually executed is over 144k. Thats insane!. Who would like to analyze such a file manually unless one have tools and luckily we do have tools. Out of the 37173 constants, 37121 just store the None type and is redundant. We can write a quick python script for finding this.
>>> for i in xrange(len(co.co_consts)):
...     if co.co_consts[i] is not None:
...             print i
...             break
...
37121
The 37122th constant stores a png file which looks interesting.
>>> co.co_consts[37122][:6]
'\x89PNG\r\n'
Fig 17: Embedded PNG file
The remaining constants store various integers and are not of much interest. Lets shift our focus to the 144k long co_code. Lets disassemble the very first instruction,
>>> import opcode
>>> opcode.opname[ord(co.co_code[0])]
'EXTENDED_ARG'

That's the EXTENDED_ARG opcode. In normal python, it is very rare to encounter this opcode. This is only generated if the operand of the instruction cannot fit in a space of 2 bytes. This can happen in rare situations such as passing more than 65,535 parameters to a function. The actual opcode on which EXTENDED_ARG is operating on is located at a offset of +3. Lets see what it is.
>>> opcode.opname[ord(co.co_code[3])]
'EXTENDED_ARG'
That's even more strange. We expected to see a real opcode here. If we continue this way, we will see a huge chain of EXTENDED_ARG opcodes and the final instruction which it is operating on is a JUMP_FORWARD which as the name suggests increments the IP by an offset.
>>> opcode.opname[ord(co.co_code[144051])]
'EXTENDED_ARG'
>>> opcode.opname[ord(co.co_code[144054])]
'EXTENDED_ARG'
>>> opcode.opname[ord(co.co_code[144057])]
'JUMP_FORWARD'

To find out the target offset of the jump we need to write a python script.
import marshal

f=open('level3.pyc', 'rb')
f.seek(8)
co=marshal.load(f)
f.close()

i = 0
arg = 0
while i < len(co.co_code):
 arg = (arg << 16) | ord(co.co_code[i+1]) | (ord(co.co_code[i+2]) << 8)
 arg = arg & 0xFFFFFFFF  
 i += 3

print hex(arg)
Running this gives us the target offset which is 0xfffdcd45 or -1,44,059. That is instead of jumping forward it jumps backward within the instruction stream. The obfuscation that is applied is akin to overlapping instruction obfuscation found in native x86 executables.

Now the size of the instruction stream (co_code) is 144060 and a 144059 long backward jump from the rear leads to the second byte. If we disassemble this we uncover a hidden series of instructions stitched together with JUMP_FORWARDs.
>>> opcode.opname[ord(co.co_code[1])]
'LOAD_NAME'
>>> opcode.opname[ord(co.co_code[4])]
'NOP'
>>> opcode.opname[ord(co.co_code[5])]
'JUMP_FORWARD'

We need to uncover this hidden instructions, join them as one after removing the NOP and JUMP_FORWARD instructions used for stitching them. Another python script to the rescue.
# level3 extract code

import marshal
import opcode
import types

cleaned_bytecode = []


def clean(opkode, arg1, arg2):
    if opcode.opname[opkode] == 'JUMP_FORWARD' or opcode.opname[opkode] == 'NOP':
        return

    else:
        if opkode >= opcode.HAVE_ARGUMENT:
            cleaned_bytecode.append(opkode)
            cleaned_bytecode.append(arg1)
            cleaned_bytecode.append(arg2)
        else:
            cleaned_bytecode.append(opkode)


def printline(offset, opname, arg):
    if opname == 'JUMP_FORWARD' or opname == 'NOP':
        return
    if arg is not None:
        print 'loc_%06d: %s %d' %(offset, opname, arg)
    else:
        print 'loc_%06d: %s' %(offset, opname)


def modifyCodeStr(code_obj):
    co_argcount = code_obj.co_argcount
    co_nlocals = code_obj.co_nlocals
    co_stacksize = code_obj.co_stacksize
    co_flags = code_obj.co_flags

    # new code string
    co_codestring = ''.join(map(chr, cleaned_bytecode))

    # Replace png file contents to facilitate decompiling
    co_constants = list(code_obj.co_consts)
    co_constants[37122] = 'PNG FILE HERE'
    co_constants = tuple(co_constants)

    co_names = code_obj.co_names
    co_varnames = code_obj.co_varnames
    co_filename = code_obj.co_filename
    co_name = code_obj.co_name
    co_firstlineno = code_obj.co_firstlineno
    co_lnotab = code_obj.co_lnotab

    return types.CodeType(co_argcount, co_nlocals, co_stacksize, \
                          co_flags, co_codestring, co_constants, co_names, \
                          co_varnames, co_filename, co_name, co_firstlineno, co_lnotab)

def main(): 
    f=open('level3.pyc', 'rb')
    f.seek(8)
    co=marshal.load(f)
    f.close()
    kode = map(ord, list(co.co_code))
    offset = 1

    while offset < len(kode):
        opkode = kode[offset]
        opname = opcode.opname[opkode]

        if opkode >= opcode.HAVE_ARGUMENT:
            arg1 = kode[offset+1]
            arg2 = kode[offset+2]
            arg = (arg2 << 8) | arg1 # Little endian
            printline(offset, opname, arg)
            offset += 3

        else:
            arg = arg1 = arg2 = None
            printline(offset, opname, arg)
            offset += 1

        clean(opkode, arg1, arg2)

        if opname == 'JUMP_FORWARD':
            offset += arg

        elif opname == 'RETURN_VALUE':
            break

    newCodeObj = modifyCodeStr(co)
    f = open('level3_deobf.pyc', 'wb')
    f.write('\x03\xF3\x0D\x0A' + '\x00'*4)
    marshal.dump(newCodeObj, f)
    f.close()


if __name__ == '__main__':
    main()

The hidden instruction stream can be found here. The python script above stitches the hidden code and replaces the PNG file contents with a dummy string to facilitate decompiling, else decompiler would choke. Lets decompile the produced level3_deobf.pyc selecting pycdc as the engine. It gives the following code.
# File: l (Python 2.7)

   = license_key[0]
    = 'PNG FILE HERE'[542]
exec       =    ==    

   = license_key[1]
    = 'PNG FILE HERE'[379]
exec       =    ==    

   = license_key[2]
    = 'PNG FILE HERE'[1020]
exec       =    ==    

   = license_key[3]
    = 'PNG FILE HERE'[457]
exec       =    ==    

   = license_key[4]
    = 'PNG FILE HERE'[203]
exec       =    ==    

   = license_key[5]
    = 'PNG FILE HERE'[203]
exec       =    ==    

   = license_key[6]
    = 'PNG FILE HERE'[39]
exec       =    ==    

   = license_key[7]
    = 'PNG FILE HERE'[379]
exec       =    ==    

   = license_key[8]
    = 'PNG FILE HERE'[65]
exec       =    ==    

   = license_key[9]
    = 'PNG FILE HERE'[54]
exec       =    ==    

   = license_key[10]
    = 'PNG FILE HERE'[379]
exec       =    ==    

   = license_key[11]
    = 'PNG FILE HERE'[40]
exec       =    ==    

   = license_key[12]
    = 'PNG FILE HERE'[262]
exec       =    ==    

   = license_key[13]
    = 'PNG FILE HERE'[54]
exec       =    ==    

   = license_key[14]
    = 'PNG FILE HERE'[379]
exec       =    ==    

   = license_key[15]
    = 'PNG FILE HERE'[250]
exec       =    ==    

   = license_key[16]
    = 'PNG FILE HERE'[704]
exec       =    ==    

   = license_key[17]
    = 'PNG FILE HERE'[1110]
exec       =    ==    

   = license_key[18]
    = 'PNG FILE HERE'[141]
exec       =    ==    

   = license_key[19]
    = 'PNG FILE HERE'[379]
exec       =    ==    

   = license_key[20]
    = 'PNG FILE HERE'[65]
exec       =    ==    

   = license_key[21]
    = 'PNG FILE HERE'[54]
exec       =    ==    

   = license_key[22]
    = 'PNG FILE HERE'[285]
exec       =    ==    

   = license_key[23]
    = 'PNG FILE HERE'[1215]
exec       =    ==    

   = license_key[24]
    = 'PNG FILE HERE'[840]
exec       =    ==    

  =   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   &  

The variable names are missing, but it is fairly evident what the code does. It compares the characters of the license key with some bytes of the PNG file. For success, each of these checks must succeed. Joining the characters we get the  license key 1_W4nnA_b3_Th3_vERy_b3ST!. Feeding this, APT Maker Pro becomes registered as shown in Fig 18.

APT Maker Pro is licensed
Fig 18: APT Maker Pro is licensed
Clicking on Generate APT drops the malware payload as EVIL_MALWARE_ CYBER_PATHOGEN .pyc. Decompiling it we get the file containing the flag for this level 
PAN{l1Ke_n0_oN3_ev3r_Wa5}

Fig 19: The flag

Tuesday, 16 August 2016

Solving the weasel keygenme by kao


Over at tuts4you kao posted a nice .net keygenme. The ultimate goal is developing a keygen which can generate keys for any name within a second.

Know thy goal
Fig 1: Know thy goal

Although the post is titled as "Solving the weasel keygenme", I did not get that far as developing a working keygen as required for the much coveted gold medal. However, the algorithm that kao implements is quite interesting to document and that is the reason for this blog post.

Solving the keygenme consists of two parts -- First to devirtualize the virtual machine and second to reverse the crypto.

De-virtualizing the VM


Dropping the file in dnSpy, reveals that method and variable names have been removed as in Fig 2.

Wazzup with those names?
Fig 2: Wazzup with those names?
The obfuscation can be removed by processing the file with de4dot which leads to a slightly better readable code as in Fig 3.

Not anonymous anymore
Fig 3: Not anonymous anymore
Now with the obfuscation out of the way, it's time to deal with the vm. A vm based software protection works by transforming the original instructions to a set of new instruction which only a custom vm understands. Executing the new set of instructions under the supervision of the vm is expected to produce the same output as executing the original instructions without the vm. As regards to the implementation of a vm this keygenme is also no different.

The virtual machine is implemented in a class named SillyVM. The constructor of this class initializes the opcode handler table as shown in Fig 4. There are 16 instructions that the vm understands.

Initializing the vm
Fig 4: Initializing the vm
Immediately, after setting up the opcode handler table the constructor initializes an array which contains the actual instructions of the vm as shown in Fig 5.
The instructions of the vm
Fig 5: The instructions of the vm
The next task is to understand the semantics of each of the 16 handlers. This is a manual task but it cannot be avoided. Understanding the operation of the handlers is crucial in comprehending the operation of the vm. Luckily, this is not a too difficult task, as the handlers are short and simple. The handlers can then be renamed as per their semantics. As shown in Fig 6, we have renamed three of the handlers to JumpIfLess, JumpIfZero, Multiply.

Renaming the handlers
Fig 6: Renaming the handlers
The complete set of handlers along with their associated semantics is listed in the following table.

INSTRUCTION OPCODE FORMAT SEMANTICS
Add 0 Add b1, b2 arr[b2] += arr[b1]
JumpIfEqual 1 JumpIfEqual b1, b2, b3 If (arr[b1] == b2) then IP = b3
NewBitArray 2 NewBitArray b1, b2 bitarr[b1] = new BitArray(b2)
JumpIfLess 3 JumpIfLess b1, b2, b3 If (arr[b1] < b2) then IP = b3
JumpIfLargePassw 4 JumpIfLargePassw b1, b2 If (arr[b1] < passw.Length) then IP = b2
Jump 5 Jump b1 IP = b1
JumpIfZero 6 JumpIfZero b1, b2 If (arr[b1] == 0) then IP = b2
BitToInt 7 BitToInt b1, b2, b3 arr[b3] = (bitarr[b1][arr[b2]] == true ? 1 : 0)
Increment 8 Increment b1 arr[b1]++
IndexOf 9 IndexOf b1, b2 arr[b2] = hardc.IndexOf(passw[arr[b1]])
SumNumOne 10 SumNumOne b1, b2 arr[b2] = arr[b1] + 1
Multiply 11 Multiply b1, b2 arr[b2] *= arr[b1]
BitArrayCopy 12 BitArrayCopy b1 bitarr[b1].CopyTo(ans)
IntToBit 13 IntToBit b1, b2, b3 bitarr[b1][arr[b2]] = arr[b3] & 1
RShr 14 RShr b1 arr[b1] >>= 1
SetZero 15 SetZero b1 arr[b1] = 0

As per the above table, we can code a disassembler in python which takes in the instruction list and emits the de-virtualized C# code.
instr = [2,2,56,15,41,15,15,5,36,9,15,8,1,8,255,34,15,1,
5,30,13,2,41,8,8,41,14,8,8,1,3,1,5,20,8,15,4,15,
9,2,1,40,15,61,15,55,15,24,5,134,7,0,61,36,8,61,
15,18,5,78,7,0,61,19,6,19,74,7,2,18,19,0,19,36,8,
61,8,18,3,18,50,60,15,11,5,122,10,11,47,5,116,7,0,
61,19,6,19,112,7,2,11,19,7,2,47,57,11,19,57,0,57,
36,8,61,8,47,3,47,50,91,8,11,3,11,49,86,13,1,55,
36,8,55,8,24,3,24,40,50,12,1]


def disassemble():
 ip = 0
 while ip < len(instr):
  opcode = instr[ip]
  print 'loc_%03d:\t' %(ip),
  ip += 1

  # Add
  if opcode == 0:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'arr[%d] += arr[%d];' %(b2, b1)
   
  # JumpIfEqual
  elif opcode == 1:
   b1 = instr[ip]
   b2 = instr[ip+1]
   b3 = instr[ip+2]
   ip += 3
   print 'if (arr[%d] == (int)((sbyte)%d)) goto loc_%03d;' %(b1, b2, b3)

  # NewBitArray
  elif opcode == 2:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'bitarr[%d] = new BitArray(%d);' %(b1, b2)
  
  # JumpIfLess
  elif opcode == 3:
   b1 = instr[ip]
   b2 = instr[ip+1]
   b3 = instr[ip+2]
   ip += 3
   print 'if ((long)arr[%d] < (long)((ulong)%d)) goto loc_%03d;' %(b1, b2, b3)
  
  # JumpIfLargePassw
  elif opcode == 4:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'if (arr[%d] < password.Length) goto loc_%03d;' %(b1, b2)

  # Jump
  elif opcode == 5:
   b1 = instr[ip]
   ip += 1
   print 'goto loc_%03d;' %(b1)

  # JumpIfZero
  elif opcode == 6:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'if (arr[%d] == 0) goto loc_%03d;' %(b1, b2)

  # BitToInt
  elif opcode == 7:
   b1 = instr[ip]
   b2 = instr[ip+1]
   b3 = instr[ip+2]
   ip += 3
   print 'arr[%d] = (bitarr[%d][arr[%d]] == true ? 1:0);' %(b3, b1, b2)

  # Increment
  elif opcode == 8:
   b1 = instr[ip]
   ip += 1
   print 'arr[%d]++;' %(b1)

  # IndexOf
  elif opcode == 9:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'arr[%d] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[arr[%d]]);' %(b2, b1)

  # SumNumOne
  elif opcode == 10:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'arr[%d] = arr[%d] + 1;' %(b2, b1)

  # Multiply
  elif opcode == 11:
   b1 = instr[ip]
   b2 = instr[ip+1]
   ip += 2
   print 'arr[%d] *= arr[%d];' %(b2, b1)

  # BitArrayCopy
  elif opcode == 12:
   b1 = instr[ip]
   ip += 1
   print 'bitarr[%d].CopyTo(ans, 0);' %(b1)

  # IntToBit
  elif opcode == 13:
   b1 = instr[ip]
   b2 = instr[ip+1]
   b3 = instr[ip+2]
   ip += 3
   print 'bitarr[%d][arr[%d]] = ((arr[%d] & 1) != 0);' %(b1, b2, b3)

  # RShr
  elif opcode == 14:
   b1 = instr[ip]
   ip += 1
   print 'arr[%d] = (int)((uint)arr[%d] >> 1);' %(b1, b1)

  # SetZero
  elif opcode == 15:
   b1 = instr[ip]
   ip += 1
   print 'arr[%d] = 0;' %(b1)

  else:
   print 'Error'
   break

if __name__ == '__main__':
 disassemble()

Running the disassembler produces the following C# code.
loc_000: bitarr[2] = new BitArray(56);
loc_003: arr[41] = 0;
loc_005: arr[15] = 0;
loc_007: goto loc_036;
loc_009: arr[8] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[arr[15]]);
loc_012: if (arr[8] == -1) goto loc_034;
loc_016: arr[1] = 0;
loc_018: goto loc_030;
loc_020: bitarr[2][arr[41]] = ((arr[8] & 1) != 0);
loc_024: arr[41]++;
loc_026: arr[8] = (int)((uint)arr[8] >> 1);
loc_028: arr[1]++;
loc_030: if ((long)arr[1] < (long)((ulong)5)) goto loc_020;
loc_034: arr[15]++;
loc_036: if (arr[15] < password.Length) goto loc_009;
loc_039: bitarr[1] = new BitArray(40);
loc_042: arr[61] = 0;
loc_044: arr[55] = 0;
loc_046: arr[24] = 0;
loc_048: goto loc_134;
loc_050: arr[36] = (bitarr[0][arr[61]] == true ? 1:0);
loc_054: arr[61]++;
loc_056: arr[18] = 0;
loc_058: goto loc_078;
loc_060: arr[19] = (bitarr[0][arr[61]] == true ? 1:0);
loc_064: if (arr[19] == 0) goto loc_074;
loc_067: arr[19] = (bitarr[2][arr[18]] == true ? 1:0);
loc_071: arr[36] += arr[19];
loc_074: arr[61]++;
loc_076: arr[18]++;
loc_078: if ((long)arr[18] < (long)((ulong)50)) goto loc_060;
loc_082: arr[11] = 0;
loc_084: goto loc_122;
loc_086: arr[47] = arr[11] + 1;
loc_089: goto loc_116;
loc_091: arr[19] = (bitarr[0][arr[61]] == true ? 1:0);
loc_095: if (arr[19] == 0) goto loc_112;
loc_098: arr[19] = (bitarr[2][arr[11]] == true ? 1:0);
loc_102: arr[57] = (bitarr[2][arr[47]] == true ? 1:0);
loc_106: arr[57] *= arr[19];
loc_109: arr[36] += arr[57];
loc_112: arr[61]++;
loc_114: arr[47]++;
loc_116: if ((long)arr[47] < (long)((ulong)50)) goto loc_091;
loc_120: arr[11]++;
loc_122: if ((long)arr[11] < (long)((ulong)49)) goto loc_086;
loc_126: bitarr[1][arr[55]] = ((arr[36] & 1) != 0);
loc_130: arr[55]++;
loc_132: arr[24]++;
loc_134: if ((long)arr[24] < (long)((ulong)40)) goto loc_050;
loc_138: bitarr[1].CopyTo(ans, 0);

The de-virtualized code thus obtained is semantically equivalent to the original code, but is splattered with numerous gotos. This is because during virtualization the code lost its original structure. Loops were converted to If-then goto statements.  Although we can directly use the code as is, it is better if we try to restore it to its original form which should also improve readability.

Restoring the structure of the de-virtualized code


To restore the original structure of the de-virtualized code we will compile it followed by decompilation with dnSpy.

Original de-virtualized code
void doIt()
{
 bitarr = new BitArray[3];
 bitarr[0] = new BitArray(hardcoded);
 arr = new int[64];
 ans = new byte[5];
 
 loc_000: bitarr[2] = new BitArray(56);
 loc_003: arr[41] = 0;
 loc_005: arr[15] = 0;
 loc_007: goto loc_036;
 loc_009: arr[8] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[arr[15]]);
 loc_012: if (arr[8] == -1) goto loc_034;
 loc_016: arr[1] = 0;
 loc_018: goto loc_030;
 loc_020: bitarr[2][arr[41]] = ((arr[8] & 1) != 0);
 loc_024: arr[41]++;
 loc_026: arr[8] = (int)((uint)arr[8] >> 1);
 loc_028: arr[1]++;
 loc_030: if ((long)arr[1] < (long)((ulong)5)) goto loc_020;
 loc_034: arr[15]++;
 loc_036: if (arr[15] < password.Length) goto loc_009;
 loc_039: bitarr[1] = new BitArray(40);
 loc_042: arr[61] = 0;
 loc_044: arr[55] = 0;
 loc_046: arr[24] = 0;
 loc_048: goto loc_134;
 loc_050: arr[36] = (bitarr[0][arr[61]] == true ? 1:0);
 loc_054: arr[61]++;
 loc_056: arr[18] = 0;
 loc_058: goto loc_078;
 loc_060: arr[19] = (bitarr[0][arr[61]] == true ? 1:0);
 loc_064: if (arr[19] == 0) goto loc_074;
 loc_067: arr[19] = (bitarr[2][arr[18]] == true ? 1:0);
 loc_071: arr[36] += arr[19];
 loc_074: arr[61]++;
 loc_076: arr[18]++;
 loc_078: if ((long)arr[18] < (long)((ulong)50)) goto loc_060;
 loc_082: arr[11] = 0;
 loc_084: goto loc_122;
 loc_086: arr[47] = arr[11] + 1;
 loc_089: goto loc_116;
 loc_091: arr[19] = (bitarr[0][arr[61]] == true ? 1:0);
 loc_095: if (arr[19] == 0) goto loc_112;
 loc_098: arr[19] = (bitarr[2][arr[11]] == true ? 1:0);
 loc_102: arr[57] = (bitarr[2][arr[47]] == true ? 1:0);
 loc_106: arr[57] *= arr[19];
 loc_109: arr[36] += arr[57];
 loc_112: arr[61]++;
 loc_114: arr[47]++;
 loc_116: if ((long)arr[47] < (long)((ulong)50)) goto loc_091;
 loc_120: arr[11]++;
 loc_122: if ((long)arr[11] < (long)((ulong)49)) goto loc_086;
 loc_126: bitarr[1][arr[55]] = ((arr[36] & 1) != 0);
 loc_130: arr[55]++;
 loc_132: arr[24]++;
 loc_134: if ((long)arr[24] < (long)((ulong)40)) goto loc_050;
 loc_138: bitarr[1].CopyTo(ans, 0);
}

Decompiled code after recompilation 
// Token: 0x06000005 RID: 5 RVA: 0x00003A94 File Offset: 0x00002A94
private void doIt()
{
 this.bitarr = new BitArray[3];
 this.bitarr[0] = new BitArray(this.hardcoded);
 this.arr = new int[64];
 this.ans = new byte[5];
 this.bitarr[2] = new BitArray(56);
 this.arr[41] = 0;
 this.arr[15] = 0;
 while (this.arr[15] < this.password.Length)
 {
  this.arr[8] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(this.password[this.arr[15]]);
  if (this.arr[8] != -1)
  {
   this.arr[1] = 0;
   while ((long)this.arr[1] < 5L)
   {
    this.bitarr[2][this.arr[41]] = ((this.arr[8] & 1) != 0);
    this.arr[41]++;
    this.arr[8] = (int)((uint)this.arr[8] >> 1);
    this.arr[1]++;
   }
  }
  this.arr[15]++;
 }
 this.bitarr[1] = new BitArray(40);
 this.arr[61] = 0;
 this.arr[55] = 0;
 this.arr[24] = 0;
 while ((long)this.arr[24] < 40L)
 {
  this.arr[36] = (this.bitarr[0][this.arr[61]] ? 1 : 0);
  this.arr[61]++;
  this.arr[18] = 0;
  while ((long)this.arr[18] < 50L)
  {
   this.arr[19] = (this.bitarr[0][this.arr[61]] ? 1 : 0);
   if (this.arr[19] != 0)
   {
    this.arr[19] = (this.bitarr[2][this.arr[18]] ? 1 : 0);
    this.arr[36] += this.arr[19];
   }
   this.arr[61]++;
   this.arr[18]++;
  }
  this.arr[11] = 0;
  while ((long)this.arr[11] < 49L)
  {
   this.arr[47] = this.arr[11] + 1;
   while ((long)this.arr[47] < 50L)
   {
    this.arr[19] = (this.bitarr[0][this.arr[61]] ? 1 : 0);
    if (this.arr[19] != 0)
    {
     this.arr[19] = (this.bitarr[2][this.arr[11]] ? 1 : 0);
     this.arr[57] = (this.bitarr[2][this.arr[47]] ? 1 : 0);
     this.arr[57] *= this.arr[19];
     this.arr[36] += this.arr[57];
    }
    this.arr[61]++;
    this.arr[47]++;
   }
   this.arr[11]++;
  }
  this.bitarr[1][this.arr[55]] = ((this.arr[36] & 1) != 0);
  this.arr[55]++;
  this.arr[24]++;
 }
 this.bitarr[1].CopyTo(this.ans, 0);
}
[Full Code]
This can be further be hand optimized to convert all arrays to variables and while loops to for loop. The optimization will be done in a later step.

The key checking algorithm


As shown in Fig 7 the keygenme expects a username/password combination. It calculates a standard MD5 hash of the username, and compares some bytes of it to another hash computed from the password. The algorithm which implements the latter hash is the crux of this keygenme. For success, these comparisons must match.

Gimme the password!
Fig 7: Gimme the password!
The user supplied password is converted to a 50 size bit array using the following algorithm.
calc = new BitArray(50);

for (int i = 0, j = 0; i < password.Length; i++)
{
 int pos = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[i]);
 if (pos != -1)
 {
  for (int k = 0; k < 5; k++)
  {
   calc[j++] = (pos & 1) != 0;
   pos >>= 1;
  }
 }
}
Next, there is a huge hard coded byte array containing 6380 entries. This is also converted to a bit array. Since 8 bits make a byte, the size of the bit array is 6380 x 8 = 51,040.

Now, suppose the 50 bit password array is represented as p0, p1, p2, p3,......, p49. Using these two bit arrays, it calculates the value of 40 such following statements. The indices of the bits which are summed and multiplied are also fetched from the hard coded bit array. To understand how this is done refer to the decompiled code listing.
bit0 = (0 + p[1] + p[2] + p[9] + ... + p[49] + (p[0] * p[2]) + (p[0] * p[3]) + ... + (p[48] * p[49])) & 1;
bit1 = (1 + p[0] + p[2] + p[4] + ... + p[48] + (p[0] * p[2]) + (p[0] * p[3]) + ... + (p[48] * p[49])) & 1;
bit2 = (1 + p[0] + p[1] + p[2] + ... + p[49] + (p[0] * p[1]) + (p[0] * p[2]) + ... + (p[47] * p[49])) & 1;
...
37 more lines
...

The 40 calculated bits are then combined 8 at a time to form 5 bytes. For success, each byte thus obtained must match the corresponding byte obtained from the MD5 of the name as explained before.

Converting to a boolean system


The algorithm the keygenme implements is a sort of combination of a system of linear & bilinear equations having 50 unknowns (p0, ...p49). Note that in each of the equations only the last bit of the sum is retained, the remaining bits are discarded. Hence this can be converted to a boolean system, but before that we need to convert the arithmetic addition and multiplication operations to boolean logic. 

Converting arithmetic addition
In a boolean system, variables can have two possible values viz 0 or 1. Further, since we are only interested in the last bit, the result of addition operation will either be 0 or 1. We can either use a  Karnaugh map or a truth table. Here I used the latter.


Truth Table for Converting Bit Addition
A B F = A + B
0 0 0
0 1 1
1 0 1
1 1 0

A & B are two bits. Bit B is added to Bit A. The rightmost column denotes the sum. Using the above truth table to convert it to a canonical sum-of-products boolean expression we get the following which is already in its simplest form,


Converting arithmetic product
Similar to addition, we can convert the product to an boolean expression,


Truth Table for converting Bit Product
A B C B.C F = A + B.C
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 0

Bit B & C are multiplied and added with Bit A. The rightmost column denotes the result. The canonical sum-of-products obtained is,


This can be further simplified to,


For simplification of boolean expressions,  there are online tools available such as http://www.32x8.com/ and http://tma.main.jp/logic/index_en.html.

An attempt at keygenning


The objective of the keygenme is thus to solve a system of equations having 50 unknowns. Now, as I said before that the de-virtualized code can further be hand optimized to get rid of the excess clutter. Here is it.
private void doIt()
{
 huge = new BitArray(hardcoded);
 calc = new BitArray(50);
 output = new BitArray(40);
 arr = new int[64];
 ans = new byte[5];

 for (int i = 0, j = 0; i < password.Length; i++)
 {
  int pos = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[i]);
  if (pos != -1)
  {
   for (int k = 0; k < 5; k++)
   {
    calc[j++] = (pos & 1) != 0;
    pos >>= 1;
   }
  }
 }

 for (int x = 0, y = 0; x < 40; x++)
 {
  bool bit = huge[y++];
  
  for (int a = 0; a < 50; a++)
   if (huge[y++])
    if (calc[a]) bit = !bit;

  for (int b = 0; b < 49; b++)
   for (int c = b + 1; c < 50; c++)
    if (huge[y++]) 
     if (calc[b] & calc[c]) bit = !bit;
  output[x] = bit;
 }
 output.CopyTo(ans, 0);
}
While loops have been converted to for loops. Arrays have been converted to variables. The last steps that remains is to develop a working keygen. For problems like this, I tend to prefer the Z3 SMT solver. Z3 has a nice python api to code against. Without further ado, here the is the code which tries to find a valid password for the name 0xec. It isn't a true keygen.
from z3 import *

from init_bits import initbits
from targ_bits import targbits
from sum_bits import sumbits
from prod_bits import prodbits

def main():
    bits = [Bool('b'+str(i)) for i in range(50)]
    s = SolverFor('sat') # Solver()
    keyspace = '23456789ABCDEFGHJKLMNPQRSTUVWXYZ'
    finalkey = ''
    tempkey = ''

    for i in range(len(initbits)):
        A = BoolVal(initbits[i])

        li = sumbits[i]
        for x in li:
            B = bits[x]
            A = Or(And(Not(A), B), And(A, Not(B)))

        li = prodbits[i]
        for x, y in li:
            B, C = bits[x], bits[y]
            A = Or(And(A, Not(B)), And(A, Not(C)), And(Not(A), B, C))

        s.add(A == targbits[i])
        print i


    if s.check() == sat:
        print 'Key Found!'
        m = s.model()
        for i in xrange(50):
            val = m[bits[i]]
            if val is not None:
                tempkey += '1'
            else:
                tempkey += '0'

        # Reverse tempkey
        tempkey = tempkey[::-1]
        for i in xrange(0, 50, 5):
            finalkey +=  keyspace[int(tempkey[i:i+5], 2)]

        finalkey = finalkey[::-1]
        print finalkey[0:5] + '-' + finalkey[5:]

    else:
        print 'Could not find a key:('

if __name__ == '__main__':
    main()
Congrats if you have read this far, however, I have disappointing news in store. The keygen developed does not generate a key within a realistic time. For a gold medal, we need to generate a key within one second. I have ran the keygen for more than an hour, and it still continued running. However, I know the code is correct since it can verify the sample username / password combinations (kao/QQRR9-DL6JF).

Further optimizations of the python code are possible. but that doesn't improve the situation. For example, if you closely look at the boolean expression for converting bit addition, you can deduce that it is the same as a 2 bit half adder where we are discarding the carry bit.


Similarly, the expression for converting bit product is a 3 bit full adder discarding the carry.

However, in spite of all of the above optimizations, it still remains unsolved.

Trying with an arithmetic system

As said before, the implemented algorithm is a combination of linear and bilinear system having 50 unknowns. In an arithmetic system, the problem looks like,


In simple maths, the above represents an equation similar to the following,


There are about 8 such equations. Each equation have a linear and a bilinear part. Without the bilinear part, we could have applied Gaussian Elimination for a solution, but that isn't the case to be. Further, my mathematical fu is not strong enough to devise an automated way to solve these type of equations. Hence, I will wait for others to solve this.