BSides Mumbai CTF 2022 Writeup - よっちんのブログ

この大会は2022/12/10 20:00(JST)～2022/12/11 20:00(JST)に開催されました。
今回もチームで参戦。結果は1905点で251チーム中14位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome To BSides Mumbai CTF (Welcome)

問題にフラグが書いてあった。

BSMumbai{W3lcome_T0_BSides_Mumbai_CTF_2022}

Warmup (Reverse)

各インデックスでASCIIコードを比較している。
例えば、以下の場合、インデックス28で、55と比較している。

10:                                               ; preds = %0
  %11 = getelementptr inbounds [100 x i8], [100 x i8]* %2, i64 0, i64 28
  %12 = load i8, i8* %11, align 4
  %13 = sext i8 %12 to i32
  %14 = icmp eq i32 %13, 55
  br i1 %14, label %15, label %207

インデックスの位置に文字をセットして、順に並べればフラグになる。

>>> flag = [''] * 39
>>> flag[28] = chr(55)
>>> flag[30] = chr(110)
>>> flag[29] = chr(49)
>>> flag[36] = chr(53)
>>> flag[13] = chr(121)
>>> flag[18] = chr(95)
>>> flag[2] = chr(77)
>>> flag[15] = chr(51)
>>> flag[34] = chr(48)
>>> flag[7] = chr(48)
>>> flag[24] = chr(102)
>>> flag[17] = chr(102)
>>> flag[26] = chr(48)
>>> flag[25] = chr(49)
>>> flag[10] = chr(100)
>>> flag[27] = chr(52)
>>> flag[3] = chr(123)
>>> flag[23] = chr(95)
>>> flag[19] = chr(49)
>>> flag[21] = chr(95)
>>> flag[31] = chr(57)
>>> flag[8] = chr(117)
>>> flag[37] = chr(51)
>>> flag[11] = chr(95)
>>> flag[33] = chr(104)
>>> flag[1] = chr(83)
>>> flag[0] = chr(66)
>>> flag[22] = chr(52)
>>> flag[32] = chr(95)
>>> flag[16] = chr(49)
>>> flag[12] = chr(109)
>>> flag[38] = chr(125)
>>> flag[35] = chr(117)
>>> flag[6] = chr(102)
>>> flag[9] = chr(110)
>>> flag[14] = chr(53)
>>> flag[4] = chr(49)
>>> flag[5] = chr(95)
>>> flag[20] = chr(110)
>>> ''.join(flag)
'BSM{1_f0und_my531f_1n_4_f10471n9_h0u53}'

BSM{1_f0und_my531f_1n_4_f10471n9_h0u53}

Poet Xor (Crypto)

8バイトXOR鍵の暗号。フラグが"BSMumbai"で始まり、最終行に記載されていると推測できることから鍵を求め、復号する。

#!/usr/bin/env python3
from itertools import cycle

with open('flag.enc', 'rb') as f:
    cipher = f.read().splitlines()

flag_head = b'BSMumbai'

key = b''
last_line = bytes.fromhex(cipher[-1].decode())
for i in range(len(flag_head)):
    key += bytes([flag_head[i] ^ last_line[i]])

for h_ct in cipher:
    ct = bytes.fromhex(h_ct.decode())
    msg = bytes([a ^ b for a, b in zip(ct, cycle(key))]).decode()
    print(msg)

メッセージの復号結果は以下の通り。

Two bits meet, each with its own
One zero, one one, they are shown
Together they combine, with a XOR
A new value is formed, never a bore.
BSMumbai{w0w_1t_1s_4_fl4g_1n_th3_3nd}

BSMumbai{w0w_1t_1s_4_fl4g_1n_th3_3nd}

Big RSA (Crypto)

eが大きいので、Wiener's Attackで復号する。

#!/usr/bin/env sage
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

def wiener(e, n):
    m = 12345
    c = pow(m, e, n)
    q0 = 1

    list1 = continued_fraction(Integer(e)/Integer(n))
    conv = list1.convergents()
    for i in conv:
        k = i.numerator()
        q1 = i.denominator()

        for r in range(30):
            for s in range(30):
                d = r*q1 + s*q0
                m1 = pow(c, d, n)
                if m1 == m:
                    return d
        q0 = q1
    return None

with open('pubkey.pem', 'r') as f:
    pub_data = f.read()

with open('flag.enc', 'r') as f:
    enc = bytes.fromhex(f.read())

pubkey = RSA.importKey(pub_data)
n = pubkey.n
e = pubkey.e

d = int(wiener(e, n))
key = RSA.construct((n, e, d))
cipher_rsa = PKCS1_v1_5.new(key)

from Crypto.Random import get_random_bytes
sentinel = get_random_bytes(16)
FLAG = cipher_rsa.decrypt(enc, sentinel).rstrip().decode()
print(FLAG)

BSMumbai{RSA_with_bigE}

EggLamal (Crypto)

以下の式が与えられている。

g = 2
m = FLAG % p
A = pow(g, a, p)
B = pow(g, b, p)
s = pow(A, b, p)
c = s * m % p

ただし、p, A, B, c は既知、a, b は未知。B が p - 1 と同じ値になっているので、以下の式が成り立つ。

b = (p - 1) // 2

これでsの値が計算でき、それとcの値からmを計算し、フラグを求める。

#!/usr/bin/env python3
from Crypto.Util.number import *
with open('params.txt', 'r') as f:
    params = f.read().splitlines()

p = int(params[0].split(' ')[-1])
A = int(params[1].split(' ')[-1])
B = int(params[2].split(' ')[-1])
c = int(params[3].split(' ')[-1])
assert B == p - 1

g = 2
b = (p - 1) // 2
s = pow(A, b, p)
m = (c * inverse(s, p)) % p
FLAG = long_to_bytes(m).decode()
print(FLAG)

BSMumbai{ElGamal_Publickey_Cryptography}