CVE-2020-7212: Uncontrolled Resource Consumption (CWE-400)
value: The _encode_invalid_chars function in util/url.py in the urllib3 library 1.25.2 through 1.25.7 for Python allows a denial of service (CPU consumption) because of an inefficient algorithm. The percent_encodings array contains all matches of percent encodings. It is not deduplicated. For a URL of length N, the size of percent_encodings may be up to O(N). The next step (normalize existing percent-encoded bytes) also takes up to O(N) for each step, so the total time is O(N^2). If percent_encodings were deduplicated, the time to compute _encode_invalid_chars would be O(kN), where k is at most 484 ((10+6*2)^2).
CWE description: The product does not properly control the allocation and maintenance of a limited resource, thereby enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
CVSS v3 base score: 7.5
Published: 2020-03-06T20:15Z
Repository: https://github.com/urllib3/urllib3
Language: Python
Files changed: CHANGES.rst, src/urllib3/util/url.py, test/test_util.py
Commit date: 2019-04-28 14:19:42 -0500
Commit message: Percent-encode invalid characters with request target (#1586)



Diff: diff --git a/CHANGES.rst b/CHANGES.rst
index 54c669e6..cf228533 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -4,10 +4,13 @@ Changes
 dev (master)
 ------------
 
 * Change ``is_ipaddress`` to not detect IPvFuture addresses. (Pull #1583)
 
+* Change ``parse_url`` to percent-encode invalid characters within the
+  path, query, and target components. (Pull #1586)
+
 
 1.25.1 (2019-04-24)
 -------------------
 
 * Add support for Google's ``Brotli`` package. (Pull #1572, Pull #1579)
diff --git a/src/urllib3/util/url.py b/src/urllib3/util/url.py
index de3c4686..0bc6ced7 100644
--- a/src/urllib3/util/url.py
+++ b/src/urllib3/util/url.py
@@ -4,10 +4,11 @@ from collections import namedtuple
 
 from ..exceptions import LocationParseError
 from ..packages import six, rfc3986
 from ..packages.rfc3986.exceptions import RFC3986Exception, ValidationError
 from ..packages.rfc3986.validators import Validator
+from ..packages.rfc3986 import abnf_regexp, normalizers, compat, misc
 
 
 url_attrs = ['scheme', 'auth', 'host', 'port', 'path', 'query', 'fragment']
 
 # We only want to normalize urls with an HTTP(S) scheme.
@@ -15,10 +16,13 @@ url_attrs = ['scheme', 'auth', 'host', 'port', 'path', 'query', 'fragment']
 NORMALIZABLE_SCHEMES = ('http', 'https', None)
 
 # Regex for detecting URLs with schemes. RFC 3986 Section 3.1
 SCHEME_REGEX = re.compile(r"^(?:[a-zA-Z][a-zA-Z0-9+\-]*:|/)")
 
+PATH_CHARS = abnf_regexp.UNRESERVED_CHARS_SET | abnf_regexp.SUB_DELIMITERS_SET | {':', '@', '/'}
+QUERY_CHARS = FRAGMENT_CHARS = PATH_CHARS | {'?'}
+
 
 class Url(namedtuple('Url', url_attrs)):
     """
     Data structure for representing an HTTP URL. Used as a return value for
     :func:`parse_url`. Both the scheme and host are normalized as they are
@@ -134,10 +138,41 @@ def split_first(s, delims):
         return s, '', None
 
     return s[:min_idx], s[min_idx + 1:], min_delim
 
 
+def _encode_invalid_chars(component, allowed_chars, encoding='utf-8'):
+    """Percent-encodes a URI component without reapplying
+    onto an already percent-encoded component. Based on
+    rfc3986.normalizers.encode_component()
+    """
+    if component is None:
+        return component
+
+    # Try to see if the component we're encoding is already percent-encoded
+    # so we can skip all '%' characters but still encode all others.
+    percent_encodings = len(normalizers.PERCENT_MATCHER.findall(
+                            compat.to_str(component, encoding)))
+
+    uri_bytes = component.encode('utf-8', 'surrogatepass')
+    is_percent_encoded = percent_encodings == uri_bytes.count(b'%')
+
+    encoded_component = bytearray()
+
+    for i in range(0, len(uri_bytes)):
+        # Will return a single character bytestring on both Python 2 & 3
+        byte = uri_bytes[i:i+1]
+        byte_ord = ord(byte)
+        if ((is_percent_encoded and byte == b'%')
+                or (byte_ord < 128 and byte.decode() in allowed_chars)):
+            encoded_component.extend(byte)
+            continue
+        encoded_component.extend('%{0:02x}'.format(byte_ord).encode().upper())
+
+    return encoded_component.decode(encoding)
+
+
 def parse_url(url):
     """
     Given a url, return a parsed :class:`.Url` namedtuple. Best-effort is
     performed to parse incomplete urls. Fields not provided will be None.
     This parser is RFC 3986 compliant.
@@ -158,26 +193,19 @@ def parse_url(url):
     if not url:
         # Empty
         return Url()
 
     is_string = not isinstance(url, six.binary_type)
-    if not is_string:
-        url = url.decode("utf-8")
 
     # RFC 3986 doesn't like URLs that have a host but don't start
     # with a scheme and we support URLs like that so we need to
     # detect that problem and add an empty scheme indication.
     # We don't get hurt on path-only URLs here as it's stripped
     # off and given an empty scheme anyways.
     if not SCHEME_REGEX.search(url):
         url = "//" + url
 
-    try:
-        iri_ref = rfc3986.IRIReference.from_string(url, encoding="utf-8")
-    except (ValueError, RFC3986Exception):
-        six.raise_from(LocationParseError(url), None)
-
     def idna_encode(name):
         if name and any([ord(x) > 128 for x in name]):
             try:
                 import idna
             except ImportError:
@@ -186,12 +214,22 @@ def parse_url(url):
                 return idna.encode(name.lower(), strict=True, std3_rules=True)
             except idna.IDNAError:
                 raise LocationParseError(u"Name '%s' is not a valid IDNA label" % name)
         return name
 
-    has_authority = iri_ref.authority is not None
-    uri_ref = iri_ref.encode(idna_encoder=idna_encode)
+    try:
+        split_iri = misc.IRI_MATCHER.match(compat.to_str(url)).groupdict()
+        iri_ref = rfc3986.IRIReference(
+            split_iri['scheme'], split_iri['authority'],
+            _encode_invalid_chars(split_iri['path'], PATH_CHARS),
+            _encode_invalid_chars(split_iri['query'], QUERY_CHARS),
+            _encode_invalid_chars(split_iri['fragment'], FRAGMENT_CHARS)
+        )
+        has_authority = iri_ref.authority is not None
+        uri_ref = iri_ref.encode(idna_encoder=idna_encode)
+    except (ValueError, RFC3986Exception):
+        return six.raise_from(LocationParseError(url), None)
 
     # rfc3986 strips the authority if it's invalid
     if has_authority and uri_ref.authority is None:
         raise LocationParseError(url)
 
@@ -207,11 +245,11 @@ def parse_url(url):
     try:
         validator.check_validity_of(
             *validator.COMPONENT_NAMES
         ).validate(uri_ref)
     except ValidationError:
-        six.raise_from(LocationParseError(url), None)
+        return six.raise_from(LocationParseError(url), None)
 
     # For the sake of backwards compatibility we put empty
     # string values for path if there are any defined values
     # beyond the path in the URL.
     # TODO: Remove this when we break backwards compatibility.
diff --git a/test/test_util.py b/test/test_util.py
index c86170cf..cc237b0e 100644
--- a/test/test_util.py
+++ b/test/test_util.py
@@ -133,12 +133,19 @@ class TestUtil(object):
 
     @pytest.mark.parametrize('url', [
         'http://user\\@google.com',
         'http://google\\.com',
         'user\\@google.com',
-        'http://google.com#fragment#',
         'http://user@user@google.com/',
+
+        # Invalid IDNA labels
+        u'http://\uD7FF.com',
+        u'http://❤️',
+
+        # Unicode surrogates
+        u'http://\uD800.com',
+        u'http://\uDC00.com',
     ])
     def test_invalid_url(self, url):
         with pytest.raises(LocationParseError):
             parse_url(url)
 
@@ -147,10 +154,19 @@ class TestUtil(object):
         ('HTTP://JeremyCline:Hunter2@Example.com:8080/',
          'http://JeremyCline:Hunter2@example.com:8080/'),
         ('HTTPS://Example.Com/?Key=Value', 'https://example.com/?Key=Value'),
         ('Https://Example.Com/#Fragment', 'https://example.com/#Fragment'),
         ('[::Ff%etH0%Ff]/%ab%Af', '[::ff%25etH0%Ff]/%AB%AF'),
+
+        # Invalid characters for the query/fragment getting encoded
+        ('http://google.com/p[]?parameter[]=\"hello\"#fragment#',
+         'http://google.com/p%5B%5D?parameter%5B%5D=%22hello%22#fragment%23'),
+
+        # Percent encoding isn't applied twice despite '%' being invalid
+        # but the percent encoding is still normalized.
+        ('http://google.com/p%5B%5d?parameter%5b%5D=%22hello%22#fragment%23',
+         'http://google.com/p%5B%5D?parameter%5B%5D=%22hello%22#fragment%23')
     ])
     def test_parse_url_normalization(self, url, expected_normalized_url):
         """Assert parse_url normalizes the scheme/host, and only the scheme/host"""
         actual_normalized_url = parse_url(url).url
         assert actual_normalized_url == expected_normalized_url
@@ -212,11 +228,18 @@ class TestUtil(object):
         ('http://google.com:', Url('http', host='google.com')),
         ('http://google.com:/', Url('http', host='google.com', path='/')),
 
         # Uppercase IRI
         (u'http://Königsgäßchen.de/straße',
-         Url('http', host='xn--knigsgchen-b4a3dun.de', path='/stra%C3%9Fe'))
+         Url('http', host='xn--knigsgchen-b4a3dun.de', path='/stra%C3%9Fe')),
+
+        # Unicode Surrogates
+        (u'http://google.com/\uD800', Url('http', host='google.com', path='%ED%A0%80')),
+        (u'http://google.com?q=\uDC00',
+         Url('http', host='google.com', path='', query='q=%ED%B0%80')),
+        (u'http://google.com#\uDC00',
+         Url('http', host='google.com', path='', fragment='%ED%B0%80')),
     ]
 
     @pytest.mark.parametrize(
         'url, expected_url',
         chain(parse_url_host_map, non_round_tripping_parse_url_host_map)

Vulnerable code:     if not is_string:
        url = url.decode("utf-8")
    try:
        iri_ref = rfc3986.IRIReference.from_string(url, encoding="utf-8")
    except (ValueError, RFC3986Exception):
        six.raise_from(LocationParseError(url), None)

    has_authority = iri_ref.authority is not None
    uri_ref = iri_ref.encode(idna_encoder=idna_encode)
        six.raise_from(LocationParseError(url), None)
        'http://google.com#fragment#',
         Url('http', host='xn--knigsgchen-b4a3dun.de', path='/stra%C3%9Fe'))
Fixed code: * Change ``parse_url`` to percent-encode invalid characters within the
  path, query, and target components. (Pull #1586)

from ..packages.rfc3986 import abnf_regexp, normalizers, compat, misc
PATH_CHARS = abnf_regexp.UNRESERVED_CHARS_SET | abnf_regexp.SUB_DELIMITERS_SET | {':', '@', '/'}
QUERY_CHARS = FRAGMENT_CHARS = PATH_CHARS | {'?'}

def _encode_invalid_chars(component, allowed_chars, encoding='utf-8'):
    """Percent-encodes a URI component without reapplying
    onto an already percent-encoded component. Based on
    rfc3986.normalizers.encode_component()
    """
    if component is None:
        return component

    # Try to see if the component we're encoding is already percent-encoded
    # so we can skip all '%' characters but still encode all others.
    percent_encodings = len(normalizers.PERCENT_MATCHER.findall(
                            compat.to_str(component, encoding)))

    uri_bytes = component.encode('utf-8', 'surrogatepass')
    is_percent_encoded = percent_encodings == uri_bytes.count(b'%')

    encoded_component = bytearray()

    for i in range(0, len(uri_bytes)):
        # Will return a single character bytestring on both Python 2 & 3
        byte = uri_bytes[i:i+1]
        byte_ord = ord(byte)
        if ((is_percent_encoded and byte == b'%')
                or (byte_ord < 128 and byte.decode() in allowed_chars)):
            encoded_component.extend(byte)
            continue
        encoded_component.extend('%{0:02x}'.format(byte_ord).encode().upper())

    return encoded_component.decode(encoding)


    try:
        split_iri = misc.IRI_MATCHER.match(compat.to_str(url)).groupdict()
        iri_ref = rfc3986.IRIReference(
            split_iri['scheme'], split_iri['authority'],
            _encode_invalid_chars(split_iri['path'], PATH_CHARS),
            _encode_invalid_chars(split_iri['query'], QUERY_CHARS),
            _encode_invalid_chars(split_iri['fragment'], FRAGMENT_CHARS)
        )
        has_authority = iri_ref.authority is not None
        uri_ref = iri_ref.encode(idna_encoder=idna_encode)
    except (ValueError, RFC3986Exception):
        return six.raise_from(LocationParseError(url), None)
        return six.raise_from(LocationParseError(url), None)

        # Invalid IDNA labels
        u'http://\uD7FF.com',
        u'http://❤️',

        # Unicode surrogates
        u'http://\uD800.com',
        u'http://\uDC00.com',

        # Invalid characters for the query/fragment getting encoded
        ('http://google.com/p[]?parameter[]=\"hello\"#fragment#',
         'http://google.com/p%5B%5D?parameter%5B%5D=%22hello%22#fragment%23'),

        # Percent encoding isn't applied twice despite '%' being invalid
        # but the percent encoding is still normalized.
        ('http://google.com/p%5B%5d?parameter%5b%5D=%22hello%22#fragment%23',
         'http://google.com/p%5B%5D?parameter%5B%5D=%22hello%22#fragment%23')
         Url('http', host='xn--knigsgchen-b4a3dun.de', path='/stra%C3%9Fe')),

        # Unicode Surrogates
        (u'http://google.com/\uD800', Url('http', host='google.com', path='%ED%A0%80')),
        (u'http://google.com?q=\uDC00',
         Url('http', host='google.com', path='', query='q=%ED%B0%80')),
        (u'http://google.com#\uDC00',
         Url('http', host='google.com', path='', fragment='%ED%B0%80')),