Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 19 Sep 2013 02:05:11 +0400
From: Alexander Cherepanov <>
CC: Eric Hodel <>,, 
 " Sharipov" <>,
 "" <>
Subject: Re: CVE-2013-4287 Algorithmic complexity vulnerability
 in RubyGems 2.0.7 and older

On 2013-09-18 04:11, Eric Hodel wrote:
> On Sep 16, 2013, at 18:28, Kurt Seifried <> 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:
>>>> '[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 
>>> '[0-9]+(?>\.[0-9a-zA-Z]+)*(-[0-9A-Za-z-]+(\.[0-9A-Za-z-]+)*)?' #
>>> /\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
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.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 .

Alexander Cherepanov

Powered by blists - more mailing lists

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.