ASIS CTF Quals 2021 Writeup - よっちんのブログ

この大会は2021/10/23 0:00(JST)～2021/10/25 0:00(JST)に開催されました。
今回もチームで参戦。結果は275点で741チーム中77位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome (Warmup)

ルールのページにフラグが書いてあった。

ASIS{W3lc0me_t0_The_ASIS_CTF_Mad3_w1th_L0ve}

Crypto Warm up (Crypto, Warmup)

暗号化の処理概要は以下の通り。

・l: flagの長さ
・p: 15bit素数
・rstr: p - l の長さのランダムprintable文字列
・msg = flag + rstr
・s: ランダム1024bit整数(is_valid(s, p)(処理は不明)がTrue)
・enc = msg[0]
・i=0～p-2に対して以下を実行
　・enc += msg[pow(s, i, p)]

暗号化文字列の長さがp。あとはフラグが"ASIS{"から始まることを前提に条件を満たすsを探す。
結果2パターンがあるので、両方についてフラグを求める。

#!/usr/bin/env python3
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    enc = f.read().rstrip().split(' = ')[1]

p = len(enc)

flag_head = 'ASIS{'

indexes = []
for i in range(2, 5):
    index = []
    j = 0
    while True:
        try:
            j = enc.index(flag_head[i], j)
            index.append(j)
            j += 1
        except:
            break
    indexes.append(index)

ss = []
for s in range(p):
    for i in indexes[0]:
        if pow(s, i - 1, p) == 2:
            for j in indexes[1]:
                if pow(s, j - 1, p) == 3:
                    for k in indexes[2]:
                        if pow(s, k - 1, p) == 4:
                            ss.append(s)

print('[+] s:', ss)

for s in ss:
    flag = 'A'
    i = 1
    while True:
        for j in range(p - 1):
            if pow(s, j, p) == i:
                flag += enc[j + 1]
                break
        if flag[-1] == '}':
            break
        i += 1

    print('[*] flag:', flag)

実行結果は以下の通り。leat文字で意味が通る方がフラグだった。

[+] s: [8562, 10927]
[*] flag: ASIS{_how_dFC.YptZTh1S?h0mx_m4d;_lGD_w;dr\_CUYpI0_5J2T3+?k!!!*Z}
[*] flag: ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}

ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}

Madras (Crypto)

RSA暗号で、nはa, b, cの素因数を持つ。a, b, cに対するいろんな計算結果が出力されているので、それを条件にz3でa, b, cを割り出す。割り出した後は、通常のRSA暗号の復号方法で復号する。

from z3 import *
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    param1 = int(f.readline().rstrip().split(' ')[-1])
    param2 = int(f.readline().rstrip().split(' ')[-1])
    param3 = int(f.readline().rstrip().split(' ')[-1])
    enc_a = int(f.readline().rstrip().split(' ')[-1])
    enc_b = int(f.readline().rstrip().split(' ')[-1])
    enc_c = int(f.readline().rstrip().split(' ')[-1])
    enc = int(f.readline().rstrip().split(' ')[-1])

a = Int('a')
b = Int('b')
c = Int('c')

s = Solver()

s.add(a * b + c == param1)
s.add(b * c + a == param2)
s.add(c * a + b == param3)
s.add(enc % a == enc_a)
s.add(enc % b == enc_b)
s.add(enc % c == enc_c)

assert s.check() == sat

m = s.model()
a = m[a].as_long()
b = m[b].as_long()
c = m[c].as_long()

print '[+] a =', a
print '[+] b =', b
print '[+] c =', c

assert a.bit_length() == 513 // 3
assert b.bit_length() == 513 // 3
assert c.bit_length() == 513 // 3

e = 65537
n = a * b * c
phi = (a - 1) * (b - 1) * (c - 1)
d = inverse(e, phi)
m = pow(enc, d, n)
FLAG = long_to_bytes(m)
print '[*] FLAG:', FLAG

実行結果は以下の通り。

[+] a = 1644376501336761869533914527999140316946467005479211
[+] b = 2769045283056871559108237639832652911114008081576651
[+] c = 1594118801665580510615541222527591707834932058213541
[*] FLAG: ASIS{m4dRa5_iZ_RSA_l1k3_cH41L3n9E?!!}

ASIS{m4dRa5_iZ_RSA_l1k3_cH41L3n9E?!!}