[New-bugs-announce] [issue32981] Catastrophic backtracking in poplib and difflib

[James Davis]

New submission from James Davis <davisjam at vt.edu>:

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"
}

----------
components: Library (Lib)
messages: 313119
nosy: davisjam
priority: normal
pull_requests: 5723
severity: normal
status: open
title: Catastrophic backtracking in poplib and difflib
type: security

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue32981>
_______________________________________