bpo-32981: Fix catastrophic backtracking vulns #5955

davisjam · 2018-03-01T21:50:22Z

Fix catastrophic backtracking vulns disclosed by email.

https://bugs.python.org/issue32981

the-knights-who-say-ni · 2018-03-01T21:50:25Z

Hello, and thanks for your contribution!

I'm a bot set up to make sure that the project can legally accept your contribution by verifying you have signed the PSF contributor agreement (CLA).

Unfortunately we couldn't find an account corresponding to your GitHub username on bugs.python.org (b.p.o) to verify you have signed the CLA (this might be simply due to a missing "GitHub Name" entry in your b.p.o account settings). This is necessary for legal reasons before we can look at your contribution. Please follow the steps outlined in the CPython devguide to rectify this issue.

Thanks again to your contribution and we look forward to looking at it!

davisjam · 2018-03-01T21:56:49Z

I have now signed the CLA.

davisjam · 2018-03-01T21:57:23Z

Because this is a security issue no issue was previously created to track it. Perhaps someone might create one now?

[Update: I created bpo-32981.]

davisjam · 2018-03-01T22:12:40Z

Travis failure:

Fixing Python file whitespace ... 2 files:
  Lib/test/test_difflib.py
  Lib/test/test_poplib.py

Took a look, I can't see what's wrong. Is there a command (or flag to configure) I can run on my end to get a more verbose error message?

gvanrossum · 2018-03-01T23:47:06Z

That error comes from Tools/scripts/patchcheck.py.

davisjam · 2018-03-02T00:13:44Z

Thank you. Fixed.

davisjam · 2018-03-02T00:39:07Z

I created bpo-32981 for this problem.

I skimmed through the git log. Commit messages for security seem to follow the 'XXX (CVE-...)' format rather than the 'bpo-XXX: ...' format. Let me know if I should change the commit messages though.

serhiy-storchaka

Please add a news entry and add your name into Misc/ACKS.

serhiy-storchaka · 2018-03-02T06:02:17Z

Lib/difflib.py

@@ -1083,7 +1083,7 @@ def _qformat(self, aline, bline, atags, btags):

 import re

-def IS_LINE_JUNK(line, pat=re.compile(r"\s*#?\s*$").match):
+def IS_LINE_JUNK(line, pat=re.compile(r"\s*(#\s*)?$").match):


Use non-capturing group: (?:#\s*).

serhiy-storchaka · 2018-03-02T06:06:07Z

Lib/test/test_difflib.py

+    def test_is_line_junk_true(self):
+        for line in ['#', '  ', ' #', '# ', ' # ', '']:
+            is_junk = difflib.IS_LINE_JUNK(line)
+            self.assertEqual(is_junk, True)


Why not assertTrue()?

Fixed this and others, thanks.

serhiy-storchaka · 2018-03-02T06:09:56Z

Lib/test/test_difflib.py

+        elapsed = end - start
+
+        self.assertEqual(is_junk, False)
+        self.assertEqual(elapsed.seconds, 0)


Timing test is very fragile. It can fail randomly when tests are paused for some reasons. I suggest to remove the timing test and increase the size of input so that it would take a hour with non-fixed code.

Then the test will pass if you wait long enough. Since the test suite already takes a long time to run and does so in parallel (so one hanging test might not be visible), this seems undesirable to me. Thoughts?

Same thing in Lib/test/test_poplib.py

If the test takes too long time for running it will be failed on buildbots due to total timeout.

davisjam · 2018-03-02T15:33:39Z

@serhiy-storchaka Thank you! I think I have addressed all of your comments so far.

serhiy-storchaka

Thank you James. Here yet few comments.

serhiy-storchaka · 2018-03-02T16:06:33Z

Misc/NEWS.d/next/Security/2018-03-02-10-24-52.bpo-32981.O_qDyj.rst

@@ -0,0 +1,3 @@
+Regexes in difflib and poplib were vulnerable to catastrophic backtracking.
+These regexes formed potential DOS vectors (REDOS). They have been
+refactored. This resolves CVE-2018-1060 and CVE-2018-1061.


Add "Patch by your name."

serhiy-storchaka · 2018-03-02T16:08:51Z

Lib/test/test_difflib.py

+    def test_is_character_junk_true(self):
+        for char in [' ', '\t']:
+            is_junk = difflib.IS_CHARACTER_JUNK(char)
+            self.assertEqual(is_junk, True)


assertTrue()?

serhiy-storchaka · 2018-03-02T16:11:48Z

Lib/test/test_difflib.py

+    def test_is_line_junk_true(self):
+        for line in ['#', '  ', ' #', '# ', ' # ', '']:
+            is_junk = difflib.IS_LINE_JUNK(line)
+            self.assertTrue(is_junk)


Why not just

self.assertTrue(difflib.IS_LINE_JUNK(line))

?

And you can add the second argument of assertTrue() for getting more information if the test fails:

self.assertTrue(difflib.IS_LINE_JUNK(line), rept(line))

But don't do this in test_is_line_junk_REDOS.

serhiy-storchaka · 2018-03-02T16:16:33Z

Lib/test/test_poplib.py

+        # At this length, evil input makes each apop call take
+        # on the order of milliseconds instead of microseconds.
+        evil_welcome = bytes('+OK' + ('<' * 500000), self.client.encoding)
+        self.client.welcome = evil_welcome


You can use a special helper swap_attr() for temporary setting the attribute:

with test.support.swap_attr(self.client, 'welcome', evil_welcome):

Ah, nice, thanks for the tip.

serhiy-storchaka · 2018-03-02T16:17:17Z

Lib/test/test_poplib.py

+        except poplib.error_proto:
+            threw = True
+        # The evil welcome is invalid, so apop should throw.
+        self.assertTrue(threw)


Why not use assertRaises()?

The reason for the poor choices of asserts is that I didn't know what asserts are available and made do with what I could find. I really appreciate your help.

https://docs.python.org/3/library/unittest.html#test-cases

assertRaises() can be used as a function:

self.assertRaises(poplib.error_proto, self.client.apop, 'foo', 'dummypassword')

or as a context manager:

with self.assertRaises(poplib.error_proto): self.client.apop('foo', 'dummypassword')

Yup I have at last found the documentation for unittest.

serhiy-storchaka · 2018-03-02T16:18:49Z

Lib/test/test_poplib.py

+        # NB The upper bound on welcome length is currently 2048.
+        # At this length, evil input makes each apop call take
+        # on the order of milliseconds instead of microseconds.
+        evil_welcome = bytes('+OK' + ('<' * 500000), self.client.encoding)


What is the advantage over just b'+OK' + b'<' * 500000?

serhiy-storchaka · 2018-03-02T16:19:47Z

Lib/test/test_poplib.py

@@ -10,6 +10,7 @@
 import os
 import errno
 import threading
+import datetime


No longer used.

serhiy-storchaka · 2018-03-02T16:20:00Z

Lib/test/test_difflib.py

@@ -3,6 +3,7 @@
 import unittest
 import doctest
 import sys
+import datetime


No longer used.

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

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>

davisjam · 2018-03-02T17:44:04Z

The latest version uses 1-million character attack strings. These take at least 3 minutes to evaluate on the master branch. I didn't want to wait for the full timeout.

serhiy-storchaka · 2018-03-02T17:53:50Z

Lib/test/test_difflib.py

+
+    def test_is_line_junk_false(self):
+        for line in ['##', ' ##', '## ', 'abc ', 'abc #', 'abc # ', 'Mr. Moose is up!']:
+            self.assertFalse(difflib.IS_LINE_JUNK(line), 'should not be junk: {}'.format(line))


The length of this line exceeds the 79 character limit allowed by PEP 8.

And since testing strings contain spaces it is hard to distinguish the following cases:

should not be junk: abc #

and

should not be junk: abc #

This is why I suggested repr().

The length of this line exceeds the 79 character limit allowed by PEP 8.

Didn't realize this was being enforced, there are other lines over this limit as well. Will do.

This is why I suggested repr().

Got it, I misread that as rept earlier and couldn't understand what you meant.

serhiy-storchaka · 2018-03-02T17:55:15Z

Lib/test/test_poplib.py

+        evil_welcome = b'+OK' + (b'<' * 1000000)
+        with test_support.swap_attr(self.client, 'welcome', evil_welcome):
+            # The evil welcome is invalid, so apop should throw.
+            self.assertRaises(poplib.error_proto, self.client.apop, 'arthur', 'kingofbritons')


Since this line is too long, a context manager form of assertRaises() would be more preferable.

serhiy-storchaka · 2018-03-02T17:57:26Z

And please make your changes as new commits rather of editing old commits. This would make reviewing easier.

davisjam · 2018-03-02T19:41:23Z

@serhiy-storchaka Acknowledged. I believe I've addressed all of the concerns you've raised.

davisjam · 2018-03-02T19:48:45Z

Should I rebase or will these be squashed during merge anyway?

serhiy-storchaka · 2018-03-02T20:03:20Z

Will be squashed during merge.

miss-islington · 2018-03-04T05:33:34Z

Thanks @davisjam for the PR, and @benjaminp for merging it 🌮🎉.. I'm working now to backport this PR to: 2.7, 3.6, 3.7.
🐍🍒⛏🤖

bedevere-bot · 2018-03-04T05:33:34Z

@benjaminp: Please replace # with GH- in the commit message next time. Thanks!

* 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> (cherry picked from commit 0e6c8ee) Co-authored-by: Jamie Davis <davisjam@vt.edu>

bedevere-bot · 2018-03-04T05:33:43Z

GH-5969 is a backport of this pull request to the 3.7 branch.

miss-islington · 2018-03-04T05:34:36Z

Sorry, @davisjam and @benjaminp, I could not cleanly backport this to 3.6 due to a conflict.
Please backport using cherry_picker on command line.
cherry_picker 0e6c8ee2358a2e23117501826c008842acb835ac 3.6

miss-islington · 2018-03-04T05:35:36Z

Sorry, @davisjam and @benjaminp, I could not cleanly backport this to 2.7 due to a conflict.
Please backport using cherry_picker on command line.
cherry_picker 0e6c8ee2358a2e23117501826c008842acb835ac 2.7

* 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>. (cherry picked from commit 0e6c8ee)

bedevere-bot · 2018-03-04T05:44:45Z

GH-5970 is a backport of this pull request to the 2.7 branch.

* 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>. (cherry picked from commit 0e6c8ee)

bedevere-bot · 2018-03-04T05:47:23Z

GH-5971 is a backport of this pull request to the 3.6 branch.

* 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> Co-authored-by: Jamie Davis <davisjam@vt.edu> (cherry picked from commit 0e6c8ee)

* 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>. (cherry picked from commit 0e6c8ee)

* 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>.

* 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>. (cherry picked from commit 0e6c8ee)

davisjam requested a review from a team as a code owner March 1, 2018 21:50

bedevere-bot added the awaiting review label Mar 1, 2018

the-knights-who-say-ni added the CLA not signed label Mar 1, 2018

davisjam force-pushed the TestAndFixCatastrophicBacktracking branch from 6c9b1ef to 38bdbdd Compare March 2, 2018 00:13

the-knights-who-say-ni added CLA signed and removed CLA not signed labels Mar 2, 2018

davisjam changed the title ~~Fix catastrophic backtracking vulns~~ bpo-32981: Fix catastrophic backtracking vulns Mar 2, 2018

serhiy-storchaka reviewed Mar 2, 2018

View reviewed changes

davisjam force-pushed the TestAndFixCatastrophicBacktracking branch 2 times, most recently from 1a03bf9 to 83bf67c Compare March 2, 2018 15:32

davisjam force-pushed the TestAndFixCatastrophicBacktracking branch from 83bf67c to 539f390 Compare March 2, 2018 15:40

serhiy-storchaka reviewed Mar 2, 2018

View reviewed changes

davisjam force-pushed the TestAndFixCatastrophicBacktracking branch from 539f390 to 71db0e4 Compare March 2, 2018 17:29

davisjam and others added 3 commits March 2, 2018 12:41

Update ACKS and News

7bf9559

davisjam force-pushed the TestAndFixCatastrophicBacktracking branch from 71db0e4 to 7bf9559 Compare March 2, 2018 17:42

serhiy-storchaka reviewed Mar 2, 2018

View reviewed changes

Address review comments

ef83b0c

bedevere-bot added the awaiting merge label Mar 2, 2018

serhiy-storchaka requested a review from tim-one March 2, 2018 19:46

serhiy-storchaka added type-bug An unexpected behavior, bug, or error needs backport to 3.6 labels Mar 2, 2018

benjaminp merged commit 0e6c8ee into python:master Mar 4, 2018

bedevere-bot removed the awaiting merge label Mar 4, 2018

bedevere-bot removed the needs backport to 3.7 label Mar 4, 2018

bedevere-bot removed the needs backport to 2.7 label Mar 4, 2018

bedevere-bot removed the needs backport to 3.6 label Mar 4, 2018

bpo-32981: Fix catastrophic backtracking vulns #5955

bpo-32981: Fix catastrophic backtracking vulns #5955

Conversation

davisjam commented Mar 1, 2018 • edited by bedevere-bot Loading

the-knights-who-say-ni commented Mar 1, 2018

davisjam commented Mar 1, 2018

davisjam commented Mar 1, 2018 • edited Loading

davisjam commented Mar 1, 2018

gvanrossum commented Mar 1, 2018

davisjam commented Mar 2, 2018

davisjam commented Mar 2, 2018 • edited Loading

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

davisjam Mar 2, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

davisjam commented Mar 2, 2018

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

davisjam commented Mar 2, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

serhiy-storchaka commented Mar 2, 2018

davisjam commented Mar 2, 2018

davisjam commented Mar 2, 2018

serhiy-storchaka commented Mar 2, 2018

miss-islington commented Mar 4, 2018

bedevere-bot commented Mar 4, 2018

bedevere-bot commented Mar 4, 2018

miss-islington commented Mar 4, 2018

miss-islington commented Mar 4, 2018

bedevere-bot commented Mar 4, 2018

bedevere-bot commented Mar 4, 2018

davisjam commented Mar 1, 2018 •

edited by bedevere-bot

Loading

davisjam commented Mar 1, 2018 •

edited

Loading

davisjam commented Mar 2, 2018 •

edited

Loading

davisjam Mar 2, 2018 •

edited

Loading