はまやんはまやんはまやん

hamayanhamayan's blog

i3CTF Writeup

Security

[web] Meta

「CTFのためだけに作られた適当なサイト」が与えられる。/meta/も実はヒントになっていて、Ctrl+Uでサイトのソースコードを開いてみると以下のようなmetaタグが付いており、フラグが得られる。

<meta name="This is Flag" content="FLAG{Developer_tools_is_useful}">

[web] login

The Road to SQL Masterということで、SQL Injectionではないかなと考えを巡らせる。とりあえず試してみよう。'と"を入れてみるが、エラーにはならない。

SQL Injectionっぽさはあるので、とりあえず想像でSQL Injectionを試す。自分はこういう時は以下のような入力を試している。[username]:[password]で表記する。

admin:" or ""="
admin:' or ''='

下で刺さってフラグが得られる。FLAG{5QL_1nJ3Ct10n}が答え。

[web] input

問題文にLet's execute the alert function!とあり、入力文字列を表示させるサイトが与えられるので、XSSを試す。とりあえず<script>alert(1);</script>としてみるが、何も起きない。

ソースコードを見てみる。

<script>
    alert_orig = alert
    alert = function(){
        console.log(this, arguments);
        console.trace();
        window.open("./flag.php");
        return alert_orig.apply(this, arguments);        
    }

    function Write(str){
        pattern = /\"|\'|\/|javascript/g;
        str = str.replace(pattern, "");
        prm = document.getElementById("prm");
        prm.innerHTML = str;
    }
</script>

"と'と/とjavascriptが消されてinnerHTML経由でサイトに埋め込まれている。alertがoverrideされてフラグ表示に繋がっているので何でもいいのでalert関数が呼べればいい。

mdnのinnerHTMLのセキュリティの考慮事項を見てみると、scriptタグはそもそも禁止されているので、上の処理が無くてもscriptタグは動かなかった。

このページでも紹介されている、imgタグを使ってみよう。'が禁止されているが、'は無くてもいいので、<img src=x onerror=alert(1)>でフラグが出てくる。

Cross-site scripting (XSS) cheat sheetで色々なXSSペイロードがまとめられているので、ここから使えそうなものを探すという方針でも良さそうですね。

[network] http

WireSharkで開き、TCPストリームで開いてみるが、gzipでエンコードされていたので、HTTPストリームで開きなおすと、gzipが展開され、フラグが出てくる。

[network] Bob

WireSharkで開く。パケットを眺めるとFTP通信がなされているので、「ファイル > オブジェクトをエクスポート > FTP-DATA」で見てみると、nagoya.pngというファイルがあるのでエクスポートして中身を見てみる。フラグが書いてある。

[network] basic

題名からbasic認証っぽさがある。TCPストリームを漁ると#1にAuthorizationヘッダーが残っていた。

Authorization: Basic Sm9objpGTEFHe0I0czFjXzFzX24wdF9zM2N1cjN9

ユーザー名:パスワードがbase64エンコードされたものなのでbase64デコードするとフラグが出てくる。

[network] layout

HTTPストリームを表示すると、色んなファイルにフラグが断片的に置いてあるのでくっつけて答えると正答。

[network] ppap

TCPストリームを順番に見えていくと#2でivorykey.pemとmaizekey.pemが送られていた。それ以降の通信を見ていくと、ESMTPの通信に移行している。この時に使われている鍵が以上の鍵だろうか。適当に調べてできたこのページを見ながらPEMファイルを適用すると、TLSが復号できる。

TCLストリーム#7をTLSストリームで見てみると、secret.zipというファイルが送られているのが見える。TCPストリーム#8のTLSストリームを見ると、パスワードがやり取りされていた。d48pwbc7

これでsecret.zipを解凍するとsecret.pcapが得られる中を見ると、動画データっぽいので以下の手順で抜き出して見てみるとフラグが出てくる。

  1. H264extractorのプラグインをWiresharkに入れておく
  2. ここを参考にWiresharkの設定 > Protocols > H.264を開き、RTP payload typeを96に設定する
  3. Wiresharkのツール > Extract h264 stream from RTPを実行すると動画ファイルが抜き出せる
  4. そのままでは見れなかったので、ffmpeg -i video_20240622-181640.264 -movflags faststart -vcodec libx264 -acodec libfaac out.mp4のようにmp4に変換すると閲覧可能。

[crypto] Julius

Qksec Tevsec Mkockb gkc k Bywkx qoxobkv kxn cdkdocwkx. K wowlob yp dro Psbcd Dbsewfsbkdo, Mkockb von dro Bywkx kbwsoc sx dro Qkvvsm Gkbc lopybo nopokdsxq rsc zyvsdsmkv bsfkv Zywzoi sx k msfsv gkb, kxn celcoaeoxdvi lomkwo nsmdkdyb pbyw 49 LM exdsv rsc kcckccsxkdsyx sx 44 LM. PVKQ sc OspqATNUTZwMIdT

が与えられる。

ROT13だろうということで、CyberChefのROT13 Brute Forceを試すと、16で良い感じに復号できた。ROT13でAmountを16とすると以下となり、フラグが分かる。

Gaius Julius Caesar was a Roman general and statesman. A member of the First Triumvirate, Caesar led the Roman armies in the Gallic Wars before defeating his political rival Pompey in a civil war, and subsequently became dictator from 49 BC until his assassination in 44 BC. FLAG is EifgQJDKJPmCYtJ

ということでFLAG{EifgQJDKJPmCYtJ}

[crypto] xor

以下のような暗号化コードが与えられる。

import random
import string
import hashlib

from Crypto.Util.number import bytes_to_long,long_to_bytes

flag = b'kore_ha_dummy_desu_anata_ha_tadori_tuku_beki_da_FLAG{dummy}'

key = random.choice(string.printable.strip()).encode()

hash = hashlib.blake2b(flag).hexdigest()

enc = b''

for i in range(len(flag)):
    a = flag[i] ^ bytes_to_long(key)
    enc += long_to_bytes(a)

print(f'enc = {enc}')
print(f'hash = {hash}')

keyとして1文字のascii文字が使われているので全探索が可能。全探索してフラグが含まれる結果を出力してくるとフラグが得られる。

enc = b'\x12\x16...[redacted]...\x0b\x04'

import random
import string
import hashlib

from Crypto.Util.number import bytes_to_long,long_to_bytes
from Crypto.Util.strxor import *

for key in string.printable:
    plain = strxor(enc, key.encode()*len(enc))
    if b"FLAG{" in plain:
        print(plain)

[crypto] rsa

import random as rd

import gmpy2
from Crypto.Util.number import *

flag = b'FLAG{dummy}'

rd_number = rd.getrandbits(64) | 1
p = gmpy2.next_prime(rd_number)

rd_number = rd.getrandbits(64) | 1
q = gmpy2.next_prime(rd_number)

n = p * q
e = 65537

c = pow(bytes_to_long(flag),e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

このような暗号化コードが与えられる。p,qのビット数が小さいのでfactordbなどで素因数分解可能。以下のようにして解く。

n = 89765553359668267846115148791526510167
e = 65537
c = 43726401623720020767763547639229741559

# https://factordb.com/index.php?query=89765553359668267846115148791526510167
p = 7188697477892891021
q = 12487040056383040627

assert p * q == n

from Crypto.Util.number import long_to_bytes
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))

[crypto] Matryoshka

色んなエンコーディングが施されているので、順番にデコードしていく。

NjItPlU0TTJ3cFJER0NwNUI4cWtvdXdZaUhDVlF2a0lnZnRremh3NXBUemtZeDROWG96RENHV0J3MGZCQ0tVYWcxbmd3TFQzdHJHemswdmRQdjBSaVVDUkV2VUJSaWtZWHd4UnJNUkVLTW0xaXRaOUFMUXdvNXh6TVpBMU12MXM1VU81RmlTMFN5M1JURnUxOGZWQ2VkdEs2VEtOWllqcGFRWWswTkwycUhURGtCVU9nVGlGSHA3VWlydTJJZlV4QUJhMW5lM0p5c2QweDNTT0hEVGEyOVR5WGZrQW1ST2JjRHRYUGxHd2V4emZsc0N6Y2g1NVVSZ0ZQOWdNcXp2NjJGVGU3VHhLY3l0T05LQ2pKUjRYem1XNlA5blBGVDlwOHB2Smh6amFYSHlndzZHVXpLQkU1VU94cGNyZXpzZjhCNG1qeVVoYk9CWDNFdGVkVzRqWHpBZnFwblVSWFMxQTdYRWlpTTZxMk5VdE9iTHpMQ0lXVG9WOXBSVzM==

- From Base64 ->

62->U4M2wpRDGCp5B8qkouwYiHCVQvkIgftkzhw5pTzkYx4NXozDCGWBw0fBCKUag1ngwLT3trGzk0vdPv0RiUCREvUBRikYXwxRrMREKMm1itZ9ALQwo5xzMZA1Mv1s5UO5FiS0Sy3RTFu18fVCedtK6TKNZYjpaQYk0NL2qHTDkBUOgTiFHp7Uiru2IfUxABa1ne3Jysd0x3SOHDTa29TyXfkAmRObcDtXPlGwexzflsCzch55URgFP9gMqzv62FTe7TxKcytONKCjJR4XzmW6P9nPFT9p8pvJhzjaXHygw6GUzKBE5UOxpcrezsf8B4mjyUhbOBX3EtedW4jXzAfqpnURXS1A7XEiiM6q2NUtObLzLCIWToV9pRW3

- From Base62 ->

58->7nH1jTqufPSpfePjTvn8iLY1zrqZ7fkGFndTJ6BRpnwumrTN151mJJ8W33oEt5FrsdLohLGmzSYHQ2E6XdpHhtc6edKjgZHPLtq6oypWaayZzC6MFmVgRZ4bdp9JVUugzbbTy7VoEAks8QU9mXMW61yo3aHcMVP2uE3G5rpRrbgckrsrqeKa25jLo2yd6As2s527fJZJeEMXBKrTCbHas8UtW9d5mVXpxqPWk1fzBQCALqrns9Q9V96pfRCQHXR8p11EoBwhPFFJUNXD2SwG

- From Base58 ->

45->BL6HW5K09SL6AG6KIA 090M6HN9WNAT091N8T09GIAK09/F61C9 H9O098DBS09+H9309:F60C9WNAT09FH81C9+H94C9/F60C90JBS09TL6GY8GH8CC9*IB+NAJIAS09EG6X09GIA-B9*IBYY9IIA 09*IBX09EH8+09*IBIN9$H9T09GS8S09IH8G09TL66B8HX7

- From Base45 ->

32->GE3C2PRXGU3TKMSEGNCTGNRTGE2DINJRGIYTGMJVG42EIMSEGNBTINJVIQ2DIMZZGM3DERBUIYZTSMRWGM2TGRRTIIZTMMRVGUZTGRBSGYZTKNJSGNDDGMBWGA3DA===

- From Base32 ->

16->75752D3E363144512131574D2D3C455D4439362D4F3926353F3B3625533D2635523F306060

- From Hex ->

uu->61DQ!1WM-<E]D96-O9&5?;6%S=&5R?0``

- Uudecode (http://uuencode.online-domain-tools.com/) -> 

FLAG{Mr_decode_master}

[crypto] pqrneca

from Crypto.Util.number import *

flag = b"FLAG{dummy}"

p = getPrime(512)
q = getPrime(512)
r = getPrime(16)

n = p * q * r

e = 65537

c = pow(bytes_to_long(flag),e,n)
a = pow(p + q + r, (p - 1) * (q - 1) * (r - 1), n) * ((p + q + r) % n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f'a = {a}')

rは小さいので直ぐに求まる。factordbにnを入れてみると、r=48973であると分かる。

\displaystyle a = (p + q + r)^{(p-1)(q-1)(r-1)} (p + q + r) \,\verb|mod|\,n

mod nの付け方微妙に違うけども、大体こんな感じ。複雑に見えるが、実はオイラーの定理より、前半部分は1になる。よって、

\displaystyle a = p + q + r \,\verb|mod|\,n \\ n = pqr

という感じに連立方程式が立てられ、未知の変数はp,qの2つなので解ける。

n = 78949977...[redacted]...8448403
e = 65537
c = 628152285...[redacted]...1805198
a = 25399154...[redacted]...97238653

r = 48973

R.<p, q> = PolynomialRing(ZZ)
f1 = p * q * r - n
f2 = p + q + r - a
rr = f1.resultant(f2).univariate_polynomial().roots()

p = rr[0][0]
q = rr[1][0]

assert p * q * r == n

from Crypto.Util.number import long_to_bytes
phi = (p-1)*(q-1)*(r-1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))

[crypto] fermat

import gmpy2
from Crypto.Util.number import *

flag = b'FLAG{dummy}'

p = getStrongPrime(2048)
q = gmpy2.next_prime(p)
n = p * q
e = 65537
c = pow(bytes_to_long(flag),e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

以上のような暗号化コードが与えられる。p,qが隣り合う素数になっている。p,qが近いときに可能な攻撃と言えば、Fermat's Methodである。そのまま実装する。

import math

n = 67631939...[redacted]...6394869
e = 65537
c = 66477080...[redacted]...0592820

for b in range(1, 101010):
    a = math.isqrt(n + b * b)
    if a * a - b * b == n:
        p = a + b
        q = a - b
        break

print(f"{p=}")
print(f"{q=}")

assert p * q == n

from Crypto.Util.number import long_to_bytes
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, n)))

[crypto] pow

from Crypto.Util.number import *

flag = b'FLAG{dummy_dummy}'
length = len(flag)

p = getStrongPrime(2048)
q = getStrongPrime(2048)
n = p * q
e = 3
c = pow(pow(pow(pow(bytes_to_long(flag),e,n),e,n),e,n),-1,n)

print(f'length = {length}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

暗号化コードは以上なので、要は以下のようなことをしている。

\displaystyle c = \verb|flag|^{-e^3} \,\verb|mod|\,n

-1は置いておいて、3eの部分はe=3なので27乗していることになる。flagの長さはlength = 18とかなり短いので27乗根を取ってやればフラグが復元できる。

n = 8329965...[redacted]...99197767
e = 3
c = 316741640...[redacted]...34387569

import gmpy2
from Crypto.Util.number import *

m,result = gmpy2.iroot(pow(c, -1, n),27)
print(long_to_bytes(m))
print(result)

[crypto] yyy

import random as rd

from Crypto.Util.number import *

from FLAG import FLAG

n = len(FLAG) * 8
m = bytes_to_long(FLAG)

su = getRandomNBitInteger(512)
w = [su]

for i in range(n-1):
    w.append(rd.randint(su + 1, 3 * su))
    su += w[-1]

b = len(bin(su)) -2

assert float(n/b) < 0.645

q = getRandomInteger(su.bit_length() + 1)

r = q
while GCD(r,q) != 1:
    r = rd.randrange(2,q)

beta = list(map(lambda x: (r * x % q), w))

c = sum(beta[i] for i in range(n) if (m >> i) & 1)

print(f'beta = {beta}')
print(f'c = {c}')

以上のような暗号化スクリプトが与えられる。注目すべきはc = sum(beta[i] for i in range(n) if (m >> i) & 1)の部分でナップザック暗号になっている。ナップサック暗号を効率的に解くCLOS法を使って解く。

beta = [5294548904499335828345210355237891313207358051780812170058389309550870875835637442465504740662736372890054872474315756834575184464146390518118,...[redacted]... 1031695206309081302780528242137986282411995505898958521992093484481502224962562588459041324990228564965929734153085401275765469364837045153698]
c = 91665257...[redacted]...83688

N = len(beta)

K = N * N
M = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    M[i][0] = K * beta[i]
    M[i][i + 1] = 100
M[N][0] = -K * c
for i in range(N):
    M[N][i + 1] = -50

cands = Matrix(ZZ, M).LLL()
for cand in cands:
    ok = (cand[0] == 0)
    for i in range(N):
        if cand[i + 1] not in [50, -50]:
            ok = False
    if ok:
        ans = 0
        for xi in reversed(cand[1:]):
            ans *= 2
            ans += (xi == 50)
        
        from Crypto.Util.number import *
        print(long_to_bytes(ans))

手元にあるCLOS法実装をそのまま使うと解けた。

[crypto] diff

import hashlib
import random as rd
import string

from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

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

def func(a, b, c, n):
    sequence = [a, b, c]
    for i in range(3, n):
        next_value = (sequence[i-1] + sequence[i-2] + sequence[i-3]) % 2**4
        sequence.append(next_value)
    return sequence

flag = b'FLAG{dummy}'
flag = pad(flag, 16)

key = ''.join(rd.sample(string.ascii_lowercase, 10))
key = key.encode()
key2 = b''
nonce = b''

l = func(rd.randint(1, 10),rd.randint(1, 10),rd.randint(1, 10),10)
l2 = func(rd.randint(1, 10),rd.randint(1, 10),rd.randint(1, 10),10)

for i in range(len(key)):
    key2 += long_to_bytes(key[i] + l[i])

for i in range(len(key2)):
    nonce += long_to_bytes(key2[i] + l2[i])

c1 = pow(bytes_to_long(key), e, n)
c2 = pow(bytes_to_long(key2), e, n)
c3 = pow(bytes_to_long(nonce), e, n)

key_hash = hashlib.sha256(key).digest()
cipher = AES.new(key_hash, AES.MODE_GCM, nonce=nonce)
encrypted_flag = cipher.encrypt(flag)

print(f'n = {n}')
print(f'e = {e}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
print(f'encrypted_flag = {encrypted_flag}')

暗号化スクリプトは以上。2段階で解いていく。

keyを求める

まずはkeyを求めよう。keyに関連する部分を抜粋して見てみよう。

def func(a, b, c, n):
    sequence = [a, b, c]
    for i in range(3, n):
        next_value = (sequence[i-1] + sequence[i-2] + sequence[i-3]) % 2**4
        sequence.append(next_value)
    return sequence

key = ''.join(rd.sample(string.ascii_lowercase, 10))
key = key.encode()
key2 = b''

l = func(rd.randint(1, 10),rd.randint(1, 10),rd.randint(1, 10),10)

for i in range(len(key)):
    key2 += long_to_bytes(key[i] + l[i])

c1 = pow(bytes_to_long(key), e, n)
c2 = pow(bytes_to_long(key2), e, n)

func関数にて乱数列を作っているが、[1,10]の乱数を3つシードとして使っていて、全探索できそうな感じに見える。乱数列lが全探索により既に分かっていると仮定すると、どんな攻撃ができそうか考えると…Franklin-Reiter Related Message Attackが出来そうに見えてくる。keyに対して乱数列lを対応するバイトへ加算することでkey2を作成している。これを式にしてみると以下のようになる。

\displaystyle \verb|key2| = \verb|key| + l_0 2^{8*9} + l_1 2^{8*8} + ... + l_8 2^8 + l_9 2^0

つまりは、key2 = key + dのような形になっているということ。そう考えると

\displaystyle \verb|c1| = \verb|key|^e \,\verb|mod|\,n \\ \verb|c2| = (\verb|key|+d)^e \,\verb|mod|\,n

という風に整理でき、これはFranklin-Reiter Related Message Attackの典型的な形である。乱数列lを作るシードを全探索して、Franklin-Reiter Related Message Attackを使ってkeyを復元すると、アルファベットの小文字からなるものが1種類しか出てこなかった。これによりkeyが復元できる。なお、自動的にkey2と乱数列lも求められたことになる。

nonceを求める

nonceは以下のように計算される。

nonce = b''

l2 = func(rd.randint(1, 10),rd.randint(1, 10),rd.randint(1, 10),10)

for i in range(len(key2)):
    nonce += long_to_bytes(key2[i] + l2[i])

c3 = pow(bytes_to_long(nonce), e, n)

前回と同様に乱数列l2のシードに対して全探索が可能。全探索してみて、nonceを作ることで、keyとnonceが手に入るのでこれを使ってAES復号化してみればいい。その中でFLAG{から始まるものが正解。

solver

n = 125812611...[redacted]...4853533
e = 137
c1 = 64345707...[redacted]...605667
c2 = 6358723...[redacted]...8677
c3 = 628063...[redacted]...82890
encrypted_flag = b"\xad...[redacted]...\xb9_"

def func(a, b, c, n):
    sequence = [a, b, c]
    for i in range(3, n):
        next_value = (sequence[i-1] + sequence[i-2] + sequence[i-3]) % 2**4
        sequence.append(next_value)
    return sequence

pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)

import hashlib
import random as rd
import string

from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad

for r1 in range(1, 11):
    for r2 in range(1, 11):
        for r3 in range(1, 11):
            l = func(r1,r2,r3,10)
            d = 0
            for i in range(10):
                d += l[i] * 2 ** (8 * (9 - i))
            
            P.<x> = PolynomialRing(Zmod(n))
            f = x^e - c1
            g = (x + d)^e - c2
            m = -pgcd(f, g).coefficients()[0]
            cand = long_to_bytes(int(m))
            if all(ord('a') <= b <= ord('z') for b in cand):
                correct_l = l
                key = cand

print(f"{correct_l=}")
print(f"{key=}")

for r1 in range(1, 11):
    for r2 in range(1, 11):
        for r3 in range(1, 11):
            l2 = func(r1,r2,r3,10)
            key2 = b''
            nonce = b''
            for i in range(len(key)):
                key2 += long_to_bytes(key[i] + correct_l[i])
            for i in range(len(key2)):
                nonce += long_to_bytes(key2[i] + l2[i])
            key_hash = hashlib.sha256(key).digest()
            cipher = AES.new(key_hash, AES.MODE_GCM, nonce=nonce)
            flag = cipher.decrypt(encrypted_flag)
            if b"FLAG{" in flag:
                print(flag)