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（非确定有限自动机）

• 一个“状态 + 字符”可能多个下一步（甚至还有不读字符就跳的“ε 转移”）

• 直觉上像同时走多条路

• 但实现上可以用“同时维护一组当前可能状态”的方式来做，同样能做到整体很高效

可以看到 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 的组合进行重复，导致指数级的尝试次数。这种指数级的回溯也叫做灾难级回溯，导致服务器性能大量降低。

用脚本绘图看看匹配时间:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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.

1
2
3
4
5
6
7
8
9

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中:

1
2
3

if(preg_match('/UNION.+?SELECT/is', $input)) {
    die('SQL Injection');
}

就可以使用大量回溯绕过

同样的:

1
2
3

if(preg_match('/UNION.+?SELECT/is', $input)) {
    die('SQL Injection');
}

虽然是非贪婪模式,但仍然可以通过传大量的a来使回溯次数超过限制,进而绕过WAF.

参考:

ReDoS-正则表达式拒绝服务攻击

PHP利用PCRE回溯次数限制绕过某些安全限制

正規表達式沒寫好會怎樣？淺談 ReDoS：利用 regexp 的攻擊

详解PCRE正则匹配的引擎、回溯、贪婪问题