ReDOS初探 – 作者:Setup

0x01 概述

其实也是在做一次Code Review项目的时候，发现了一个ReDos的问题，但是由于惰性，没记录一下。最近比较有空了，所以抽个时间记录一下。

0x02 知识铺垫

所谓的 ReDOS(Regular expression Denial of Service) 正则表达式拒绝服务攻击 。实际上开发人员使用了正则表达式来对用户输入的数据进行有效性校验, 当编写校验的正则表达式存在缺陷或者不严谨时, 攻击者可以构造特殊的字符串来大量消耗服务器的系统资源，造成服务器的服务中断或停止。
正则表达式是什么，其实大家应该都知道，或者都用到过，但是这里需要提及一些东西就是正则表达式的引擎。这里首先涉及到一个概念： 有限状态自动机 。

（FSM “finite state machine” 或者FSA “finite state automaton” ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。

而有限状态自动机还可以分成确定与非确定两种, 非确定有限状态自动机可以转化为确定有限状态自动机。（小声bb，其实这不是关键）。关键在于正则表达式引擎分成两类：一类称为DFA（确定性有限状态自动机），另一类称为NFA（非确定性有限状态自动机）。

两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。

两个引擎其实存在本质上的差别：

1. DFA对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词（见item 4）；
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

这里引用别人的例子，因为我觉得举的很好。

现在有个文本为： perlmanbook ，一个正则表达式为 /perl|perlman/ ，而这个正则表达式在两种引擎下的匹配结果我们可以看下。

首先是NFA，它是以正则为导向，怎么说呢，这时候我们手上第一个子正则表达式为 /perl/ ，而该引擎针对 perlmanbook 字符串进行扫描，从左开始，当进度进行到 perl manbook 的时候，最开始部分的 perl 已经和第一个子正则表达式匹配而上，而当引擎进度扫描到m字符的时候，发现与第一个子正则表达式不匹配，于是把m吐出来，向上汇报说成功匹配 perl ，不再关心其他，也不尝试第二个子正则式 /perlman/ 。

若是DFA引擎的情况下，它是以文本为导向，针对正则从左开始进行扫描，当扫描到 /p/ 的时候，发现匹配的上了，然后继续往下匹配，当将第一个子正则 /perl/ 全部匹配上之后，这时候就会把这个正则甩开，去吃第二个子正则式的 /p/ 。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 ‘perlman’ 。

也就是说我们可以总结一下，NFA引擎要翻来覆去吃字符、吐字符，速度慢，且可能会陷入递归险境导致性能极差。因此使用NFA引擎的正则表达式就可能出现 ReDOS 的问题了。

0x03 漏洞样例

目前正则引擎支持的语言种类：

我们来看一个demo。

简单说明一下这个^(a+)+$正则的作用是什么：

^：匹配输入字符串的开始位置，也就是说从下面str_list字符串中的最开头开始匹配。

a：就是字符a，这里不多做说明

+：“+”(懒惰) 重复一次或更多次，例如”aaaaaaaa” 匹配字符串中所有的a。

$：\$会匹配行或字符串的结尾。

那么我们通过一段代码进行一下验证

根据Regular Expression Denial of Service这个个PPT里面，总结了一下：

• 重复分组构造
• 重复组内应出现：1.重复，2.交替重叠

会出现ReDOS的样例正则表达式。

1. (a+)+
2. ([a-zA-Z]+)*
3. (a|aa)+
4. (a|a?)+
5. (.*a){x} | for x > 10

Payload: “aaaaaaaaaaaaaaaaaaX”

当然我们也可以使用python的re模块来验证一下是否存在ReDOS，因为Python的re模块用的就是NFA的引擎。

该PPT中提供了一些业务场景下可能存在ReDOS的正则表达式写法

下面我们来展示一些实际业务场景中会用到的缺陷正则。

• Person Name:
  • Regex: ^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!
• Java Classname
  • Regex: ^(([a-z])+.)+[A-Z]([a-z])+$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
• Email Validation
  • Regex: ^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$
  • Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
• Multiple Email address validation
  • Regex: ^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*\s+<(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})>$|^(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaa!
• Decimal validator
  • Regex: ^\d*[0-9](|.\d*[0-9]|)*$
  • Payload: 1111111111111111111111111!
• Pattern Matcher
  • Regex: ^([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?\.){0,}([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?){1,63}(\.[a-z0-9]{2,7})+$
  • Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

我们可以用下面这段python代码来辅助验证。

#!/usr/bin/env python
# coding: utf-8

import re
import time

s1 = time.time()
regex = re.compile('^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$')
str='aaaaaaaaaaaaaaaaa!'        
#str='aaaaaaaaaaaaaaaaaaa!'
regex.match(str)
s2=time.time()
print(str)
print(s2-s1)

分别定义

str='aaaaaaaaaaaaaaaaa!'          
str='aaaaaaaaaaaaaaaaaaa!'

最后结果

aaaaaaaaaaaaaaaaa!
0.0207

aaaaaaaaaaaaaaaaaaa!
0.0776

之前Ph师傅的 code-breaking 题目里面就有一题 prefwaf ，这题实际上就涉及到这个问题，首先源码是这样的。

<?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);
}

其实这里很明显我们要写入webshell，但是要绕过 is_php 函数中的 /<\?.*[(`;?>].*/is 正则表达式，假设我们输入的字符是 <?php phpinfo();//aaaaa ，那么这个字符串匹配流程我们看一下这个动图。

我们看到，到第4步开始由于?.*是贪婪模式匹配，因此抓取到了这个字符串也就是 //aaaaa 的末尾，而立实际上还有部分内容是 [(`;?>] 等特殊字符，也就是说这部分代码里面如果存在这些字符就匹配成功，而该NFA引擎的正则表达式目前没有找到，因此它从第5步开始回溯，先吐出一个a，输入变成第5步显示的//aaaa，但仍然匹配不上正则，继续吐出a，变成//aaa，仍然匹配不上……。直到第12步回溯的 ; 匹配上了字符 [(`;?>] 中的 ; 。

然后 第13步 又匹配 .* ，执行贪婪匹配，通过 ; 将回溯源 <?php phpinfo(); 全部抓了出来，并返回匹配成功。

PHP为了防止正则表达式的拒绝服务攻击（reDOS），给pcre设定了一个回溯次数上限pcre.backtrack_limit。我们可以通过var_dump(ini_get('pcre.backtrack_limit'));的方式查看当前环境下的上限。

这里的回溯上限是1000000，也就是说我们看看超过回溯上限的执行结果。

php > var_dump(preg_match('/<\?.*[(`;?>].*/is','<?php phpinfo();//'.str_repeat('a',1000000)));
bool(false)

preg_match返回的非1和0，而是false。preg_match函数返回false表示此次执行失败了，我们可以调用var_dump(preg_last_error() === PREG_BACKTRACK_LIMIT_ERROR);，发现失败的原因的确是回溯次数超出了限制。

这里修复的话，php.net针对这个函数提及到了修复建议。

如果用preg_match对字符串进行匹配，一定要使用===全等号来判断返回值，如：

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

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

这样，即使正则执行失败返回false，也不会进入if语句。

Reference

DFA和NFA

Regular Expression Denial of Service

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

来源：freebuf.com 2019-04-08 19:13:22 by: Setup