[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
_gnutls_hostname_compare: exponential slowdown with multiple wildcards
From: |
Kalle Olavi Niemitalo |
Subject: |
_gnutls_hostname_compare: exponential slowdown with multiple wildcards |
Date: |
Wed, 04 May 2011 00:25:00 +0300 |
User-agent: |
Gnus/5.110007 (No Gnus v0.7) Emacs/23.0.51 (gnu/linux) |
I tried a few _gnutls_hostname_compare calls in GnuTLS 2.8.6.
The implementation in 2.10.5 is identical.
_gnutls_hostname_compare("*************a", 14, "bbbbbbbbbbbbbbb")
returns 0 in 1 second.
_gnutls_hostname_compare("**************a", 15, "bbbbbbbbbbbbbbbb")
returns 0 in 5 seconds.
_gnutls_hostname_compare("***************a", 16, "bbbbbbbbbbbbbbbbb")
returns 0 in 15 seconds.
_gnutls_hostname_compare("****************a", 17, "bbbbbbbbbbbbbbbbbb")
returns 0 in 63 seconds.
_gnutls_hostname_compare("*****************a", 18, "bbbbbbbbbbbbbbbbbbb")
returns 0 in 243 seconds.
As you can see, the time grows exponentially as more characters
and wildcards are added.
I think the worst case of this function could be made a lot faster.
After a wildcard has been reached, there is never any need to
backtrack to a previous wildcard. I'll probably implement such
an algorithm in ELinks, for use with OpenSSL.
Alternatively, I suppose you could just reject the whole pattern
if it has more than ten wildcards. :)
pgpqTVeOgA4Ff.pgp
Description: PGP signature
- _gnutls_hostname_compare: exponential slowdown with multiple wildcards,
Kalle Olavi Niemitalo <=