Home page logo

pen-test logo 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

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:


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:


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?


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.

  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]