TokyoWesterns CTF 6th 2020 Writeup

1. はじめに

2020/09/19(土) 00:09:00 JST — 2020/09/21(月) 00:09:00 JST で、TokyoWesterns CTF 6th 2020 にTeam 「N30Z30N」としてソロ参加し、Welcome以外にCryoto3問を解いて496点（得点を得た648チーム中96位）でした。

ちなみに、去年はをCryoto2問を解いて224位/1004チームなので、「少しだけ進歩した」のかもしれません。

2. Writeup

2-0. Welcome!! (33点、warm up)

問題文

The flag is TWCTF{Welcome_to_TWCTF_2020!!!}.

解法

フラグの部分をコピペします。

フラグ

TWCTF{Welcome_to_TWCTF_2020!!!}

2-1. easy hash (Cryoto、75点、warm up)

問題文

Source Code: easy_hash.7z
Web Server: https://crypto01.chal.ctf.westerns.tokyo

For beginners: you can use curl to interact with the web server.

(Example)
$ curl https://crypto01.chal.ctf.westerns.tokyo -d 'twctf: hello 2020'

添付ファイル（解凍後）

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)

requirements.txt

functions-framework ~= 2.0

Dockerfile

FROM python:3.8

ENV APP_HOME /app
WORKDIR $APP_HOME
COPY . .

RUN pip install -r requirements.txt

# This is only for deployment on GCP, not related to the task.
RUN wget https://github.com/nomeaning777/exec-with-secret/releases/download/v0.1.2/exec-with-secret-amd64 -O /bin/exec-with-secret && chmod +x /bin/exec-with-secret

USER nobody:nogroup
ENTRYPOINT [ "/bin/exec-with-secret", "functions-framework", "--target", "index" ]

解法

いわゆる「proof of work」です。main.pyを読むと、送り込む文字列の条件として「先頭7文字が'twctf: '」「末尾4文字が'2020'」とあります。最低限これだけを満たせばOKなのですが、少し遊び心を出して、MSGの「flag」の部分をほかの文字列に書き換える形のソルバを作りました。

solve.py

import struct
import itertools
from Crypto.Util.number import *

MSG = b'twctf: please give me the flag of 2020'
MSG_H = b'twctf: please give me the '
MSG_T = b' of 2020'

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

em = easy_hash(MSG)

for x, y, z, w in itertools.product(range(0x20,0x7f),repeat=4):
  s = MSG_H + long_to_bytes(x) + long_to_bytes(y) + long_to_bytes(z) + long_to_bytes(w) + MSG_T
  if(easy_hash(s) == em):
    print(s.decode())
    exit()

文字列「twctf: please give me the ~~~ of 2020」（theの右側は半角スペース2つ）を得ます。さしづめ、「ミミズ（ ~~~）をください」といったところでしょうか:-)。問題文のsuggestionにあるとおり手元のLinux上で

curl https://crypto01.chal.ctf.westerns.tokyo -d 'twctf: please give me the ~~~ of 2020'

を実行して、フラグをゲットできました。

フラグ

TWCTF{colorfully_decorated_dream}

2.2 twin-d (Cryoto、172点)

問題文

twin-d.7z

添付ファイル（解凍後）

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

output

{"n":"26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433","e1":"3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127","e2":"20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905","enc":"18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046"}

解法

RSA問題ですが、modulus(n)、exponent(e1)、暗号文(enc)の三点セットに加え、e2 * (d+2) = 1 mod (p-1)(q-1) を満たす e2 が与えられています。
e1、e2の作り方から、 2 * e1 * e2 - e1 + e2 は mod (p-1)(q-1) で 0 となります。
ゆえに、mod n で考えて enc ** (2 * e2) = m ** (2 * e1 * e2) = m ** (e1 - e2)。
ここで、gcd(e1,e2) = gcd(e1, e1-e2) = 1 ですから、e1, (e1-e2) に関する "common modulus attack" を適用できます。

solve.py

from Crypto.Util.number import *
from factordb.factordb import FactorDB
import gmpy2

n = 26524843197458127443771133945229625523754949369487014791599807627467226519111599787153382777120140612738257288082433176299499326592447109018282964262146097640978728687735075346441171264146957020277385391199481846763287915008056667746576399729177879290302450987806685085618443327429255304452228199990620148364422757098951306559334815707120477401429317136913170569164607984049390008219435634838332608692894777468452421086790570305857094650986635845598625452629832435775350210325954240744747531362581445612743502972321327204242178398155653455971801057422863549217930378414742792722104721392516098829240589964116113253433
e1 = 3288342258818750594497789899280507988608009422632301901890863784763217616490701057613228052043090509927547686042501854377982072935093691324981837282735741669355268200192971934847782966333731663681875702538275775308496023428187962287009210326890218776373213535570853144732649365499644400757341574136352057674421661851071361132160580465606353235714126225246121979148071634839325793257419779891687075215244608092289326285092057290933330050466351755345025419017436852718353794641136454223794422184912845557812856838827270018279670751739019476000437382608054677808858153944204833144150494295177481906551158333784518167127
e2 = 20586777123945902753490294897129768995688830255152547498458791228840609956344138109339907853963357359541404633422300744201016345576195555604505930482179414108021094847896856094422857747050686108352530347664803839802347635174893144994932647157839626260092064101372096750666679214484068961156588820385019879979501182685765627312099064118600537936317964839371569513285434610671748047822599856396277714859626710571781608350664514470335146001120348208741966215074474578729244549563565178792603028804198318917007000826819363089407804185394528341886863297204719881851691620496202698379571497376834290321022681400643083508905
enc = 18719581313246346528221007858250620803088488607301313701590826442983941607809029805859628525891876064099979252513624998960822412974893002313208591462294684272954861105670518560956910898293761859372361017063600846481279095019009757152999533708737044666388054242961589273716178835651726686400826461459109341300219348927332096859088013848939302909121485953178179602997183289130409653008932258951903333059085283520324025705948839786487207249399025027249604682539137261225462015608695527914414053262360726764369412756336163681981689249905722741130346915738453436534240104046172205962351316149136700091558138836774987886046

enc0 = pow(enc, 2*e2, n)
e0 = e1 - e2

_, x0, x1 = gmpy2.gcdext(e0, e1)
print(long_to_bytes((pow(enc0,x0,n)*pow(enc,x1,n))%n).decode())

フラグ

TWCTF{even_if_it_is_f4+e}

2.3 sqrt (Cryoto、216点)

問題文

sqrt.7z

添付ファイル（解凍後）

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

output.txt

5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233

解法

※後から見直しても、「力技」感が否めません。もっとスマートな方法があったような気がしますが、自分の力ではこれが精一杯でした。
平文を $m$、暗号文を $c$ とすると、$c = m^{2^{64}} \mod p$ という関係にあります。$2$ 冪なのでこの問題のタイトルである「sqrt」（平方根計算）を頑張ればどうにかなりそうな気分なのですが、$2^{64}$ 乗根は流石に辛いので少し頭を使う必要があります。
まずは事前にFactorDBで $p-1$ の $2$ 冪約数を事前に調べ、「$p-1$ は $2^{30}$ をきっかり割る」ことを把握しました。
$2^{34}$ の $\mod{(p-1)/(2^{30})} $ での逆元 $u$ は計算できますので、これを使って
$c^{u} \mod{p}= (m^{2^{64}})^{u} \mod{p}= (m^{2^{30}})^{2^{34}u} \mod{p} = m^{2^{30}} \mod{p} $
とできます。つまり、$m^{2^{30}} \mod{p} = c^{u} \mod{p}$ となる $m$ を求める問題に帰着（状況改善）します。
この段階で、$c^{u}$ の $\mod{p}$ での平方根を $30$ 回とったものが解の候補となるのですが、これ以上状況を改善する方法がみつからなかったので、「$c^{u} \mod{p}$ の $2^{30}$ 乗根1つ」に「$1 \mod{p}$ の原始 $2^{30}$ 乗根」を逐次乗じてbruteforceすることにしました。なお、$\mod{p}$ での平方根計算のため、「SageMath」の力を借りています。

solve.sage

from sage.all import *
from Crypto.Util.number import *
c = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
k = 64
F = GF(p)

def square_root(x, mod, times):
  for _ in range(times):
    x =  F(x).sqrt()
  return(x)

cnt = 30 #by FactorDB

t = (p - 1) // (2 ** cnt)
assert(t % 2 !=0 and t * (2**cnt)== p-1)
u = inverse(2**(k-cnt), t)
C = pow(c, u, p)

r_C = square_root(C, p, cnt)
assert(pow(r_C, 2**cnt, p) == C)
r_ONE = square_root(p-1, p, cnt-1)
assert(pow(r_ONE, 2**(cnt-1), p) == p-1)

x = r_C
for i in range(2**(cnt-1)):
  x = (x * r_ONE) % p
  if(long_to_bytes(x)[0:6] == b"TWCTF{"):
    print(long_to_bytes(x).decode())
    exit()
  if(long_to_bytes(p-x)[0:6] == b"TWCTF{"):
    print(long_to_bytes(p-x).decode())
    exit()

数時間経過後、フラグが現れました。

フラグ

TWCTF{17s_v3ry_34sy_70_f1nd_th3_n_7h_r007}

3. おわりに

warmup問題は全て解きたかったのですが、力不足のため未遂に終わりました。
今回は十分な睡眠を心掛けたので、健康面での問題はほぼ皆無でした。
なお、「気合と根性でやれば出来たのでは？」という疑問を持つ向きもあると思いますが、必要だったなのはそういったものではなく、「短時間でサクサク解く実力」だったと考えます。