Mastering LDAP Search Filters

The Basics

LDAP is the protocol used to access a Directory. A directory contains entries. Entries are composed of collections of attributes. Attributes are composed of a type, zero or more options, and a value. Attributes can be single-valued or multi-valued. Attributes that are single-valued can only appear once in an entry, multi-valued attributes can appear multiple times but each value must be unique.

An example entry

Below is an example of an entry in an LDAP directory. The primary key of the entry is the uid attribute value user1. In LDAP terms, ou=people is immediately superior to uid=user1. The entry has a cn or commonName, an sn or surName, can contain attributes of the shadowAccount, posixAccount, inetOrgPerson, organizationalPerson, and person objectClasses. The top objectClass appears in every entry, which implies that every entry must contain at least one objectClass.

The entry has a DN (distinguished name) of uid=user1,ou=people,dc=example,dc=com.

The password for the entry is stored in the userPassword attribute value, which in this case is a salted, SHA2 digest of 512 bits. There is also a SHA1 cryptographic hash function, but SHA1 should not be used in mission-critical authentication environments due to known mathematical weaknesses in SHA1.

dn: uid=user1,ou=people,dc=example,dc=com
objectClass: top
objectClass: person
objectClass: organizationalPerson
objectClass: inetOrgPerson
objectClass: posixAccount
objectClass: shadowAccount
uid: user1
cn: Terry Gardner
sn: Gardner
loginShell: /bin/bash
userPassword: {SSHA512}SCMmLlStPIxVtJc8Y6REiGTMsgSEFF7xVQFoYZYg39H0nEeDuK/fWxxNZCdSYlRgJK3U3q0lYTka3Nre2CjXzeNUjbvHabYP
homeDirectory: /home/user1
uidNumber: 1002
gidNumber: 50
shadowLastChange: 15645

Search Parameters

At a minimum, clients must supply the following information to locate an entry in the directory:

The base object, or base DN. The base object is the point in the tree at which the search begins. No objects superior to the base object will be returned in the search
The scope, either base-level, one-level, or subtree. Base-level searches return only the base object, one-level searches search only the immediate subordinates of the base object, and subtree searches can return all objects subordinate to the base object.
a filter; a filter is used to narrow down the search results
a list of attributes to be returned to the client from each entry that matches the search parameters. Attributes are either user attributes (uid, description, etc.) or operational attributes (createTimestamp, modifyTimestamp, etc.). The type of attribute, its syntax, matching rules, and other information is defined in the directory server schema.

Clients can specify a time-limit and a size-limit to the search. In most cases, clients should always supply a size-limit and a time-limit, though these are not required.

Example Searches

The DN is known

When the DN is known to the client:

base object is the DN
scope is base-level
filter is '(&)'
a list of attributes

Note: some broken implementations (notably Sun DSEE in certain versions) fail to support the legal search filter '(&)'. In this case, use the present filter (objectClass=*) to work-around these broken servers and clients.

For example, to retrieve the cn and description attributes from the known DN in the example usign the modern ldapsearch tool:

ldapsearch -h localhost -p 1389 -D cn=RootDN -b uid=user1,ou=people,dc=example,dc=com -s base --sizeLimit 1 --timeLimit 1 '(&)' cn description
Password for user 'cn=RootDN':
dn: uid=user1,ou=people,dc=example,dc=com
cn: Terry Gardner

The same search using the legacy OpenLDAP ldapsearch tool:

ldapsearch -x -LLL -h ldap.example.com -p 1389 -D cn=RootDN -w '{ks8845nnn&&}' -b uid=user1,ou=people,dc=example,dc=com -s base -z 1 -l 1 '(&)' cn description
dn: uid=user1,ou=people,dc=example,dc=com
cn: Terry Gardner

The DN is not known

When the DN is not known to the client, the client must supply parameters sufficient to locate the entry.

The naming context is known

When the client knows the root (naming context) of the directory tree:

the base object is the root of the tree
scope is subtree
filter is '(uid=user1)'
a list of attributes

Example:

ldapsearch -h localhost -p 1389 -D cn=RootDN -b dc=example,dc=com -s sub --sizeLimit 1 --timeLimit 1 --noPropertiesFile '(uid=user1)' cn description
Password for user 'cn=RootDN':
dn: uid=user1,ou=people,dc=example,dc=com
cn: Terry Gardner

A slightly deeper base object could be used if known:

ldapsearch -h localhost -p 1389 -D cn=RootDN -b ou=people,dc=example,dc=com -s sub --sizeLimit 1 --timeLimit 1 --noPropertiesFile '(uid=user1)' cn description
Password for user 'cn=RootDN':
dn: uid=user1,ou=people,dc=example,dc=com
cn: Terry Gardner

About Search Filters

According to RFC4511, the search filter in an LDAP search request “defines the conditions that must be fulfilled in order for the Search to match a given entry”.

The search filter is used to match candidate entries that are in the scope of the search at or below the base object (for one-level search and subtree search). Entries that do not match the search filter are not returned to the LDAP client in the search result. The filter supplied as a parameter to a search request evaluates to true, false, or undefined for each entry in scope (an example of a filter that evaluates to undefined is a filter that contains an attribute that is not known to the directory server). Directory administrators should be made aware of the types of filters before they are used - they might need to index directory attributes to achieve desirable performance results.

Whether a filter matches an entry is determined by the matching rule for the attribute description. Therefore, it is crucial when constructing filters to understand the attribute types and the matching rule associated with the attribute description. There is a common misconception that LDAP data is not case-sensitive, but this does not state the reality correctly. The directory server must perform matching and ordering functions using matching rules and ordering rules, respectively. Some widely used attribute syntaxes like DirectoryString are defined to use the caseIgnoreMatch equality matching rule, which can make it seem to the application that data and searches are not case-sensitive. When an LDAP client requires that a search be case-sensitive, an extensible match filter that specifies the matching rule can be used:

(uid:caseExactMatch:=User.0)

The above filter will match "User.0" but not "user.0". Some broken directory servers do not fully implement the LDAP standards and do not support this useful capability.

The examples use the modern syntax of the ldapsearch command line tool. Users of the legacy OpenLDAP ldapsearch tool will find the syntax somewhat different, but that does not matter, what matters is the filter.

Each assertion in the filter must match the definition of the attribute. For example, the filter '(modifyTimestamp>=0)' would fail because modifyTimestamp has generalized time syntax and the value 0 is not a valid value in generalized time format.

Attributes and Schema Definitions

The following attributes are used in the examples:

name and subtype initials

The attribute type definition for initials:

attributeTypes: ( 2.5.4.43 NAME 'initials' SUP name X-ORIGIN 'RFC 4519' )

This attribute type definition for initials indicates that initials is a subtype of name. The attribute type definition of name is:

attributeTypes: ( 2.5.4.41 NAME 'name' EQUALITY caseIgnoreMatch
  SUBSTR caseIgnoreSubstringsMatch SYNTAX 1.3.6.1.4.1.1466.115.121.1.15{32768}
  X-ORIGIN 'RFC 4519' )

'name' has syntax 'DirectoryString' (1.3.6.1.4.1.1466.115.121.1.15) and a matching rule 'caseIgnoreMatch', hence, the value AEA matches the filter '(initials=aea)'. This syntax is known as 'DirectoryString' and must consist of one or more characters from the Universal Character Set (zero-length Directory Strings are not permitted). Case is folded, that is, not significant.

uid

attributeTypes: ( 0.9.2342.19200300.100.1.1 NAME ( 'uid' 'userid' )
EQUALITY caseIgnoreMatch SUBSTR caseIgnoreSubstringsMatch
SYNTAX 1.3.6.1.4.1.1466.115.121.1.15{256} X-ORIGIN 'RFC 4519' )

This attribute type definition gives the equality matching rule for 'uid' and 'userid' as 'caseIgnoreMatch'. The syntax of 'uid' (and 'userid') is '1.3.6.1.4.1.1466.115.121.1.15'. This syntax is known as 'DirectoryString' and must consist of one or more characters from the Universal Character Set (zero-length Directory Strings are not permitted). Case is folded, that is, not significant.

Types of Filters

LDAP search filters can be broadly classified into the following types:

And

An 'and' filter consists of at least one filter element, and is true if all filter in the set of filters evaluate to true.

ldapsearch --propertiesFilePath ldap-connection.properties \
       --baseDN o=training \
       --searchScope sub '(&(uid=user.0)(initials=aea))' uid initials
dn: uid=user.0,ou=People,o=training
uid: user.0
initials: AEA

note the case-folding of “aea”.

OR

An or filter consists of at least one filter element, and is true is any filter in the set of filters evaluates as true.

ldapsearch --propertiesFilePath ldap-connection.properties \
           --baseDN o=training \
           --searchScope sub \
           --countEntries '(|(uid=user.0)(initials=aea))' uid initials

dn: uid=user.0,ou=People,o=training
uid: user.0
initials: AEA

dn: uid=user.176,ou=People,o=training
uid: user.176
initials: AEA

dn: uid=user.2,ou=People,o=training
uid: user.2
initials: AEA

dn: uid=user.239,ou=People,o=training
uid: user.239
initials: AEA

dn: uid=user.271,ou=People,o=training
uid: user.271
initials: AEA

dn: uid=user.315,ou=People,o=training
uid: user.315
initials: AEA

dn: uid=user.32,ou=People,o=training
uid: user.32
initials: AEA

dn: uid=user.381,ou=People,o=training
uid: user.381
initials: AEA

dn: uid=user.416,ou=People,o=training
uid: user.416
initials: AEA

dn: uid=user.420,ou=People,o=training
uid: user.420
initials: AEA

dn: uid=user.476,ou=People,o=training
uid: user.476
initials: AEA

dn: uid=user.80,ou=People,o=training
uid: user.80
initials: AEA

# Total number of matching entries: 12

NOT

'not' or 'negation' filters must contain one and only one filter element.

There are some commercial software applications (OAM for example) that can be configured to generate illegal not filters containing more than one filter element. If the installation is failing, check for illegal filters.

ldapsearch --hostname localhost \
           --port 11389 \
           --baseDn dc=example,dc=com \
           --searchScope sub --sizeLimit 4 '(!(uid=abc)(obname=*))' 1.1
The provided search filter '(!(uid=abc)(obname=*))' could not be 
decoded because the NOT filter between positions 2 and 21 
did not contain exactly one filter component

Note the illegal filter in the example above.

ldapsearch --hostname localhost --port 11389 \
       --baseDn dc=example,dc=com \
       --searchScope sub --sizeLimit 4 '(!(uid=abc))' 1.1
dn: dc=example,dc=com

dn: uid=admin,dc=example,dc=com

dn: ou=People,dc=example,dc=com

dn: uid=user.0,ou=People,dc=example,dc=com

This search operation has sent the maximum of 4 entries to the client
Result Code:  4 (Size Limit Exceeded)
Diagnostic Message:  This search operation has sent the maximum of 4 entries to the client

This example uses a sizeLimit to limit the number of entries returned to the LDAP client because the filter matches hundreds of thousands of entries in my directory server. From RFC4511:

A size limit that restricts the maximum number of entries to be returned as a result of the
Search.  A value of zero in this field indicates that no client-requested size limit
restrictions are in effect for the Search.  Servers may also enforce a maximum number of
entries to return.

In other words, clients can limit the number of entries returned from a search so as to:

Not overload the server (being a good LDAP citizen)
Not overload the network (being a good network citizen)
Reduce the resources required for the application to execute

The server can also restrict the number of entries returned to clients. Clients must never make assumptions about the number of entries that might be returned or the order in which entries and attributes are returned.

ldapsearch --propertiesFilePath ds-setup/11389/ldap-connection.properties \
  --baseDN o=training \
  --searchScope sub 
  --sizeLimit 4 '(!(initials=aea))' uid initials

dn: o=training

dn: cn=c,o=training

dn: ou=common groups,o=training

dn: cn=a,ou=common groups,o=training

This search operation has sent the maximum of 4 entries to the client
Result Code:  4 (Size Limit Exceeded)
Diagnostic Message:  This search operation has sent the maximum of 4 entries to the client

Equality Match

From RFC4511:

The matching rule for an equalityMatch filter is defined by the
EQUALITY matching rule for the attribute type or subtype.  The filter
is TRUE when the EQUALITY rule returns TRUE as applied to the
attribute or subtype and the asserted value.

ldapsearch --propertiesFilePath ldap-connection.properties \
    --baseDN o=training \
    --searchScope sub '(uid=user.0)' 1.1
dn: uid=user.0,ou=People,o=training

This equality filter, given the syntax of uid and the matching rule caseIgnoreMatch means that the filter will match at least the following values:

User.0
USER.0
uSeR.0

and all other combinations of case-insignificant user.0. The number of characters in the attribute value must match the number characters in the filter assertion. The requested attribute '1.1' is an OID that will never match any attribute type.

Substring

From RFC4511:

There SHALL be at most one 'initial' and at most one 'final' in the
'substrings' of a SubstringFilter.  If 'initial' is present, it SHALL
be the first element of 'substrings'.  If 'final' is present, it
SHALL be the last element of 'substrings'.

The matching rule for an AssertionValue in a substrings filter item
is defined by the SUBSTR matching rule for the attribute type or
subtype.  The filter is TRUE when the SUBSTR rule returns TRUE as
applied to the attribute or subtype and the asserted value.

Note that the AssertionValue in a substrings filter item conforms to
the assertion syntax of the EQUALITY matching rule for the attribute
type rather than to the assertion syntax of the SUBSTR matching rule
for the attribute type.  Conceptually, the entire SubstringFilter is
converted into an assertion value of the substrings matching rule
prior to applying the rule.

ldapsearch --hostname localhost       \
    --port 11389                      \
    --baseDn dc=example,dc=com        \
    --searchScope sub --sizeLimit 4 '(uid=u*)' 1.1
dn: uid=user.0,ou=People,dc=example,dc=com

dn: uid=user.1,ou=People,dc=example,dc=com

dn: uid=user.5,ou=People,dc=example,dc=com

dn: uid=user.6,ou=People,dc=example,dc=com

This search operation has sent the maximum of 4 entries to the client
Result Code:  4 (Size Limit Exceeded)
Diagnostic Message:  This search operation has sent the maximum of 4 entries to the client

The filter '(uid=u*)' matched at least the 4 entries that were returned. Note that a client requested size limit was specified, which is a very good practice.

Greater or Equal

Ordering match.

ldapsearch --hostname localhost       \
    --port 11389                      \
    --baseDn dc=example,dc=com        \
    --searchScope sub --sizeLimit 4 '(uid>=user.0)' 1.1
dn: uid=user.1,ou=People,dc=example,dc=com

dn: uid=user.5,ou=People,dc=example,dc=com

dn: uid=user.6,ou=People,dc=example,dc=com

dn: uid=user.11,ou=People,dc=example,dc=com

This search operation has sent the maximum of 4 entries to the client
Result Code:  4 (Size Limit Exceeded)

Less or Equal