gh-98433: Fix quadratic time idna decoding. by gpshead · Pull Request #99092 · python/cpython · GitHub

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear and adds an upfront length check to avoid even bothering the decoding attempt when clearly unreasonable.

test-with-buildbots
(to be done on the backport PR chain) get release manager decision on the shape of the backports.

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

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. An early length check would still be a good idea given that DNS IDNA label names cannot be more than 63 ASCII characters.

The code looks weird (already did before the change):

    RandAL = [stringprep.in_table_d1(x) for x in label]
    any_in_table_d2 = any(stringprep.in_table_d2(x) for x in label)
    for c in RandAL:
        if c:
            if any_in_table_d2:
                raise UnicodeError("Violation of BIDI requirement 2")
            if not RandAL[0] or not RandAL[-1]:
                raise UnicodeError("Violation of BIDI requirement 3")

Doesn't make sense to run the same two inner checks multiple times (note they don't use c). Either they raise the first time or they never do.

Is there a good reason it's not as follows? (Replaced the for+if with if any, unindented, and moved the D2 check back down where it was before the change).

    RandAL = [stringprep.in_table_d1(x) for x in label]
    if any(RandAL):
        if any(stringprep.in_table_d2(x) for x in label):
            raise UnicodeError("Violation of BIDI requirement 2")
        if not RandAL[0] or not RandAL[-1]:
            raise UnicodeError("Violation of BIDI requirement 3")

I think it's only because the code was written in 2003 and any didn't exist yet (introduced in 2006).

The code looks weird (already did before the change)

+10

I think it's only because the code was written in 2003 and any didn't exist yet (introduced in 2006).

Ahha, that explains so much. Thanks @pochmann! I was aiming for minimal diff once I profiled to find the hot spot, but this code is pretty gross. I'll go with your suggested version. Much cleaner.

random observation: If someone wanted a truly minimal patch, putting a break at the end of the for c in RandAL: ... if c: ... block would also work. I went with the modern easier to understand suggestion from Stefan.

I'm okay with leaving this length limit out either entirely - or just out of the backports if release managers are uncomfortable with this in a bugfix.

I view it as protection from other as yet unknown future idna or punycode decoder logic bugs to avoid wasting cpu time. The only reference numbers related to my arbitrary input length limit choice are: A DNS hostname is 255 bytes at most. A label within a DNS name is 63 bytes at most.

The "Nothing" characters in question that are removed in nameprep() in https://github.com/python/cpython/blob/main/Lib/encodings/idna.py#L18 are non-ascii unicode oddities.

Other IDNA decoding libraries in the wild like the well known ICU library do not limit the length at this level of API, instead leaving that to higher levels in the application:

cc'ing release managers @pablogsal and @ambv for feedback on the shape of this to backport. See the code review comment i left on the news entry.

Q: backport (a) just the unnecessarily quadratic algorithm removal OR (b) also the added up front length check.

I think either would be fine. The conservative backport choice would be (a). I'm happy to do either.

🤖 New build scheduled with the buildbot fleet by @gpshead for commit bd51456 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

thanks victor!

LGTM.

Merging. I'll trigger the other backports from the 3.11 backport PR and let RMs chime in there.

Thanks @gpshead for the PR 🌮🎉.. I'm working now to backport this PR to: 3.11.
🐍🍒⛏🤖

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. This also adds an early length check in IDNA decoding to outright reject huge inputs early on given the ultimate result is defined to be 63 or fewer characters. (cherry picked from commit d315722) Co-authored-by: Gregory P. Smith <greg@krypto.org>

GH-99222 is a backport of this pull request to the 3.11 branch.

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Hi! The buildbot s390x Fedora Clang Installed 3.x has failed when building commit d315722.

What do you need to do:

Don't panic.
Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
Go to the page of the buildbot that failed (https://buildbot.python.org/all/#builders/531/builds/2842) and take a look at the build logs.
Check if the failure is related to this commit (d315722) or if it is a false positive.
If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.

You can take a look at the buildbot page here:

https://buildbot.python.org/all/#builders/531/builds/2842

Summary of the results of the build (if available):

Click to see traceback logs

fatal: unable to access 'https://github.com/python/cpython.git/': The requested URL returned error: 503

chmod: cannot access 'target/': No such file or directory

make: *** No rule to make target 'distclean'.  Stop.

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit d315722) Co-authored-by: Gregory P. Smith <greg@krypto.org>

) (pythonGH-99222) There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit d315722) (cherry picked from commit a6f6c3a) Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> Co-authored-by: Gregory P. Smith <greg@krypto.org>

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit a6f6c3a) Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> Co-authored-by: Gregory P. Smith <greg@krypto.org>

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit d315722) (cherry picked from commit a6f6c3a) Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> Co-authored-by: Gregory P. Smith <greg@krypto.org>

The buildbot failed with: fatal: unable to access 'https://github.com/python/cpython.git/': The requested URL returned error: 503
https://www.githubstatus.com/ confirms “intermittent availability issues on some GitHub services”. Later builds are green.

The buildbot failed with: fatal: unable to access 'https://github.com/python/cpython.git/': The requested URL returned error: 503

Network issues should not mark a whole build as failure. I made buildbot change to mark next builds as "warning" rather than "failed" in this case: python/buildmaster-config#348

… (GH-99231) There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit d315722) (cherry picked from commit a6f6c3a) Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> Co-authored-by: Gregory P. Smith <greg@krypto.org>

… (#99230) There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. (cherry picked from commit d315722) (cherry picked from commit a6f6c3a) Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com> Co-authored-by: Gregory P. Smith <greg@krypto.org>

Add a *limit* argument to nameprep to allow ToASCII and ToUnicode to reject extremely large input early. This replaces the check in python#99092, while allowing any number of harmless "characters mapped to nothing" (RFC 3454 §3.1). The default stays unlimited, to not change behaviour for users that call nameprep manually (and don't necessarily follow up with punycode).

Add a *limit* argument to nameprep to allow ToASCII and ToUnicode to reject extremely large input early. This replaces the check in #99092, while allowing any number of harmless "characters mapped to nothing" (RFC 3454 §3.1). The default stays unlimited, to not change behaviour for users that call nameprep manually (and don't necessarily follow up with punycode). Co-authored-by: Stan Ulbrych <stan@python.org>

gpshead added 2 commits November 4, 2022 09:29

pythongh-98433 : Fix quadratic time idna decoding.

365a6cb

There was an unnecessary quadratic loop in idna decoding. This restores the behavior to linear. An early length check would still be a good idea given that DNS IDNA label names cannot be more than 63 ASCII characters.

drop the timing test, add an upfront limit.

4bf248b

gpshead added type-bug An unexpected behavior, bug, or error type-security A security issue needs backport to 3.7 needs backport to 3.11 only security fixes labels Nov 4, 2022

bedevere-bot mentioned this pull request Nov 4, 2022

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

Closed

bedevere-bot added the awaiting core review label Nov 4, 2022

gpshead requested a review from vstinner November 4, 2022 10:17

gpshead commented Nov 4, 2022

View reviewed changes

Comment thread Lib/encodings/idna.py Outdated

gpshead marked this pull request as ready for review November 4, 2022 10:33

gpshead added 2 commits November 4, 2022 10:56

Expand the label limit comments.

db498cb

Also add a short "too long" test assert.

be30a48

Refactor into nicer code. Expand the NEWS entry.

038bbcd

gpshead added 2 commits November 4, 2022 19:54

news wording tweak.

cf3a20e

more RFC links and explanation.

bd51456

gpshead commented Nov 4, 2022

View reviewed changes

gpshead requested review from ambv and pablogsal November 4, 2022 20:29

gpshead added release-blocker 🔨 test-with-buildbots Test PR w/ buildbots; report in status section labels Nov 4, 2022

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Nov 4, 2022

bedevere-bot added awaiting merge and removed awaiting core review labels Nov 7, 2022

assertRaisesRegex

5a3b037

thanks victor!

vstinner approved these changes Nov 7, 2022

View reviewed changes

gpshead removed needs backport to 3.7 labels Nov 8, 2022

gpshead merged commit d315722 into python:main Nov 8, 2022

bedevere-bot removed the awaiting merge label Nov 8, 2022

bedevere-bot removed the needs backport to 3.11 only security fixes label Nov 8, 2022

gpshead deleted the security/idna_dos_mitigation branch November 8, 2022 01:21

encukou mentioned this pull request Sep 17, 2026

gh-157675: Add *limit* argument to encodings.idna.nameprep #157682

Merged

+              such as :mod:`urllib` http ``3xx`` redirects potentially allow for an attacker
+              to supply such a name.
+              Individual labels within an IDNA encoded DNS name will now raise an error early

gh-98433: Fix quadratic time idna decoding. by gpshead · Pull Request #99092 · python/cpython · GitHub

Repository navigation

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

gh-98433: Fix quadratic time idna decoding.#99092gpshead merged 8 commits intopython:mainpython/cpython:mainfrom gpshead:security/idna_dos_mitigationgpshead/cpython:security/idna_dos_mitigationCopy head branch name to clipboard

Conversation

gpshead commented Nov 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

pochmann commented Nov 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gpshead commented Nov 4, 2022

Uh oh!

gpshead commented Nov 4, 2022

Uh oh!

gpshead Nov 4, 2022

Choose a reason for hiding this comment

Uh oh!

gpshead commented Nov 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bedevere-bot commented Nov 4, 2022

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

gpshead commented Nov 8, 2022

Uh oh!

miss-islington commented Nov 8, 2022

Uh oh!

bedevere-bot commented Nov 8, 2022

Uh oh!

bedevere-bot commented Nov 8, 2022

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Uh oh!

encukou commented Nov 8, 2022

Uh oh!

vstinner commented Nov 8, 2022

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

gh-98433: Fix quadratic time idna decoding.#99092
gpshead merged 8 commits into
python:mainfrom
gpshead:security/idna_dos_mitigation

gpshead commented Nov 4, 2022 •
edited
Loading

pochmann commented Nov 4, 2022 •
edited
Loading

gpshead commented Nov 4, 2022 •
edited
Loading