Denial of service in requests_kerberos.kerberos_._negotiate_value

Hi there,

I believe I've found a denial-of-service (DoS) bug in requests_kerberos.kerberos_._negotiate_value. To start, I'm operating on some background information from this document: How does Kerberos actually work in the HTTP world?. The bug itself is a ReDoS bug causing catastrophic backtracking. To reproduce the issue we can use the following code:

from requests_kerberos.kerberos_ import _negotiate_value
response = type("", (), {})  # Mock response hack
response.headers = {'www-authenticate': ',' * 64 + ' '}
_negotiate_value(response)
...Spins...

The issue itself is in the following regular expression:

regex = re.compile(r'(?:.*,)*\s*Negotiate\s*([^,]*),?', re.I)

In particular, the (?:.*,)* portion. Since "." and "," overlap and there are nested quantifiers we can cause catastrophic backtracking by repeating a comma. Building from the Kerberos authentication document above, this means a server can send a specially crafted header along with an HTTP 401 and cause a DoS on the client.

I won't speculate on the severity of the issue too much - you will surely understand the impact better than I will. Although, the fact that this is client-side as opposed to server-side appears to reduce the severity, however the fact that it's a security-sensitive context (Kerberos authentication) may raise the severity.

Note that there was a similar issue in the Python standard library (looks like this code may have actually been inspired by it?): bp39503, which resulted in CVE-2020-8492.

One possible fix would be changing the regex expression to the following:

regex = re.compile(r'(?:[^,]*,)*\s*Negotiate\s*([^,]*),?', re.I)

This removes the character overlap in the nested quantifier and thus negates the catastrophic backtracking.

Let me know if you have any questions or what the next steps are from here. Thanks for supporting Python security!

requests / requests-kerberos

Denial of service in requests_kerberos.kerberos_._negotiate_value #145