Slow IDNA decoding with large strings [CVE-2022-45061]

@tiran

Bug report

Originally reported to the security address on September 9.

('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:

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

PR: gh-98433: Fix quadratic time idna decoding. #99092

PR: [3.11] gh-98433: Fix quadratic time idna decoding. (GH-99092) #99222

PR: [3.10] gh-98433: Fix quadratic time idna decoding. (GH-99092) (GH-99222) #99229

PR: [3.9] gh-98433: Fix quadratic time idna decoding. (GH-99092) (GH-99222) #99230

PR: [3.8] gh-98433: Fix quadratic time idna decoding. (GH-99092) (GH-99222) #99231

PR: [3.7] gh-98433: Fix quadratic time idna decoding. (GH-99092) (GH-99222) #99232

This is probably in ToUnicode and ToASCII of https://github.com/python/cpython/blob/main/Lib/encodings/idna.py and/or in https://github.com/python/cpython/blob/main/Lib/encodings/punycode.py itself, where we could presumably just do an up front length check and reject inputs that are obviously too long to possibly decode into a label length that DNS standards will accept.

If there are libraries that allow an attacker controlled hostname without a reasonable length check on it to get into a connect or similar call that tries idna decoding, that'd make this remotely exploitable. Based solely on code inspection, the urllib.request.HTTPRedirectHandler class is probably vulnerable to this - https://github.com/python/cpython/blob/main/Lib/urllib/request.py#L652 - the location or uri headers it consumes on a HTTP 302 redirect reponse to construct the new URL are not obviously limited, nor is the host that ultimately winds it way down into the socket module. (I didn't test this, I was just reading code) A test case would be to point urllib at a malicious server that sends a 2000 byte idna hostname in a 302 redirect header...

The issue #99083 was marked as a duplicate of this issue.

pythongh-98433: Fix quadratic time idna decoding.

gh-98433: Fix quadratic time idna decoding. (#99092)

pythongh-98433: Fix quadratic time idna decoding. (pythonGH-99092)

[3.11] gh-98433: Fix quadratic time idna decoding. (GH-99092) (#99222)

[3.11] pythongh-98433: Fix quadratic time idna decoding. (pythonGH-99092

00394-cve-2022-45061-cpu-denial-of-service-via-inefficient-idna-decod…

00394: CVE-2022-45061: CPU denial of service via inefficient IDNA dec…

Navigation Menu

Repository navigation

Slow IDNA decoding with large strings [CVE-2022-45061] #98433

Bug report

Your environment

15 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Slow IDNA decoding with large strings [CVE-2022-45061] #98433

Description

Bug report

Your environment

Activity

gpshead commented on Nov 4, 2022

vstinner commented on Nov 4, 2022

15 remaining items

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions