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