ReDos及PHP正则回溯绕过学习
是谁都5202年了8102年的知识点还没见过٩(ŏ﹏ŏ、)۶
ReDos
ReDos(正则表达式拒绝服务攻击) 是一种利用正则表达式引擎缺陷来发起的拒绝服务攻击.
正则表达式都是一种自动机.
关于自动机
自动机(Automaton)是一个理论计算机科学中的数学模型,代表一种能自动执行预定操作的序列的抽象计算设备,它通过在有限状态之间根据输入符号进行转换(跳转)来处理信息,并最终判断是否接受(识别)这个输入,在计算机科学中广泛用于编译器设计,模式匹配,语言识别等领域.
核心概念
状态: 自动机在任何时刻所处的情况,是有限的.
输入字母表: 自动机可以接收的符号集合
转移函数(Transition Function): 决定了在当前状态下,接收到特定输入符号后,自动机将跳转到哪个新状态.
起始状态: 自动机开始工作时的状态
接受状态(Accept State)/终止状态(Final State): 当输入处理完毕,如果停在接受状态,则认为该输入被"接受"或"识别"
语言(Langua): 自动机所能识别(接受)的所有字符串(输入序列)的集合
简单来说,可以把自动机类比为一个售货机
状态：投入硬币前、投入5元、投入10元、找零。
输入：投入硬币。
转移：投入1元，从“初始”状态跳到“1元”状态；投入5元，从“1元”跳到“6元”状态。
接受：当总金额满足商品价格时，进入“可购买”状态。
自动机分为两种,一种是有限自动机(FA)另一种是有限状态机(FSM)
正则语境中的自动机,通常指有限自动机,其又可以分为 DFA（确定性有限状态自动机）和 NFA（非确定性有限状态自动机）.
DFA 是用文本去匹配正则，对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；
NFA 则是使用正则表达式去匹配字符串，吃掉一个字符，就把它跟正则表达式比较。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
通过描述可以看出来，DFA 的速度会快很多，因为文本中的字符串只会比对一次，但功能较少；NFA 要不断的吃透字符串，虽然很慢但是具有分组、替换、分隔等特性，也支持惰性、回溯、反向引用等模式。
DFA（确定有限自动机）
每个“状态 + 字符最多只有一个下一步
所以匹配时永远只有一条路走线性扫描，很快、很稳定
NFA（非确定有限自动机）
一个“状态 + 字符”可能多个下一步（甚至还有不读字符就跳的“ε 转移”）
直觉上像同时走多条路
但实现上可以用“同时维护一组当前可能状态”的方式来做，同样能做到整体很高效
| 引擎类型 | 程序 |
|---|---|
| DFA | awk(大多数版本)、egrep（大多数版本）、flex、lex、MySQL、Procmail |
| 传统型 NFA | GNU Emacs、Java、grep（大多数版本）、less、more、.NET语言、PCRE library、Perl、PHP（所有三套正则库）、Python、Ruby、set（大多数版本）、vi |
| POSIX NFA | mawk、Mortice Lern System’s utilities、GUN Emacs（明确指定时使用） |
| DFA/NFA混合 | GNU awk、GNU grep/egrep、Tcl |
可以看到 PHP、JAVA、Python 等语言使用的就是 NFA 的引擎。
ReDos
在介绍自动机的时候我们提到了NFA支持回溯模式,而回溯会导致指数爆炸.
🌰 假设有这样一个正则:
/A(B|C+)+D/g
这个正则的意思是:
1.A:匹配字符A
2.(B|C+):匹配字符B或者一个或多个连续的字符C
3.+:匹配前面的模式(B|C+)一次或多次
4.D:匹配字符D
我们用ABC来做匹配,因为没有用D结尾,所以正则最终会失败,但在试图匹配时，正则表达式引擎会尝试所有可能的组合来看看是否可以成功匹配，特别是在 (B|C+) 和后面的 + 量词之间。
正则会尝试匹配尽可能多的 C，然后再尝试匹配 D。当匹配 D 失败时，它会回溯，并尝试匹配稍微少一些的 C，再尝试匹配 D。这种尝试和回溯的过程会对每个可能的 C 的组合进行重复，导致指数级的尝试次数。这种指数级的回溯也叫做灾难级回溯，导致服务器性能大量降低。
用脚本绘图看看匹配时间:
import re
import time
import math
import matplotlib.pyplot as plt
pattern = re.compile(r"A(B|C+)+D")
def measure(n: int) -> float:
s = "AB" + ("C" * n)
t0 = time.perf_counter()
ok = pattern.fullmatch(s) is not None
t1 = time.perf_counter()
return (t1 - t0), ok
def main():
max_n = 40
max_seconds = 3.0
repeat = 1
ns = []
times = []
print("n_Cs\tseconds\t\tmatched")
for n in range(1, max_n + 1):
best = math.inf
matched_any = False
for _ in range(repeat):
dt, ok = measure(n)
best = min(best, dt)
matched_any = matched_any or ok
ns.append(n)
times.append(best)
print(f"{n}\t{best:.6f}\t{matched_any}")
if best >= max_seconds:
print(f"\nStopped: time {best:.3f}s exceeded max_seconds={max_seconds}")
break
plt.figure()
plt.plot(ns, times, marker="o")
plt.yscale("log")
plt.xlabel("Number of 'C' characters (n)")
plt.ylabel("Match time (seconds, log scale)")
plt.title(r"Backtracking blowup demo: A(B|C+)+D vs AB + C*n (no D)")
plt.grid(True, which="both", linestyle="--", linewidth=0.5)
plt.tight_layout()
plt.savefig("redos.png", dpi=200)
print("saved: redos.png")
if __name__ == "__main__":
main()
不止回溯,正则表达式匹配还有贪婪和非贪婪模式
对于RCRE(PHP正则表达式)
有4个比较常用的元字符：
*匹配前面的子表达式零次或多次+匹配前面的子表达式一次或多次?匹配前面的子表达式零次或一次{n,m}匹配前面的子表达式n-m次，{n,}匹配前面的子表达式至少n次，{n}匹配前面的子表达式n次
再举个🌰
对于待匹配字符串abbbc
先用/ab{2,3}+bc/来匹配
这个正则的意思是贪婪+不允许回溯
匹配时就会直接吃掉所有的b,匹配bc的时候匹配不到b又无法回溯,就会直接匹配失败
而用ab{2,3}?bc进行非贪婪匹配
会尽量少吃b,在这个表达式中由于{2,3}限制,所以会先吃掉两个b,然后匹配bc的时候恰好匹配到,最后匹配成功.
在贪婪模式下,如果允许回溯,并且遇到多个分支或可选项,就会发生回溯爆炸
详见: 快速了解-ReDoS
CTF中的应用
在CTF中,如果有正则表达式存在ReDos漏洞,则我们可以利用服务器返回时间的不同来爆破flag.
console.time('CTF{a');
console.log(/CTF{[a](((((.*)*)*)*)*)!/.test('CTF{this_is_flag}'))
console.timeEnd('CTF{a');
// CTF{a: 0.071ms
console.time('CTF{t');
console.log(/CTF{[t](((((.*)*)*)*)*)!/.test('CTF{this_is_flag}'))
console.timeEnd('CTF{t');
// CTF{t: 24.577s
PHP正则回溯绕过
PHP为了防止正则表达式的拒绝服务攻击（reDOS），给pcre设定了一个回溯次数上限pcre.backtrack_limit,上限默认是100万,而当我们的回溯次数超过了100万,preg_match函数就不再返回0或1,而是返回false,表示此次执行失败,失败的原因是回溯次数超出了限制.
比如,在这个WAF中:
if(preg_match('/UNION.+?SELECT/is', $input)) {
die('SQL Injection');
}
就可以使用大量回溯绕过
同样的:
if(preg_match('/UNION.+?SELECT/is', $input)) {
die('SQL Injection');
}
虽然是非贪婪模式,但仍然可以通过传大量的a来使回溯次数超过限制,进而绕过WAF.