Issue 32981: Catastrophic backtracking in poplib (CVE-2018-1060) and difflib (CVE-2018-1061)

Hi Python security team,

My name is James Davis. I'm a security researcher at Virginia Tech.

The python core (cpython) has 2 regular expressions vulnerable to catastrophic backtracking that look like potential DOS vectors.
The vulnerable expressions are listed below.

Each vulnerability has the following keys, explained in more detail below:
 - pattern
 - filesIn (as of December/January; I excluded any appearances in irrelevant-looking dirs, and in '.min' files)
 - stringLenFor10Sec
 - nPumpsFor10Sec
 - attackFormat
 - blowupCurve

The attack format describes how to generate an attack string.
On my machine, an attack string generated using nPumpsFor10Sec repetitions ("pumps") of the pump string(s)
blocks the python regex engine for 10 seconds, though this will vary based on your hardware.

Compose an attack string like this:
  'prefix 1' + 'pump 1' X times + 'prefix 2' + 'pump 2' X times + ... + suffix
Example:
  With pumpPairs: [{'prefix': 'a', 'pump': 'b'}], suffix: 'c', an attack string with three pumps would be:
    abbbc

Catastrophic backtracking blows up at either an exponential rate or a super-linear (power law) rate.
The blowupCurve indicates how severe the blow-up is.
The 'type' is either EXP(onential) or POW(er law) in the number of pumps (x).
The 'parms' are the parameters for the two curve types. The second parameter is more important, because:
  EXP: f(x) = parms[0] * parms[1]^x
  POW: f(x) = parms[0] * x^parms[1]

JSON formatted:

Vuln 1:

{
   "attackFormat" : {
      "pumpPairs" : [
         {
            "pump" : "<a",
            "prefix" : "+OKa"
         }
      ],
      "suffix" : "+"
   },
   "blowupCurve" : {
      "parms" : [
         2.71096268836868e-08,
         1.83422078906374
      ],
      "type" : "POWER",
      "r2" : 0.997503282766243
   },
   "stringLenFor10Sec" : 96655,
   "nPumpsFor10Sec" : "48325",
   "pattern" : "\\+OK.*(<[^>]+>)",
   "filesIn" : [
      [
         "Lib/poplib.py"
      ]
   ]
}

Vuln 2:

{
   "blowupCurve" : {
      "parms" : [
         1.31911634447601e-08,
         1.89691808610459
      ],
      "r2" : 0.998387790742004,
      "type" : "POWER"
   },
   "stringLenFor10Sec" : 48328,
   "attackFormat" : {
      "pumpPairs" : [
         {
            "pump" : "\t",
            "prefix" : "\t"
         }
      ],
      "suffix" : "##"
   },
   "pattern" : "\\s*#?\\s*$",
   "filesIn" : [
      [
         "Lib/difflib.py"
      ]
   ],
   "nPumpsFor10Sec" : "48325"
}

New changeset 0e6c8ee2358a2e23117501826c008842acb835ac by Benjamin Peterson (Jamie Davis) in branch 'master':
bpo-32981: Fix catastrophic backtracking vulns (#5955)
https://github.com/python/cpython/commit/0e6c8ee2358a2e23117501826c008842acb835ac

New changeset 0902a2d6b2d1d9dbde36aeaaccf1788ceaa97143 by Benjamin Peterson (Miss Islington (bot)) in branch '3.7':
bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
https://github.com/python/cpython/commit/0902a2d6b2d1d9dbde36aeaaccf1788ceaa97143

New changeset e052d40cea15f582b50947f7d906b39744dc62a2 by Benjamin Peterson in branch '2.7':
[2.7] bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
https://github.com/python/cpython/commit/e052d40cea15f582b50947f7d906b39744dc62a2

New changeset c9516754067d71fd7429a25ccfcb2141fc583523 by Benjamin Peterson in branch '3.6':
[3.6] bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
https://github.com/python/cpython/commit/c9516754067d71fd7429a25ccfcb2141fc583523

New changeset 942cc04ae44825ea120e3a19a80c9b348b8194d0 by larryhastings (Ned Deily) in branch '3.4':
[3.4] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) (#6035)
https://github.com/python/cpython/commit/942cc04ae44825ea120e3a19a80c9b348b8194d0

New changeset 937ac1fe069a4dc8471dff205f553d82e724015b by larryhastings (Ned Deily) in branch '3.5':
[3.5] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) (#6034)
https://github.com/python/cpython/commit/937ac1fe069a4dc8471dff205f553d82e724015b

Is this ready to close?

> Is this ready to close?

The fixes are now available from the cpython repo for all current security and maintenance branches (3.4 to 3.7 plus 2.7).  They are now released in 3.6.5rc1 and will be available in the next releases of other branches: 3.7.0, 3.5.6, 3.4.9, and 2.7.15.

Thanks again for reporting the issues, James, and helping to resolve them!

FYI I tracked this vulnerability at:
http://python-security.readthedocs.io/vuln/cve-2018-1060_difflib_and_poplib_catastrophic_backtracking.html

nosy: + ned.deily
messages: + msg313803

resolution: fixed
stage: patch review -> resolved