SECCON CTF 2021の参加記録

はじめに

VLANouroboros の HK-ilohas として，SECCON CTF 2021 に参加しました．

僕が解けたのは pppp と oOoOoO の 2 問だけですが，記念に参加記録でも書いておくことにしました．実力不足と未だに脱初心者できねー！って感じで非常に悔しいです．

pppp

問題ファイル

problem.sage

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))

考察 & 解法

$$\begin{align*} &p, q: 素数\\ &n = pq\\ &e = 65537\\ &m_1, m_2: フラグを分割したもの（256ビット） \end{align*}$$

$i$ 行 $j$ 列にかけられる 768 ビットのランダムな素数を $r_{i,j}$ とすると，$m$ は次のような行列になります．

$$m = \begin{bmatrix} pr_{0,0} & pr_{0,1} & pr_{0,2} & pr_{0,3} \\ 0 & m_1r_{1,1} & m_1r_{1,2}& m_1r_{1,3} \\ 0 & 0 & m_2r_{2,2} & m_2r_{2,3} \\ 0 & 0 & 0 & r_{3,3} \end{bmatrix}$$

これを $e$ 乗したものが暗号文 $c$ として渡されます（$\mathbb{Z}_n$ での演算です）．

$$c = m^e$$

とりあえず，手計算で色々と試してみると，対角成分がちょうど $e$ 乗になることに気が付きました（上三角行列なので当たり前ですが）．

$$c = \begin{bmatrix} (pr_{0,0})^e & \cdots & &\\ 0 & (m_1r_{1,1})^e & \cdots & &\\ 0 & 0 & (m_2 r_{2,2})^e & \cdots\\ 0 & 0 & 0 & r_{3,3}^e \end{bmatrix}$$

このことから，p = gcd(c[0][0], n) を計算することで $p$, $q$ を求められます．

本番中はここから先で詰まってしまいました．$p$, $q$ から $e^{-1}$ を計算し，$m_1 r_{1,1}$ と $m_2 r_{2,2}$ を求めても $r_{i,j}$ は未知だよな…っとなりました．

そこで，落ち着いて条件を見直してみると，$r_{i,j}$ は 768 ビットなのに対して $m_i$ は 256 ビットでした．なら，$m_i r_{i,j}$ って頑張れば素因数分解できるんじゃね？？？？という気になりました．ということで，YAFU に投げてみると体感 10 分程度で出てきました．このとき，多分作問者に申し訳ない解き方をしてる 😢😢 って感じでした．

solve.py

from math import gcd
from Crypto.Util.number import *


n = 139167515668183984855584233262421636549219808362436809125322963984953234794207403032462532211718407628015534917936237180092470832870352873174416729863982860547330562153111496168661222608038945799305565324740297535609102402946273092600303759078983973524662838350143815732516927299895302494977521033451618509313
e = 65537
c = [(92641859227150025014514674882433433169736939888930400782213731523244191029744271714915087397818608658221982921496921528927873080896272971564627162670330785041427348269531449548757383647994986600796703130771466176972483905051546758332111818555173685323233367295631863710855125823503925281765070200264928761744, 1077078501560459546238096407664459657660011596619515007448272718633593622581663318232822694070053575817000584000976732545349394411037957356817674297166036371321332907845398174111343765006738074197964396832305908342965034091516961317164203682771449331094865994143953470394418754170915147984703343671839620070, 19878161032897109459692857500488708331148676837923170075630073845924376353394086221031683671854185288619608305138965881628353471119235227157715699650190844508727073649527735233175347600167954253143204293274253676829607434380971492999430389536409563073620686264607716424139208756197843637115228155976163983619, 122958657434560838063916316490126514822437273152981380647634868499620566657448363565613345650206126542999322277498960954804580159527199119604554047697342524367459283765958189416627623253226055220105627822118413649499651442079969872322463271891353808314530249098525814619479135297014148780695960117897387220659), (0, 85635304452753185796593135650704585992713419302092444931829191186284566226617686976975731459756968679710078670232999566062343743901469759277582454092882685887985731708244015567469990157564460035983017331880588783841581502687752495254387549274422591338211161917565559735193456411356422539814020979699927207024,
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                26528377397409932803048052918715873209845190225305139460936852681030879561522825277119360099719008486268731610926098705442795761739644784858085976938906030639986454157616558457541083641717564142619063815917161350343604401278251069255966146207538326575595944701499010180658631016268689550402326369924649514049, 17173480018007185616783556851363148729840100207266610547324632027095687866456613104465211034834604995290825437734467654701021261504226847008483339028335703977866796341754911432666568936460974103742649586111260163432789617417125379644939110280618415377202845096157056174169392363954229816964869557167190373166), (0, 0, 81417110160690915414859599923077760437964436481940074249510026432592954854440295980578313776441414052192070135409849396229653279814546498083873720679422968334818254076803899882280264290639872486915551889441082468560654475422089052988909565455596584407805229280743723696618903551087160338683566908533474596220, 88524270641123978066493517684012199807956329430551155649688209766850898125045959831704501988313531767120589113923546449704920649814085765896894870692227804052901254644766662594723181025793077392532746071480212649880063471693730914835259139038459097504431147211622052068997412540488201406879310193174863792764), (0, 0, 0, 130146806238985078905344376697263038970354607413027156915068014483770022716717215156189413217688976902906182579031431264733207976605553885314360422441780388319618199732296392330859801016851191010568169307878720202422104375360360029207688301496478751250969744747470242179561459045172707909287093959859681318497)]

p = gcd(c[0][0], n)
q = n // p

d = pow(e, -1, (p-1)*(q-1))
m1r11 = pow(c[1][1], d, n)
m2r22 = pow(c[2][2], d, n)

r11 = 890941089701337639742923670629764992383197102649368033477055542426171609788212371754143394788213291456300216361551640449365841636339404366563906765128981689755176699342918904671528454362377482743831820969956624190146702130809843851
m1 = m1r11 // r11

r22 = 1001860113482890555017710485492420423876242421736095074738385131002929692458471110177277127310688011729127988908466398932019505500863392332136664225101034793814078136979376956873726395552928651794389376576934283525340824695529351511
m2 = m2r22 // r22

flag = long_to_bytes(m1) + long_to_bytes(m2)
print(flag.decode())

$ python3 solve.py
SECCON{C4n_y0u_prove_why_decryptable?}

oOoOoO

問題ファイル

problem.py

import signal
from typing import MutableSequence
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random
from flag import flag

message = b""
for _ in range(128):
    message += b"o" if random.getrandbits(1) == 1 else b"O"

M = getPrime(len(message) * 5)
S = bytes_to_long(message) % M

print("M =", M)
print('S =', S)
print('MESSAGE =', message.upper().decode("utf-8"))
print(f"{message=}")

signal.alarm(600)
ans = input('message =').strip().encode()

if ans == message:
    print(flag)
else:
    print("🧙")

考察 & 本番中の解法

$$\begin{align*} &\text{message}：元のメッセージで当てる対象\\ &\text{MESSAGE}：全部\, \text{O}\, の文字\\ &M：素数\\ &S \equiv \text{message} \pmod M \end{align*}$$

$M$, $S$ が与えられた状態で message を復元する問題です．message は o と O の 2 種類の文字から構成されます．しかし，魔女大先生のパワーで message は全てが O になります．

問題をぼんやりと眺めていると，これは o と O の差分 0x20 を各桁に足す足さないのナップザック暗号の類だと気が付きました．$k_i \in \{0, 1\}$ として，

$$\begin{align*} &S \equiv \text{message} \pmod{M}\\ &S \equiv \text{MESSAGE} + 32 \cdot 16^0 k_0 + 32 \cdot 16^2 k_1 + \cdots 32 \cdot 16^{254} k_{127} \pmod {M}\\ &\text{MESSAGE} - S + 32 \cdot 16^0 k_0 + 32 \cdot 16^2 k_1 + \cdots 32 \cdot 16^{254} k_{127} + M l = 0\\ \end{align*}$$

これを基に格子を作ってみました．

$$B = \begin{bmatrix} 32 \cdot 16^0 & 1 & 0 & 0 & \cdots & 0\\ 32 \cdot 16^2 & 0 & 1 & 0 & \cdots & 0\\ 32 \cdot 16^4 & 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 32 \cdot 16^{254} & 0 & 0 & 0 & \cdots & 1 \\ \text{MESSAGE} - S & 0 & 0 & 0 & \cdots & 0\\ M & 0 & 0 & 0 & \cdots & 0 \end{bmatrix}$$

$B$ に LLL を使うとたまにしか成功しませんでした．本番中は試行回数で乗り切りましたが，終了後に BKZ でいけるみたいな話を見かけて (・・?？❓ ってなってます（現在進行形）．

solve.sage

from Crypto.Util.number import long_to_bytes, bytes_to_long


MESSAGE = b"OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"
M = 4296072306836887687980673774381704166205403018972787671575165621123442878815781831549000956483723234218910010200125467663329060281140685621573979820006074362442678060712929561126912283226883523
S = 1965402809320098074246818343271877025564965958587689534033304168965677237622715285275273898016472591781012471103692096198637466125821215781239405507711963471167044804932449051695673349602793955

diff_char = 0x20

B = matrix.column(ZZ, vector([diff_char * 16 ^ (2*i) for i in range(128)]))
B = B.augment(matrix.identity(128))
B = B.stack(vector([S - bytes_to_long(MESSAGE)] + [0] * 128))
B = B.stack(vector([M] + [0] * 128))
B = B.LLL()

v = B[1][1:]
print(v)

message = b""

for k in v:
    if k != 0:
        message = b"o" + message
    else:
        message = b"O" + message

print(message)
# SECCON{Here_is_Huge-Huge_Island_yahhoOoOoOoOoOoO}

ちゃんと解き直したバージョン

上の方法ではたまにしか解けませんでした．それを修正したのが次のスクリプトです．

$$B = \begin{bmatrix} 32 \cdot 16^0 & 1 & 0 & 0 & \cdots & 0 & 0\\ 32 \cdot 16^2 & 0 & 1 & 0 & \cdots & 0 & 0\\ 32 \cdot 16^4 & 0 & 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 32 \cdot 16^{254} & 0 & 0 & 0 & \cdots & 1 & 0\\ \text{MESSAGE} - S & 0 & 0 & 0 & \cdots & 0 & 1\\ M & 0 & 0 & 0 & \cdots & 0 & 0 \end{bmatrix}$$

solve2.sage

from pwn import *
from Crypto.Util.number import bytes_to_long


MESSAGE = b"O" * 128
message = b""
diff_char = 0x20  # b"o" - b"O"

io = remote("oooooo.quals.seccon.jp", 8000)
io.recvuntil(b"M = ")
M = int(io.recvline())
io.recvuntil(b"S = ")
S = int(io.recvline())

# create lattice
B = matrix(ZZ, 130, 130)
for i in range(128):
    B[i, 0] = diff_char * 16 ^ (2*i)
for i in range(129):
    B[i, i+1] = 1
B[128, 0] = bytes_to_long(MESSAGE) - S
B[129, 0] = M
B = B.dense_matrix()
B = B.BKZ()

v = B[0]
for k in v[1:-1]:
    if abs(k) == 1:
        message = b"o" + message
    else:
        message = b"O" + message

print(message)

io.recvuntil(b"message =")
io.sendline(message)
print(io.recvline().decode())

解けなかった問題の反省

XXX は格子は組めたのですが，LLL 後の取り出し周りで失敗してました．卒論とかが落ち着いたら，格子をちゃんと勉強しなおそうと思いました（永遠にやらないパターン）．

cerberus は残り 1 時間で解法に気が付いたのですが，外でラーメン食べている最中だったのでコーディングが間に合わなかったです 😢 今度は早めに AES 問題に取り掛かります…

CCC は何にもわからなかったです．$p+q$ を何かそれっぽく書けないかなーっていじってましたが，全然ダメでした．

Sign_Wars は何かこれも格子っぽいなーって思いつつも，うまく作れませんでした．どのみち，後半の乱数パートもわからなかったので詰みですが．

来年こそ…！！