CVE-2020-7212 (Python, published 2020-03-06T20:15Z)
Description: 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).
Severity: HIGH (CVSS v3 base score: 7.5)
Weakness: CWE-400 \u2014 Uncontrolled Resource Consumption
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.
Repository: https://github.com/urllib3/urllib3
Files changed:
CHANGES.rst
src/urllib3/util/url.py
test/test_util.py
Commit message: Percent-encode invalid characters with request target (#1586)




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')),