From: Rogan Dawes (discard@dawes.za.net)
Date: Wed Nov 29 2006 - 20:02:04 EST
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
------------------------------------------------------------------------
This archive was generated by hypermail 2.1.7 : Sat Apr 12 2008 - 10:57:24 EDT