bugtraq - Re: Regular Expression Denial of Service

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Sun, 13 Sep 2009 20:32:37 +0200 (CEST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: Alex Roichman <Alexr@...ckmarx.com>
Cc: bugtraq@...urityfocus.com
Subject: Re: Regular Expression Denial of Service

On Thu, 10 Sep 2009, Alex Roichman wrote:

> The art of attacking the Web by ReDoS is by finding inputs which cannot
> be matched by Regexes and on these Regexes a Regex-based Web systems get
> stuck.

It is a shame your presentation assumes a primitive NFA implementation
and does not take optimizations used by real implementations into account
(they are not even mentioned).

A quick test confirms PCRE does not backtrack when it evaluates regular
expressions like ^(a+)*$ and the rest of your "real examples of ReDos"
(because their ambiguity is optimized away) and something rather
convoluted like ^((a{1,2}){1,2}){1,10}$ is needed to trigger
backtracking. See "Backtracking" in perlre manpage.

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /