Break the Syntax CTF 2022 Writeup

この大会は2022/6/4 1:00(JST)~2022/6/5 19:00(JST)に開催されました。
今回もチームで参戦。結果は4095点で118チーム中5位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity check (misc)

Discordに入り、#ruleチャネルのルールの一番最後にフラグが書いてあった。

BtSCTF{good_luck}

Identity (crypto)

x, yについて以下を満たすように指定するとフラグが表示される。

x == pow(generator, y, prime_p) * pubkey) % prime_p

すべてのパラメータがわかっているので、適当なyで計算し、xを求めればよい。

#!/usr/bin/env python3
import socket
import json

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('34.107.92.149', 30085))

prime_p = 177722061268479172618036265876397003509269048504268861767046046115994443156284488651055714387194800232244730303458489864174073986896097610603558449505871398422283548997781783328299833985053166443389417018452145117134522568709774729520563358860355765070837814475957567869527710749697252440829860298572991179307
prime_q = 88861030634239586309018132938198501754634524252134430883523023057997221578142244325527857193597400116122365151729244932087036993448048805301779224752935699211141774498890891664149916992526583221694708509226072558567261284354887364760281679430177882535418907237978783934763855374848626220414930149286495589653
generator = 155023513036247948265047543654868687396096131010469506673664792405197011708229660714554316186573661708325589755749538173765363486885279182722265095526282277543504738661074255038508180451933144124775391105622347889120007632958758010276343139080391061202699695556814560529729431091459632136589488173063954346793
pubkey = 93091921640159468106305784288442650651946378295897246569419220256788465679993825629909743857075454596032445144833173746431710294553277863156332557755414563641361390587128850058131535616906913180516458195808877783654160132170722826553007632858895507833301845277489859624212766615307390655119628578839365223546

y = 0
x = (pow(generator, y, prime_p) * pubkey) % prime_p
payload = json.dumps({"x": x, "y": y})

data = recvuntil(s, b': ')
print(data + payload)
s.sendall(payload.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

send proof in json format: {"x": 93091921640159468106305784288442650651946378295897246569419220256788465679993825629909743857075454596032445144833173746431710294553277863156332557755414563641361390587128850058131535616906913180516458195808877783654160132170722826553007632858895507833301845277489859624212766615307390655119628578839365223546, "y": 0}
Verification success
BtSCTF{I_d1DN7_m4K3_i7_Ch4113nG1nG}
BtSCTF{I_d1DN7_m4K3_i7_Ch4113nG1nG}

Identity-2 (crypto)

x, yについて以下を満たすように指定するとフラグが表示される。

x == (pow(generator, y, prime_p) * pow(pubkey, c, prime_p)) % prime_p

cのパラメータも実行時にわかり、すべてのパラメータがわかっているので、適当なyで計算し、xを求めればよい。

#!/usr/bin/env python3
import socket
import json

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('34.107.92.149', 2439))

prime_p = 136062877477772021443963986821466822423928306636725705955189295265171531194630539497933022412421177627488716473227275120023271715397034546804175879349877168981582602251424924699340785448683074807806407936267383798949594772365085169340683942944085482956202789355681500477966677233789310292180313638378062381719
prime_q = 68031438738886010721981993410733411211964153318362852977594647632585765597315269748966511206210588813744358236613637560011635857698517273402087939674938584490791301125712462349670392724341537403903203968133691899474797386182542584670341971472042741478101394677840750238983338616894655146090156819189031190859
generator = 68695322546411990097618816719880607069395444393834268960741680054974511660271970026150039567236118658479679444015844573677880347686810169165388385685914903968147097279757787122753390447954112451193808647256026282821032909814441591222220915875289906762225085266354556177943238500761050758957943922408034634359
pubkey = 36991800195284720665844271720947930981390989677197504667186660329002236402308726349324091955441781822949964937615015455023644196915268032941399396215222246260792225979887225009692399584709504066456654354497353988045808198493705842231370889778472138080706702885925221219949367522908916161488494916365255595354

data = recvuntil(s, b'\n').rstrip()
print(data)
chal = json.loads(data)
c = chal['c']

y = 0
x = (pow(generator, y, prime_p) * pow(pubkey,c,prime_p)) % prime_p
payload = json.dumps({"x": x, "y": y})

print(payload)
s.sendall(payload.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)

実行結果は以下の通り。

{"c": 8554508060026173226740607295246315481427823631609160646634016323372970087540956464852944707162677753349119195341916576402218028466551901371599644851155529}
{"x": 94209527141091215246160364916298062874273740936838084385724116936981081681291298343374894548823434041566575151153307598728950139107263463064351870013395135637557545179594967732376670015816246625364136115416032390664982895193253147782808215079678053471101913177960586980909603494537253124184157972055892048616, "y": 0}
Verification success
BtSCTF{NuMb3r_Us3d_0nLy_Tw1c3}
BtSCTF{NuMb3r_Us3d_0nLy_Tw1c3}

xoxoxo (crypto)

1バイト鍵のXOR暗号と推測し、フラグが"B"から始まる前提で復号する。

#!/usr/bin/env python3
with open('xoxoxo', 'r') as f:
    enc = bytes.fromhex(f.read().rstrip())

key = enc[0] ^ ord('B')

flag = ''
for c in enc:
    flag += chr(c ^ key)
print(flag)
BtSCTF{0n3_by7e_p4d_r4r3ly_w0rks}

Shorty (crypto)

nをyafuで素因数分解する。

>yafu-x64.exe "factor(56767131765767377932609645263054275838382295575884897700121797017632070969059)" -v -threads 4


06/04/22 19:03:10 v1.34.5 @ RINA-TAKUMI, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes
measured cpu frequency ~= 2919.493460
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> fac: factoring 56767131765767377932609645263054275838382295575884897700121797017632070969059
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C77
rho: x^2 + 2, starting 1000 iterations on C77
rho: x^2 + 1, starting 1000 iterations on C77
pm1: starting B1 = 150K, B2 = gmp-ecm default on C77
fac: setting target pretesting digits to 23.69
fac: sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t23.69
ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 23.69
fac: t15: 1.00
fac: t20: 0.04
fac: sum of completed work is t15.18
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t23.69
ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 23.69
fac: t15: 7.17
fac: t20: 1.04
fac: t25: 0.05
fac: sum of completed work is t20.24
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 149 more curves at B1=50000 needed to get to t23.69
ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec
fac: setting target pretesting digits to 23.69
fac: t15: 28.45
fac: t20: 8.13
fac: t25: 0.74
fac: t30: 0.05
fac: sum of completed work is t23.72

starting SIQS on c77: 56767131765767377932609645263054275838382295575884897700121797017632070969059

==== sieve params ====
n = 77 digits, 255 bits
factor base: 34944 primes (max prime = 878387)
single large prime cutoff: 74662895 (85 * pmax)
allocating 7 large prime slices of factor base
buckets hold 2048 elements
using SSE4.1 enabled 32k sieve core
sieve interval: 10 blocks of size 32768
polynomial A has ~ 10 factors
using multiplier of 1
using SPV correction of 20 bits, starting at offset 32
using SSE2 for x64 sieve scanning
using SSE2 for resieving 13-16 bit primes
using SSE2 for 8x trial divison to 13 bits
using SSE4.1 and inline ASM for small prime sieving
using SSE2 for poly updating up to 15 bits
using SSE4.1 for medium prime poly updating
using SSE4.1 and inline ASM for large prime poly updating
trial factoring cutoff at 90 bits

==== sieving in progress ( 4 threads):   35008 relations needed ====
====            Press ctrl-c to abort and save state            ====
35677 rels found: 17740 full + 17937 from 186367 partial, (10589.02 rels/sec)

sieving required 74801 total polynomials
trial division touched 2858589 sieve locations out of 49021583360
QS elapsed time = 19.3016 seconds.

==== post processing stage (msieve-1.38) ====
begin with 204107 relations
reduce to 51278 relations in 2 passes
attempting to read 51278 relations
recovered 51278 relations
recovered 37175 polynomials
freed 12 duplicate relations
attempting to build 35665 cycles
found 35665 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 17740
   length 2 : 17925
largest cycle: 2 relations
matrix is 34944 x 35665 (5.1 MB) with weight 1045467 (29.31/col)
sparse part has weight 1045467 (29.31/col)
filtering completed in 4 passes
matrix is 25460 x 25524 (4.0 MB) with weight 839149 (32.88/col)
sparse part has weight 839149 (32.88/col)
saving the first 48 matrix rows for later
matrix is 25412 x 25524 (3.3 MB) with weight 680053 (26.64/col)
sparse part has weight 601219 (23.56/col)
matrix includes 64 packed rows
using block size 10209 for processor cache size 16384 kB
commencing Lanczos iteration
memory use: 3.0 MB
lanczos halted after 403 iterations (dim = 25412)
recovered 18 nontrivial dependencies
Lanczos elapsed time = 0.8870 seconds.
Sqrt elapsed time = 0.0120 seconds.
SIQS elapsed time = 20.2011 seconds.
pretesting / qs ratio was 0.55
Total factoring time = 31.4245 seconds


***factors found***

P39 = 198575889004568310405059947668702420947
P39 = 285871220571302236301037423024394027697

ans = 1

素因数分解できたので、RSA暗号としてkeyを復号する。
あとはAESと推測して、まずECBモードで復号するが、フラグにならない。
暗号の先頭16バイトをIVとして、CBCモードで復号すると、フラグになった。

#!/usr/bin/env python3
from Crypto.Util.number import *
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES

import base64

enc_flag = 'TVlfUkFORE9NX0lWX0NCQ3tBV1dLOJ1J/nMvT0BsVlHdmJEgYO5ZPpwU1tPifgcq5pFfxezgomriywd9wf9J693MiGqB3AnaXKF6JnyxDQw='
enc_flag = base64.b64decode(enc_flag)

c = 39418869940107296504467504059240015071240032703306554459991103074090231844776
e = 3
n = 56767131765767377932609645263054275838382295575884897700121797017632070969059

p = 198575889004568310405059947668702420947
q = 285871220571302236301037423024394027697
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
key = long_to_bytes(m)

iv = enc_flag[:16]
enc_flag = enc_flag[16:]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc_flag), 16).decode()
print(flag)
BtSCTF{rs4_4nd_sh0r7_k3ys_d0nt_m1x_l1k3_tw0_b17s}

Code book (crypto)

$ nc 34.107.92.149 4444
What is your name?
a
Here is your encrypted message:
62751a7345c8ef7528b17c13ace71270c42fbd0c5121dfad626395626b942dcb4e65733c45eb661fa356f2feb6ee84e2e05c89b4d261d9951fe6632f0d2fa5c525b9a72a2ae2a3f9fb1831049460d0fd
DEBUG MODE ON
LOGGING USER INPUT {"username": "a", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd04c376666008f6e42e8066d34f4ba3100ec28d0e54098068706b05b7f69c714c63d9205627136779fdaa848029a1ed521b120bc969ca4a4849feaca85b8b2c90a
DEBUG MODE ON
LOGGING USER INPUT {"username": "aa", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aaaaaaaa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd0de046e55630d9691bb655055b99875b188c871b167c489f15698ccf0102fc72452012aaf36f9382a475c1e939f0d02b6c8cf5eec385953e22833c030376311ec
DEBUG MODE ON
LOGGING USER INPUT {"username": "aaaaaaaa", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aaaaaaaaaaaa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd0662c99d1292fc6a6586a088709add2fc9e0f536b0f7422c43175286fa1b0ff4c0f88fd90bce333b4abfd0dfb96d06349e8bc98d98a3aa734a0041d78ebab4012
DEBUG MODE ON
LOGGING USER INPUT {"username": "aaaaaaaaaaaa", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aaaaaaaaaaaaaaaa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd009cf7331864195029ac0fb176ca2fab902f3407f34ff7eda3d194a2e49ae2ee190b2911291a2e057682daaa65fcc76f8466c9e5f0355cf8cbd7ec192dfc64861
DEBUG MODE ON
LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aaaaaaaaaaaaaaaaa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd0fd2e19347f803cd0ef96662d1ca238b6c42fbd0c5121dfad626395626b942dcb4e65733c45eb661fa356f2feb6ee84e2e05c89b4d261d9951fe6632f0d2fa5c525b9a72a2ae2a3f9fb1831049460d0fd
DEBUG MODE ON
LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"}

$ nc 34.107.92.149 4444
What is your name?
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd083505c5fbd22f8d37c897dde817e805e83505c5fbd22f8d37c897dde817e805e4c376666008f6e42e8066d34f4ba3100ec28d0e54098068706b05b7f69c714c63d9205627136779fdaa848029a1ed521b120bc969ca4a4849feaca85b8b2c90a
DEBUG MODE ON
LOGGING USER INPUT {"username": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "flag": "redacted for security reasons"}

以下のようにAES ECBモードで暗号化されると推測できる。

0123456789abcdef
{"username": "aa
aaaaaaaaaaaaaaa"
, "flag": "FFFFF
FFFFFFFFFFFFFFFF
FFFFFFFFFFFFFF"}
PPPPPPPPPPPPPPPP

0123456789abcdef
{"username": "aa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
", "flag": "FFFF
FFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFF"
}PPPPPPPPPPPPPPP

フラグを1文字ずつはみ出させ、ブルートフォースでブロック単位で暗号が一致するものを求めていく。
フラグ1バイト目をはみ出させる場合は、以下のような構成。

0123456789abcdef
{"username": "aa
aaa", "flag": "?
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaa", "flag": "F
FFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFF
FF"}PPPPPPPPPPPP
#!/usr/bin/env python3
import socket
import json

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

flag = ''
for i in range(35):
    for code in range(32, 127):
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect(('34.107.92.149', 4444))

        cmp_pt = ('aaa", "flag": "' + flag)[-15:]
        try_pt = 'aa' + cmp_pt + chr(code) + 'a' * (35 - i)

        data = recvuntil(s, b'\n').rstrip()
        print(data)
        print(try_pt)
        s.sendall(try_pt.encode() + b'\n')
        data = recvuntil(s, b'\n').rstrip()
        print(data)
        data = recvuntil(s, b'\n').rstrip()
        print(data)
        try_ct = data
        data = recvuntil(s, b'\n').rstrip()
        print(data)
        data = recvuntil(s, b'}')
        print(data)
        s.close()

        if try_ct[32*1:32*2] == try_ct[32*4:32*5]:
             flag += chr(code)
             break

print(flag)

実行結果は以下の通り。

        :
What is your name?
aas_why_3cb_sucksza
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd071b0148352af4709e8e03ebf62397be372957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924
DEBUG MODE ON
LOGGING USER INPUT {"username": "aas_why_3cb_sucksza", "flag": "redacted for security reasons"}
What is your name?
aas_why_3cb_sucks{a
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd043642ee30ab2a12b427f8c50237fc14672957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924
DEBUG MODE ON
LOGGING USER INPUT {"username": "aas_why_3cb_sucks{a", "flag": "redacted for security reasons"}
What is your name?
aas_why_3cb_sucks|a
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd0b89c902f4933db53c54d40bd04d41f9172957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924
DEBUG MODE ON
LOGGING USER INPUT {"username": "aas_why_3cb_sucks|a", "flag": "redacted for security reasons"}
What is your name?
aas_why_3cb_sucks}a
Here is your encrypted message:
f1c424769c602d96e3d7d9649139efd09c0a04efd23960a8e629361af9a251dc72957d0030941d593331515523fb9cf2e625b3aa92c97b3c7b6a9d87f2c0d3959c0a04efd23960a8e629361af9a251dc1f55fec5399eade2d7851e3c61f5d924
DEBUG MODE ON
LOGGING USER INPUT {"username": "aas_why_3cb_sucks}
BtSCTF{0h_s0_th1s_1s_why_3cb_sucks}
BtSCTF{0h_s0_th1s_1s_why_3cb_sucks}

Substitute (crypto)

some_catsディレクトリには26個の猫の画像がある。おそらくアルファベットに対応している。catsフォルダには同じ猫の画像の他に、スペースや記号の画像がある。まずは画像ファイルのハッシュ値を元に、catsフォルダの画像を文字に対応付けしてみる。

#!/usr/bin/env python3
from hashlib import *
from string import *

hashes = []
for i in range(1, 27):
    fname = 'static/some_cats/%d.jpg' % i
    with open(fname, 'rb') as f:
        data = f.read()
    hashes.append(md5(data).hexdigest())

msg = ''
others = {}
for i in range(1, 682):
    fname = 'static/cats/%d.jpg' % i
    with open(fname, 'rb') as f:
        data = f.read()
    h = md5(data).hexdigest()
    if h in hashes:
        msg += ascii_uppercase[hashes.index(h)]
    elif h in others:
        msg += others[h]
    else:
        if i == 4:
            others[h] = ' '
            msg += ' '
        elif i == 58:
            others[h] = '.'
            msg += '.'
        elif i == 249:
            others[h] = ','
            msg += ','
        elif i == 335:
            others[h] = '{'
            msg += '{'
        elif i == 339:
            others[h] = '_'
            msg += '_'
        elif i == 367:
            others[h] = '}'
            msg += '}'

print(msg)

文字に対応付けした結果は以下の通り。

GUR PNG VF N QBZRFGVP FCRPVRF BS FZNYY PNEAVIBEBHF ZNZZNY. VG VF GUR BAYL QBZRFGVPNGRQ FCRPVRF VA GUR SNZVYL SRYVQNR NAQ VF BSGRA ERSREERQ GB NF GUR QBZRFGVP PNG GB QVFGVATHVFU VG SEBZ GUR JVYQ ZRZOREF BS GUR SNZVYL. N PNG PNA RVGURE OR N UBHFR PNG, N SNEZ PNG BE N SRENY PNG. GUR YNGGRE ENATRF SERRYL NAQ NIBVQF UHZNA PBAGNPG. OGFPGS{EBG_VF_SHAAVRE_JVGU_N_PNG_GJVFG}QBZRFGVP PNGF NER INYHRQ OL UHZNAF SBE PBZCNAVBAFUVC NAQ GURVE NOVYVGL GB XVYY EBQRAGF. GUR PNG VF FVZVYNE VA NANGBZL GB GUR BGURE SRYVQ FCRPVRF. VG UNF N FGEBAT SYRKVOYR OBQL, DHVPX ERSYRKRF, FUNEC GRRGU NAQ ERGENPGNOYR PYNJF NQNCGRQ GB XVYYVAT FZNYY CERL. VGF AVTUG IVFVBA NAQ FRAFR BS FZRYY NER JRYY QRIRYBCRQ.

quipqiupで復号する。

THE CAT IS A DOMESTIC SPECIES OF SMALL CARNIVOROUS MAMMAL. IT IS THE ONLY DOMESTICATED SPECIES IN THE FAMILY FELIDAE AND IS OFTEN REFERRED TO AS THE DOMESTIC CAT TO DISTINGUISH IT FROM THE WILD MEMBERS OF THE FAMILY. A CAT CAN EITHER BE A HOUSE CAT, A FARM CAT OR A FERAL CAT. THE LATTER RANGES FREELY AND AVOIDS HUMAN CONTACT. BTSCTF{ROT_IS_FUNNIER_WITH_A_CAT_TWIST}DOMESTIC CATS ARE VALUED BY HUMANS FOR COMPANIONSHIP AND THEIR ABILITY TO KILL RODENTS. THE CAT IS SIMILAR IN ANATOMY TO THE OTHER FELID SPECIES. IT HAS A STRONG FLEXIBLE BODY, QUICK REFLEXES, SHARP TEETH AND RETRACTABLE CLAWS ADAPTED TO KILLING SMALL PREY. ITS NIGHT VISION AND SENSE OF SMELL ARE WELL DEVELOPED.
BtSCTF{rot_is_funnier_with_a_cat_twist}