CVE-2021-3733: ReDoS in urllib.request

[yetingli]

BPO	43075
Nosy	@orsenthil, @vstinner, @ned-deily, @ambv, @serhiy-storchaka, @miss-islington, @yetingli, @StayPirate
PRs	bpo-43075: Fix ReDoS in request #24391 [3.9] bpo-43075: Fix ReDoS in urllib AbstractBasicAuthHandler (GH-24391) #25247 [3.8] bpo-43075: Fix ReDoS in urllib AbstractBasicAuthHandler (GH-24391) #25248 [3.7] bpo-43075: Fix ReDoS in urllib AbstractBasicAuthHandler (GH-24391) #25249 [3.6] bpo-43075: Fix ReDoS in urllib AbstractBasicAuthHandler (GH-24391) #25250
Files	redos_python.py redos_python2.py

^{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 2021-05-06.17:00:47.929>
created_at = <Date 2021-01-30.08:11:46.452>
labels = ['type-security', 'easy', '3.8', '3.9', '3.10', '3.7', 'library']
title = 'CVE-2021-3733: ReDoS in urllib.request'
updated_at = <Date 2021-09-07.20:12:23.266>
user = 'https://github.com/yetingli'

bugs.python.org fields:

activity = <Date 2021-09-07.20:12:23.266>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2021-05-06.17:00:47.929>
closer = 'ned.deily'
components = ['Library (Lib)']
creation = <Date 2021-01-30.08:11:46.452>
creator = 'yetingli'
dependencies = []
files = ['49778', '49938']
hgrepos = []
issue_num = 43075
keywords = ['patch', 'easy', 'newcomer friendly']
message_count = 16.0
messages = ['385974', '385987', '385993', '386009', '388358', '388665', '390415', '390417', '390419', '390420', '390425', '390441', '392885', '393109', '400130', '401341']
nosy_count = 8.0
nosy_names = ['orsenthil', 'vstinner', 'ned.deily', 'lukasz.langa', 'serhiy.storchaka', 'miss-islington', 'yetingli', 'crazybyte']
pr_nums = ['24391', '25247', '25248', '25249', '25250']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue43075'
versions = ['Python 3.6', 'Python 3.7', 'Python 3.8', 'Python 3.9', 'Python 3.10']

[yetingli]

Hi,

I find this regex '(?:^|,)[ \t]*([^ \\t]+)[ \t]+' may be stucked by input.

The vulnerable regex is located in

cpython/Lib/urllib/request.py

Line 946 in 5c5a938

rx = re.compile('(?:^|,)' # start of the string or ','

The ReDOS vulnerability of the regex is mainly due to the sub-pattern ',([^ \\t]+)' and can be exploited with the following string
attack_str = "," * 10000

You can execute redos_python.py to reproduce the ReDos vulnerability.

I am willing to suggest that you replace '(?:^|,)[ \t]([^ \\t]+)[ \t]+' with '(?:^|,)[ \t]([^ \\t,]+)[ \t]+'

Looking forward for your response​!

Best,
Yeting Li

[serhiy-storchaka]

I agree. There is no catastrophic backtracking here (it was fixed in bpo-39503), but the complexity of matching the regular expression is linear. Searching the pattern in a sequence of commas has quadratic complexity, because every step has linear complexity and we advance only one character at every attempt.

The proposed solution looks correct to me and fixes the issue. Yeting Li, do you mind to create a pull request for it? I can do it myself, but since you have found the problem and the solution, it would be better if the commit be attributed to you.

[orsenthil]

+1. The suggested fix looks good to me.