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

この大会は2022/7/15 23:00(JST)～2022/7/16 23:00(JST)に開催されました。
今回もチームで参戦。結果は246点で421チーム中96位でした。
自分で解けた問題をWriteupとして書いておきます。

Mic Check

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

CCTF{Th3_B3sT_1S_Yet_t0_C0m3!!}

polyRSA

RSA暗号。スクリプトを見ると、以下の式で表せるので、n = p * qからkの方程式となる。

p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011

kを求めることができたら、p, qが割り出せ、フラグを求めることができる。

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

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

n = int(params[0].split(' = ')[1])
c = int(params[1].split(' = ')[1])
e = 31337

k = symbols('k')
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
ans = solve(p * q - n, k)
k = int(ans[0])
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
assert p * q == n

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag)

CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}

Klamkin

$ nc 04.cr.yp.toc.tf 13777
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hello, now we are finding the integer solution of two divisibility  |
|  relation. In each stage send the requested solution. Have fun :)    |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| We know (ax + by) % q = 0 for any (a, b) such that (ar + bs) % q = 0
| and (q, r, s) are given!
| Options: 
|	[G]et the parameters 
|	[S]end solution 
|	[Q]uit
G
| q = 215878944134145492027429935034914189893
| r = 189988045489632921439900375442954959636
| s = 50693894044872920716130473461170925311
| Options: 
|	[G]et the parameters 
|	[S]end solution 
|	[Q]uit
S
| please send requested solution like x, y such that x is 12-bit:

この条件を満たすようできるだけチェックして、x, yを送信する。

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

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

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('04.cr.yp.toc.tf', 13777))

data = recvuntil(sock, b'[Q]uit\n').rstrip()
print(data)
print('G')
sock.sendall(b'G\n')

data = recvuntil(sock, b'\n').rstrip()
print(data)
q = int(data.split(' = ')[1])
data = recvuntil(sock, b'\n').rstrip()
print(data)
r = int(data.split(' = ')[1])
data = recvuntil(sock, b'\n').rstrip()
print(data)
s = int(data.split(' = ')[1])

nums = 8192
_as = []
_bs = []
for i in range(nums):
    a = random.randint(0, q - 1)
    b = (- a * r) * inverse(s, q) % q
    _as.append(a)
    _bs.append(b)

data = recvuntil(sock, b'[Q]uit\n').rstrip()
print(data)
print('S')
sock.sendall(b'S\n')

for _ in range(5):
    data = recvuntil(sock, b'\n').rstrip()
    print(data)
    bits = int(data.split(' ')[-1].split('-')[0])

    while True:
        x = getPrime(bits)
        y = (- _as[0] * x) * inverse(_bs[0], q) % q
        success = True
        for i in range(1, nums):
            if (_as[i] * x + _bs[i] * y) % q != 0:
                success = False
                break
        if success:
            break

    payload = '%d, %d' % (x, y)
    print(payload)
    sock.sendall(payload.encode() + b'\n')
    data = recvuntil(sock, b'\n').rstrip()
    print(data)

100%ではないが、何回かスクリプトを実行したら、フラグが表示された。

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hello, now we are finding the integer solution of two divisibility  |
|  relation. In each stage send the requested solution. Have fun :)    |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| We know (ax + by) % q = 0 for any (a, b) such that (ar + bs) % q = 0
| and (q, r, s) are given!
| Options:
|       [G]et the parameters
|       [S]end solution
|       [Q]uit
G
| q = 194048517521350378413240926000241468131
| r = 124091173172322909192577830065380311502
| s = 125784318141643034410048832868626560137
| Options:
|       [G]et the parameters
|       [S]end solution
|       [Q]uit
S
| please send requested solution like x, y such that x is 12-bit:
4003, 56315245500619432502650438678207650543
| good job, try to solve the next challenge :P
| please send requested solution like x, y such that x is 13-bit:
4969, 67239017344217759003982457872096061654
| good job, try to solve the next challenge :P
| please send requested solution like x, y such that x is 16-bit:
35591, 9353017490916509269353419200010234699
| good job, try to solve the next challenge :P
| please send requested solution like x, y such that x is 19-bit:
423697, 16192597119110039724350397972254848401
| good job, try to solve the next challenge :P
| please send requested solution like x, y such that x is 25-bit:
29193553, 98744654374489514592696831569244696517
| Congrats, you got the flag: CCTF{f1nDin9_In7Eg3R_50Lut1Ons_iZ_in73rEStIn9!}

CCTF{f1nDin9_In7Eg3R_50Lut1Ons_iZ_in73rEStIn9!}

Baphomet

暗号処理は以下の通り。

・ba: flagをbase64エンコード
・baph, key = '', ''
・baの各文字について、以下の処理を実行
　・英小文字の場合、baphに大文字にして結合、keyに'0'を結合
　・英小文字以外の場合、baphに小文字にして結合、keyに'1'を結合
・key: keyをバイト文字列に変換
・enc = b''
・baphの長さだけ以下の処理を実行
　・baph[i] ^ key[i % len(key)]のバイト文字をencに結合
・encをファイル出力

フラグがCCTF{から始まることを前提にkeyを求める。

#!/usr/bin/env python3
from base64 import b64encode, b64decode

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

assert len(enc) == 48

flag_head = b'CCTF{'
b64_flag_head = b64encode(flag_head)[:-2]
baph = ''
for b in b64_flag_head.decode():
    if b.islower():
        baph += b.upper()
    else:
        baph += b.lower()

key = b''
for i in range(len(baph)):
    key += bytes([ord(baph[i]) ^ enc[i]])

assert len(key) == 48 // 8

rev_b64_flag = b''
for i in range(len(enc)):
    rev_b64_flag += bytes([enc[i] ^ key[i % len(key)]])
rev_b64_flag = rev_b64_flag.decode()

b64_flag = b''
for b in rev_b64_flag:
    if b.isupper():
        b64_flag += b.lower().encode()
    else:
        b64_flag += b.upper().encode()

flag = b64decode(b64_flag).decode()
print(flag)

CCTF{UpP3r_0R_lOwER_17Z_tH3_Pr0bL3M}

Volgo

「GET ENCRYPTED FLAG :)」をクリックすると、以下の情報が得られる。

{"flag": "BBHAC QDFAA KGBMH RVZSK RNVZH NGRAM WYHHE HKHJU UCQBL HPVAP TXDCZ ZMKWX ETCKC CMBSC VKUUF BMAIV RTAJE EWOUS SMOTQ KNQBF IRDVZ YJWQK WEAIA TONBI MMBUI RCULP BKEIO LNOAM XLUDR XJYAM DMWJN DUXXV FDVOC BBHAC QDFAA"}

「ENCIPHER ABOVE TEXT」でいくつか平文を入力し、暗号を試してみる。

A
{"cipher": "BBHAC QDFAA IXXXX BBHAC QDFAA"}

AA
{"cipher": "BBHAC QDFAA IUXXX BBHAC QDFAA"}

AAA
{"cipher": "BBHAC QDFAA IUVXX BBHAC QDFAA"}

AAAA
{"cipher": "BBHAC QDFAA IUVLX BBHAC QDFAA"}

AAAAA
{"cipher": "BBHAC QDFAA IUVLR BBHAC QDFAA"}

BBBBB
{"cipher": "BBHAC QDFAA HTUKQ BBHAC QDFAA"}

AAAAAAAAAAAAAAAAAAAA
{"cipher": "BBHAC QDFAA IUVLR EJVRR FJUSV MLFRY BBHAC QDFAA"}

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
{"cipher": "BBHAC QDFAA IUVLR EJVRR FJUSV MLFRY WRGMP HQGSO MVPQF AOPPR BBHAC QDFAA"}

BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
{"cipher": "BBHAC QDFAA HTUKQ DIUQQ EITRU LKEQX VQFLO GPFRN LUOPE ZNOOQ BBHAC QDFAA"}

どうやら先頭と末尾の"BBHAC QDFAA"を除いて、Vigenere暗号になっているようだ。"flag"の暗号と同じ長さ(5*31)になるよう"A"の文字列を指定し、暗号を求める。この場合の暗号は鍵になるので、その鍵から"flag"の暗号を復号する。

"A" * 155
{"cipher": "BBHAC QDFAA IUVLR EJVRR FJUSV MLFRY WRGMP HQGSO MVPQF AOPPR HJLPF YXOPQ IKUJY KFIAP UMOLQ ZLBZV TXSIJ SHZIO WPNUO JPSUK HFREL NVZTS TGLVN PTGFR GYGRS STPGB PZWTG DYITJ SOPQU JHWPT SIBSE QDYSW TPPMT BBHAC QDFAA"}

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

def decrypt(key, ct):
    pt = ''
    for i in range(len(ct)):
        index_c = ascii_uppercase.index(ct[i])
        index_k = ascii_uppercase.index(key[i])
        index = (index_k - index_c) % len(ascii_uppercase)
        pt += ascii_uppercase[index]
    return pt

msg_enc = 'BBHAC QDFAA KGBMH RVZSK RNVZH NGRAM WYHHE HKHJU UCQBL HPVAP ' \
    + 'TXDCZ ZMKWX ETCKC CMBSC VKUUF BMAIV RTAJE EWOUS SMOTQ KNQBF IRDVZ ' \
    + 'YJWQK WEAIA TONBI MMBUI RCULP BKEIO LNOAM XLUDR XJYAM DMWJN DUXXV ' \
    + 'FDVOC BBHAC QDFAA'
msg_enc = msg_enc.replace('BBHAC QDFAA', '')
msg_enc = msg_enc.replace(' ', '')

key = 'BBHAC QDFAA IUVLR EJVRR FJUSV MLFRY WRGMP HQGSO MVPQF AOPPR HJLPF ' \
    + 'YXOPQ IKUJY KFIAP UMOLQ ZLBZV TXSIJ SHZIO WPNUO JPSUK HFREL NVZTS ' \
    + 'TGLVN PTGFR GYGRS STPGB PZWTG DYITJ SOPQU JHWPT SIBSE QDYSW TPPMT ' \
    + 'BBHAC QDFAA'
key = key.replace('BBHAC QDFAA', '')
key = key.replace(' ', '')

msg = decrypt(key, msg_enc)
print(msg)

復号した結果は以下の通り。

YOUZKNOWZHOWZTOZFORMATZFLAGZJUSTZPUTZUPCOMINGZLETTERSZWITHINZCURLYZBRACESZFOLLOWEDZBYZCCTFZOOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR

"Z"をスペースに置き換える。

YOU KNOW HOW TO FORMAT FLAG JUST PUT UPCOMING LETTERS WITHIN CURLY BRACES FOLLOWED BY CCTF OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR

CCTF{OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR}