---
# System prepended metadata

title: '2025-12-09_"hit-and-miss": 251218'
tags: [misc, easy, alpaca, CTF]

---

# 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

```sh
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. ファイルの確認

```sh
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` の内容:

```python
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> ` を送信

#### 初期実装の問題

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

```python
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)` を呼ぶと、データが来ないためタイムアウト

#### 修正

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

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

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

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

```python
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. 実行結果

```sh
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）を掛けた言葉遊び。
