Penetration Testing mailing list archives
Optimal wildcard search algorithm
From: Tim <tim-pentest () sentinelchicken org>
Date: Mon, 27 Nov 2006 13:02:18 -0500
Hello pentesters, I've come across a number of minor injections in applications which allow the speedy brute-forcing of records and/or record fields via wildcards. There are two main language syntaxes where this has come up, namely SQL and LDAP searches. In these syntaxes, the wildcard characters '%' and '*' (respectively) may be used in some contexts to narrow the search space for certain records. For example, I recently ran across an application which permits LDAP injection in a username field, and from this one could brute-force all usernames in the system, given a script and enough time. This particular application would return just enough information to determine whether or not one or more users exist, given some wildcard expression. (In such a scenario, injections of search syntax may of course, allow an attacker to look up all users with particular password hash, which is more interesting, but we'll focus on username brute-forcing for this example.) One approach to finding all usernames would be a kind of breadth-first search based on the character set and character position. Given a character set of [a-z0-9], we could try the following: a* b* c* ... and determine which characters exist in the first position. From there, each second letter would be tried for each successfully identified first letter, and so on. This particular algorithm seems to have bad storage properties, obviously. In addition, there may be steps where more information could be learned up-front to reduce the later searching. For instance, would it be better to start with queries such as: *a* *b* *c* ... in order to eliminate some sub-set of characters from all usernames early in the search? Let us assume for now that the only wildcard character is the '*' or '%' kind (and not the single-character kind), and that the string we're searching for could be of any length. Has anyone else ever pondered the optimal algorithm for something like this, and come up with an answer of some kind? 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)