An issue was discovered in Python before 3.11.1. An unnecessary quadratic algorithm exists in one path when processing some inputs to the IDNA (RFC 3490) decoder, such that a crafted, unreasonably long name being presented to the decoder could lead to a CPU denial of service. Hostnames are often supplied by remote servers that could be controlled by a malicious actor; in such a scenario, they could trigger excessive CPU consumption on the client attempting to make use of an attacker-supplied supposed hostname. For example, the attack payload could be placed in the Location header of an HTTP response with status code 302. A fix is planned in 3.11.1, 3.10.9, 3.9.16, 3.8.16, and 3.7.16.
# Bug report

Originally reported to the security address on September 9.

```python
('xn--016c'+'a'*5000).encode('utf-8').decode('idna')
```

The execution time is not linear in relation to the input string size, which can cause slowness with large inputs:

10 chars = 0.016 seconds
100 chars = 0.047 seconds
1000 chars = 2.883 seconds
2500 chars = 17.724 seconds
5000 chars = 1 min 10 seconds

Comment by @tiran:

> According to spec https://unicode.org/reports/tr46/ an IDNA label must not be longer than 63 characters. Python's idna module enforces the restriction, but too late.

This may be abused in some cases, for example by passing a crafted host name to `asyncio create_connection`:

```python
import asyncio

async def main():
    loop = asyncio.get_running_loop()

    await loop.create_connection(
        lambda: [], ('xn--016c'+'a'*5000).encode('utf-8'), 443
    )

asyncio.run(main())
```

# Your environment

- CPython versions tested on: CPython repository 'main' branch checkout, version 3.8.12, version 2.7.18
- Operating system and architecture: Ubuntu Linux x64

<!-- gh-pr-number: gh-99092 -->
* PR: gh-99092
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99222 -->
* PR: gh-99222
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99229 -->
* PR: gh-99229
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99230 -->
* PR: gh-99230
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99231 -->
* PR: gh-99231
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99232 -->
* PR: gh-99232
<!-- /gh-pr-number -->

Slow IDNA decoding with large strings [CVE-2022-45061]
This is a GitHub Issue
repo:cpython
owner:python
Title : Slow IDNA decoding with large strings [CVE-2022-45061]
Issue date:

--- start body ---
# Bug report

Originally reported to the security address on September 9.

```python
('xn--016c'+'a'*5000).encode('utf-8').decode('idna')
```

The execution time is not linear in relation to the input string size, which can cause slowness with large inputs:

10 chars = 0.016 seconds
100 chars = 0.047 seconds
1000 chars = 2.883 seconds
2500 chars = 17.724 seconds
5000 chars = 1 min 10 seconds

Comment by @tiran:

> According to spec https://unicode.org/reports/tr46/ an IDNA label must not be longer than 63 characters. Python's idna module enforces the restriction, but too late.

This may be abused in some cases, for example by passing a crafted host name to `asyncio create_connection`:

```python
import asyncio

async def main():
    loop = asyncio.get_running_loop()

    await loop.create_connection(
        lambda: [], ('xn--016c'+'a'*5000).encode('utf-8'), 443
    )

asyncio.run(main())
```

# Your environment

- CPython versions tested on: CPython repository 'main' branch checkout, version 3.8.12, version 2.7.18
- Operating system and architecture: Ubuntu Linux x64

<!-- gh-pr-number: gh-99092 -->
* PR: gh-99092
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99222 -->
* PR: gh-99222
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99229 -->
* PR: gh-99229
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99230 -->
* PR: gh-99230
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99231 -->
* PR: gh-99231
<!-- /gh-pr-number -->


<!-- gh-pr-number: gh-99232 -->
* PR: gh-99232
<!-- /gh-pr-number -->

--- end body ---

A potential Denial of Service (DoS) vulnerability exists in the IDNA decoding process of Python's idna module, where the execution time is not linear with respect to input size. This can lead to significant delays when processing large strings, allowing for abuse in scenarios such as passing crafted host names to asyncio's create_connection method.