Regexploit: 可导致DoS的正则表达式

2021年3月11日 - 作者：Ben Caller

当谈及拒绝服务(DoS)攻击时，我们通常关注分布式拒绝服务(DDoS)，即数百万僵尸机通过发起数据海啸使服务过载。然而，通过滥用Web应用程序使用的算法，攻击者只需单个请求就能使服务器瘫痪。这需要找到在特定条件下性能极差的算法，然后触发这些条件。一个广泛且经常存在漏洞的领域是正则表达式(regexes)的误用。

正则表达式用于各种文本处理任务。它们可能看起来运行良好，但如果正则表达式容易受到正则表达式拒绝服务(ReDoS)的攻击，就可能构造输入导致CPU以100%运行数年。

在这篇博文中，我们发布了一个新工具来分析正则表达式并寻找ReDoS漏洞。我们的启发式方法已被证明极其有效，正如在流行的NPM、Python和Ruby依赖中发现许多漏洞所证明的那样。

用Regexploit检查你的正则表达式

🚀 @doyensec/regexploit - pip install regexploit 并发现一些错误。

回溯机制

要深入理解这个话题，让我们回顾一下Python、Perl、Ruby、C#和JavaScript等语言中正则表达式匹配引擎的工作原理。想象我们使用这个故意设计得很愚蠢的正则表达式来提取版本号：

(.+)\.(.+)\.(.+)

这将正确处理类似123.456.789的内容，但这是一个相当低效的正则表达式。匹配过程如何工作？

第一个.+捕获组贪婪地匹配到字符串末尾，因为点号匹配每个字符。

123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789

$1="123.456.789"。 匹配器然后查找字面点字符。 找不到时，它尝试从第一个.+中逐个移除字符

123.456.789 123.456.789 123.456.789 123.456.789 123.456.789

直到成功匹配一个点 - $1="123.456"

123.456.789 123.456.789 123.456.789

第二个捕获组匹配最后三个数字$2="789"，但我们需要另一个点，所以必须回溯。

123.456.789 123.456.789 123.456.789

嗯…似乎捕获组1的匹配不正确，让我们尝试回溯。

123.456.789 123.456.789 123.456.789 123.456.789 123.456.789

好的，让我们尝试$1="123"，并让组2贪婪地匹配到末尾。

123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789

$2="456.789"但现在没有点！那不可能是正确的组2…

123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789 123.456.789

最终我们有了成功的匹配：$1="123", $2="456", $3="789"

如你所见，正则表达式匹配过程中可能有很多来回操作。这种回溯是由于正则表达式的模糊性，输入可以以不同方式匹配。如果正则表达式设计不当，恶意输入可能导致比这更资源密集的回溯循环。如果回溯需要极长时间，将导致拒绝服务，如2019年Cloudflare发生的情况。在NodeJS等运行时中，事件循环将被阻塞，停止所有计时器、等待、请求和响应，直到正则表达式处理完成。

ReDoS示例

现在我们可以看一个ReDoS示例。ua-parser包包含一个巨大的正则表达式列表，用于解析浏览器User-Agent头。CVE-2020-5243中报告的一个正则表达式是：

; *([^;/]+) Build[/ ]Huawei(MT1-U06|[A-Z]+\d+[^\);]+)[^\);]*\)

如果我们仔细查看结尾部分，可以看到三个重叠的重复组：

\d+[^\);]+[^\);]*\)

数字字符由\d和[^\);]匹配。如果N个数字的字符串进入该部分，有½(N-1)N种可能的方式在\d+、[^\);]+和[^\);]*组之间分割。导致ReDoS的关键是提供不成功匹配的输入，例如不在恶意输入末尾加上右括号。正则表达式引擎将回溯并尝试所有可能的匹配方式，希望找到)。

这个匹配步骤的可视化是通过使用我的cpython分支从cpython的正则表达式引擎发出详细调试信息生成的。

Regexploit

今天，我们发布了一个名为Regexploit的工具，用于从代码中提取正则表达式、扫描它们并查找ReDoS。已有几个工具可以找到具有指数最坏情况复杂度的正则表达式（形式为(a+)+b的正则表达式），但立方复杂度的正则表达式（a+a+a+b）仍然可能造成损害。

Regexploit遍历正则表达式并尝试找到单个字符可能被多个重复部分捕获的模糊性。然后它寻找使正则表达式不匹配的方法，从而迫使正则表达式引擎回溯。

regexploit脚本允许你通过stdin输入正则表达式。如果正则表达式看起来正常，它会说"No ReDoS found"。对于上面的正则表达式，它显示了漏洞：

1
2
3

最坏情况复杂度：3 ⚠⚠⚠ (立方)
重复字符：[[0-9]]
示例：';0 Build/HuaweiA' + '0' * 3456

输出的最后一行提供了创建User-Agent头的配方，该头将在使用旧版本ua-parser的站点上导致ReDoS，可能导致Bad Gateway错误。

User-Agent: ;0 Build/HuaweiA0000000000000000000000000000...

要扫描源代码，内置支持从Python、JavaScript、TypeScript、C#、JSON和YAML中提取正则表达式。如果你能从其他语言提取正则表达式，可以将它们管道输入并分析。

一旦找到易受攻击的正则表达式，仍然需要一些手动调查。如果不可信输入不可能到达正则表达式，那么它可能不代表安全问题。在某些情况下，可能需要前缀或后缀才能将有效负载送到正确位置。

ReDoS调查

那么存在什么样的ReDoS问题？我们使用Regexploit分析了前几千个npm和pypi库（从libraries.io API获取）来找出答案。

我们试图排除构建工具和测试框架，因为这些中的错误不太可能有任何安全影响。当找到易受攻击的正则表达式时，我们需要弄清楚不可信输入如何到达它。

结果

最有问题的领域是使用正则表达式解析编程或标记语言。使用正则表达式解析某些语言，如Markdown、CSS、Matlab或SVG，充满危险。这些语言的语法设计为由专门的词法分析器和解析器处理。尝试用正则表达式执行此任务会导致过于复杂的模式，普通人难以阅读。

漏洞的一个重复来源是处理可选空白。例如，让我们以Python模块CairoSVG为例，它使用以下正则表达式：

rgba\([ \n\r\t]*(.+?)[ \n\r\t]*\)

1
2
3
4
5
6
7
8

$ regexploit-py .env/lib/python3.9/site-packages/cairosvg/
.env/lib/python3.9/site-packages/cairosvg/colors.py #190中的易受攻击正则表达式
模式：rgba\([ \n\r\t]*(.+?)[ \n\r\t]*\)
上下文：RGBA = re.compile(r'rgba\([ \n\r\t]*(.+?)[ \n\r\t]*\)')
---
Starriness: 3 ⚠⚠⚠ (立方)
重复字符：[20,09,0a,0d]
示例：'rgba(' + ' ' * 3456

开发人员希望找到类似rgba( 100,200, 10, 0.5 )的字符串并提取中间部分而不包含周围空格。不幸的是，中间的.+也接受空格。如果字符串不以右括号结尾，正则表达式将不匹配，我们可以获得O(n3)回溯。

让我们看看输入"rgba(" + " " * 19的匹配过程：

多么浪费CPU周期！

在cpython的http.cookiejar中发现了一个有趣的ReDoS错误，使用这个华丽的正则表达式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

模式：^
    (\d\d?)            # 日
       (?:\s+|[-\/])
    (\w+)              # 月
        (?:\s+|[-\/])
    (\d+)              # 年
    (?:
          (?:\s+|:)    # 时钟前的分隔符
       (\d\d?):(\d\d)  # 时:分
       (?::(\d\d))?    # 可选秒
    )?                 # 可选时钟
       \s*
    ([-+]?\d{2,4}|(?![APap][Mm]\b)[A-Za-z]+)? # 时区
       \s*
    (?:\(\w+\))?       # 括号中的时区ASCII表示
       \s*$
上下文：LOOSE_HTTP_DATE_RE = re.compile(
---
Starriness: 3 ⚠⚠⚠
重复字符：[SPACE]
导致回溯的最终字符：[^SPACE]
示例：'0 a 0' + ' ' * 3456 + '0'

它用于处理cookie过期日期，如Fri, 08 Jan 2021 23:20:00 GMT，但兼容一些已弃用的日期格式。正则表达式模式的最后5行包含三个由可选组分隔的\s*组，因此我们有一个立方ReDoS。受害者只需发出像requests.get('http://evil.server')这样的HTTP请求，就可能被远程服务器攻击，响应形式为：

Set-Cookie: b;Expires=1-c-1 X

在Python中，HTTP头行最多可容纳65506个空格，客户端将需要超过一周时间来完成处理头。

再次，问题在于设计正则表达式来处理可选部分之间的空白。另一点要注意的是，根据git历史，我们发现的麻烦正则表达式大多自首次进入代码库以来保持不变。虽然这表明正则表达式在正常情况下似乎不会引起问题，但也许表明正则表达式太难以维护。如果上面的正则表达式没有注释解释它应该匹配什么，谁敢尝试修改它？可能只有xkcd的那家伙。

抱歉，我想把这个漫画塞到某个地方

缓解措施 - 安全第一

使用DFA

那么为什么我不费心在Golang中寻找ReDoS？Go的正则表达式引擎re2不回溯。其设计（确定性有限自动机）被选择为即使正则表达式本身不可信也是安全的。保证是无论输入如何，正则表达式匹配将在线性时间内发生。

但有一个权衡。根据你的用例，像re2这样的库可能不是最快的引擎。还有一些正则表达式功能，如反向引用，不得不放弃。但在病态情况下，正则表达式不会让你的网站宕机。许多语言都有re2库，因此你可以优先使用它而不是Python的re模块。

不要全部用正则表达式做

对于空白模糊问题，通常可以先使用简单的正则表达式，然后从结果的两侧修剪/去除空格。

许多小正则表达式

在Ruby中，标准库包含StringScanner，有助于"词法扫描操作"。虽然http-cookie gem比巨型正则表达式有更多代码行，但它在解析Set-Cookie头时避免了REDoS。一旦字符串的每个部分被匹配，它就拒绝回溯。在某些正则表达式风格中，你可以使用"占有量词"将部分标记为不可回溯，并实现类似效果。

必须抓住它们所有 🐛🐞🐜

CVE-2020-5243: uap-core影响uap-python、uap-ruby等（User-Agent头解析） CVE-2020-8492: cpython的urllib.request（WWW-Authenticate头解析） CVE-2021-21236: CairoSVG（SVG解析） CVE-2021-21240: httplib2（WWW-Authenticate头解析） CVE-2021-25292: python-pillow（PDF解析） CVE-2021-26813: python-markdown2（Markdown解析） CVE-2021-27290: npm/ssri（SRI解析） CVE-2021-27291: pygments词法分析器用于ADL、CADL、Ceylon、Evoque、Factor、Logos、Matlab、Octave、ODIN、Scilab和Varnish VCL（语法高亮） CVE-2021-27292: ua-parser-js（User-Agent头解析） CVE-2021-27293: RestSharp（.NET C#包中的JSON反序列化） bpo-38804: cpython的http.cookiejar（Set-Cookie头解析） SimpleCrawler（已归档）（HTML解析） CVE-2021-28092: 待发布 加上许多未发布的错误在少数pypi、npm、ruby和nuget包中。我们将在https://github.com/doyensec/regexploit 更新此列表