Home page logo
/

oss-sec logo oss-sec mailing list archives

Re: CVE-2013-4287 Algorithmic complexity vulnerability in RubyGems 2.0.7 and older
From: Alexander Cherepanov <cherepan () mccme ru>
Date: Thu, 19 Sep 2013 02:05:11 +0400

On 2013-09-18 04:11, Eric Hodel wrote:
On Sep 16, 2013, at 18:28, Kurt Seifried <kseifried () redhat com> wrote:
On 09/14/2013 03:11 PM, Alexander Cherepanov wrote:
On 2013-09-10 09:32, Eric Hodel wrote:
The vulnerability can be fixed by changing the first grouping to
an atomic grouping in Gem::Version::VERSION_PATTERN in
lib/rubygems/version.rb.  For RubyGems 2.0.x:

-  VERSION_PATTERN =
'[0-9]+(\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?' #
:nodoc: +  VERSION_PATTERN =
'[0-9]+(?>\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?' #
:nodoc:

For RubyGems 1.8.x:

-  VERSION_PATTERN = '[0-9]+(\.[0-9a-zA-Z]+)*' # :nodoc: +
VERSION_PATTERN = '[0-9]+(?>\.[0-9a-zA-Z]+)*' # :nodoc:

This is not enough. The following script:

# Regexes are from 
https://github.com/rubygems/rubygems/blob/master/lib/rubygems/version.rb#L150


VERSION_PATTERN =
'[0-9]+(?>\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?' #
:nodoc: ANCHORED_VERSION_PATTERN =
/\A\s*(#{VERSION_PATTERN})*\s*\z/ # :nodoc: 
'1111111111111111111111111111.' =~ ANCHORED_VERSION_PATTERN

takes ~1m on my machine. The problem is not in VERSION_PATTERN but
in its possible repetition inside ANCHORED_VERSION_PATTERN.


Great, I guess we're going to need a new CVE. Before I assign one can
we make sure we fix this so more fiddly expressions don't cause
problems? Thanks.

Here's a new patch to go with the new (unassigned) CVE.  This new patch replaces regular expression matches that are 
susceptible to backtracking with a parser-like approach.

According to your patch 'versions have only one "-" (per semver)'. This
means that "*" after "(#{VERSION_PATTERN})" in ANCHORED_VERSION_PATTERN
is a bug. It should be "?". If you fix it then there should be no
problem with VERSION_PATTERN at all. AFAICT VERSION_PATTERN gives you a
linear complexity. Hence there is no need to suppress backtracking...

This patch applies to RubyGems 2.1.x releases.  I will create patches for RubyGems 1.8.23.1, 1.8.26, 2.0.9 and 2.1.4 
if it there is no obvious flaw seen in it.

I would like to release this fix by Monday, 23 September as I will be traveling mid-week.

The vulnerable regular expression constants are still present, but I can't think of a way to construct them that does 
not allow backtracking.

...but if you really want to suppress backtracking (say, for
optimization) it is easy: either atomic grouping for every repetition
(exactly the way you have already done but for other repetitions also)
or add extra "+" after each "+" and "*". That's according to
http://www.ruby-doc.org/core-2.0.0/Regexp.html .

-- 
Alexander Cherepanov


  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]