Penetration Testing mailing list archives
Re: Optimal wildcard search algorithm
From: Tim <tim-pentest () sentinelchicken org>
Date: Tue, 28 Nov 2006 09:18:36 -0500
Do I understand correctly, that the wildcard test you describe only gives an exists/doesn't exist answer? How many tests can you afford per second?
Yes, the attack would be somewhat blind, resulting in yes/no or yes/no/error responses. For instance, if this were a login form using LDAP, it might return success for a proper username/password combination, failure for a nonexistent username or bad password, and an error for a wildcarded username that does exist but can't be bound to, since there's no injection in the LDAP bind request.
What you can try is to analyse some sample username lists for ways to equalise their distribution. For example, you wouldn't want to start with a*, better jump directly to aa*, ab*, ..., az*
You think starting with 2-character prefixes is actually faster? It doesn't seem that way to me. In the worst case for a single character test, you need to make 36+36*m, where m is the number of successful results from the first round. If you start with 2-character tuples, you'll always need to perform 36*36 tests to get to the same point in the search, which is certainly slower on average.
You might try taking samples from http://www.galbithink.org/names/agnames.htm http://blogs.parc.com/playon/archives/2006/06/naming_patterns.html or similar, some username/password combo lists, etc. You can also test for suffixes (*a, *b, ..) hoping for a better distribution.
Indeed, I think using common names, or even just starting with the most probable characters would speed up the initial findings. This is very useful if your goal is simply to find one or a few usernames. However, if you want to find them all, it probably doesn't help much. Besides, the general algorithm I seek would be useable on other fields. Take for example, the following ldap injections: *)(userPassword=A* *)(userPassword=B* ... If an LDAP server isn't properly secured, this could allow one to brute-force all password hashes using just the blind responses. Password hashes wouldn't have predictable distribution. Similar situations may exist in SQL injections as well, though there's probably easier attacks in that situation.
If you're allowed single-char wildcards, you could do more interesting searches - tests for certain username lengths being the most important. You can also walk the search space based on the *second* letter of the username _a%, _b% etc, which will (I guess) be more equally distributed than the first letter.
Indeed, with single-character wildcards, a lot of additional information can be divulged. In fact, one could determine the length range of all strings right off, which would make it easy to determine when we're "done". I didn't want to complicate the question by introducing these though.
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 ------------------------------------------------------------------------ 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 ------------------------------------------------------------------------
Current thread:
- Optimal wildcard search algorithm Tim (Nov 27)
- Re: Optimal wildcard search algorithm Sir Mordred (Nov 28)
- Re: Optimal wildcard search algorithm Tim (Nov 28)
- Re: Optimal wildcard search algorithm Andres Riancho (Nov 29)
- Re: Optimal wildcard search algorithm Tim (Nov 28)
- Re: Optimal wildcard search algorithm Sir Mordred (Nov 28)