[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: _gnutls_hostname_compare: exponential slowdown with multiple wildcar
From: |
Nikos Mavrogiannopoulos |
Subject: |
Re: _gnutls_hostname_compare: exponential slowdown with multiple wildcards |
Date: |
Thu, 05 May 2011 22:31:55 +0200 |
User-agent: |
Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.14) Gecko/20110223 Thunderbird/3.1.8 |
On 05/03/2011 11:25 PM, Kalle Olavi Niemitalo wrote:
> 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. :)
Ouch. I think something like 6 might be quite realistic. Thank you for
reporting that.
regards,
Nikos