| 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) *  |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
Date: 2013-05-16 20:29 |
| Indeed, doing this _without a regexp_ is preferred. :) |
|
|
| msg189419 - (view) |
Author: Christian Heimes (christian.heimes) * |
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 (vstinner) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
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) * |
Date: 2013-05-17 13:13 |
| Attached patch forbidding more than one wildcard per fragment. |
|
|
| msg189452 - (view) |
Author: Christian Heimes (christian.heimes) * |
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) * |
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) * |
Date: 2013-05-17 14:05 |
| #17997 |
|
|
| msg189517 - (view) |
Author: Christian Heimes (christian.heimes) * |
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) * |
Date: 2013-05-18 16:00 |
| Ok, this should be fixed now. Thanks a lot for reporting! |
|
|