Re: CVE-2013-4287 Algorithmic complexity vulnerability in RubyGems 2.0.7 and older

[Eric Hodel <drbrain () segment7 net>]

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.

Attachment: CVE-2013-XXXX.patch
Description:

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.  I think they should be removed for the security fix release, but a fellow maintainer is 
worried about backwards compatibility and thinks they should be removed in the next feature release (2.2).  What do 
people typically do?

Here is a script to check the patch:

Attachment: check.CVE-2013-XXXX.rb
Description: