Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 18 Sep 2013 18:03:00 -0700
From: Eric Hodel <>
To: Alexander Cherepanov <>
 " Sharipov" <>,
 "" <>
Subject: Re: CVE-2013-4287 Algorithmic complexity vulnerability in RubyGems 2.0.7 and older

On Sep 18, 2013, at 15:05, Alexander Cherepanov <> wrote:
> On 2013-09-18 04:11, Eric Hodel wrote:
>> 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…

Good catch, I think this is a bug, but I'll need to check with the person who added that.

>> 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
> .

Thank you.  I glossed over the * in ANCHORED_VERSION_PATTERN, and this fixes the problem with minimal change (something I would prefer for a security fix).

Here is a complete updated patch including the backtracking and extra "-" fixes:

Download attachment "CVE-2013-XXXX.2.patch" of type "application/octet-stream" (2406 bytes)

The same script as my previous message can be used to verify it.

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.