_gnutls_hostname_compare: exponential slowdown with multiple wildcards

[Nikos Mavrogiannopoulos]

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