PHP利用回溯次数限制绕过

回溯绕过

这里以i春秋圣诞欢乐赛中一道题为例
代码如下

<?php
function areyouok($greeting){
return preg_match('/Merry.*Christmas/is',$greeting);
}

$greeting=@$_POST['greeting'];
if(!areyouok($greeting)){
if(strpos($greeting,'Merry Christmas')!==false){
echo 'Merry Christmas. '.'flag{259efcb4-bb57-4967-8aa8-8271f04f655a}';
}else{
echo 'Do you know .swp file?';
}
}else{
echo 'Do you know PHP?';
}
?>

题目虽然有更简单的解法，但是为了说明问题，我们来讨论如何绕过正则

PHP为了防止正则表达式的拒绝服务攻击（reDOS），给pcre设定了一个回溯次数上限，这个上限默认是100万

所以当我们向其发送100万个a然后在发送Merry Christmas就可以绕过正则的校验，函数会返回NULL，也就符合了题目要求

什么是正则表达式

比较规范的说法是：正则表达式是一个可以被“有限状态自动机”接受的语言类。

常见的正则引擎有DFA和NFA，分别叫做确定性有限状态自动机和非确定性有限状态自动机

其中NFA的执行过程存在回溯，PHP就使用了NFA引擎，其中PCRE库属于NFA引擎