cryptofreehard

TAUtology

tjctf

Task: regex validator runs re.match(user_pattern, flag) with 0.20s SIGALRM timeout but never returns the result. Solution: ReDoS timing side-channel — use lookahead + catastrophic backtracking pattern to distinguish correct vs wrong character guesses by response time, extracting the flag character by character.

$ ls tags/ techniques/
side_channelregextiming_attackredoscatastrophic_backtrackinglookaheadpython_re
redos_timing_oraclecatastrophic_backtracking_side_channellookahead_prefix_verificationmedian_noise_reductionconfirmation_rounds

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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:

...

$ grep --similar

Similar writeups