[CVE-2022-45061] Fix quadratic time idna decoding.tizen_9.0_m2_releasetizen_8.0_m2_releasesubmit/tizen_base/20230329.061525accepted/tizen/base/tool/20230330.065249accepted/tizen/base/20230714.003458accepted/tizen/9.0/base/20241030.075436accepted/tizen/8.0/base/20231005.045056tizen_basetizen_9.0_basetizen_8.0_baseaccepted/tizen_base_toolaccepted/tizen_baseaccepted/tizen_9.0_baseaccepted/tizen_8.0_base

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

There was an unnecessary quadratic loop in idna decoding. This restores
the behavior to linear.

(cherry picked from commit d315722564927c7202dd6e111dc79eaf14240b0d)

(cherry picked from commit a6f6c3a3d6f2b580f2d87885c9b8a9350ad7bf15)

Change-Id: I44e6d661eaaf144e742c1d30712d60785a4fee0c
Co-authored-by: Miss Islington (bot) <31488909+miss-islington@users.noreply.github.com>
Co-authored-by: Gregory P. Smith <greg@krypto.org>
Signed-off-by: JinWang An <jinwang.an@samsung.com>

3 files changed, 27 insertions, 17 deletions

diff --git a/Lib/encodings/idna.py b/Lib/encodings/idna.py
index ea90d67..2ce798c 100644
--- a/Lib/encodings/idna.py
+++ b/Lib/encodings/idna.py
@@ -39,23 +39,21 @@ def nameprep(label):
 
     # Check bidi
     RandAL = map(stringprep.in_table_d1, label)
-    for c in RandAL:
-        if c:
-            # There is a RandAL char in the string. Must perform further
-            # tests:
-            # 1) The characters in section 5.8 MUST be prohibited.
-            # This is table C.8, which was already checked
-            # 2) If a string contains any RandALCat character, the string
-            # MUST NOT contain any LCat character.
-            if filter(stringprep.in_table_d2, label):
-                raise UnicodeError("Violation of BIDI requirement 2")
-
-            # 3) If a string contains any RandALCat character, a
-            # RandALCat character MUST be the first character of the
-            # string, and a RandALCat character MUST be the last
-            # character of the string.
-            if not RandAL[0] or not RandAL[-1]:
-                raise UnicodeError("Violation of BIDI requirement 3")
+    if any(RandAL):
+        # There is a RandAL char in the string. Must perform further
+        # tests:
+        # 1) The characters in section 5.8 MUST be prohibited.
+        # This is table C.8, which was already checked
+        # 2) If a string contains any RandALCat character, the string
+        # MUST NOT contain any LCat character.
+        if any(stringprep.in_table_d2(x) for x in label):
+            raise UnicodeError("Violation of BIDI requirement 2")
+        # 3) If a string contains any RandALCat character, a
+        # RandALCat character MUST be the first character of the
+        # string, and a RandALCat character MUST be the last
+        # character of the string.
+        if not RandAL[0] or not RandAL[-1]:
+            raise UnicodeError("Violation of BIDI requirement 3")
 
     return label
 
diff --git a/Lib/test/test_codecs.py b/Lib/test/test_codecs.py
index 0ec8bf5..76428e1 100644
--- a/Lib/test/test_codecs.py
+++ b/Lib/test/test_codecs.py
@@ -1318,6 +1318,12 @@ class IDNACodecTest(unittest.TestCase):
         self.assertEqual(u"pyth\xf6n.org".encode("idna"), "xn--pythn-mua.org")
         self.assertEqual(u"pyth\xf6n.org.".encode("idna"), "xn--pythn-mua.org.")
 
+    def test_builtin_decode_length_limit(self):
+        with self.assertRaisesRegexp(UnicodeError, "too long"):
+            (b"xn--016c"+b"a"*1100).decode("idna")
+        with self.assertRaisesRegexp(UnicodeError, "too long"):
+            (b"xn--016c"+b"a"*70).decode("idna")
+
     def test_stream(self):
         import StringIO
         r = codecs.getreader("idna")(StringIO.StringIO("abc"))
diff --git a/Misc/NEWS.d/next/Security/2022-11-04-09-29-36.gh-issue-98433.l76c5G.rst b/Misc/NEWS.d/next/Security/2022-11-04-09-29-36.gh-issue-98433.l76c5G.rst
new file mode 100644
index 0000000..5185fac
--- /dev/null
+++ b/Misc/NEWS.d/next/Security/2022-11-04-09-29-36.gh-issue-98433.l76c5G.rst
@@ -0,0 +1,6 @@
+The IDNA codec decoder used on DNS hostnames by :mod:`socket` or :mod:`asyncio`
+related name resolution functions no longer involves a quadratic algorithm.
+This prevents a potential CPU denial of service if an out-of-spec excessive
+length hostname involving bidirectional characters were decoded. Some protocols
+such as :mod:`urllib` http ``3xx`` redirects potentially allow for an attacker
+to supply such a name.