$ cat writeup.md…
$ cat writeup.md…
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.
$ cat /etc/rate-limit
Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.
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.
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:
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