Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Catastrophic backtracking in poplib (CVE-2018-1060) and difflib (CVE-2018-1061) #77162

Closed
davisjam mannequin opened this issue Mar 2, 2018 · 10 comments
Closed

Catastrophic backtracking in poplib (CVE-2018-1060) and difflib (CVE-2018-1061) #77162

davisjam mannequin opened this issue Mar 2, 2018 · 10 comments
Labels
3.7 (EOL) end of life 3.8 only security fixes stdlib Python modules in the Lib dir type-security A security issue

Comments

@davisjam
Copy link
Mannequin

davisjam mannequin commented Mar 2, 2018

BPO 32981
Nosy @tim-one, @vstinner, @larryhastings, @benjaminp, @ned-deily, @davisjam
PRs
  • bpo-32981: Fix catastrophic backtracking vulns #5955
  • [3.7] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) #5969
  • [2.7] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) #5970
  • [3.6] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) #5971
  • [3.5] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) #6034
  • [3.4] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) #6035
    		•

    Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
closed_at = <Date 2018-03-14.05:23:09.730>
created_at = <Date 2018-03-02.00:36:19.854>
labels = ['type-security', '3.8', '3.7', 'library']
title = 'Catastrophic backtracking in poplib (CVE-2018-1060) and difflib (CVE-2018-1061)'
updated_at = <Date 2019-05-10.18:09:12.303>
user = 'https://github.com/davisjam'

    bugs.python.org fields:

    activity = <Date 2019-05-10.18:09:12.303>
actor = 'ned.deily'
assignee = 'none'
closed = True
closed_date = <Date 2018-03-14.05:23:09.730>
closer = 'ned.deily'
components = ['Library (Lib)']
creation = <Date 2018-03-02.00:36:19.854>
creator = 'davisjam'
dependencies = []
files = []
hgrepos = []
issue_num = 32981
keywords = ['patch', 'security_issue']
message_count = 10.0
messages = ['313119', '313198', '313200', '313202', '313203', '313609', '313610', '313611', '313803', '316124']
nosy_count = 6.0
nosy_names = ['tim.peters', 'vstinner', 'larry', 'benjamin.peterson', 'ned.deily', 'davisjam']
pr_nums = ['5955', '5969', '5970', '5971', '6034', '6035']
priority = 'critical'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue32981'
versions = ['Python 2.7', 'Python 3.4', 'Python 3.5', 'Python 3.6', 'Python 3.7', 'Python 3.8']
    @davisjam
    Copy link
    Mannequin Author

    davisjam mannequin commented Mar 2, 2018

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

    @davisjam davisjam mannequin added stdlib Python modules in the Lib dir type-security A security issue labels Mar 2, 2018
    @benjaminp
    Copy link
    Contributor

    New changeset 0e6c8ee by Benjamin Peterson (Jamie Davis) in branch 'master':
    bpo-32981: Fix catastrophic backtracking vulns (bpo-5955)
    0e6c8ee

    @benjaminp
    Copy link
    Contributor

    New changeset 0902a2d by Benjamin Peterson (Miss Islington (bot)) in branch '3.7':
    bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
    0902a2d

    @benjaminp
    Copy link
    Contributor

    New changeset e052d40 by Benjamin Peterson in branch '2.7':
    [2.7] bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
    e052d40

    @benjaminp
    Copy link
    Contributor

    New changeset c951675 by Benjamin Peterson in branch '3.6':
    [3.6] bpo-32981: Fix catastrophic backtracking vulns (GH-5955)
    c951675

    @ned-deily ned-deily added 3.7 (EOL) end of life 3.8 only security fixes labels Mar 8, 2018
    @ned-deily ned-deily changed the title Catastrophic backtracking in poplib and difflib Catastrophic backtracking in poplib (CVE-2018-1060) and difflib (CVE-2018-1061) Mar 8, 2018
    @larryhastings
    Copy link
    Contributor

    New changeset 942cc04 by larryhastings (Ned Deily) in branch '3.4':
    [3.4] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) (bpo-6035)
    942cc04

    @larryhastings
    Copy link
    Contributor

    New changeset 937ac1f by larryhastings (Ned Deily) in branch '3.5':
    [3.5] bpo-32981: Fix catastrophic backtracking vulns (GH-5955) (bpo-6034)
    937ac1f

    @larryhastings
    Copy link
    Contributor

    Is this ready to close?

    @ned-deily
    Copy link
    Member

    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!

    @vstinner
    Copy link
    Member

    vstinner commented May 3, 2018

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

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    3.7 (EOL) end of life 3.8 only security fixes stdlib Python modules in the Lib dir type-security A security issue
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    4 participants
    @vstinner @benjaminp @ned-deily @larryhastings