(OWASP汉化)攻击系列大全(五十一):正则表达式拒绝服务(ReDoS)

最新版本(mm/dd/yy): 07/5/2017
翻译至Regular expression Denial of Service – ReDoS

引言

正则表达式拒绝服务(Regular expression Denial of Service-ReDoS)是一种拒绝服务攻击(Denial of Service ),它利用了大多数正则表达式实现可能会导致极端情况的原因,这些极端情况导致它们工作得非常缓慢(与输入大小呈指数关系),然后攻击者可以使用正则表达式导致程序进入这些极端情况,然后挂起很长时间。

概述

有问题的正则表达式naïve算法

有问题的正则表达式naïve算法构建非确定性有限自动机( Nondeterministic Finite Automaton (NFA)),它是一个有限状态机,其中对于每对状态和输入符号,可能存在几个可能的下一个状态。然后引擎开始转换直到输入结束。由于可能有几个可能的下一个状态,所以使用确定性算法。该算法逐个尝试所有可能的路径(如果需要),直到找到匹配(或者所有路径都尝试失败)。

如下例子,正则表达式 ^(a+)+$ 由以下状态机表示:

对于输入aaaaX,上图中有16个可能的路径。但对于aaaaaaaaaaaaaaaaX,则有65536个可能的路径,并且该数字是每个附加a的两倍。这是一个极端的情况,其中naïve算法是有问题的,因为它必须经过许多路径,然后失败。

请注意,并非所有算法都是天真的,实际上可以用高效的方式编写正则表达式(Regex)算法。不幸的是,今天大多数正则表达式引擎不仅试图解决“纯粹”的正则表达式,而且还通过“特殊添加”来解决“扩展”正则表达式,例如不能总是有效解决的反向引用(请参阅Wiki中的非常规语言的模式( Patterns for non-regular languages) – 更多细节的正则表达式)。所以即使正则表达式不是“扩展”的,也使用了一种简单的算法。

邪恶的regex

如果一个正则表达式可以被固定在精心设计的输入上,那么它就被称为“邪恶(evil)”。

邪恶的正则表达式模式包含:

  • 重复分组(Grouping with repetition)
  • 在重复组内(Inside the repeated group: ):
    • 重复 (Repetition)
    • 交替重叠的(Alternation with overlapping)

例子

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x} | for x > 10

以上所有的人都容易受到输入的影响,aaaaaaaaaaaaaaaaa!(当使用更快或更慢的机器时,最小输入长度可能会略有变化)。

风险因素

网络是基于正则表达式的:

在WEB的每一层都有正则表达式,可能包含邪恶的正则表达式。攻击者可以挂起WEB浏览器(在计算机上或可能在移动设备上),挂起Web应用程序防火墙(WAF),攻击数据库,甚至堆叠易受攻击的WEB服务器。

例如,如果程序员使用Regex来验证系统的客户端,并且Regex包含邪恶的 Regex,则攻击者可以假定在服务器端使用相同的易受攻击的Regex,并发送精心设计的输入,堆叠WEB服务器。

实例

在线存储库中的易受攻击的正则表达式

正则表达式数据库,id = 1757(电子邮件验证)看到黑体字部分,这是段邪恶的正则表达式:

  • ^([a-zA-Z0-9])**(([-.]|[_]+)?([a-zA-Z0-9]+))***(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$

输入:

  • aaaaaaaaaaaaaaaaaaaaaaaa!

OWASP验证正则表达式库,Java类名,看到黑体字部分,这是段邪恶的正则表达式:

  • ^(([a-z])+.)+A-Z+$

输入:

  • aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

Web应用程序攻击

  • 打开一个JavaScript
  • 找到邪恶的正则表达式
  • 为找到的正则表达式创建恶意输入
  • 通过拦截代理提交有效的值
  • 更改请求,将恶意输入包含在内
  • 你完成了!

ReDoS通过正则表达式注入

以下示例检查用户名是否是用户输入的密码的一部分。

String userName = textBox1.Text;
String password = textBox2.Text;
Regex testPassword = new Regex(userName);
Match match = testPassword.Match(password);
if (match.Success)
{
    MessageBox.Show("Do not include name in password.");
}
else
{
    MessageBox.Show("Good password.");
}

如果攻击者输入 ^(([a-z])+.)+A-Z+$ 作为用户名,输入 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! 作为密码,那么该程序将挂起。

相关的威胁代理

待定(TBD)

相关攻击

相关漏洞

相关控件

参考文献