[security] Infinite loop on folding email (_fold_as_ew()) if an header has no spaces

[rad164]

BPO	33529
Nosy	@warsaw, @vstinner, @ned-deily, @bitdancer, @maxking, @tirkarthi
PRs	bpo-33529: Fix Infinite loop on folding email if headers has non_ascii #7763 bpo-33529: Fix infinite loop in email header encoding #12020 [3.7] bpo-33529, email: Fix infinite loop in email header encoding (GH-12020) #13321 [3.6] bpo-33529, email: Fix infinite loop in email header encoding (GH-12020) #14162

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2019-06-18.08:31:25.562>
created_at = <Date 2018-05-16.00:12:28.457>
labels = ['type-security', '3.7', '3.8', 'expert-email']
title = '[security] Infinite loop on folding email (_fold_as_ew()) if an header has no spaces'
updated_at = <Date 2019-06-18.08:31:25.561>
user = 'https://bugs.python.org/rad164'

bugs.python.org fields:

activity = <Date 2019-06-18.08:31:25.561>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2019-06-18.08:31:25.562>
closer = 'vstinner'
components = ['email']
creation = <Date 2018-05-16.00:12:28.457>
creator = 'rad164'
dependencies = []
files = []
hgrepos = []
issue_num = 33529
keywords = ['patch']
message_count = 11.0
messages = ['316747', '319807', '330925', '342487', '342512', '344561', '345874', '345878', '345879', '345938', '345960']
nosy_count = 7.0
nosy_names = ['barry', 'vstinner', 'ned.deily', 'r.david.murray', 'maxking', 'rad164', 'xtreak']
pr_nums = ['7763', '12020', '13321', '14162']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue33529'
versions = ['Python 3.6', 'Python 3.7', 'Python 3.8']

[rad164]

I just reported a bug about email folding at bpo-33524, but this issue is more fatal in some languages like Chinese or Japanese, which does not insert spaces between each words.
Python 3.6.5 has this issue, while 3.6.4 does not.

Create an email with longer header than max_line_length set by its policy. And the header contains non-ascii characters but no white spaces.
When try to fold it, python gets stuck and finally system hangs. There are no output unless I stop it with Ctrl-C.

^CTraceback (most recent call last):
  File "emailtest.py", line 7, in <module>
    policy.fold("Subject", msg["Subject"])
  File "/usr/lib/python3.6/email/policy.py", line 183, in fold
    return self._fold(name, value, refold_binary=True)
  File "/usr/lib/python3.6/email/policy.py", line 205, in _fold
    return value.fold(policy=self)
  File "/usr/lib/python3.6/email/headerregistry.py", line 258, in fold
    return header.fold(policy=policy)
  File "/usr/lib/python3.6/email/_header_value_parser.py", line 144, in fold
    return _refold_parse_tree(self, policy=policy)
  File "/usr/lib/python3.6/email/_header_value_parser.py", line 2651, in _refold_parse_tree
    part.ew_combine_allowed, charset)
  File "/usr/lib/python3.6/email/_header_value_parser.py", line 2735, in _fold_as_ew
    ew = _ew.encode(first_part)
  File "/usr/lib/python3.6/email/_encoded_words.py", line 215, in encode
    blen = _cte_encode_length['b'](bstring)
  File "/usr/lib/python3.6/email/_encoded_words.py", line 130, in len_b
    groups_of_3, leftover = divmod(len(bstring), 3)
KeyboardInterrupt

Code to reproduce:

from email.message import EmailMessage
from email.policy import default

policy = default # max_line_length = 78
msg = EmailMessage()
msg["Subject"] = "á"*100
policy.fold("Subject", msg["Subject"])

No problems in following cases:

1. If the header is shorter than max_line_length.
2. If the header can be split with spaces and the all chunk is shorter than max_line_length.
3. If the header is fully composed with ascii characters. In this case, there is no problem even if it is very long without spaces.

[tirkarthi]

I tried the test case on master branch. I ran the test case on 1GB RAM Linux based digitalocean droplet to have the script killed. Please find the results as below :

# Python build

➜ cpython git:(master) ✗ ./python
Python 3.8.0a0 (heads/bpo33095-add-reference:9d49f85, Jun 17 2018, 07:22:33)
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>

# Test case

➜ cpython git:(master) ✗ cat foo.py

from email.message import EmailMessage
from email.policy import default

policy = default # max_line_length = 78
msg = EmailMessage()
msg["Subject"] = "á"*100
policy.fold("Subject", msg["Subject"])

# Test case execution

➜ cpython git:(master) ✗ time ./python foo.py
[2] 13637 killed ./python foo.py
./python foo.py 387.36s user 3.85s system 90% cpu 7:11.94 total

# I tried to do Ctrl + C after 2 minutes to stop and the stack trace is as below :

➜  cpython git:(master) ✗ time ./python foo.py
^CTraceback (most recent call last):
  File "foo.py", line 7, in <module>
    policy.fold("Subject", msg["Subject"])
  File "/root/cpython/Lib/email/policy.py", line 183, in fold
    return self._fold(name, value, refold_binary=True)
  File "/root/cpython/Lib/email/policy.py", line 205, in _fold
    return value.fold(policy=self)
  File "/root/cpython/Lib/email/headerregistry.py", line 258, in fold
    return header.fold(policy=policy)
  File "/root/cpython/Lib/email/_header_value_parser.py", line 144, in fold
    return _refold_parse_tree(self, policy=policy)
  File "/root/cpython/Lib/email/_header_value_parser.py", line 2650, in _refold_parse_tree
    part.ew_combine_allowed, charset)
  File "/root/cpython/Lib/email/_header_value_parser.py", line 2728, in _fold_as_ew
    ew = _ew.encode(first_part, charset=encode_as)
  File "/root/cpython/Lib/email/_encoded_words.py", line 226, in encode
    qlen = _cte_encode_length['q'](bstring)
  File "/root/cpython/Lib/email/_encoded_words.py", line 93, in len_q
    return sum(len(_q_byte_map[x]) for x in bstring)
  File "/root/cpython/Lib/email/_encoded_words.py", line 93, in <genexpr>
    return sum(len(_q_byte_map[x]) for x in bstring)
KeyboardInterrupt
./python foo.py  131.41s user 0.43s system 98% cpu 2:13.89 total

Thanks

[vstinner]

Since it's a denial of service which can be triggered by an user, I mark this issue as a security issue.

I can be wrong, but it seems like Python 2.7 isn't affected: Lib/email/_header_value_parser.py was added by bpo-12586 (commit 0b6f6c8). Python 2.7 doesn't have this file nor policies.

[vstinner]

New changeset c1f5667 by Victor Stinner (Krzysztof Wojcik) in branch 'master':
bpo-33529, email: Fix infinite loop in email header encoding (GH-12020)
c1f5667

[vstinner]

New changeset 2fef5b0 by Victor Stinner (Miss Islington (bot)) in branch '3.7':
bpo-33529, email: Fix infinite loop in email header encoding (GH-12020) (GH-13321)
2fef5b0

[vstinner]

Python 3.6, 3.5 and 2.7 are still vulnerable. Is there someone interested to backport the fix?

[vstinner]

It's unclear to me if Python 3.5 is affected or not.

The fix changes the function _fold_as_ew(), Python 3.5 doesn't have this function *but* there is a call a _fold_as_ew() method!?

Lib/email/_header_value_parser.py:427: in _fold() method

        ...
        if is_ew or last_ew:
            # It's too big to fit on the line, but since we've
            # got encoded words we can use encoded word folding.
            part._fold_as_ew(folded)
            continue
        ...

If I backport the 2 tests, they fail *but* they don't hang forever (they complete in less than 1 second).

======================================================================
FAIL: test_fold_overlong_words_using_RFC2047 (test.test_email.test_headerregistry.TestFolding)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/vstinner/prog/python/3.5/Lib/test/test_email/test_headerregistry.py", line 1601, in test_fold_overlong_words_using_RFC2047
    'X-Report-Abuse: =?utf-8?q?=3Chttps=3A//www=2Emailitapp=2E'
AssertionError: 'X-Report-Abuse: <https://www.mailitapp.com/report_abuse.p[50 chars]x>\n' != 'X-Report-Abuse: =?utf-8?q?=3Chttps=3A//www=2Emailitapp=2E[114 chars]?=\n'
- X-Report-Abuse: <https://www.mailitapp.com/report_abuse.php?mid=xxx-xxx-xxxxxxxxxxxxxxxxxxxxxxxx==-xxx-xx-xx>
+ X-Report-Abuse: =?utf-8?q?=3Chttps=3A//www=2Emailitapp=2Ecom/report=5Fabuse?=
+  =?utf-8?q?=2Ephp=3Fmid=3Dxxx-xxx-xxxxxxxxxxxxxxxxxxxxxxxx=3D=3D-xxx-xx-xx?=
+  =?utf-8?q?=3E?=

======================================================================
FAIL: test_non_ascii_chars_do_not_cause_inf_loop (test.test_email.test_policy.PolicyAPITests)
----------------------------------------------------------------------

Traceback (most recent call last):
  File "/home/vstinner/prog/python/3.5/Lib/test/test_email/test_policy.py", line 241, in test_non_ascii_chars_do_not_cause_inf_loop
    12 * ' =?utf-8?q?=C4=85?=\n')
AssertionError: 'Subject: =?utf-8?b?xIXEhcSFxIXEhcSFxIXEhcSFxIXEhcSF?=\n' != 'Subject: \n =?utf-8?q?=C4=85?=\n =?utf-8?q?=C4=85?[209 chars]?=\n'
- Subject: =?utf-8?b?xIXEhcSFxIXEhcSFxIXEhcSFxIXEhcSF?=
+ Subject: 
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=
+  =?utf-8?q?=C4=85?=

[vstinner]

Python 3.5 is not vulnerable, it doesn't hang on the following code:

import email.policy
policy = email.policy.default.clone(max_line_length=20)
actual = policy.fold('Subject', '\u0105' * 12)