Exponential IDNA codec decoding potential denial of service

[gpshead]

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

This takes over 1 minute to run.

Tested on the latest cpython repo checkout and on Ubuntu's python3 on a relatively modern Linux pc.

Clear exponential complexity:

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

-- As reported by @guidovranken via our Python security response team mailing list on 2022-09-09.

---

I can reproduce the issue. This should be an easy fix. 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.
-- @tiran

---

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.

It doesn't currently feel urgent enough to treat specially. If filing a public issue about this attracts other attention to identify specific reasons why this is a security DoS issue and should be more of a priority, expect more people to become interested in actually working on a proper fix.

It might be interesting to add the idna codec to oss-fuzz tests in Modules/_xxtestfuzz?

-- @gpshead

@vstinner asked that I go ahead and file a public issue for this as nobody else had replied or done so yet. Done! 😁

[pochmann]

Clear exponential complexity:

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

That doesn't look exponential. Only quadratic.

And it's the same as #98433 (comment), no?

[gpshead]

oh, it had been filed. yay, i missed that. closing as a duplicate of #98433