bpo-32981: Fix catastrophic backtracking vulns (#5955)

* Prevent low-grade poplib REDOS (CVE-2018-1060)

The regex to test a mail server's timestamp is susceptible to
catastrophic backtracking on long evil responses from the server.

Happily, the maximum length of malicious inputs is 2K thanks
to a limit introduced in the fix for CVE-2013-1752.

A 2KB evil response from the mail server would result in small slowdowns
(milliseconds vs. microseconds) accumulated over many apop calls.
This is a potential DOS vector via accumulated slowdowns.

Replace it with a similar non-vulnerable regex.

The new regex is RFC compliant.
The old regex was non-compliant in edge cases.

* Prevent difflib REDOS (CVE-2018-1061)

The default regex for IS_LINE_JUNK is susceptible to
catastrophic backtracking.
This is a potential DOS vector.

Replace it with an equivalent non-vulnerable regex.

Also introduce unit and REDOS tests for difflib.

Co-authored-by: Tim Peters <tim.peters@gmail.com>
Co-authored-by: Christian Heimes <christian@python.org>

1 files changed, 21 insertions, 1 deletions

diff --git a/Lib/test/test_difflib.py b/Lib/test/test_difflib.py
index 156b523..aaefe6d 100644
--- a/Lib/test/test_difflib.py
+++ b/Lib/test/test_difflib.py
@@ -466,13 +466,33 @@ class TestBytes(unittest.TestCase):
             list(generator(*args))
         self.assertEqual(msg, str(ctx.exception))
 
+class TestJunkAPIs(unittest.TestCase):
+    def test_is_line_junk_true(self):
+        for line in ['#', '  ', ' #', '# ', ' # ', '']:
+            self.assertTrue(difflib.IS_LINE_JUNK(line), repr(line))
+
+    def test_is_line_junk_false(self):
+        for line in ['##', ' ##', '## ', 'abc ', 'abc #', 'Mr. Moose is up!']:
+            self.assertFalse(difflib.IS_LINE_JUNK(line), repr(line))
+
+    def test_is_line_junk_REDOS(self):
+        evil_input = ('\t' * 1000000) + '##'
+        self.assertFalse(difflib.IS_LINE_JUNK(evil_input))
+
+    def test_is_character_junk_true(self):
+        for char in [' ', '\t']:
+            self.assertTrue(difflib.IS_CHARACTER_JUNK(char), repr(char))
+
+    def test_is_character_junk_false(self):
+        for char in ['a', '#', '\n', '\f', '\r', '\v']:
+            self.assertFalse(difflib.IS_CHARACTER_JUNK(char), repr(char))
 
 def test_main():
     difflib.HtmlDiff._default_prefix = 0
     Doctests = doctest.DocTestSuite(difflib)
     run_unittest(
         TestWithAscii, TestAutojunk, TestSFpatches, TestSFbugs,
-        TestOutputFormat, TestBytes, Doctests)
+        TestOutputFormat, TestBytes, TestJunkAPIs, Doctests)
 
 if __name__ == '__main__':
     test_main()