Re: Optimal wildcard search algorithm

[Rogan Dawes <discard () dawes za net>]

Tim wrote:

> > I don't know if searching for substrings in the middle hoping they
> > would prune the search tree will be helpful - but you can analyze
> > those sample lists and see if particular patterns come up. If there is
> > a good set of 2 or 3 character strings that have near-zero frequencies
> > in the sample lists, that's the way to go.
>
> Yes, one of my burning questions is to figure out whether mid-string
> checks can be beneficial.  Multi-character mid-string searches are
> likely a bad idea, for the same reasons I described above.
>
> While I appreciate the ideas you've suggested, I'm really looking for a
> more formal answer to the optimality question.
>
> thanks,
> tim

Well, let's consider the effort vs the reward of performing a character 
set search. Note that I am only suggesting a single character match, not 
a multi-character match here.

Say our potential character set is 52 characters [a-zA-Z], and the space 
that we are prepared to brute force is up to 8 characters long.

Then to brute force the entire space, we would need to perform 52^8 tests.

If we can reduce the character set by doing an initial pass of

*a*, *b*, *c*, etc,

and establish that we are only matching say 30 out of 52 characters, we 
can narrow our search space dramatically: now 30^8

Even if we are not able to narrow the search space at all (i.e. ALL 52 
characters are in use), all we have done is "waste" 52 tests. In the 
scale of the number of tests that we could save just by eliminating 1 
character (according to Google: (52^8) - (51^8) = 7.69178396 × 10^12), 
I'd suggest that that is a VERY valuable tradeoff.

In the case of the password hashes, of course, we are unlikely to be 
able to eliminate anything, since hopefully, the hashes are distributed 
uniformly, and so the (hex-)characters should statistically have an 
equal distribution too.

Rogan

------------------------------------------------------------------------
This List Sponsored by: Cenzic

Need to secure your web apps?
Cenzic Hailstorm finds vulnerabilities fast.
Click the link to buy it, try it or download Hailstorm for FREE.
http://www.cenzic.com/products_services/download_hailstorm.php?camp=701600000008bOW
------------------------------------------------------------------------