# 2025-12-09_"hit-and-miss": 251218
{%preview https://alpacahack.com/daily/challenges/hit-and-miss %}
Level: Easy
Type: Misc
solved day: 2025-12-18

## solution

python try1.py

出力:

progress: R
progress: Re
progress: Reg
progress: Reg3
progress: Reg3x
progress: Reg3x_
progress: Reg3x_C
progress: Reg3x_Cr
progress: Reg3x_Cro
progress: Reg3x_Cros
progress: Reg3x_Cross
progress: Reg3x_Crossw
progress: Reg3x_Crossw0
progress: Reg3x_Crossw0r
progress: Reg3x_Crossw0rd
FLAG = Alpaca{Reg3x_Crossw0rd}

Flag: `Alpaca{Reg3x_Crossw0rd}`

## How I thought.

### 1. ファイルの確認

ls -la

.rw-r--r--@  234 s12810162  7 Dec 03:57 app.py
.rw-r--r--@  164 s12810162  7 Dec 10:17 compose.yaml
.rw-r--r--@  185 s12810162  6 Dec 06:08 Dockerfile

### 2. サーバーコードの解析

`app.py` の内容:

import os, re

FLAG = os.environ.get("FLAG", "Alpaca{REDACTED}")
assert re.fullmatch(r"Alpaca\{\w+\}", FLAG)

while pattern := input("regex> "):
    if re.match(pattern, FLAG):
        print("Hit!")
    else:
        print("Miss...")

#### 分析

* サーバーは正規表現パターンを受け取り、フラグとマッチするか判定
* マッチすれば `Hit!`、しなければ `Miss...` を返す
* フラグの形式は `Alpaca{\w+}` （英数字とアンダースコアのみ）
* **Regex Oracle Attack** が可能：正規表現を使ってフラグを1文字ずつ特定できる

### 3. 攻撃手法の設計

#### 基本方針

正規表現の前方一致を利用して、フラグを1文字ずつ推測する。

例：
* `^Alpaca\{` → Hit! （フラグの先頭は `Alpaca{`）
* `^Alpaca\{R` → Hit! （最初の文字は `R`）
* `^Alpaca\{Re` → Hit! （2文字目は `e`）

#### 効率化：二分探索

候補文字が63文字（`[a-zA-Z0-9_]`）ある場合、総当たりでは最悪63回のクエリが必要。
文字クラスを使った二分探索で効率化：

1. 候補を半分に分割：`[a-z0-9_]` と `[A-Z]` など
2. `^Alpaca\{prefix[a-z0-9_]` でクエリ
3. Hit なら左半分、Miss なら右半分に絞り込む
4. 候補が1文字になるまで繰り返す

この方法なら、1文字あたり約 log₂(63) ≈ 6回のクエリで特定できる。

### 4. 実装上の注意点

#### プロトコルの理解

サーバーとの通信フロー：
1. 接続後、サーバーが `regex> ` プロンプトを送信
2. クライアントが正規表現パターンを送信
3. サーバーが `Hit!` または `Miss...` + 次の `regex> ` を送信

#### 初期実装の問題

最初のコードではタイムアウトエラーが発生：

def query(sock, pattern: str) -> bool:
    recv_until(sock, PROMPT)  # ← これが原因！
    sendline(sock, pattern)
    resp = recv_until(sock, PROMPT)
    return b"Hit!" in resp

問題点：
* `query()` を呼ぶ前に既にプロンプトは受信済み
* もう一度 `recv_until(sock, PROMPT)` を呼ぶと、データが来ないためタイムアウト

#### 修正

def query(sock, pattern: str) -> bool:
    sendline(sock, pattern)  # すぐにパターンを送信
    resp = recv_until(sock, PROMPT)  # 応答を待つ
    return b"Hit!" in resp

そして、接続直後に初期プロンプトを読み取る：

def solve_fast():
    s = socket.socket()
    s.connect((HOST, PORT))
    recv_until(s, PROMPT)  # 初期プロンプトを消費
    assert query(s, r"^Alpaca\{")
    # ...

### 5. 解答スクリプト (`try1.py`)

import socket

HOST = "34.170.146.252"
PORT = 60263
PROMPT = b"regex> "

# ASCIIの\wに対応する集合
ALPHABET = list("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_")

def recv_until(sock, marker=PROMPT, timeout=5.0):
    sock.settimeout(timeout)
    data = b""
    while True:
        chunk = sock.recv(4096)
        if not chunk:
            break
        data += chunk
        if marker in data:
            break
    return data

def sendline(sock, s: str):
    sock.sendall(s.encode() + b"\n")

def query(sock, pattern: str) -> bool:
    sendline(sock, pattern)
    resp = recv_until(sock, PROMPT)
    return b"Hit!" in resp

def classpat(prefix: str, chars: list[str]) -> str:
    # 文字クラスを使ったパターン: ^Alpaca\{prefix[charset]
    charset = "".join(chars)
    return rf"^Alpaca\{{{prefix}[{charset}]"

def solve_fast():
    s = socket.socket()
    s.connect((HOST, PORT))
    # Read initial prompt after connection
    recv_until(s, PROMPT)
    assert query(s, r"^Alpaca\{")

    prefix = ""
    while True:
        # 終端（}）の可能性を先にテスト
        if query(s, rf"^Alpaca\{{{prefix}\}}$"):
            print("FLAG =", f"Alpaca{{{prefix}}}")
            break

        # 二分探索：集合を半分にして所属を判定
        candidates = ALPHABET[:]
        while len(candidates) > 1:
            mid = len(candidates) // 2
            left, right = candidates[:mid], candidates[mid:]
            # 次の文字が left 側にあるか？
            if query(s, classpat(prefix, left)):
                candidates = left
            else:
                candidates = right

        # 1文字に絞れたはず
        c = candidates[0]
        # 念のため確認
        if query(s, rf"^Alpaca\{{{prefix}{c}"):
            prefix += c
            print("progress:", prefix)
        else:
            # ありえないが、落ちたら総当たりにフォールバック
            for c2 in ALPHABET:
                if query(s, rf"^Alpaca\{{{prefix}{c2}"):
                    prefix += c2
                    print("progress:", prefix)
                    break
            else:
                # どれも当たらない→終端確認
                if query(s, rf"^Alpaca\{{{prefix}\}}$"):
                    print("FLAG =", f"Alpaca{{{prefix}}}")
                    break
                print("Unexpected failure.")
                break

    s.close()

if __name__ == "__main__":
    solve_fast()

### 6. 動作の流れ

1. サーバーに接続し、初期プロンプトを受信
2. `^Alpaca\{` でフラグの先頭を確認
3. 各文字位置で二分探索：
* 候補文字集合を2分割
* `^Alpaca\{prefix[left_half]` でクエリ
* Hit/Miss で候補を絞り込み
* 1文字に絞れたら確定
4. `^Alpaca\{prefix\}$` で終端を検出
5. フラグを出力

### 7. 実行結果

python try1.py

約6秒でフラグを取得：

progress: R
progress: Re
progress: Reg
progress: Reg3
progress: Reg3x
progress: Reg3x_
progress: Reg3x_C
progress: Reg3x_Cr
progress: Reg3x_Cro
progress: Reg3x_Cros
progress: Reg3x_Cross
progress: Reg3x_Crossw
progress: Reg3x_Crossw0
progress: Reg3x_Crossw0r
progress: Reg3x_Crossw0rd
FLAG = Alpaca{Reg3x_Crossw0rd}

## まとめ

* **Regex Oracle Attack**: 正規表現の判定結果を利用してフラグを抽出
* **二分探索**: 文字クラスを使って効率的に候補を絞り込み
* **プロトコル理解が重要**: 初期プロンプトの処理と、query関数内での recv_until の順序に注意
* 総クエリ数: 約 15文字 × 6回 = 90回程度で効率的にフラグを取得

フラグ名 `Reg3x_Crossw0rd` は正規表現（Regex）とクロスワード（Crossword）を掛けた言葉遊び。