Regular Expression Denial of Service

Checkmarx Research Lab presents a new attack vector on Web applications. =
By
exploiting the Regular Expression Denial of Service (ReDoS) =
vulnerability an
attacker can make a Web application unavailable to its intended users. =
ReDoS
is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar =
Weidman
from Checkmarx show how serious it is and how using this technique, =
various
applications can be =93ReDoSed=94. These include, among others, =
Server-side of
Web applications and Client-side Browsers. 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.

For further reading:
http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3


Alex=A0Roichman
Chief Architect, Checkmarx Ltd.=A0
Mobile: +972 54=A0774=A05198=A0=A0 Fax:=A0 +972-3-6870794=A0=A0 Website: =
www.Checkmarx.com






Replies to this exploit:

From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it. 


From: Gadi Evron ge@linuxbox.org
Sent: Fri 11. Sep 2009 19:21
Alex Roichman wrote:
> Checkmarx Research Lab presents a new attack vector on Web applications. By
> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
> attacker can make a Web application unavailable to its intended users. ReDoS
> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
> from Checkmarx show how serious it is and how using this technique, various
> applications can be “ReDoSed”. These include, among others, Server-side of
> Web applications and Client-side Browsers. 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.
> 
> For further reading:
> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3

Alex, nice work. Thank you for sharing it with us.

Id recommend taking a look at Ilja van Sprundels work with regular 
expression bugs in his Unusual bugs presentation.
... Where he played a bit with Google Code Search back in 2007, I think. 
He helped Google out by giving them his research, of course.

I found two versions online:
http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
http://www.slideshare.net/amiable_indian/unusual-bugs

Ilja and I later discussed creating a real regex fuzzer to discover 
vulnerabilities, but I at least never had the time to play with it. He 
might have, I am CC:ing him.

My best to Adar,

Gadi Evron,
http://www.gadievron.com/


From: Gadi Evron ge@linuxbox.org
Sent: Sat 12. Sep 2009 00:10
Thierry Zoller wrote:
> Hi ,
> 
> With all due respect - this is known to be a vulnerability class since
> over  a  century.  Just  because  it  doesnt  have a acronym à la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the  attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
> 
> Its  the  impact  of  something  that makes it a vulnerability no the
> name.

Thierry, you are quite right. However, I dont think they claimed it was 
a new class of vulnerabilities, and the responses since just added data 
to it. So I think that while you are factually correct, you misread 
their post. They shared their research with us.

	Gadi.


> 
> 
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerability an
>>> attacker can make a Web application unavailable to its intended users. ReDoS
>>> is commonly known as a “bug” in systems, but Alex Roichman and Adar Weidman
>>> from Checkmarx show how serious it is and how using this technique, various
>>> applications can be “ReDoSed”. These include, among others, Server-side of
>>> Web applications and Client-side Browsers. 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.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=23&cat=3
> 
> GE> Alex, nice work. Thank you for sharing it with us.
> 
> GE> Id recommend taking a look at Ilja van Sprundels work with regular 
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I think.
> GE> He helped Google out by giving them his research, of course.
> 
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
> 
> GE> Ilja and I later discussed creating a real regex fuzzer to discover 
> GE> vulnerabilities, but I at least never had the time to play with it. He
> GE> might have, I am CC:ing him.
> 
> GE> My best to Adar,
> 
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
> 


From: Jeffrey Walton noloader@gmail.com
Sent: Fri 11. Sep 2009 17:35
Hi Thierry,

> With all due respect - this is known to be a vulnerability
> class since over  a  century.
The referenced web page is titled, "ReDoS (Regular Expression Denial
of Service) Revisited". The authors cite work as early as 2003 in
their paper.

> Can we please stop the  attitude of inventing
> acronyms for vulnerabilites, ...
Having a bad day?

> Its  the  impact  of  something  that makes it a vulnerability
> no the name.
In my humble opinion, the novelty is that Checkermax, a firm which
specializes in source code analysis, may be staging a tool to help
solve or alleviate the problem. At minimum, the firm has added to the
body of knowledge.

If youve ever had the pleasure of working behind someone who thinks
K&R terseness is cool, you will welcome any and all tools to perform
static and dynamic analysis. These folks live in a fantasy world where
function calls do not fail and bad guys do not exist.

Jeff

On Fri, Sep 11, 2009 at 1:06 PM, Thierry Zoller <Thierry@zoller.lu> wrote:
> Hi ,
>
> With all due respect - this is known to be a vulnerability class since
> over =A0a =A0century. =A0Just =A0because =A0it =A0doesnt =A0have a acron=
ym =E0 la XSS
> doesnt mean its not known to be a vulnerability. Can we please stop
> the =A0attitude of inventing acronyms for vulnerabilites, making it look
> like its something new and funky.
>
> Its =A0the =A0impact =A0of =A0something =A0that makes it a vulnerability=
 no the
> name.
>
>
> GE> Alex Roichman wrote:
>>> Checkmarx Research Lab presents a new attack vector on Web applications=
. By
>>> exploiting the Regular Expression Denial of Service (ReDoS) vulnerabili=
ty an
>>> attacker can make a Web application unavailable to its intended users. =
ReDoS
>>> is commonly known as a =93bug=94 in systems, but Alex Roichman and Adar=
 Weidman
>>> from Checkmarx show how serious it is and how using this technique, var=
ious
>>> applications can be =93ReDoSed=94. These include, among others, Server-=
side of
>>> Web applications and Client-side Browsers. The art of attacking the Web=
 by
>>> ReDoS is by finding inputs which cannot be matched by Regexes and on th=
ese
>>> Regexes a Regex-based Web systems get stuck.
>>>
>>> For further reading:
>>> http://www.checkmarx.com/NewsDetails.aspx?id=3D23&cat=3D3
>
> GE> Alex, nice work. Thank you for sharing it with us.
>
> GE> Id recommend taking a look at Ilja van Sprundels work with regular
> GE> expression bugs in his Unusual bugs presentation.
> GE> ... Where he played a bit with Google Code Search back in 2007, I thi=
nk.
> GE> He helped Google out by giving them his research, of course.
>
> GE> I found two versions online:
> GE> http://www.ruxcon.org.au/files/2006/unusual_bugs.pdf
> GE> http://www.slideshare.net/amiable_indian/unusual-bugs
>
> GE> Ilja and I later discussed creating a real regex fuzzer to discover
> GE> vulnerabilities, but I at least never had the time to play with it. H=
e
> GE> might have, I am CC:ing him.
>
> GE> My best to Adar,
>
> GE> Gadi Evron,
> GE> http://www.gadievron.com/
>
>
>
> --
> http://blog.zoller.lu
> Thierry Zoller
>
>
>


From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 20:32
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 /



From: Pavel Kankovsky peak@argo.troja.mff.cuni.cz
Sent: Sun 13. Sep 2009 21:35
Oops. "PCRE" in my response should have read "Perl". PCRE implementation
is different from the implementation included in Perl--and rather
ironically it seems PCRE is vulnerable.

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



From: hackerwebzine@gmail.com
Sent: Mon 28. Sep 2009 07:19
Alex, it isnt a new technique in web-application security. If you queried Google, or did some research on recent (2007) Blackhat talks, youll probably noticed that this is very well known and understood technique. Even Charles Miller talked about it (on the OSX Safari exploits). So the claim that security researchers are not aware of it, it somewhat misleading. I personally (and many others too) used the same techniques, albeit slightly different for over 8 years when auditing applications. Since you seem to propose a serious "new" research area, i expect you to research its history first before claiming "new" research, at least I would appreciate it.