classification
Title: CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names
Type: security Stage: resolved
Components: Library (Lib) Versions: Python 3.4, Python 3.3, Python 3.2
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Arfrever, bkabrda, christian.heimes, fweimer, georg.brandl, gregory.p.smith, haypo, iankko, lemburg, mpessas, pitrou, python-dev, tim.peters, timehorse
Priority: normal Keywords: patch

Created on 2013-05-15 10:25 by fweimer, last changed 2013-05-18 16:00 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
ssl_wildcard_dos.patch pitrou, 2013-05-16 18:34
ssl_wildcard_dos2.patch pitrou, 2013-05-17 13:13
Messages (35)
msg189280 - (view) Author: Florian Weimer (fweimer) Date: 2013-05-15 10:25
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).
msg189291 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-15 18:22
Does the RFC say anything about this? How much wildcards are necessary to take up a significant amount of CPU time?
msg189348 - (view) Author: Jan Lieskovsky (iankko) Date: 2013-05-16 10:16
The CVE identifier of CVE-2013-2099 has been assigned:
  http://www.openwall.com/lists/oss-security/2013/05/16/6

to this issue.
msg189353 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 10:51
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
msg189354 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 10:56
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.
msg189357 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-16 11:15
RFC 2818 doesn't say anything about the maximum amount of wildcards. I'm going to check OpenSSL's implementation now.
msg189361 - (view) Author: Florian Weimer (fweimer) Date: 2013-05-16 12:10
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).
msg189366 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 12:33
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
msg189368 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 12:43
> 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?
msg189369 - (view) Author: Florian Weimer (fweimer) Date: 2013-05-16 12:50
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.
msg189373 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-16 13:08
I think a malicious user could abuse SNI to craft a longer host name and trigger the pathological case.
msg189380 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 13:34
In GnuTLS, _gnutls_hostname_compare() (lib/gnutls_str.c) uses a trivial recursive approach with a maximum number of 5 wildcards.
msg189391 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-05-16 17:39
Wildcard matching can easily be done in worst-case linear time, but not with regexps.  doctest.py's internal _ellipsis_match() shows one way to do it (doctest can use "..." as a wildcard marker).
msg189396 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-16 18:10
We could use an algorithm that doesn't need regexp for most cases.

pseudo code:

value = value.lower()
hostname = hostname.lower()

if '*' not in value:
   return value == hostname

vparts = valuesplit(".")
hparts = hostname.split(".")
if len(vparts) != len(hparts):
    # * doesn't match a dot
    return False

for v, h in zip(vparts, hparts):
    if v == "*":
        # match any host part
        continue
    asterisk = v.count("*")
    if asterisk == 0:
        if v != h:
            return False
    elif asterisk == 1:
        # match with simple re
    else:
        # don't support more than one * in a FQDN part
        raise TooManyAsterisk
msg189398 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 18:13
> Wildcard matching can easily be done in worst-case linear time, but
> not with regexps.  doctest.py's internal _ellipsis_match() shows one
> way to do it (doctest can use "..." as a wildcard marker).

Thanks, this may be a nice enhancement for 3.4.

For 3.2 and 3.3, I'd prefer to go the safe way of simply limiting the
number of wildcards. If OpenSSL only accepts one per fragment, accepting
one or two is certainly fine for Python as well :-)
msg189399 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-16 18:34
Here is a patch allowing at most 2 wildcards per domain fragment. Georg, do you think this should go into 3.2?
msg189402 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2013-05-16 18:45
It's certainly a security fix, but probably not one that warrants an immediate release.

If you commit it to the 3.2 branch, that's fine, it will get picked up by coming releases.
msg189407 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2013-05-16 20:29
Indeed, doing this _without a regexp_ is preferred. :)
msg189419 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-17 01:09
Are multiple wildcards per fragment even specified? I'm unable to find information if the wildcard is supposed to be a greedy or a non-greedy match.

By the way Chromium does more fancy checks. For example it requires * to match at least on character and it does special handling of IDN. X509Certificate::VerifyHostname() around line 500.

http://src.chromium.org/viewvc/chrome/trunk/src/net/cert/x509_certificate.cc
msg189430 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2013-05-17 07:51
> Are multiple wildcards per fragment even specified?

I don't know the standard, but it sounds strange to have more than one wildcard per part of an URL. "*.*.*.google.com" looks valid to me, whereas "*a*a*a*.google.com" looks very suspicious.

Said differently, I expect:

assert max(part.count("*") for part in url.split(".")) <= 1

"*" pattern is replace with '[^.]+' regex, so I may not cause the exponential complexity issue. (I didn't check.)
msg189432 - (view) Author: Florian Weimer (fweimer) Date: 2013-05-17 08:20
> "*" pattern is replace with '[^.]+' regex, so I may not cause the exponential complexity issue. (I didn't check.)

A possessive quantifier might also help, that is [^.]+?.
msg189433 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2013-05-17 09:21
SSL certificate hostname matching is defined in RFC 2818:

 * http://www.ietf.org/rfc/rfc2818.txt

It's not very verbose on how exactly matching should be done:

"""
   Names may contain the wildcard
   character * which is considered to match any single domain name
   component or component fragment. E.g., *.a.com matches foo.a.com but
   not bar.foo.a.com. f*.com matches foo.com but not bar.com.
"""

Given that it's underspecified, I doubt that anyone using wildcards in certificates for valid purposes would risk using anything but very simply prefix/suffix matching - most certainly not any matching that would require backtracking to succeed.

There are several variants out there of how the matching is done.
See e.g. http://search-hadoop.com/c/Hadoop:hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/security/ssl/SSLHostnameVerifier.java||dns
msg189434 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 09:23
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
msg189436 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 09:34
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?
msg189437 - (view) Author: Florian Weimer (fweimer) Date: 2013-05-17 09:40
Antoine, support for OpenSSL host name matching is quite new: <http://www.openssl.org/docs/crypto/X509_check_host.html>
msg189438 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 09:43
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.
msg189439 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 09:44
> Antoine, support for OpenSSL host name matching is quite new

Ah, thanks. I was looking in 1.0.1e.
msg189444 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2013-05-17 10:52
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.
msg189451 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 13:13
Attached patch forbidding more than one wildcard per fragment.
msg189452 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-17 13:23
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'
msg189453 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-17 13:36
> 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).
msg189455 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-17 14:05
#17997
msg189517 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-05-18 14:37
The IDNA RFC contains additional rules for wildcard matching ... very well hidden indead!

http://tools.ietf.org/html/rfc6125#section-6.4.3
msg189525 - (view) Author: Roundup Robot (python-dev) Date: 2013-05-18 15:59
New changeset b9b521efeba3 by Antoine Pitrou in branch '3.2':
Issue #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 #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 #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
msg189526 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-05-18 16:00
Ok, this should be fixed now. Thanks a lot for reporting!
History
Date User Action Args
2013-05-18 16:00:16pitrousetstatus: open -> closed
resolution: fixed
messages: + msg189526

stage: patch review -> resolved
2013-05-18 15:59:23python-devsetnosy: + python-dev
messages: + msg189525
2013-05-18 14:37:31christian.heimessetmessages: + msg189517
2013-05-17 14:05:17christian.heimessetmessages: + msg189455
2013-05-17 13:36:56pitrousetmessages: + msg189453
2013-05-17 13:23:42christian.heimessetmessages: + msg189452
2013-05-17 13:13:30pitrousetfiles: + ssl_wildcard_dos2.patch

messages: + msg189451
stage: needs patch -> patch review
2013-05-17 10:52:43lemburgsetmessages: + msg189444
2013-05-17 09:44:36pitrousetmessages: + msg189439
2013-05-17 09:43:05pitrousetmessages: + msg189438
2013-05-17 09:40:17fweimersetmessages: + msg189437
2013-05-17 09:34:22pitrousetmessages: + msg189436
2013-05-17 09:23:16pitrousetmessages: + msg189434
2013-05-17 09:21:27lemburgsetnosy: + lemburg
messages: + msg189433
2013-05-17 08:20:28fweimersetmessages: + msg189432
2013-05-17 07:51:18hayposetmessages: + msg189430
2013-05-17 06:39:53bkabrdasetnosy: + bkabrda
2013-05-17 01:09:43christian.heimessetmessages: + msg189419
2013-05-16 20:29:17gregory.p.smithsetnosy: + gregory.p.smith
messages: + msg189407
2013-05-16 20:20:45hayposetnosy: + haypo
2013-05-16 18:45:01georg.brandlsetmessages: + msg189402
2013-05-16 18:34:26pitrousetfiles: + ssl_wildcard_dos.patch

nosy: + georg.brandl
messages: + msg189399

keywords: + patch
2013-05-16 18:13:19pitrousetmessages: + msg189398
2013-05-16 18:10:43christian.heimessetmessages: + msg189396
2013-05-16 17:39:47tim.peterssetnosy: + tim.peters
messages: + msg189391
2013-05-16 15:21:50timehorsesetnosy: + timehorse
2013-05-16 13:34:22pitrousetmessages: + msg189380
2013-05-16 13:08:04christian.heimessetmessages: + msg189373
2013-05-16 12:50:10fweimersetmessages: + msg189369
2013-05-16 12:45:00Arfreversetnosy: + Arfrever
2013-05-16 12:43:57pitrousetmessages: + msg189368
title: CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names -> CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names
2013-05-16 12:33:31pitrousetmessages: + msg189366
2013-05-16 12:30:54mpessassetnosy: + mpessas
2013-05-16 12:10:18fweimersetmessages: + msg189361
2013-05-16 11:15:56christian.heimessetmessages: + msg189357
2013-05-16 10:56:44pitrousetnosy: + christian.heimes
2013-05-16 10:56:39pitrousetmessages: + msg189354
2013-05-16 10:51:47pitrousetmessages: + msg189353
2013-05-16 10:34:23pitrousetstage: needs patch
type: security
versions: + Python 3.2, Python 3.4
2013-05-16 10:16:41iankkosetnosy: + iankko

messages: + msg189348
title: ssl.match_hostname() trips over crafted wildcard names -> CVE-2013-2099 ssl.match_hostname() trips over crafted wildcard names
2013-05-15 18:22:58pitrousetnosy: + pitrou
messages: + msg189291
2013-05-15 10:25:06fweimercreate