CakeCTF 2021 Writeup

この大会は2021/8/28 8:00(JST)～2021/8/29 20:00(JST)に開催されました。
今回もチームで参戦。結果は1890点で157チーム中22位でした。
自分で解けた問題をWriteupとして書いておきます。

discrete log (warmup, crypto)

フラグの各文字について、以下のように暗号化している。

pow(g, r*m, p)

rは未知だが、以下の式が成り立つので、pow(g, r, p)が算出できる。

pow(g, r*m, p) = pow(pow(g, r, p), m, p)

あとはmをブルートフォースで割り出せばフラグが求められる。

from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    p = int(f.readline().rstrip())
    g = int(f.readline().rstrip())
    cs = eval(f.readline().rstrip())

d = inverse(ord('C'), p - 1)
g_r0 = pow(cs[0], d, p)
d = inverse(ord('a'), p - 1)
g_r1 = pow(cs[1], d, p)
assert g_r0 == g_r1
g_r = g_r0

flag = ''
for c in cs:
    for code in range(32, 127):
        if pow(g_r, code, p) == c:
            flag += chr(code)
            break
print flag

CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}

improvisation (crypto)

LFSRの問題。rをz3で求め、復号する。

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

def LFSR(r):
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

r = BitVec('r', 64)
lfsr = LFSR(r)
flag_head = 'CakeCTF{'
m = bytes_to_long(flag_head[::-1])

## add '0' to arrange
b_ct = '0' + bin(0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053)[2:]

s = Solver()
for i in range(len(flag_head) * 8):
    s.add(((m & 1) ^ next(lfsr)) == int(b_ct[i]))
    m >>= 1

res = s.check()
if res == sat:
    m = s.model()
    r = m[r].as_long()
else:
    exit(1)

lfsr = LFSR(r)
bin_flag = ''
for i in range(len(b_ct)):
    b = int(b_ct[i]) ^ next(lfsr)
    bin_flag = str(b) + bin_flag

flag = long_to_bytes(int(bin_flag, 2))[::-1]
print flag

CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}

Survey (survey)

アンケートに答えたら、フラグが表示された。

CakeCTF{w4s_th1s_CTF_p13c3_0f_c4k3_4U?}