CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names

@malemburg

BPO	17980
Nosy	@malemburg, @tim-one, @birkenfeld, @gpshead, @pitrou, @vstinner, @tiran
Files	ssl_wildcard_dos.patch ssl_wildcard_dos2.patch

^{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 2013-05-18.16:00:16.484>
created_at = <Date 2013-05-15.10:25:06.692>
labels = ['type-security', 'library']
title = 'CVE-2013-2099 ssl.match_hostname() trips over crafted\twildcard names'
updated_at = <Date 2013-05-18.16:00:16.483>
user = 'https://bugs.python.org/fweimer'

bugs.python.org fields:

activity = <Date 2013-05-18.16:00:16.483>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2013-05-18.16:00:16.484>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2013-05-15.10:25:06.692>
creator = 'fweimer'
dependencies = []
files = ['30288', '30292']
hgrepos = []
issue_num = 17980
keywords = ['patch']
message_count = 35.0
messages = ['189280', '189291', '189348', '189353', '189354', '189357', '189361', '189366', '189368', '189369', '189373', '189380', '189391', '189396', '189398', '189399', '189402', '189407', '189419', '189430', '189432', '189433', '189434', '189436', '189437', '189438', '189439', '189444', '189451', '189452', '189453', '189455', '189517', '189525', '189526']
nosy_count = 14.0
nosy_names = ['lemburg', 'tim.peters', 'georg.brandl', 'gregory.p.smith', 'pitrou', 'vstinner', 'christian.heimes', 'timehorse', 'Arfrever', 'iankko', 'python-dev', 'bkabrda', 'fweimer', 'mpessas']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'security'
url = 'https://bugs.python.org/issue17980'
versions = ['Python 3.2', 'Python 3.3', 'Python 3.4']

If the name in the certificate contains many "*" characters, matching the compiled regular expression against the host name can take a very long time. Certificate validation happens before host name checking, so I think this is a minor issue only because it can only be triggered in cooperation with a CA (which seems unlikely).

The fix is to limit the number of "*" wildcards to a reasonable maximum (perhaps even 1).

Does the RFC say anything about this? How much wildcards are necessary to take up a significant amount of CPU time?

The CVE identifier of CVE-2013-2099 has been assigned:
http://www.openwall.com/lists/oss-security/2013/05/16/6

to this issue.

This is caused by the regex engine's performance behaviour:
http://bugs.python.org/issue1662581
http://bugs.python.org/issue1515829
http://bugs.python.org/issue212521

I would like to know what is the expected scenario:

does the attacker only control the certificate?
or does the attacker control both the certificate and the hostname being validated?

The reason is that the matching cost for a domain name fragment seems to be O(n**k), where n is the fragment length and k is the number of wildcards. Therefore, if the attacker controls both n and k, even limiting k to 2 already allows a quadratic complexity attack.

RFC 2818 doesn't say anything about the maximum amount of wildcards. I'm going to check OpenSSL's implementation now.

OpenSSL supports only a single wildcard character.

In my tests, I used a host name like aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.example.org, and a dNSName like a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*.example.org. Quadratic behavior wouldn't be too bad because the host name is necessarily rather short (more than 255 characters will not pass through DNS).

Indeed, two wildcards seem to be ok with a 255-character domain name:

$ ./python -m timeit -s "import ssl; cert = {'subject': ((('commonName', '*a*a.com'),),)}" "try: ssl.match_hostname(cert, 'a' * 250 +'z.com')" "except ssl.CertificateError: pass"
1000 loops, best of 3: 797 usec per loop

Three wildcards already start producing some load:

$ ./python -m timeit -s "import ssl; cert = {'subject': ((('commonName', '*a*a*a.com'),),)}" "try: ssl.match_hostname(cert, 'a' * 250 +'z.com')" "except ssl.CertificateError: pass"
10 loops, best of 3: 66.2 msec per loop

Four wildcards are more than enough for a DoS:

$ ./python -m timeit -s "import ssl; cert = {'subject': ((('commonName', '*a*a*a*a.com'),),)}" "try: ssl.match_hostname(cert, 'a' * 250 +'z.com')" "except ssl.CertificateError: pass"
10 loops, best of 3: 4.12 sec per loop

In my tests, I used a host name like
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.example.org, and a dNSName
like a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*.example.org.
Quadratic behavior wouldn't be too bad because the host name is
necessarily rather short (more than 255 characters will not pass
through DNS).

Hmm, but the host name doesn't necessarily come from DNS, does it?

The host name is looked up to get the IP address to connect to. The lookup will fail if the host name is longer than 255 characters, and the crafted certificate is never retrieved.

I think a malicious user could abuse SNI to craft a longer host name and trigger the pathological case.

Non-greedy matching actually makes things worse :-)

$ ./python -m timeit -s "import re; pat = re.compile('\A*a*a*a\Z'.replace('*', '[^.]+'), re.IGNORECASE)" "pat.match('a' * 100 +'z')"
100 loops, best of 3: 3.31 msec per loop

$ ./python -m timeit -s "import re; pat = re.compile('\A*a*a*a\Z'.replace('*', '[^.]+?'), re.IGNORECASE)" "pat.match('a' * 100 +'z')"
100 loops, best of 3: 6.91 msec per loop

Florian, I'm actually surprised by your assertion that OpenSSL supports a single wildcard character. Last I looked, I couldn't find any hostname matching function in OpenSSL (which is why I had to write our own). Could you point me to the relevant piece of code?

Antoine, support for OpenSSL host name matching is quite new: <http://www.openssl.org/docs/crypto/X509_check_host.html\>

libcurl supports a single wildcard for the whole domain name pattern (not even one per fragment), as per lib/hostcheck.c

(this is when linked against OpenSSL; when linked against GnuTLS, curl will use the GnuTLS-provided matching function)

Based on all the evidence, I think allowing one wildcard per fragment is sufficient.

Antoine, support for OpenSSL host name matching is quite new

Ah, thanks. I was looking in 1.0.1e.

Here's another long discussions about SSL hostname matching that may provide some useful insights:

https://bugzilla.mozilla.org/show_bug.cgi?id=159483

Note how RFC 2595 doesn't even allow sub-string matching. It only allows '*' to be used as component.

Attached patch forbidding more than one wildcard per fragment.

I still think that sub string wildcard should not match the IDN "xn--" prefix. With current code the rules "x*.example.de" gives a positive match for "götter.example.de".

>>> u"götter.example.de".encode("idna")
'xn--gtter-jua.example.de'

I still think that sub string wildcard should not match the IDN
"xn--" prefix. With current code the rules "x*.example.de" gives a
positive match for "götter.example.de".

You should open a separate issue for this (possibly with a patch).

bpo-17997

The IDNA RFC contains additional rules for wildcard matching ... very well hidden indead!

http://tools.ietf.org/html/rfc6125#section-6.4.3

New changeset b9b521efeba3 by Antoine Pitrou in branch '3.2':
Issue bpo-17980: Fix possible abuse of ssl.match_hostname() for denial of service using certificates with many wildcards (CVE-2013-2099).
http://hg.python.org/cpython/rev/b9b521efeba3

New changeset c627638753e2 by Antoine Pitrou in branch '3.3':
Issue bpo-17980: Fix possible abuse of ssl.match_hostname() for denial of service using certificates with many wildcards (CVE-2013-2099).
http://hg.python.org/cpython/rev/c627638753e2

New changeset fafd33db6ff6 by Antoine Pitrou in branch 'default':
Issue bpo-17980: Fix possible abuse of ssl.match_hostname() for denial of service using certificates with many wildcards (CVE-2013-2099).
http://hg.python.org/cpython/rev/fafd33db6ff6

Ok, this should be fixed now. Thanks a lot for reporting!

Navigation Menu

Repository navigation

CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names #62180

11 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names #62180

Description

Activity

fweimer commented on May 15, 2013

pitrou commented on May 15, 2013

iankko commented on May 16, 2013

pitrou commented on May 16, 2013

pitrou commented on May 16, 2013

tiran commented on May 16, 2013

fweimer commented on May 16, 2013

pitrou commented on May 16, 2013

pitrou commented on May 16, 2013

fweimer commented on May 16, 2013

tiran commented on May 16, 2013

11 remaining items

pitrou commented on May 17, 2013

pitrou commented on May 17, 2013

fweimer commented on May 17, 2013

pitrou commented on May 17, 2013

pitrou commented on May 17, 2013

malemburg commented on May 17, 2013

pitrou commented on May 17, 2013

tiran commented on May 17, 2013

pitrou commented on May 17, 2013

tiran commented on May 17, 2013

tiran commented on May 18, 2013

python-dev commented on May 18, 2013

pitrou commented on May 18, 2013

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions