cc @serhiy-storchaka

This fix looks good to me!

Would be nice to add a test.

Just a heads up, CVE-2020-8492 has been created. I'm not sure how Python CVEs are generally tracked, but it may be useful to include the information on the bug tracker issue 👍

Not only (?:.*,)* is inefficient, but it's also useless. It can be removed. Simplified example:

# reference
>>> all(re.search("(?:a,)*b", text) for text in ("a,b", "a,a,b", "b"))
True
# only match last ","
>>> all(re.search("(?:,)?b", text) for text in ("a,b", "a,a,b", "b"))
True
# don't match the prefix
>>> all(re.search("b", text) for text in ("a,b", "a,a,b", "b"))
True

We can either simplify the regex to prevent the "catastrophic backtracking" or even remove the prefix.

UPDATE: Oops, my example was wrong, I fixed it :-)

Does this also fix https://bugs.python.org/issue38826 ?

Not only (?:.*,)* is inefficient, but it's also useless. It can be removed.

It seems to me that the (?:.*,)* is there so that the last realm is selected, as mentioned in the comment above the regex. See:

>>> header = 'basic realm="1", x, other realm="2"'
>>> re.search("(?:.*,)*[ \t]*([^ \t]+)[ \t]+", header).group(1)
'other'
>>> re.search("[ \t]*([^ \t]+)[ \t]+", header).group(1)
'basic'
>>> 

I don't see a way to fix this by just changing the regex while preserving the previous behavior. Then again, corner cases of the previous behavior might be wrong.

I rebased my PR and added more tests.

@serhiy-storchaka: I don't understand if you consider that the fix is wrong or that the fix is not enough (it remains possible to create a denial of service)?

@vstinner your fix helps, but we can do better. It has cubic complexity, my suggestion has quadratic complexity. It is possible to implement an algorithm with linear complexity, but not with such small changes.

I also added some tests and implemented a simpler complexity regex - see master...davidfraser:urllib_basic_auth_regex

It's worth seeing how the results of this regex are actually used

Note my comment in f79379c:

Note that the original regex was roughly O(2**n)
The search for commas and spaces is unnecessary
(and insufficient to ensure that this starts a new scheme).
Replace with a simpler search for an initial scheme, since
we already check that the text starts with 'basic'.

WWW-Authenticate is badly specified. The RFC doesn't specify if a single HTTP header can contain multiple challenges.

I found these resources:

• https://tools.ietf.org/html/rfc7235#section-4.1
• https://tools.ietf.org/html/rfc7617
• https://developer.mozilla.org/fr/docs/Web/HTTP/Headers/WWW-Authenticate
• https://www.iana.org/assignments/http-authschemes/http-authschemes.xhtml : official list of schemes (Basic, Digest, ...)
• https://stackoverflow.com/questions/10239970/what-is-the-delimiter-for-www-authenticate-for-multiple-schemes : list of links of people asking how softwares are supposed to handle multiple challenges

A variant is to have multiple WWW-Authenticate: one challenge per WWW-Authenticate header.

By the way, AbstractBasicAuthHandler code contains this interesting comment:

        # XXX could be multiple headers
        authreq = headers.get(authreq, None)

Current behavior:

• Even if there are multiple WWW-Authenticate headers, only parse the first header. That's a bug: the Basic challenge may be in a following WWW-Authenticate header. Moreover, there may be two Basic challenges with two different realm.

• scheme = str.split()[0] parses the scheme, if scheme.lower() != "basic": raise a ValueError.

• Use the regex to parse the realm.

• If the header contains multiple realm=xxx: use the last realm, even if it belongs to another challenge using a different scheme. IMO it's a bug: we should not check the scheme at the beginning of the header and use the last realm at the end of the string.

For example, WWW-Authenticate: Basic realm="ACME Widget Store", Digest realm="other realm" header is accepted since it starts with Basic, but the extracted realm is other realm: the wrong realm is used.

@serhiy-storchaka:

2. Keep rx.search() and replace (?:.*,)* with (?:^|,).

Sorry, I misunderstood this proposition. In fact, I proposed something similar except that I missed the "start of the string" (regex ^) case. I modified my PR to use this PR. I also added comments to the regex to explain it.

I decided to write a way more complex change to not only fix the vulnerability, but also fix the parser since it didn't look possible to fix the regex without changing the behavior. Currently, the code uses the last realm if there are multiple challenges per header. I fixed this behavior to use the realm of the first Basic challenge.

I also modified the code to support multiple headers, except of only parsing the first one.

Ok, the PR is now ready for a new round of reviews. I fixed the vulnerability but I also changed the code to parse all WWW-Authenticate HTTP Headers and accept multiple challenges per header.

Oh, Ben Caller reported the issue at 2019-11-17: https://bugs.python.org/issue38826

cc @orsenthil

I also modified the code to support multiple headers, except of only parsing the first one.

Thanks, @vstinner - This was a good detection and change.

I am reviewing the patch further.

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

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Hi! The buildbot s390x SLES 3.x has failed when building commit 0b297d4.

What do you need to do:

1. Don't panic.
2. Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
3. Go to the page of the buildbot that failed (https://buildbot.python.org/all/#builders/6/builds/675) and take a look at the build logs.
4. Check if the failure is related to this commit (0b297d4) or if it is a false positive.
5. If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.

You can take a look at the buildbot page here:

https://buildbot.python.org/all/#builders/6/builds/675

Failed tests:

• test_imaplib

Failed subtests:

• test_logout - test.test_imaplib.RemoteIMAP_STARTTLSTest

Summary of the results of the build (if available):

== Tests result: FAILURE then FAILURE ==

404 tests OK.

10 slowest tests:

• test_concurrent_futures: 3 min 8 sec
• test_multiprocessing_spawn: 2 min 44 sec
• test_tokenize: 1 min 47 sec
• test_multiprocessing_forkserver: 1 min 39 sec
• test_unparse: 1 min 26 sec
• test_multiprocessing_fork: 1 min 24 sec
• test_capi: 1 min 21 sec
• test_asyncio: 1 min 1 sec
• test_lib2to3: 56.4 sec
• test_signal: 51.2 sec

1 test failed:
test_imaplib

15 tests skipped:
test_devpoll test_ioctl test_kqueue test_msilib test_ossaudiodev
test_readline test_sqlite test_startfile test_tix test_tk
test_ttk_guionly test_winconsoleio test_winreg test_winsound
test_zipfile64

1 re-run test:
test_imaplib

Total duration: 7 min 14 sec

Traceback (most recent call last):
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/imaplib.py", line 989, in _command
    self.send(data + CRLF)
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/imaplib.py", line 331, in send
    self.sock.sendall(data)
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/ssl.py", line 1204, in sendall
    v = self.send(byte_view[count:])
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/ssl.py", line 1173, in send
    return self._sslobj.write(data)
BrokenPipeError: [Errno 32] Broken pipe


Traceback (most recent call last):
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/test/test_imaplib.py", line 951, in tearDown
    self.server.logout()
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/imaplib.py", line 641, in logout
    typ, dat = self._simple_command('LOGOUT')
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/imaplib.py", line 1213, in _simple_command
    return self._command_complete(name, self._command(name, *args))
  File "/home/dje/cpython-buildarea/3.x.edelsohn-sles-z/build/Lib/imaplib.py", line 991, in _command
    raise self.abort('socket error: %s' % val)
imaplib.IMAP4.abort: socket error: [Errno 32] Broken pipe

Thanks @vstinner for the PR 🌮🎉.. I'm working now to backport this PR to: 3.8.
🐍🍒⛏🤖

Thanks @vstinner for the PR 🌮🎉.. I'm working now to backport this PR to: 3.7.
🐍🍒⛏🤖

GH-19296 is a backport of this pull request to the 3.8 branch.

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