Hack in the Box 2014 CTF Writeup - KeygenMe with RSA

這次被以 HITCON 的身份邀請到馬來西亞參加 HITB 2014 CTF，照慣例來寫篇 Write Up

這次結果只有亞軍第二名有點殘念，第二天下午攻擊程式停了四小時少了幾萬分，不然應該有望第一XD

不過也是經驗，有個自動化攻擊以及送 Flag 的 Framework 真的還滿重要的，沒準備好也是失策XDRZ

HITB 這次是以 Attack & Defense 加上 Jeopardy 形式舉辦，每個隊伍有一檯實體主機，上面 run 個 Ubuntu 14.04 on VMPlayer。 隊伍要想辦法自己取得 root 以及找到服務開啟，到比賽截止前主辦方共放出了 4 個 Daemon 以及 7 個 Challenge

比賽形式是以宇宙機戰的模式進行，每回合成功 Keep 住 Daemon 獲得 100 生命值，成功攻擊其他隊伍 Daemon Flag 獲得 200 生命值，而 Challenges 則是加分項目，成功解開一個獲得 2000 - 3000 不等的生命值

而雖然這次的比賽是以 Attack & Defense 型式進行，不過各 Daemon 服務比較像是 Reversing & Puzzle 的綜合，成功解開後 Daemon 會自行讀取 Flag 吐給你，所以整場比賽也都不會用到 Overflow, Shellcode, ROP… 等，另外的 Challenge 則比較偏向 Reversing 以及 Stego 的形式。

這次的 Write Up 就是本次 CTF Challenge 中的一題 Reversing 題目，雖然本身是 Web 狗、滲透狗，不過在這種對我們不友善的地方還是只能哭著下去看 T_____T

題目是一題 Keygen Me，標題是 HITB2013KUL 不知道是 Typo Error 還是去年出的題目沒有用上放到今年開XDDDDD

很直觀的就是一個驗證程式要寫出註冊碼，正確會顯示 Correct 錯誤會顯示 Wrong，理所當然使用爆破直接改跳轉點是沒有用的。 二話不說拖進 IDA!

一堆臭臭長長的 Function 沒有辨識出來，OEP 怪怪的不過不影響分析，Visual C++ 編出來的程式多了一些怪程式區段滿機車的 T___T

使用 GetDlgItemText 可以把關鍵地方定位出來，仔細觀察發現程式有使用 MIRACL 的 C++ 大數函示庫，可以從 這篇 文章中將各個函數作用大致識別出來，如 subtract, divide, powmod 等，如此一來分析輕鬆了許多！

接著花了幾個小時分析，把大致程式邏輯給弄懂如下

（IDA 靜態分析中雖然沒有看到對於 e 的賦值，不過可以透過動態追蹤會發現 e = 17）

看起來是對 Input 進行處理後使用 RSA 加密起來並且最後與密文進行比對，成功則是正確的 Flag！ RSA 依靠大質數保護演算法的安全，其中用到的大質數乘積為

7906961983747432626460011685427449111190647169309825535629493220735583689550836202522449

滿短的應該可以很快解出，丟進 Factordb 中可以馬上分解出

7906961983…49 = 88899280969284710491078307117271523349979587 x 88942923919478497069248398794539034790292827

所以現在有了

p = 88899280969284710491078307117271523349979587
q = 88942923919478497069248398794539034790292827
e = 17
n = 7906961983…49

複習了一下好久沒碰的 RSA，當把 N 解開有了 P 跟 Q 後接下來可以求出 Private Key D 來，這邊使用 rsatool 來用

1
2
3
4
5
6
7
8
9
10
11
12
13
orange@me:~$ python rsatool.py \
    -p 88899280969284710491078307117271523349979587 \
    -q 88942923919478497069248398794539034790292827 \
    -e 17 \
    -n 7906961983747432626460011685427449111190647169309825535629493220735583689550836202522449

Using (p, q) to initialise RSA instance

n = fe6277ac25de48eedb829ad5458bc32e0dd678c80a123ecd73a54cb08eb719017cc88c751
e = 17 (0x11)
d = d17e446fa6b70ee2d2e40709fd09afcb92ec72dbe4c3614dcfb8a25b150b817622e58ae49
p = 3fc8381a552f012766fc3078a07f8103761c3
q = 3fd03c2f3c9b63f9208ee942c904d16536d5b

得到 D 之後就可以解上面要解的密文了！

1
2
3
4
5
6
orange@me:~$ echo 021abe7c17d73978e63835b0e76ad6120f5a3f8148f3de87da6e5b07bf7b76041c78aedf0c |  \
    xxd -r -p | python rsacrack.py \
        -d d17e446fa6b70ee2d2e40709fd09afcb92ec72dbe4c3614dcfb8a25b150b817622e58ae49 \
        fe6277ac25de48eedb829ad5458bc32e0dd678c80a123ecd73a54cb08eb719017cc88c751 | xxd -p -c 64

0000000000000000000000000000000000000000000001c2f3db8f478caafc84b10ed113

得到明文 1c2f3db8f478caafc84b10ed113，不過這是運算過後的結果 =___=

所以要根據剛剛的運算弄出逆算法（數學苦手XDRZ）

最後推出

0x1c2f3db8f478caafc84b10ed113 * 66772239585999913610952241123315507216972277506025821^N + 29411180916569003283374190496632319086172136623216324

出來的結果就可以以十進位五個一組五個一組推回原本的 FLAG ，又因為是 mod 的逆運算，根據 N 的值答案可以不只一組（ N=1,2,3 … ），最後得出當 N=1 的時候會有 printable 的解!

2385648152415111590458116323765417147676516881603229820532451315251688506013237646763

解碼後為