Friday, December 11, 2015

SECCON 2015 - Nonogram - 300 point Programming Challenge

Short break but we're back CTFing. I've been away because I took a month of lab time doing the OSCP certification which I will write a review of later. It was very fun though. Today I'm writing up how I solved this challenge at SecCon 2015 since it was one I spent some non-trivial time on.

A nonogram is a type of Japanese crossword type puzzle with numbers. You fill in boxes based on numbers in the rows and columns and eventually make a picture.

The SecCon implementation looked like this (NO! added for comedic effect :P ):



I looked into solving the puzzle category itself but grew tired of reading the rules and instead looked at solving engines other people had written.

I first selected this one from Github. The solver worked and was simple to integrate with some simple network code but it was very slow and often tried to perform useless exhaustive searches for perfect solutions which just didn't ever seem to end.

That was where I spent most of my time on this challenge, diagnosing why Nonograms take time to solve. I found that there's often more than one solution and sometimes there are many possible solutions.

So I went back on the hunt for a better Nonogram solver and came across this article about using Google CP solver for faster Nonogram solutions using DefaultSearch.

Sounded good and, again was in Python, so I basically swapped out the old engine of my solution for this one in a couple of minutes and immediately saw results. The solver was way faster and knew how to give up after finding 2 (or, modified as many as you like) possible solutions.

With that engine, some very rough web and table parsing code, and we had a solver for this challenge that would:

  1. Grab the first / next challenge nonogram table
  2. Parse for the values in the first column and top row into two zero padded lists
  3. Feed that into the Google constraint programming engine via some borrowed Python code
  4. Get a text output, write that using Python Image Library to a PNG file
  5. Parse the PNG for a QR code
  6. Send the QR code decoded output to the server and fetch the next challenge
We had to do this a total of 30 times and the solutions aren't always perfect and the QR codes don't always work so a few attempts need to be run.


Anyway, I include the code before, sorry you have to see this messy hack but I don't mind, 300 points it got me :)


#!/usr/bin/python
# -*- coding: utf-8 -*-

import requests 
import re
from itertools import izip
import PIL
from PIL import ImageFont,Image,ImageDraw
import subprocess
import sys
from ortools.constraint_solver import pywrapcp

URL = 'http://qrlogic.pwn.seccon.jp:10080/game/'

#
# Make a transition (automaton) list of tuples from a
# single pattern, e.g. [3,2,1]
#
def make_transition_tuples(pattern):
  p_len = len(pattern)
  num_states = p_len + sum(pattern)

  tuples = []

  # this is for handling 0-clues. It generates
  # just the minimal state
  if num_states == 0:
    tuples.append((1, 0, 1))
    return (tuples, 1)

  # convert pattern to a 0/1 pattern for easy handling of
  # the states
  tmp = [0]
  c = 0
  for pattern_index in range(p_len):
    tmp.extend([1] * pattern[pattern_index])
    tmp.append(0)

  for i in range(num_states):
    state = i + 1
    if tmp[i] == 0:
      tuples.append((state, 0, state))
      tuples.append((state, 1, state + 1))
    else:
      if i < num_states - 1:
        if tmp[i + 1] == 1:
          tuples.append((state, 1, state + 1))
        else:
          tuples.append((state, 0, state + 1))
  tuples.append((num_states, 0, num_states))
  return (tuples, num_states)


#
# check each rule by creating an automaton and transition constraint.
#
def check_rule(rules, y):
  cleaned_rule = [rules[i] for i in range(len(rules)) if rules[i] > 0]
  (transition_tuples, last_state) = make_transition_tuples(cleaned_rule)

  initial_state = 1
  accepting_states = [last_state]

  solver = y[0].solver()
  solver.Add(solver.TransitionConstraint(y,
                                         transition_tuples,
                                         initial_state,
                                         accepting_states))
 
def silly(rows, row_rule_len, row_rules, cols, col_rule_len, col_rules):
  font = ImageFont.truetype('clacon.ttf')
  img = Image.new("RGBA", (300,1500),(255,255,255))
  draw = ImageDraw.Draw(img)
  y_text = 8

  # Create the solver.
  solver = pywrapcp.Solver('Nonogram')

  #
  # variables
  #
  board = {}
  for i in range(rows):
    for j in range(cols):
      board[i, j] = solver.IntVar(0, 1, 'board[%i, %i]' % (i, j))

  board_flat = [board[i, j] for i in range(rows) for j in range(cols)]

  # Flattened board for labeling.
  # This labeling was inspired by a suggestion from
  # Pascal Van Hentenryck about my (hakank's) Comet
  # nonogram model.
  board_label = []
  if rows * row_rule_len < cols * col_rule_len:
    for i in range(rows):
      for j in range(cols):
        board_label.append(board[i, j])
  else:
    for j in range(cols):
      for i in range(rows):
        board_label.append(board[i, j])

  #
  # constraints
  #
  for i in range(rows):
    check_rule(row_rules[i], [board[i, j] for j in range(cols)])

  for j in range(cols):
    check_rule(col_rules[j], [board[i, j] for i in range(rows)])

  #
  # solution and search
  #
  parameters = pywrapcp.DefaultPhaseParameters()
  parameters.heuristic_period = 200000

  db = solver.DefaultPhase(board_label, parameters)

  solver.NewSearch(db)

  num_solutions = 0
  while solver.NextSolution():
    num_solutions += 1
    for i in range(rows):
      row = [board[i, j].Value() for j in range(cols)]
      row_pres = []
      for j in row:
        if j == 1:
          row_pres.append('█')
        else:
          row_pres.append(' ')
      outline = ''.join(row_pres)
      outline = unicode(outline,"utf-8")
      width, height = font.getsize(outline)
      draw.text((0,y_text),outline,(0,0,0),font=font)
      y_text += height
      draw = ImageDraw.Draw(img)

    draw.text((0,y_text)," ",(0,0,0),font=font)
    y_text += height
    draw.text((0,y_text)," ",(0,0,0),font=font)
    y_text += height
    draw.text((0,y_text)," ",(0,0,0),font=font)
    y_text += height

    if num_solutions >= 6:
      break

  solver.EndSearch()
  img = img.resize((700,2000))
  img.show()  

def mainloop(answer):

 if answer:
  print "[*] Posting result: " + answer
  payload = { 'ans' : answer }
  r = s.post(URL, data=payload)
 else:
  print "[*] Using GET Method to get first challenge..."
  r = s.get(URL)

 toprow = []
 firstcolumn = []

 for line in r.content.splitlines():
  if 'Stage:' in line:
   thestage = line.split(" ")[1]
   print "[*] Stage: " + thestage + " / 30"

  if '<th class="cols">' in line:
   headerblocks = line.split("</th>")
   p = re.compile("<span>(.*?)</span>")
   for block in headerblocks:
    columnnums = []
    if '<th class="rows">' in block:
     break

    subblocks = block.split("<br />")
    for subblock in subblocks: 
     m = p.search(subblock)
     if m:
      columnnums.append(int(m.group(1),10))
   
    if len(columnnums) > 0:
     toprow.append(columnnums)

  if '<th class="rows">' in line:
   if '<th class="cols">' in line:
    line = line.split('<th class="rows">')[1]

   headerblocks = line.split("</th>")
   p = re.compile("<span>(.*?)</span>")
   for block in headerblocks:
    columnnums = []
    subblocks = block.split(" ")
    for subblock in subblocks: 
     m = p.search(subblock)
     if m:
      columnnums.append(int(m.group(1),10))
   
    if len(columnnums) > 0:
     firstcolumn.append(columnnums)

 # hacked together since the Google CP engine needs more than the old engine 
        rulelen = 0
        for x in toprow:
                if len(x) > rulelen:
                        rulelen = len(x)
 # zero pad the rules
 for x in toprow:
  while len(x) < rulelen:
   x.insert(0,0)

        rulelen2 = 0
        for x in firstcolumn:
                if len(x) > rulelen2:
                        rulelen2 = len(x)

 # zero pad the rules
 for x in firstcolumn:
  while len(x) < rulelen2:
   x.insert(0,0)


 silly(len(firstcolumn), rulelen, firstcolumn, len(toprow), rulelen2, toprow)


s = requests.Session()
ans = ""

# super ugly 
while(1):
 mainloop(ans)
 
 try:
  thedata = subprocess.check_output(["zbarimg -q /tmp/tmp*"],shell=True).split(":")[1].strip().splitlines()[0]
 except:
  thedata = ""

 print "[*] Decoded QR: " + thedata

 if thedata == "":
  # maybe try and scan it on your phone or something :P 
  ans = raw_input("Enter QR Code result> ")
 else:
  ans = thedata

 try:
  subprocess.check_output(["killall","-9","display"])
 except:
  pass

And when we run it we get the even less impressive wall of mangled output:


# ./pgame2.py 
[*] Using GET Method to get first challenge...
[*] Stage: 1 / 30
[02:14:26] src/constraint_solver/default_search.cc:1307: Init impact based search phase on 441 variables, initialization splits = 100, heuristic_period = 200000, run_all_heuristics = 1, restart_log_size = -1
[02:14:26] src/constraint_solver/default_search.cc:471:   - initial log2(SearchSpace) = 50
[02:14:26] src/constraint_solver/default_search.cc:526:   - init done, time = 2 ms, 14 values removed, log2(SearchSpace) = 36
[*] Decoded QR: JkhM3JiP6dU
Killed
[*] Posting result: JkhM3JiP6dU
[*] Stage: 2 / 30
[02:14:27] src/constraint_solver/default_search.cc:1307: Init impact based search phase on 441 variables, initialization splits = 100, heuristic_period = 200000, run_all_heuristics = 1, restart_log_size = -1
[02:14:27] src/constraint_solver/default_search.cc:471:   - initial log2(SearchSpace) = 26
[02:14:27] src/constraint_solver/default_search.cc:526:   - init done, time = 0 ms, 2 values removed, log2(SearchSpace) = 24
[*] Decoded QR: yUNXAQa1421B
Killed
[*] Posting result: yUNXAQa1421B
[*] Stage: 3 / 30
[02:14:28] src/constraint_solver/default_search.cc:1307: Init impact based search phase on 441 variables, initialization splits = 100, heuristic_period = 200000, run_all_heuristics = 1, restart_log_size = -1
[02:14:28] src/constraint_solver/default_search.cc:471:   - initial log2(SearchSpace) = 31
[02:14:28] src/constraint_solver/default_search.cc:526:   - init done, time = 0 ms, 3 values removed, log2(SearchSpace) = 28
[*] Decoded QR: fHOFYusdRKYlN
[*] Posting result: fHOFYusdRKYlN
Killed
[*] Stage: 4 / 30
[02:14:28] src/constraint_solver/default_search.cc:1307: Init impact based search phase on 441 variables, initialization splits = 100, heuristic_period = 200000, run_all_heuristics = 1, restart_log_size = -1
[02:14:28] src/constraint_solver/default_search.cc:471:   - initial log2(SearchSpace) = 46
[02:14:28] src/constraint_solver/default_search.cc:526:   - init done, time = 1 ms, 1 values removed, log2(SearchSpace) = 45
[*] Decoded QR: eQS2SwyUa56wWN
[*] Posting result: eQS2SwyUa56wWN
Killed
[*] Stage: 5 / 30
[*] Decoded QR: k94Lgdg4lEtnezi
[*] Posting result: k94Lgdg4lEtnezi
Killed
...
[*] Stage: 29 / 30
[*] Decoded QR: oELkD87acQsH299lL4ajOgUPqh0dy5LW7g474S0
[*] Posting result: oELkD87acQsH299lL4ajOgUPqh0dy5LW7g474S0
Killed
[*] Stage: 30 / 30
[02:20:43] src/constraint_solver/default_search.cc:1307: Init impact based search phase on 1089 variables, initialization splits = 100, heuristic_period = 200000, run_all_heuristics = 1, restart_log_size = -1
[02:20:43] src/constraint_solver/default_search.cc:471:   - initial log2(SearchSpace) = 79
[02:20:43] src/constraint_solver/default_search.cc:526:   - init done, time = 2 ms, 11 values removed, log2(SearchSpace) = 68
[*] Decoded QR: SECCON{YES_WE_REALLY_LOVE_QR_CODE_BECAUSE_OF_ITS_CLEVER_DESIGN}

Anyway, it was actually fun to solve this as I always do like the challenge response type problems. I probably suffered a bit here from trying to reuse some of the code I previously used for another challenge but not too badly.

Overall I really enjoyed SecCon 2015!




Friday, October 23, 2015

EKOPARTY 2015 - XOR Crypter - Crypto 200

Very quick challenge this one, solved in one line shell script. Here's the clue:


The ZIP file contains a Python script called "shiftcrypt.py". The meat is this part:


result = []
blocks = struct.unpack("I" * (len(data) / 4), data)

print repr(blocks)

for block in blocks:
    result += [block ^ block >> 16]

The first thing I thought here is, this is not right? We can just do the same operation and get back the original data yes?

Let's try, we take the string they gave us to decrypt:
  • CjBPewYGc2gdD3RpMRNfdDcQX3UGGmhpBxZhYhFlfQA=
And we make it encrypt it again:

root@mankrik:~/ekoparty/crypto200# echo CjBPewYGc2gdD3RpMRNfdDcQX3UGGmhpBxZhYhFlfQA= | base64 -d > c; ./shiftcrypt.py "`cat c`" | tail -1 | base64 -d
EKO{unshifting_the_unshiftable}

There we go, our flag:
  • EKO{unshifting_the_unshiftable}

EKOPARTY 2015 - Custom ACL - Web 100pt Challenge

Cool CTF, finished top 10 so I'm happy with that. Again it began mid week for me but I got sick with a virus so had to stay home anyway. What better to do than to CTF until I feel better?

Great challenge this one but I'm seeing a lot of people were doing strange things to the poor 3rd party involved in their writeups, like nmap scanning etc. None of that was necessary.

Here's the clue:


So another PHP challenge I suppose, we browse on over and then append "s" on the URL to give us:

Which coughs up the source code for us:

<?php

include ('flag.php');

if (isset($_SERVER['REMOTE_ADDR'])) $remote_ip = $_SERVER['REMOTE_ADDR'];
else die('Err');

$octets = explode('.', $remote_ip, 4);

if ($octets[0] == '67' 
    && $octets[1] == '222' 
    && $octets[2] == '139' 
    && intval($octets[3]) >= 223 
    && intval($octets[3]) <= 230) {
    if (isset($_POST['admin'])) {
        $admin = $_POST['admin'];
        $is_admin = 1;
        print strlen($admin);
        if (strlen($admin) == 256) {
            for ($i = 0; $i < 256; $i++) {
                if ($admin[$i] != chr($i)) $is_admin = 0;
            }
        } else $is_admin = 0;
        if ($is_admin == 1) echo "Your flag is $flag";
        else  die('Err');
    } else die('Err');
} else die('Err');
?>

Ok so the ONLY acceptable IPs are very specifically in the 67.222.139.223 - 67.222.139.230 range. What's special about that? We ask NSLookup to reverse lookup this IP:

root@mankrik:~# nslookup 67.222.139.223
Server:  192.168.36.2
Address: 192.168.36.2#53

Non-authoritative answer:
223.139.222.67.in-addr.arpa name = serverIP223.runnable.com.

Runnable.com? Let's check these guys out...


Ok so online sandboxes we can run code in. Great, but I'm on a deadline here... Oh whats this:


I don't know, Am I?

I click that link (http://code.runnable.com/) and I'm taken to the meat of their site, a list of code snippets we can run for various reasons. I pick one at random and am greeted with a surprise. Each code snippet gets a kind of web-based terminal to interact with:


The terminal is furnished with useful tools as well, namely "curl":

root@runnable:/root# curl                                                                  curl: try 'curl --help' or 'curl --manual' for more information                            root@runnable:/root#                                                                                                
 
So i feel we have the vector now, we just need to pass all the other checks. Re-examining the source we need to:
  • Query must be post, fine we can use -d in curl for that
  • Query must contain the admin parameter, fine
  • Admin parameter must be 256 bytes long, fine ok
  • Each byte of the admin parameter value must equal the value of it's index in the string, er ok? Many of those characters wont be printable, we'll need to handle that
So I turn to Python and here's the source I come up with:

#!/usr/bin/python

import urllib

payload = ''

for i in range(0,256):
 payload += chr(i)

payload = urllib.quote(payload)
payload = 'curl -d "admin=' + payload + '" http://ctfchallenges.ctf.site:10000/ipfilter/admin.php'

print payload

Which gives me the following output:

curl -d "admin=%01%02%03%04%05%06%07%08%09%0A%0B%0C%0D%0E%0F%10%11%12%13%14%15%16%17%18%19%1A%1B%1C%1D%1E%1F%20%21%22%23%24%25%26%27%28%29%2A%2B%2C-./0123456789%3A%3B%3C%3D%3E%3F%40ABCDEFGHIJKLMNOPQRSTUVWXYZ%5B%5C%5D%5E_%60abcdefghijklmnopqrstuvwxyz%7B%7C%7D%7E%7F%80%81%82%83%84%85%86%87%88%89%8A%8B%8C%8D%8E%8F%90%91%92%93%94%95%96%97%98%99%9A%9B%9C%9D%9E%9F%A0%A1%A2%A3%A4%A5%A6%A7%A8%A9%AA%AB%AC%AD%AE%AF%B0%B1%B2%B3%B4%B5%B6%B7%B8%B9%BA%BB%BC%BD%BE%BF%C0%C1%C2%C3%C4%C5%C6%C7%C8%C9%CA%CB%CC%CD%CE%CF%D0%D1%D2%D3%D4%D5%D6%D7%D8%D9%DA%DB%DC%DD%DE%DF%E0%E1%E2%E3%E4%E5%E6%E7%E8%E9%EA%EB%EC%ED%EE%EF%F0%F1%F2%F3%F4%F5%F6%F7%F8%F9%FA%FB%FC%FD%FE%FF" http://ctfchallenges.ctf.site:10000/ipfilter/admin.php


Which I copy and paste into the Runnable.com web terminal:

root@runnable:/root# curl -d "admin=%01%02%03%04%05%06%07%08%09%0A%0B%0C%0D%0E%0F%10%11%12%13%14%15%16%17%18%19%1
A%1B%1C%1D%1E%1F%20%21%22%23%24%25%26%27%28%29%2A%2B%2C-./0123456789%3A%3B%3C%3D%3E%3F%40ABCDEFGHIJKLMNOPQRSTUVWXYZ%
5B%5C%5D%5E_%60abcdefghijklmnopqrstuvwxyz%7B%7C%7D%7E%7F%80%81%82%83%84%85%86%87%88%89%8A%8B%8C%8D%8E%8F%90%91%92%93
%94%95%96%97%98%99%9A%9B%9C%9D%9E%9F%A0%A1%A2%A3%A4%A5%A6%A7%A8%A9%AA%AB%AC%AD%AE%AF%B0%B1%B2%B3%B4%B5%B6%B7%B8%B9%B
A%BB%BC%BD%BE%BF%C0%C1%C2%C3%C4%C5%C6%C7%C8%C9%CA%CB%CC%CD%CE%CF%D0%D1%D2%D3%D4%D5%D6%D7%D8%D9%DA%DB%DC%DD%DE%DF%E0%
E1%E2%E3%E4%E5%E6%E7%E8%E9%EA%EB%EC%ED%EE%EF%F0%F1%F2%F3%F4%F5%F6%F7%F8%F9%FA%FB%FC%FD%FE%FF" http://ctfchallenges.c
tf.site:10000/ipfilter/admin.php                                                                                    
256Your flag is EKO{runnable_com_31337_s3rv1c3} 


Voila, our flag:

  • EKO{runnable_com_31337_s3rv1c3}




Thursday, October 22, 2015

Hack.Lu - Creative Cheating 150pt Crypto Challenge

A mid week CTF when I have final exams! Argh! Still I play because I'm an idiot. Fun CTF, hard to read the font they chose but still fun. This was a classical RSA challenge with almost no difficult points but I'll write up anyway.


Ok so the linked file is a PCAPNG file and we're given two RSA public keys.

Immediately I'm thinking those modulii are too small and so I just go and plug them into factordb.com. I'm rewarded and have our p & q values for both Alice and Bob:

  • Alice: http://factordb.com/index.php?query=1696206139052948924304948333474767
  • Bob: http://factordb.com/index.php?query=3104649130901425335933838103517383
Next I examine the PCAP. It's trivial to extract the data which is just base64 encoded ciphertext strings. I just use wireshark for this because tcpflow is giving me grief over the PCAP:

root@mankrik:~/hacklu/creative# cat strings.64 
U0VRID0gMTM7IERBVEEgPSAweDNiMDRiMjZhMGFkYWRhMmY2NzMyNmJiMGM1ZDZMOyBTSUcgPSAweDJlNWFiMjRmOWRjMjFkZjQwNmE4N2RlMGIzYjRMOw==
U0VRID0gMDsgREFUQSA9IDB4NzQ5MmY0ZWM5MDAxMjAyZGNiNTY5ZGY0NjhiNEw7IFNJRyA9IDB4YzkxMDc2NjZiMWNjMDQwYTRmYzJlODllM2U3TDs=
U0VRID0gNTsgREFUQSA9IDB4OTRkOTdlMDRmNTJjMmQ2ZjQyZjlhYWNiZjBiNUw7IFNJRyA9IDB4MWUzYjZkNGVhZjExNTgyZTg1ZWFkNGJmOTBhOUw7
U0VRID0gNDsgREFUQSA9IDB4MmMyOTE1MGYxZTMxMWVmMDliYzlmMDY3MzVhY0w7IFNJRyA9IDB4MTY2NWZiMmRhNzYxYzRkZTg5ZjI3YWM4MGNiTDs=
...

Theres 148 messages total, when we decode them, each consists of three components:

  • Sequence number
  • Data
  • Signature

An example is below:


SEQ = 13; DATA = 0x3b04b26a0adada2f67326bb0c5d6L; SIG = 0x2e5ab24f9dc21df406a87de0b3b4L;
SEQ = 0; DATA = 0x7492f4ec9001202dcb569df468b4L; SIG = 0xc9107666b1cc040a4fc2e89e3e7L;
SEQ = 5; DATA = 0x94d97e04f52c2d6f42f9aacbf0b5L; SIG = 0x1e3b6d4eaf11582e85ead4bf90a9L;
SEQ = 4; DATA = 0x2c29150f1e311ef09bc9f06735acL; SIG = 0x1665fb2da761c4de89f27ac80cbL;
...

Ok so immediately you know the sequence numbers are out of order so reassembly in order is probably required later. If you parse the data you'll also notice sequence numbers repeat. For example:

root@mankrik:~/hacklu/creative# ./c1.py | grep "SEQ = 0"
SEQ = 0; DATA = 0x7492f4ec9001202dcb569df468b4L; SIG = 0xc9107666b1cc040a4fc2e89e3e7L;
SEQ = 0; DATA = 0x633282273f9cf7e5a44fcbe1787bL; SIG = 0x2b15275412244442d9ee60fc91aeL;
SEQ = 0; DATA = 0x59e9bb001b0d9167dbc39dd544c9L; SIG = 0x66e706951133b2d1bfde29dc82aL;

So my theory becomes:

  1. Data is out of sequence, reassemble in order
  2. Use the digital signatures to validate which of the multiple data blocks is the correct one for that sequence number

This is simple to code, we just need the math. A signature is calculated as:

  • s = md mod n

To validate a signature, you calculate:

  • v = se mod n

The resulting v should match your decrypted m. If they do, then you have a validated message. Here we have the Python:



#!/usr/bin/python

from pwn import *
import binascii
import sys

e = 0x10001

#alice - http://factordb.com/index.php?query=1696206139052948924304948333474767
a_n = 0x53a121a11e36d7a84dde3f5d73cf
a_p = 44106885765559411
a_q = 38456719616722997

#bob - http://factordb.com/index.php?query=3104649130901425335933838103517383
b_n = 0x99122e61dc7bede74711185598c7
b_p = 62515288803124247
b_q = 49662237675630289

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return x

codez = open('strings.64').read().splitlines()

messages = []
for code in codez:
 msg = b64d(code).split(';')[0:3]
 out = []
 for m in msg:
  out.append(m.split('=')[1].strip().replace('0x','').replace('L',''))
 
 messages.append(out)  

flag = []
for msg in messages:
 seq = int(msg[0],10)
 c   = int(msg[1],16)
 sig = int(msg[2],16)

 d = egcd(e, (b_p - 1) * (b_q - 1))
 m = pow(c, d, b_n)
 v = pow(sig,e,a_n) # calculate the actual signature
 
 if m == v:
  flag.append([seq,chr(m)])

flag.sort(key=lambda y: int(y[0]))
print "[+] flag: ",
for c in flag:
 sys.stdout.write(c[1])

print

And the flag:

root@mankrik:~/hacklu/creative# ./c.py 
[+] flag: flag{n0th1ng_t0_533_h3r3_m0v3_0n}




Monday, October 19, 2015

Hackover15 - goto - 150pt Reverse Engineering Challenge

I didn't get time to play Hackover 15 as much as I wanted. It looked like a really fun competition but unfortunately it overlapped with Hitcon 2015. However I woke up super early (6am Saturday - eek!) to get a few hours in on Hackover before Hitcon started.

Here's an RE challenge I did very quickly and I just want to show how sometimes the environment you work in gives you a leg up. In this case PEDA (the GDB add-on) gave me the flag faster than I could reverse the binary.

The clue was:


The file, a compressed tarball, contains just one file: "goto.bin" which identifies as "data" with file...


root@mankrik:~/hackover/re150/writeup# tar -zxvf goto-03661d1a42ad20065ef6bfbe5a06287c.tgz 
goto.bin
root@mankrik:~/hackover/re150/writeup# file goto.bin 
goto.bin: data

Small headscratch here. I look at the file in XXD and see there's some shell script header here:


root@mankrik:~/hackover/re150/writeup# xxd goto.bin | head -5
0000000: 543d 743b 6361 7420 2430 207c 2074 6169  T=t;cat $0 | tai
0000010: 6c20 2d63 202b 3735 207c 2067 756e 7a69  l -c +75 | gunzi
0000020: 7020 2d20 3e20 2454 3b63 686d 6f64 202b  p - > $T;chmod +
0000030: 7820 2454 3b2e 2f24 543b 726d 202e 2f24  x $T;./$T;rm ./$
0000040: 543b 6578 6974 2030 3b0a 1f8b 0808 efae  T;exit 0;.......
root@mankrik:~/hackover/re150/writeup# head -1 goto.bin
T=t;cat $0 | tail -c +75 | gunzip - > $T;chmod +x $T;./$T;rm ./$T;exit 0;

Fine... Great... Mild obfuscation I am ok with :)

I decide just to let it decode itself...


root@mankrik:~/hackover/re150/writeup# sh goto.bin
PASSWORD:^C
root@mankrik:~/hackover/re150/writeup# ls -la t
-rwxr-xr-x 1 root root 4882 Oct 19 22:01 t
root@mankrik:~/hackover/re150/writeup# file t
t: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), for GNU/Linux 2.6.24, dynamically linked (uses shared libs), stripped

We now have the meat of the challenge, the ELF binary. Executing it, as we saw, simply asks for a PASSWORD:. I assume the flag is the password. Either way off to IDA Pro we go....

I decide to dynamically examine comparison points before diving in to perform a full static analysis. Often times simpler RE challenges can be solved rapidly with dynamic analysis, skipping a lot of time on the static analysis. I decide to set breakpoints at obvious loops.

The second such loop I examine is this one, I set a breakpoint at 0x4006aa (the cmp instruction):


I fire up GDB w/PEDA and watch the program execution:


root@mankrik:~/hackover/re150# gdb ./t 
GNU gdb (GDB) 7.4.1-debian
gdb-peda$ br *0x4006aa
Breakpoint 1 at 0x4006aa
gdb-peda$ r
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
PASSWORD:a
[----------------------------------registers-----------------------------------]
RAX: 0x601071 ("aMTCvd@CacAOEe #EgkPTSrd#S_oAOS e#SmvSO gs# eeSODoe#GtrWOEnr$Re1OONnt%Ao5ROIa ^Nr{DaE y&TCI\020sDgo#ET_\020l\020iu$DFU\020d\020v!%\020_S\020j\020e\020^\020{E\020k\020 \020&\020t_\020a\020y\020(\020hG\020s\020o\020^\020iO\020d\020u\020&\020sT\020j\020 \020*\020iO\020k\020u\020^\020s_\020l\020p\020&\020aW\020a\020,\020*\020dH\020"...)
RBX: 0x7fffffffe228 --> 0x7fffff000061 
RCX: 0xfbad2268 
RDX: 0x602010 --> 0x0 
RSI: 0x7ffff7ff4002 --> 0x0 
RDI: 0x7fffffffe22a --> 0xe26f00007fffff00 
RBP: 0x602010 --> 0x0 
RSP: 0x7fffffffe220 --> 0xc2 
RIP: 0x4006aa (cmp    cl,0x10)
R8 : 0x7ffff7dd8df0 --> 0x0 
R9 : 0x7ffff7fcf700 (0x00007ffff7fcf700)
R10: 0x22 ('"')
R11: 0x246 
R12: 0x40077f (xor    ebp,ebp)
R13: 0x7fffffffe360 --> 0x1 
R14: 0x0 
R15: 0x0
EFLAGS: 0x216 (carry PARITY ADJUST zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x40069e: mov    eax,0x601068
   0x4006a3: add    rax,0x9
   0x4006a7: mov    cl,BYTE PTR [rax-0x9]
=> 0x4006aa: cmp    cl,0x10
   0x4006ad: je     0x4006b6
   0x4006af: mov    BYTE PTR [rdx],cl
   0x4006b1: inc    rdx
   0x4006b4: jmp    0x4006a3
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffe220 --> 0xc2 
0008| 0x7fffffffe228 --> 0x7fffff000061 
0016| 0x7fffffffe230 --> 0x7fffffffe26f --> 0x7fffffffe36036 
0024| 0x7fffffffe238 --> 0x1 
0032| 0x7fffffffe240 --> 0x1 
0040| 0x7fffffffe248 --> 0x4008dd (add    rbx,0x1)
0048| 0x7fffffffe250 --> 0x7ffff7a61c48 --> 0xc001200002732 
0056| 0x7fffffffe258 --> 0x400890 (push   r15)
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00000000004006aa in ?? ()
gdb-peda$ 

Ok nothing so far, let's watch this loop for a while. I hit "c" for continue and watch the screen idly while the loop iterates. It's about at this point I stop because I notice a string being built in memory...


gdb-peda$ 

[----------------------------------registers-----------------------------------]
RAX: 0x6010ef --> 0x10261020106b1045 
RBX: 0x7fffffffe228 --> 0x7fffff000061 
RCX: 0xfbad2253 
RDX: 0x60201e --> 0x0 
RSI: 0x7ffff7ff4002 --> 0x0 
RDI: 0x7fffffffe22a --> 0xe26f00007fffff00 
RBP: 0x602010 ("hackover15{I_U")
RSP: 0x7fffffffe220 --> 0xc2 
RIP: 0x4006aa (cmp    cl,0x10)
R8 : 0x7ffff7dd8df0 --> 0x0 
R9 : 0x7ffff7fcf700 (0x00007ffff7fcf700)
R10: 0x22 ('"')
R11: 0x246 
R12: 0x40077f (xor    ebp,ebp)
R13: 0x7fffffffe360 --> 0x1 
R14: 0x0 
R15: 0x0
EFLAGS: 0x202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x40069e: mov    eax,0x601068
   0x4006a3: add    rax,0x9
   0x4006a7: mov    cl,BYTE PTR [rax-0x9]
=> 0x4006aa: cmp    cl,0x10
   0x4006ad: je     0x4006b6
   0x4006af: mov    BYTE PTR [rdx],cl
   0x4006b1: inc    rdx
   0x4006b4: jmp    0x4006a3
[------------------------------------stack-------------------------------------]
0000| 0x7fffffffe220 --> 0xc2 
0008| 0x7fffffffe228 --> 0x7fffff000061 
0016| 0x7fffffffe230 --> 0x7fffffffe26f --> 0x7fffffffe36036 
0024| 0x7fffffffe238 --> 0x1 
0032| 0x7fffffffe240 --> 0x1 
0040| 0x7fffffffe248 --> 0x4008dd (add    rbx,0x1)
0048| 0x7fffffffe250 --> 0x7ffff7a61c48 --> 0xc001200002732 
0056| 0x7fffffffe258 --> 0x400890 (push   r15)
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Breakpoint 1, 0x00000000004006aa in ?? ()
gdb-peda$ 

I decide to let this run to it's foregone conclusion.... Eventually the string decoding completes and RBP points to the entire flag:

RBP: 0x602010 ("hackover15{I_USE_GOTO_WHEREEVER_I_W4NT}")

I'm happy with that, I take the quick win and move on. I never did analyse the binary I but I don't mind...

HITCON 2015: PuzzleNG - 250pt Forensics Challenge

I don't mind admitting that Hitcon was HARD. Possibly some of the hardest challenges I've faced CTFing so far. Or maybe I was just rusty. Anyway here's one challenge I found particularly rewarding from Hitcon 2015.

The clue was fairly cryptic, not giving anything away. It simply delivered a compressed tarball...


When extracting the tarball we are rewarded with two files: "encrypt" and "flag.puzzle":

root@mankrik:~/hitcon/puzzleng/writeup# tar -zxvf puzzleng-edb16f6134bafb9e8b856b441480c117.tgz 
flag.puzzle
encrypt
root@mankrik:~/hitcon/puzzleng/writeup# ls -la
total 288
drwxr-xr-x  2 root root    4096 Oct 19 18:21 .
drwxr-xr-x 11 root root  262144 Oct 19 18:21 ..
-rwxr-xr-x  1  501 staff   9092 Oct 17 05:01 encrypt
-rw-r--r--  1  501 staff   1135 Oct 17 01:01 flag.puzzle
-rw-r--r--  1 root root    4409 Oct 17 16:10 puzzleng-edb16f6134bafb9e8b856b441480c117.tgz
root@mankrik:~/hitcon/puzzleng/writeup# file encrypt 
encrypt: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x7042def34be83440653a5031ea23059b5f5c7fb2, not stripped
root@mankrik:~/hitcon/puzzleng/writeup# file flag.puzzle 
flag.puzzle: data

So an ELF binary and a chunk of unidentified data which, judging by the name of the ELF binary may be "encrypted" flag file.

Sweet.

First things first, I examine the contents of flag.puzzle with a hexeditor but nothing immediate is revealed. Next I try the executable:


root@mankrik:~/hitcon/puzzleng/writeup# ./encrypt 
encrypt: encrypt.cpp:7: int main(int, char**): Assertion `argc == 3' failed.
Aborted

Ok it needs argc == 3, so we learned two things. It's written in C++ and requires two command line arguments.


root@mankrik:~/hitcon/puzzleng/writeup# ./encrypt 1 2
encrypt: encrypt.cpp:13: int main(int, char**): Assertion `fp != __null' failed.
Aborted

And so I assume one of the arguments needed is a file and the other is probably a key value.

Let's build a sample input and try and operate the encryption program against it.

I will choose a file consisting of all one character and a single byte key to observe the behavior of whatever algorithm or mechanics this encrypt program uses:


root@mankrik:~/hitcon/puzzleng/writeup# perl -e 'print "A" x 1000' > test.plain
root@mankrik:~/hitcon/puzzleng/writeup# ./encrypt A test.plain > test.cipher

The result looks ordered by blocks. We chose a 1,000 byte repeating character input and received a 1,000 byte output of ordered blocks of data of 50 bytes per block:


root@mankrik:~/hitcon/puzzleng/writeup# xxd test.cipher | head -10
0000000: 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c  ,,,,,,,,,,,,,,,,
0000010: 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c  ,,,,,,,,,,,,,,,,
0000020: 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c 2c2c  ,,,,,,,,,,,,,,,,
0000030: 2c2c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c  ,,..............
0000040: 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c  ................
0000050: 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c 8c8c  ................
0000060: 8c8c 8c8c 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d  ................
0000070: 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d  ................
0000080: 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d  ................
0000090: 0d0d 0d0d 0d0d a3a3 a3a3 a3a3 a3a3 a3a3  ................

Repeated executions give me the same output so there's probably no random IV or other input to the algorithm being used.

Time to fire up IDA Pro and examine the encrypt binary in the decompiler. We examine the main() function and see pretty much what we expect.


  if ( argc != 3 )
    __assert_fail("argc == 3", "encrypt.cpp", 7u, "int main(int, char**)");
  v3 = strlen(argv[1]);
  SHA1(argv[1], v3, v11);
  stream = fopen(argv[2], "r");
  if ( !stream )
    __assert_fail("fp != __null", "encrypt.cpp", 0xDu, "int main(int, char**)");
  fseek(stream, 0LL, 2);
  v8 = ftell(stream);
  rewind(stream);
  for ( i = 0; i <= 19; ++i )
  {
    for ( j = 0; j < (v8 + 19) / 20; ++j )
    {
      v9 = fgetc(stream);
      if ( v9 == -1 )
        break;
      putchar(v9 ^ v11[i]);
    }
  }
Above you can see the important bits of the code, it takes the command line argument, hashes it with SHA1 and uses the SHA1 output as a key across the input file. It spreads the key bytes across 20 even blocks of the input, using XOR of one of the key bytes per block.

So in theory, all we need to do to solve this is:

  • Divide the input into 20 evenly sized blocks
  • Discover the single-byte XOR key for each block, decrypt the block
  • Re-assemble the file into the decrypted output
Easy?!

To begin with, we use an old trick of a known plaintext attack. We think up likely strings that might appear somewhere in the file in order to get a headstart on some of the blocks. 

I try obvious ones first, JFIF, GIF and PNG as input strings, and using the "xorsearch" tool I quickly discover the encrypted file is probably a PNG:

root@mankrik:~/hitcon/puzzleng/writeup# xorsearch flag.puzzle PNG
Found XOR 65 position 0001: PNG....

So we found two pieces of information here, the file format (PNG) and the XOR key for the first block (0x65).

Next I split the file into blocks, before I do though, I use a quick Python script to double-check the actual block size being used here:


#!/usr/bin/python
import subprocess
open('generated.plaintext','w').write('A' * 1135)
ctext = subprocess.check_output(['./encrypt','a','generated.plaintext'])

firstbyte = ctext[0]

for b in range(0,len(ctext)):
        if ctext[b] != firstbyte:
                print "blocksize is " + str(b)
  quit()

Which returns:

root@mankrik:~/hitcon/puzzleng/writeup# ./c.py 
blocksize is 57

So we can use split to extract the chunks:


root@mankrik:~/hitcon/puzzleng/writeup# split -b 57 -d flag.puzzle 

Next we can use the known plaintext attack against further chunks. We know PNG files contain IDAT before image data chunks and end with "IEND", we use that to recover two more keys:


root@mankrik:~/hitcon/puzzleng/writeup# xorsearch x01 IDAT
Found XOR 30 position 0021: IDATx...A..0......5..H_v
root@mankrik:~/hitcon/puzzleng/writeup# xorsearch x19 IEND
Found XOR 1B position 002C: IEND.B`.

Great, getting somewhere. We have 3/20 keys. What other patterns can we use for this attack?

Well PNGs can contain several IDAT chunks, but nope we don't find any evidence of that in this image. No Exif data. Hmm. 17 files each with 256 possible keys adds up to a lot of possible image files.

I was stuck here a while, until i decided to look for non obvious patterns. Luckily I found two such patterns very quickly. Inside the final chunk, decrypted using the key we found with xorsearch above, we see the following:


root@mankrik:~/hitcon/puzzleng/writeup# xortool-xor -h 1b -f x19 > x19.plain
root@mankrik:~/hitcon/puzzleng/writeup# xxd x19.plain 
0000000: 6bc9 bf5b 4824 1289 4422 9148 2412 8944  k..[H$..D".H$..D
0000010: 2291 4824 1289 4422 9148 2412 795c ff00  ".H$..D".H$.y\..
0000020: c3f9 b034 d9bf 3b6a 0000 0000 4945 4e44  ...4..;j....IEND
0000030: ae42 6082 0a                             .B`..

Repeated strings of H$ and D". Could this be re-occuring throughout the file? Worth a try.

In fact they do, each chunk of encrypted data has either H$ or D" (usually both) inside it with little variation on position:


root@mankrik:~/hitcon/puzzleng/writeup# xorsearch x02 H$
Found XOR 56 position 0012: H$..D".H$..D".H$..D".H....k}..{M={O}W..
Found XOR 56 position 0019: H$..D".H$..D".H....k}..{M={O}W..
Found XOR 56 position 0020: H$..D".H....k}..{M={O}W..
root@mankrik:~/hitcon/puzzleng/writeup# xorsearch x03 D\"
Found XOR C3 position 0001: D".H........"..}.>.!..D"....,]...D.f.)..D"..w...
Found XOR C3 position 0017: D"....,]...D.f.)..D"..w...
Found XOR C3 position 0029: D"..w...

And so on throughout the file...

Using this method we are able to isolate the entire 20 byte xor key which we find to be:

653056c378ff4bbff74737e36f53264c25f4d11b

Using this Python code we quickly split and decrypt the file using our recovered key:


#!/usr/bin/python

thekeys = ['\x65','\x30','\x56','\xc3','\x78','\xff','\x4b','\xbf','\xf7','\x47','\x37','\xe3','\x6f','\x53','\x26','\x4c','\x25','\xf4','\xd1','\x1b']

blocksize = 57
plain = []

puzzle = open('flag.puzzle','rb').read()
whichkey = 0
for i in range(0,len(puzzle),blocksize):
        piece = puzzle[i:i+blocksize]
        chunklist = list(piece)
        for c in range(0,len(chunklist)):
                plain.append(chr(ord(chunklist[c])^ord(thekeys[whichkey])))      
        whichkey += 1

open('output.png','wb').write("".join(plain))


Resulting in the following output...


Great? A purple block...

Thinking there's more to it, I switch to the trusty old Stegosolve.jar program and flip through the standard filters. On the blue plane we are lucky and find a hidden QR code:


Which, THANKFULLY, stores the text of the flag:

hitcon{qrencode -s 16 -o flag.png -l H --foreground 8F77B5 --background 8F77B4}

A fun little challenge for sure.