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

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

Welcome!

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

CCTF{Unleash_Your_Cipher_Skills!}

Did it!

サーバの処理概要は以下の通り。

・_flag = False
・n = 127
・l = 20
・N: 0以上n未満の集合
・K: 20個のランダム0以上n-1以下整数値の配列
・cnt = 0
・STEP = 2 * n // l - 1
・以下繰り返し
　・ans: 入力
　・_A: ansの","区切りの数値の配列
　・_Aの長さが20以下で、Nの部分集合の場合
　　・DID = did(n, l, K, _A)
　　　・A, K = set(A), set(K)
　　　・R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
　　　・Rを返却

Kを推測する問題。ランダム値を考慮しても衝突しない20個を指定して、該当する値があるかどうかをチェックする。該当する値がなければ、Kに含まれているので割り出すことができる。

#!/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)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('00.cr.yp.toc.tf', 11337))

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

n, l = 127, 20
N = list(range(0, n))
K = []
while True:
    answer = []
    rs = []
    dic = {}
    N2 = N
    for i in N2:
        r = pow(i, 2, n)
        if r not in rs and r + 1 not in rs:
            answer.append(str(i))
            rs.append(r)
            rs.append(r + 1)
            dic[r] = str(i)
            dic[r + 1] = str(i)
            N.remove(i)
        if len(answer) == 20:
            break

    ans = ','.join(answer)
    print(ans)
    s.sendall(ans.encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    DID = eval(data.split(' = ')[1])
    non_K = []
    for d in DID:
        non_K.append(dic[d])
    k = list(set(answer) - set(non_K))
    K += k

    if len(N) == 0:
        break

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

実行結果は以下の通り。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ .::   Hi all, she DID it, you should do it too! Are you ready? ::.   +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
0,2,4,6,8,10,13,15,18,20,22,24,27,29,31,34,36,38,40,42
+ DID = [1, 5, 17, 37, 64, 101, 43, 98, 71, 19, 104, 68, 94, 79, 73, 13, 26, 47, 76, 114]
1,5,9,12,17,21,25,28,32,37,41,45,47,49,52,54,56,58,60,63
+ DID = [9, 2, 26, 82, 30, 18, 120, 51, 35, 116, 38, 61, 123, 88, 117, 62, 44]
3,11,16,23,30,35,43,46,50,53,57,61,64,67,69,72,78,80,85,87
+ DID = [10, 83, 62, 105, 121, 71, 85, 2, 51, 87, 15, 113, 76, 75, 38, 11]
7,19,33,44,51,59,65,71,74,79,82,84,88,90,92,95,97,99,101,103
+ DID = [73, 11, 41, 50, 68, 16, 19, 121, 107, 62, 71, 125, 99, 53, 83]
14,39,55,66,70,76,81,86,91,96,100,104,107,110,112,114,116,118,120,123
+ DID = [73, 39, 94, 75, 124, 22, 69, 35, 98, 84, 43, 121, 30, 104, 81, 17]
26,62,73,77,89,94,102,106,109,115,119,122,125
+ DID = [117, 122, 60, 71, 87, 18, 65, 35, 47, 41, 73]
48,75,93,105,111,117,124
+ DID = [103, 37, 3, 18, 101, 9, 14]
68,98,113,126
+ DID = [70, 53, 1]
83,121
+ DID = [36, 32]
108
+ DID = [108]
37,63,28,23,78,67,64,44,99,95,71,65,91,76,120,107,122,125,98
+ DID = []
+ Congrats! the flag: CCTF{W4rM_Up_CrYpt0_Ch4Ll3n9e!!}

CCTF{W4rM_Up_CrYpt0_Ch4Ll3n9e!!}

Blue Office

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

・enc = encrypt(seed, flag)
　・seedは2**32以下の値であることをチェック
　・c, d = 0, seed
　・enc, l = b'', len(flag)
　・cがlより小さい間以下を実行
　　・d = d * 214013 + 2531011
　　・encにflag[c] ^ ((d >> 16) & 0xff)の文字を追加
　・encを返却
・encの16進数表記を出力

フラグは"CCTF{"で始まることを前提に、z3でseedを求める。あとはseedからXORの鍵を求め、復号する。

#!/usr/bin/env python3
from z3 import *
import binascii

def reseed(s):
    return s * 214013 + 2531011

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

enc = binascii.unhexlify(enc)

x = BitVec('x', 32)
s = Solver()

flag_head = b'CCTF{'
d = x
for i in range(len(flag_head)):
    d = reseed(d)
    s.add(flag_head[i] ^ ((d >> 16) & 0xff) == enc[i])

r = s.check()
assert r == sat
m = s.model()
seed = m[x].as_long()
print('[+] seed =', seed)

d = seed
flag = b''
for i in range(len(enc)):
    d = reseed(d)
    flag += (enc[i] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')

flag = flag.decode()
print('[*] flag =', flag)

実行結果は以下の通り。

[+] seed = 10364460
[*] flag = CCTF{__B4ck_0r!F1c3__C1pHeR_!!}

CCTF{__B4ck_0r!F1c3__C1pHeR_!!}

Suction

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

・r, nbit = 8, 128
・PKEY, pkey = keygen(nbit, r)
　・p, q: 128ビット素数
　・e: 16ビット素数
　・n = p * q
　・GCD(e, phi) == 1の場合
　　・N: nの2進数文字列で末尾8ビット切り落とし
　　・E: eの2進数文字列で末尾8ビット切り落とし
　　・PKEY = N + E
　　・pkey = (n, e)
　　・PKEY, pkeyを返却
・PKEYの10進数表記を出力
・FLAG: flagから'CCTF{'と'}'を削除した文字列
・enc = encrypt(FLAG, pkey, r)
　・m: FLAGの数値化したもの
　・n, e = pkey
　・c = pow(m, e, n)
　・C: cの2進数文字列で末尾8ビット切り落とし
　・Cを返却
・Cの10進数表記を出力

PKEYから2進数文字列で末尾8ビットがEそれより前がNとなる。まずはNからブルートフォースでnの候補を列挙する。

[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396571
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396577
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396583
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396589
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396603
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396613
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396633
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396643
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396667
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396723
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396751
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396783

それぞれfactordbで素因数分解した値のビット数を見て、128ビット2つに分解できるものを探す。以下の場合しかないことがわかる。

n = 55208723145458976481271800608918815438075571763947979755496510859604544396613

この場合、素因数分解したp, qは以下のようになる。

p = 188473222069998143349386719941755726311
q = 292926085409388790329114797826820624883

同様にEからブルートフォースでeの候補を出し、それぞれ復号し、printableなものになるものを探す。

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

def is_printable(s):
    for c in s:
        if c < 32 or c > 126:
            return False
    return True

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

PKEY = int(params[0].split(' ')[-1])
C = int(params[1].split(' ')[-1])

PKEY = bin(PKEY)[2:]
N = int(PKEY[:-8], 2)
E = int(PKEY[-8:], 2)

## enumeration of n candidates ##
for i in range(256):
    n = N * 256 + i
    error = False
    for j in range(2, 2**20):
        if n % j == 0:
            error = True
            break
    if not error:
        print('[+] n?:', n)

## analysis result of n ##
n = 55208723145458976481271800608918815438075571763947979755496510859604544396613
print('[+] ... n:', n)

p = 188473222069998143349386719941755726311
q = 292926085409388790329114797826820624883
phi = (p - 1) * (q - 1)

## enumeration of e candidates and get flag ##
found = False
for i in range(256):
    e = E * 256 + i
    if isPrime(e):
        d = inverse(e, phi)
        for j in range(256):
            c = C * 256 + j
            m = pow(c, d, n)
            flag = long_to_bytes(m)
            if is_printable(flag):
                #found = True
                print('[+] ... e:', e)
                print('[+] ... c:', c)
                flag = 'CCTF{%s}' % flag.decode()
                print('[*] flag:', flag)
                break
    if found:
        break

実行結果は以下の通り。

[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396571
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396577
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396583
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396589
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396603
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396613
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396633
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396643
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396667
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396723
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396751
[+] n?: 55208723145458976481271800608918815438075571763947979755496510859604544396783
[+] ... n: 55208723145458976481271800608918815438075571763947979755496510859604544396613
[+] ... e: 32983
[+] ... c: 32561828321881834735632894563707571322808353997859875093072961921724833474846
[*] flag: CCTF{6oRYGy&Dc$G2ZS}

CCTF{6oRYGy&Dc$G2ZS}