ReDoS 正则回溯与时序侧信道防御

ReDoS 通过构造恶意输入触发回溯 NFA 引擎指数级复杂度，进而阻塞单线程 Event Loop 或迫使 WAF 超时放行（Fail-Open）；Timing Attack 则利用字符串提前退出比较与分支耗时差，在统计采样下逐字节还原 Secret/Token。两者都无法仅靠“提高超时时间”或“局部微调延迟”解决，必须从算法复杂度上限与恒定时间密码学原语入手根治。

防御工作流

识别所有处理不可信输入的正则表达式与秘密比较点
  → 将回溯正则替换 Linear-Time 引擎（RE2）或结构化解析器
  → 设定严格输入长度上限与 Fail-Closed 匹配超时，隔离出主事件循环
  → Token/API Key/签名校验统一改为先哈希定长再执行恒定时间比较
  → 验证增长长度不引起超线性耗时且不同前缀耗时分布不可区分

1. ReDoS 根治策略

A. 更换线性时间引擎与专用解析器

场景	易受攻击正则模式	推荐安全替代方案
通用复杂匹配	标准 PCRE / JS RegExp / Python re	Node 使用 re2，Python 使用 google-re2（Guarantees $O(n)$），Go 原生 regexp（基于 RE2），Rust regex
Email / URL 校验	长邮箱/域名嵌套量词正则	Python urllib.parse + email.utils.parseaddr；JavaScript 使用标准 new URL()；配合最大长度限制（Email <= 254 字符）
路由 Rewrite / 路径匹配	/a/a/.../! 触发路径正则爆炸	使用前缀树（Trie）或确定性路径路由器，避免任意长重复段正则

B. 消除危险模式与强制边界

若受限于运行环境无法引入 RE2：

1. 消除回溯结构：严禁使用嵌套量词 (a+)+、([a-z]+)*，严禁含重叠前缀的选择分支 (a|aa)+、(\w+|\d+)+，避免无锚定重复通配 .*.*。在支持的引擎（PCRE/Python 3.11+）中可使用原子组 (?>...) 或占有量词 ++/*+ 禁止回溯。
2. 强制输入长度截断：在正则执行前先做硬性长度判断（如 if len(value) > 256: return 400），将最坏匹配开销锁死在可控常量级。
3. WAF / 网关 Fail-Closed：WAF 正则规则触发匹配超时或步数限制时，必须默认拒绝请求（返回 403 / 400），严禁“超时跳过规则放行后端”（Fail-Open）。
4. 隔离主 Event Loop：Node.js/Python asyncio 单线程服务不得在主事件循环内对长文本执行用户可控或未验证复杂度的正则，应剥离至带预算限制的 Worker 线程池/子进程。

2. 时序侧信道（Timing Attack）根治

1. 禁止普通等号比较秘密值：token == expected 或 strcmp 会在首个不匹配字节立刻返回，经由数千次统计采样（trimmed mean/median）即可还原完整密钥。
2. 先定长摘要再恒定时间比较：某些语言中即便调用对比函数，若输入长度不等仍可能提前返回从而泄露长度先验。标准做法是使用随机或固定密钥对双方计算定长 HMAC-SHA256，再执行恒定时间比对：
   • Python: hmac.compare_digest(hmac.new(key, user_tok, "sha256").digest(), hmac.new(key, real_tok, "sha256").digest())
   • Node.js: 先计算相同长度 crypto.createHmac("sha256", key)...digest()，再调用 crypto.timingSafeEqual(bufA, bufB)
   • Go: subtle.ConstantTimeCompare(macA, macB) == 1
3. 消除前置早退分支：不要在比对前先查询数据库并依据“用户存在/格式合法”采取不同路径耗时的逻辑；如先检查前缀格式再做 HMAC，依然会暴露格式/长度特征。应统一提取定长哈希后走同一校验路径，并叠加账户/IP 级速率限制降低采样信噪比。

3. 可运行 ReDoS 检测与恒定时间校验器

以下 Python 脚本包含两项实用验证能力：（1）对给定正则表达式执行典型回溯结构静态检查与阶梯长度耗时递增测试；（2）提供不泄露长度与前缀的恒定时间 Secret 校验器并做统计基准验证：

#!/usr/bin/env python3
"""ReDoS 正则退化防护检测 + 恒定时间 Secret 校验器。"""
import hmac
import hashlib
import os
import re
import statistics
import time

# 常见灾难性回溯结构特征（启发式预检）
RISKY_REGEX_PATTERNS = [
    re.compile(r"\([^)]*[+*][^)]*\)[+*]"),       # 嵌套量词 (a+)+ / ([a-z]+)*
    re.compile(r"\([^)]*\|[^)]*\)[+*]"),         # 分支外包量词 (a|aa)+
]


def precheck_regex_safety(pattern: str) -> list[str]:
    warnings = []
    for rx in RISKY_REGEX_PATTERNS:
        if rx.search(pattern):
            warnings.append(f"potential catastrophic backtracking pattern matched: {rx.pattern}")
    return warnings


def benchmark_growth(pattern: str, char: str = "a", suffix: str = "!", lengths=(10, 16, 22), max_ms: float = 20.0) -> list[dict]:
    """核查正则在不同输入长度下是否出现指数级时间增长（先在沙盒隔离调用）。"""
    compiled = re.compile(pattern)
    rows = []
    for n in lengths:
        sample = char * n + suffix
        t0 = time.perf_counter()
        compiled.match(sample)
        elapsed_ms = (time.perf_counter() - t0) * 1000.0
        rows.append({"n": n, "elapsed_ms": round(elapsed_ms, 3), "exceeded_budget": elapsed_ms > max_ms})
    return rows


_COMPARE_KEY = os.urandom(32)


def constant_time_verify(candidate: str, expected: str) -> bool:
    """使用定长 HMAC-SHA256 + hmac.compare_digest，同时消除逐字节与长度泄露。"""
    mac_a = hmac.new(_COMPARE_KEY, candidate.encode("utf-8"), hashlib.sha256).digest()
    mac_b = hmac.new(_COMPARE_KEY, expected.encode("utf-8"), hashlib.sha256).digest()
    return hmac.compare_digest(mac_a, mac_b)


if __name__ == "__main__":
    # 1. 检测不安全正则与安全重写正则的对比
    unsafe_pat = r"^([a-z]+)+$"
    safe_pat = r"^[a-z]{1,64}$"

    assert precheck_regex_safety(unsafe_pat), "unsafe regex should trigger warning"
    assert not precheck_regex_safety(safe_pat), "safe bounded regex should have no warnings"

    unsafe_bench = benchmark_growth(unsafe_pat, lengths=(10, 18, 24), max_ms=5.0)
    safe_bench = benchmark_growth(safe_pat, lengths=(10, 18, 240), max_ms=5.0)
    print("unsafe growth:", unsafe_bench)
    print("safe growth:", safe_bench)
    assert any(r["exceeded_budget"] for r in unsafe_bench), "expected exponential spike on unsafe regex"
    assert all(not r["exceeded_budget"] for r in safe_bench), "safe regex exceeded budget"

    # 2. 校验恒定时间比较正确性及分布稳定性
    secret = "tok_live_9f8e7d6c5b4a3210"
    assert constant_time_verify(secret, secret) is True
    assert constant_time_verify("tok_live_9f8e7d6c5b4a3211", secret) is False
    assert constant_time_verify("x", secret) is False

    timings_match_prefix = []
    timings_wrong_prefix = []
    for _ in range(500):
        t0 = time.perf_counter()
        constant_time_verify("tok_live_9f8e7d6c5b4a321X", secret)
        timings_match_prefix.append((time.perf_counter() - t0) * 1e6)
        t0 = time.perf_counter()
        constant_time_verify("z", secret)
        timings_wrong_prefix.append((time.perf_counter() - t0) * 1e6)

    print(
        f"[PASS timing] match_prefix_median={statistics.median(timings_match_prefix):.2f}us, "
        f"wrong_len_median={statistics.median(timings_wrong_prefix):.2f}us"
    )

验证与判定标准

验证项	预期加固表现	阻断失败标志
正则长度增长曲线	输入长度线性递增时耗时保持平稳微秒/低毫秒级，无指数拐点	长度增加 4 字符即引起耗时翻倍或突破预算阈值
并发 Event Loop 稳定性	并发发送边界长度输入时，健康探针接口延迟不随恶意请求同步上升	触发正则的请求导致同实例其他接口同步卡死
WAF 超时策略	WAF 规则计算超限时统一返回 403/400 拒绝（Fail-Closed）	插入超长回溯前缀后使后续恶意 Payload 绕过检测
恒定时间 Secret 比较	正确前缀、错误前缀与不同长度输入的中位耗时分布无统计学分离	多轮采样后 top1 候选字符耗时稳定高于其他字符

MCP 工具映射

防御环节	MCP 工具	说明
防御知识路由	kb_router	按 redos、timing、re2、constant time 检索加固文档
读取攻击模型	kb_read_file	对照 ctf-website/03-injection/redos-timing 与 22-dos/04-redos 覆盖全部模式
浏览目录索引	kb_catalog	确认 03-injection 与 16-rate-limit 相关防御条目
时延基线对比	http_probe	切换到 red 或 both 轨道后测试长度递增输入与超时处理是否符合 Fail-Closed