Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What is going on with this article?
@MFT-N-E

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

1
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
MFT-N-E
Independent Scholar(Mathematics, Railway history), system engineer, and newbie CTF player. In rehabilitation of mathematics while playing CTF...

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
1
Help us understand the problem. What is going on with this article?