Securinets CTF Quals 2022 Writeup

CTF writeup

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

Welcome Quals 2K22 (Welcome)

Discordに入り、#announcementチャネルのメッセージを見ると、フラグが書いてあった。

Securinets{WelCome_T0_QuAls_2k22}

Escrime (Cryptography)

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

・prime: 512bit素数
・p1, q1: genPrime(prime)
・p2, q2: genPrime(prime)
・n1 = p1*q1
・n2 = p2*q2
・e = 65537
・m1: FLAGの前半の文字列の数値化
・m2: FLAGの後半の文字列の数値化
・c1 = pow(m1, e, n1)
・c2 = pow(m2, e, n2)
・n1, n2, e, c1, c2出力

※genPrime(prime)：2*prime*[256bit素数] + 1の素数のペア生成

式を変形してみる。

n1 = p1 * q1 = (2 * prime * a1 + 1) * (2 * prime * b1 + 1)
             = 2 * prime * (2 * prime * a1 * b1 + a1 + b1) + 1
n2 = p2 * q2 = (2 * prime * a2 + 1) * (2 * prime * b2 + 1)
             = 2 * prime * (2 * prime * a2 * b2 + a2 + b2) + 1

n1 - 1, n2 - 1のGCDはprimeの倍数。このことからprimeを算出することができる。さらに以下のことが言える。

((n1 - 1) // (2 * prime)) % (2 * prime) = a1 + b1
((n2 - 1) // (2 * prime)) % (2 * prime) = a2 + b2

phi1 = (p1 - 1) * (q1 - 1)
     = n1 - (p1 + q1) + 1 = n1 - (2 * prime * (a1 + b1) + 2) + 1
phi2 = (p2 - 1) * (q2 - 1)
     = n2 - (p2 + q2) + 1 = n2 - (2 * prime * (a2 + b2) + 2) + 1

あとはこのまま復号すればよい。

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

n1 = 5285941989924581490741575774796326221790301948671605967204654261159288826022690654909746856601734294076351436205238123432817696904524845143908229601315593896823359605609172777227518764838488130850768836467030938547486936412484230693105639039311878853055295612388722273133638524917106191321503530749409311343663516633298043891444321772817485480644504762143353706512690041092791539952154332856635651319630479019844011333570438615137628705917690349203588170944935681
n2 = 5512656145670579765357132887430527554149315293720001536465226567777071834432904027590899542293511871806792894769506962601330354553170015126601443256295513753986998761021594415121386822360537570074896704547101502955980189351257681515387379761554807684880212096397524725819607628411147885452294832392886405475830663300445429053365129797792206619514994944481130684176571005780217091773969415001961227566026934419626425934895777818074251010427154279687683891897394401
e = 65537
c1 = 3792561290017712418676552700903779226679678307521013229152018077539055935181708693237786486418411190513573593312739874489485768872374239333562352570689090751306553033406629945001093355613620844532659507519582518955178617942044813600181673015763469247380587771641089223066734168709065596269187564842646397647564064090886856491267151338586218098150720579275673440512159074650632829004798635425409766385176472514086448897744502264325566940224093583630788193949908215
c2 = 3222093169881176821995152873609430742364413196826316856495679228145853706169389758246323802005549827444022148276365869623395771621464376723299960525487777645386674088866891887984766934440527885549168365996216682223515034398685244541695223412679979637178695229351272286453267599205874775267533781360269542834699741976380260822746797186755978820611721151719635986648586937891954519919600047846994285652165076540057377973800029963140392459328016771048953153246246886

prime = GCD(n1 - 1, n2 - 1)
for i in range(256, 1, -1):
    if prime % i == 0:
        prime //= i

assert isPrime(prime)

a1_plus_b1 = ((n1 - 1) // (2 * prime)) % (2 * prime)
a2_plus_b2 = ((n2 - 1) // (2 * prime)) % (2 * prime)

phi1 = n1 - (2 * prime * (a1_plus_b1) + 2) + 1
phi2 = n2 - (2 * prime * (a2_plus_b2) + 2) + 1
d1 = inverse(e, phi1)
d2 = inverse(e, phi2)
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
FLAG = (long_to_bytes(m1) + long_to_bytes(m2)).decode()
print(FLAG)

Securinets{G3n3r4t1ng_pr1m3s_1n_4_sp3c1f1c_f0rm_4lm0st_4lw4ys_3nds_b4dly}

AES² (Cryptography)

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

・key, iv1, iv2: ランダム16バイト
・alice_username: ランダム32バイト
・alice_token = get_token(alice_username, iv1, iv2)
　・blocks: alice_username16バイトごとのブロック配列
　・enc = ''
　・tmp1 = iv1
　・tmp2 = iv2
　・blocksの各ブロックについて以下の処理を実行
　　・tmp: blockとtmp1のXORのAES-ECB暗号化
　　・_tmp: tmpとtmp2のXORのAES-ECB暗号化
　　・enc += _tmp
　　・tmp1 = _tmp
　　・tmp2 = tmp
　・encを返す。
・alice_usernameとalice_tokenを16進数表記で出力
・以下繰り返し
　・username: 16進数表記で入力→hexデコード
　・token = get_token(username, iv1, iv2)
　・usernameとtokenを16進数表記で出力
　・proof(token) == proof(alice_token)の場合、
　　tokenとalice_tokenが異なれば、フラグが表示される。

Aliceの暗号は以下のようなイメージとなる。

平文1ブロック目 ^ iv1             --(AES暗号)--> M1 ^ iv2 --(AES暗号)--> 暗号1ブロック目
平文2ブロック目 ^ 暗号1ブロック目 --(AES暗号)--> M2 ^ M1  --(AES暗号)--> 暗号2ブロック目

暗号の各ブロックのXORがAliceの暗号の各ブロックのXORと同じになればよい。
平文3ブロック目 ^ 暗号2ブロック目 == 平文2ブロック目 ^ 暗号1ブロック目になる平文3ブロック目を指定する。
さらに平文4ブロック目 ^ 暗号3ブロック目 == 平文2ブロック目 ^ 暗号1ブロック目になる平文4ブロック目を指定する。
こうすれば、以下のようなイメージで、tokenは同じになるはず。

平文1ブロック目 ^ iv1             --(AES暗号)--> M1 ^ iv2 --(AES暗号)--> 暗号1ブロック目
平文2ブロック目 ^ 暗号1ブロック目 --(AES暗号)--> M2 ^ M1  --(AES暗号)--> 暗号2ブロック目
平文3ブロック目 ^ 暗号2ブロック目 --(AES暗号)--> M2 ^ M2  --(AES暗号)--> 暗号3ブロック目
平文4ブロック目 ^ 暗号3ブロック目 --(AES暗号)--> M2 ^ M2  --(AES暗号)--> 暗号4ブロック目(暗号3ブロック目と同じ)

以上を元にスクリプトにする。

#!/usr/bin/env python3
import socket

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

def xor(a, b):
    return bytes(i ^ j for i, j in zip(a, b))

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('20.233.7.174', 4870))

for _ in range(8):
    data = recvuntil(s, b'\n').rstrip()
    print(data)

data = recvuntil(s, b'\n').rstrip()
print(data)
alice_pt = bytes.fromhex(data.split(' : ')[1].split(' -> ')[0])
alice_ct = bytes.fromhex(data.split(' : ')[1].split(' -> ')[1])

#### 1st try ####
pt3 = xor(xor(alice_pt[16:], alice_ct[:16]), alice_ct[16:])
username1 = (alice_pt + pt3).hex()

data = recvuntil(s, b': ')
print(data + username1)
s.sendall(username1.encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
token1 = bytes.fromhex(data.split(' : ')[1].split(' -> ')[1])
data = recvuntil(s, b'\n').rstrip()
print(data)

#### 2nd try ####
pt4 = xor(xor(alice_pt[16:], alice_ct[:16]), token1[32:])
username2 = (alice_pt + pt3 + pt4).hex()

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

実行結果は以下の通り。

  ┌─────────────────────┐
  | ┌──(quals@ctf)-[~]  |
  | └─$ ./AES²          |
  |                     |
  |       By Aptx       |
  └─────────────────────┘

Alice's creds : c2d4719d0fe7716ea48624ca88ba1ff703e3fe408b0d9e0345f474df1d894f66 -> 192a45970801d87e7acd12034994d2367801ce8b3319918db5f93603021fc8b0

Username : c2d4719d0fe7716ea48624ca88ba1ff703e3fe408b0d9e0345f474df1d894f6662c8755cb015d7f08ac050df560255e0
Your creds : c2d4719d0fe7716ea48624ca88ba1ff703e3fe408b0d9e0345f474df1d894f6662c8755cb015d7f08ac050df560255e0 -> 192a45970801d87e7acd12034994d2367801ce8b3319918db5f93603021fc8b02fe3b9d8f9d4abb7de9f6083a0245aaa
Try again!

Username : c2d4719d0fe7716ea48624ca88ba1ff703e3fe408b0d9e0345f474df1d894f6662c8755cb015d7f08ac050df560255e0352a020f7ad8edcae1a6065ff439c7fa
Your creds : c2d4719d0fe7716ea48624ca88ba1ff703e3fe408b0d9e0345f474df1d894f6662c8755cb015d7f08ac050df560255e0352a020f7ad8edcae1a6065ff439c7fa -> 192a45970801d87e7acd12034994d2367801ce8b3319918db5f93603021fc8b02fe3b9d8f9d4abb7de9f6083a0245aaa2fe3b9d8f9d4abb7de9f6083a0245aaa
Hey Alice! Here is your flag b'Securinets{r0ll_y0ur_0wn_structur3_4nd_g3t_c0ll1d3d}'
Securinets{r0ll_y0ur_0wn_structur3_4nd_g3t_c0ll1d3d}