Lightweight Directory Access Protocol (LDAP) and X.500 Component Matching Rules
Network Working Group S. Legg
Request for Comments: 3687 Adacel Technologies
Category: Standards Track February 2004
Lightweight Directory Access Protocol (LDAP)
and X.500 Component Matching Rules
Status of this Memo
This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
The syntaxes of attributes in a Lightweight Directory Access Protocol
(LDAP) or X.500 directory range from simple data types, such as text
string, integer, or boolean, to complex structured data types, such
as the syntaxes of the directory schema operational attributes.
Matching rules defined for the complex syntaxes usually only provide
the most immediately useful matching capability. This document
defines generic matching rules that can match any user selected
component parts in an attribute value of any arbitrarily complex
attribute syntax.
Legg Standards Track [Page 1]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Conventions. . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. ComponentAssertion . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Component Reference. . . . . . . . . . . . . . . . . . . 6
3.1.1. Component Type Substitutions . . . . . . . . . . 7
3.1.2. Referencing SET, SEQUENCE and CHOICE Components. 8
3.1.3. Referencing SET OF and SEQUENCE OF Components. . 9
3.1.4. Referencing Components of Parameterized Types. . 10
3.1.5. Component Referencing Example. . . . . . . . . . 10
3.1.6. Referencing Components of Open Types . . . . . . 12
3.1.6.1. Open Type Referencing Example . . . . . 12
3.1.7. Referencing Contained Types. . . . . . . . . . . 14
3.1.7.1. Contained Type Referencing Example. . . 14
3.2. Matching of Components . . . . . . . . . . . . . . . . . 15
3.2.1. Applicability of Existing Matching Rules . . . . 17
3.2.1.1. String Matching . . . . . . . . . . . . 17
3.2.1.2. Telephone Number Matching . . . . . . . 17
3.2.1.3. Distinguished Name Matching . . . . . . 18
3.2.2. Additional Useful Matching Rules . . . . . . . . 18
3.2.2.1. The rdnMatch Matching Rule. . . . . . . 18
3.2.2.2. The presentMatch Matching Rule. . . . . 19
3.2.3. Summary of Useful Matching Rules . . . . . . . . 20
4. ComponentFilter. . . . . . . . . . . . . . . . . . . . . . . . 21
5. The componentFilterMatch Matching Rule . . . . . . . . . . . . 22
6. Equality Matching of Complex Components. . . . . . . . . . . . 24
6.1. The OpenAssertionType Syntax . . . . . . . . . . . . . . 24
6.2. The allComponentsMatch Matching Rule . . . . . . . . . . 25
6.3. Deriving Component Equality Matching Rules . . . . . . . 27
6.4. The directoryComponentsMatch Matching Rule . . . . . . . 28
7. Component Matching Examples. . . . . . . . . . . . . . . . . . 30
8. Security Considerations. . . . . . . . . . . . . . . . . . . . 37
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 37
10. IANA Considerations. . . . . . . . . . . . . . . . . . . . . . 37
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 38
11.1. Normative References. . . . . . . . . . . . . . . . . . 38
11.2. Informative References. . . . . . . . . . . . . . . . . 40
12. Intellectual Property Statement. . . . . . . . . . . . . . . . 40
13. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 41
14. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 42
Legg Standards Track [Page 2]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
1. Introduction
The structure or data type of data held in an attribute of a
Lightweight Directory Access Protocol (LDAP) [7] or X.500 [19]
directory is described by the attribute's syntax. Attribute syntaxes
range from simple data types, such as text string, integer, or
boolean, to complex data types, for example, the syntaxes of the
directory schema operational attributes.
In X.500, the attribute syntaxes are explicitly described by Abstract
Syntax Notation One (ASN.1) [13] type definitions. ASN.1 type
notation has a number of simple data types (e.g., PrintableString,
INTEGER, BOOLEAN), and combining types (i.e., SET, SEQUENCE, SET OF,
SEQUENCE OF, and CHOICE) for constructing arbitrarily complex data
types from simpler component types. In LDAP, the attribute syntaxes
are usually described in Augmented Backus-Naur Form (ABNF) [2],
though there is an implied association between the LDAP attribute
syntaxes and the X.500 ASN.1 types. To a large extent, the data
types of attribute values in either an LDAP or X.500 directory are
described by ASN.1 types. This formal description can be exploited
to identify component parts of an attribute value for a variety of
purposes. This document addresses attribute value matching.
With any complex attribute syntax there is normally a requirement to
partially match an attribute value of that syntax by matching only
selected components of the value. Typically, matching rules specific
to the attribute syntax are defined to fill this need. These highly
specific matching rules usually only provide the most immediately
useful matching capability. Some complex attribute syntaxes don't
even have an equality matching rule let alone any additional matching
rules for partial matching. This document defines a generic way of
matching user selected components in an attribute value of any
arbitrarily complex attribute syntax, where that syntax is described
using ASN.1 type notation. All of the type notations defined in
X.680 [13] are supported.
Section 3 describes the ComponentAssertion, a testable assertion
about the value of a component of an attribute value of any complex
syntax.
Section 4 introduces the ComponentFilter assertion, which is an
expression of ComponentAssertions. The ComponentFilter enables more
powerful filter matching of components in an attribute value.
Section 5 defines the componentFilterMatch matching rule, which
enables a ComponentFilter to be evaluated against attribute values.
Legg Standards Track [Page 3]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
Section 6 defines matching rules for component-wise equality matching
of attribute values of any syntax described by an ASN.1 type
definition.
Examples showing the usage of componentFilterMatch are in Section 7.
For a new attribute syntax, the Generic String Encoding Rules [9] and
the specifications in sections 3 to 6 of this document make it
possible to fully and precisely define the LDAP-specific encoding,
the LDAP and X.500 binary encoding (and possibly other ASN.1
encodings in the future), a suitable equality matching rule, and a
comprehensive collection of component matching capabilities, by
simply writing down an ASN.1 type definition for the syntax. These
implicit definitions are also automatically extended if the ASN.1
type is later extended. The algorithmic relationship between the
ASN.1 type definition, the various encodings and the component
matching behaviour makes directory server implementation support for
the component matching rules amenable to automatic code generation
from ASN.1 type definitions.
Schema designers have the choice of storing related items of data as
a single attribute value of a complex syntax in some entry, or as a
subordinate entry where the related data items are stored as separate
attribute values of simpler syntaxes. The inability to search
component parts of a complex syntax has been used as an argument for
favouring the subordinate entries approach. The component matching
rules provide the analogous matching capability on an attribute value
of a complex syntax that a search filter has on a subordinate entry.
Most LDAP syntaxes have corresponding ASN.1 type definitions, though
they are usually not reproduced or referenced alongside the formal
definition of the LDAP syntax. Syntaxes defined with only a
character string encoding, i.e., without an explicit or implied
corresponding ASN.1 type definition, cannot use the component
matching capabilities described in this document unless and until a
semantically equivalent ASN.1 type definition is defined for them.
2. Conventions
Throughout this document "type" shall be taken to mean an ASN.1 type
unless explicitly qualified as an attribute type, and "value" shall
be taken to mean an ASN.1 value unless explicitly qualified as an
attribute value.
Legg Standards Track [Page 4]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
Note that "ASN.1 value" does not mean a Basic Encoding Rules (BER)
[17] encoded value. The ASN.1 value is an abstract concept that is
independent of any particular encoding. BER is just one possible
encoding of an ASN.1 value. The component matching rules operate at
the abstract level without regard for the possible encodings of a
value.
Attribute type and matching rule definitions in this document are
provided in both the X.500 [10] and LDAP [4] description formats.
Note that the LDAP descriptions have been rendered with additional
white-space and line breaks for the sake of readability.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED" and "MAY" in this document are
to be interpreted as described in BCP 14, RFC 2119 [1]. The key word
"OPTIONAL" is exclusively used with its ASN.1 meaning.
3. ComponentAssertion
A ComponentAssertion is an assertion about the presence, or values
of, components within an ASN.1 value, i.e., an instance of an ASN.1
type. The ASN.1 value is typically an attribute value, where the
ASN.1 type is the syntax of the attribute. However, a
ComponentAssertion may also be applied to a component part of an
attribute value. The assertion evaluates to either TRUE, FALSE or
Undefined for each tested ASN.1 value.
A ComponentAssertion is described by the following ASN.1 type
(assumed to be defined with "EXPLICIT TAGS" in force):
ComponentAssertion ::= SEQUENCE {
component ComponentReference (SIZE(1..MAX)) OPTIONAL,
useDefaultValues BOOLEAN DEFAULT TRUE,
rule MATCHING-RULE.&id,
value MATCHING-RULE.&AssertionType }
ComponentReference ::= UTF8String
MATCHING-RULE.&id equates to the OBJECT IDENTIFIER of a matching
rule. MATCHING-RULE.&AssertionType is an open type (formerly known
as the ANY type).
The "component" field of a ComponentAssertion identifies which
component part of a value of some ASN.1 type is to be tested, the
"useDefaultValues" field indicates whether DEFAULT values are to be
substituted for absent component values, the "rule" field indicates
Legg Standards Track [Page 5]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
how the component is to be tested, and the "value" field is an
asserted ASN.1 value against which the component is tested. The
ASN.1 type of the asserted value is determined by the chosen rule.
The fields of a ComponentAssertion are described in detail in the
following sections.
3.1. Component Reference
The component field in a ComponentAssertion is a UTF-8 character
string [6] whose textual content is a component reference,
identifying a component part of some ASN.1 type or value. A
component reference conforms to the following ABNF [2], which extends
the notation defined in Clause 14 of X.680 [13]:
component-reference = ComponentId *( "." ComponentId )
ComponentId = identifier /
from-beginning /
count /
from-end / ; extends Clause 14
content / ; extends Clause 14
select / ; extends Clause 14
all
identifier = lowercase *alphanumeric
*(hyphen 1*alphanumeric)
alphanumeric = uppercase / lowercase / decimal-digit
uppercase = %x41-5A ; "A" to "Z"
lowercase = %x61-7A ; "a" to "z"
hyphen = "-"
from-beginning = positive-number
count = "0"
from-end = "-" positive-number
content = %x63.6F.6E.74.65.6E.74 ; "content"
select = "(" Value *( "," Value ) ")"
all = "*"
positive-number = non-zero-digit *decimal-digit
decimal-digit = %x30-39 ; "0" to "9"
non-zero-digit = %x31-39 ; "1" to "9"
Legg Standards Track [Page 6]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
An conforms to the definition of an identifier in ASN.1
notation (Clause 11.3 of X.680 [13]). It begins with a lowercase
letter and is followed by zero or more letters, digits, and hyphens.
A hyphen is not permitted to be the last character and a hyphen is
not permitted to be followed by another hyphen.
The rule is described by the Generic String Encoding Rules
(GSER) [9].
A component reference is a sequence of one or more ComponentIds where
each successive ComponentId identifies either an inner component at
the next level of nesting of an ASN.1 combining type, i.e., SET,
SEQUENCE, SET OF, SEQUENCE OF, or CHOICE, or a specific type within
an ASN.1 open type.
A component reference is always considered in the context of a
particular complex ASN.1 type. When applied to the ASN.1 type the
component reference identifies a specific component type. When
applied to a value of the ASN.1 type a component reference identifies
zero, one or more component values of that component type. The
component values are potentially in a DEFAULT value if
useDefaultValues is TRUE. The specific component type identified by
the component reference determines what matching rules are capable of
being used to match the component values.
The component field in a ComponentAssertion may also be absent, in
which case the identified component type is the ASN.1 type to which
the ComponentAssertion is applied, and the identified component value
is the whole ASN.1 value.
A valid component reference for a particular complex ASN.1 type is
constructed by starting with the outermost combining type and
repeatedly selecting one of the permissible forms of ComponentId to
identify successively deeper nested components. A component
reference MAY identify a component with a complex ASN.1 type, i.e.,
it is not required that the component type identified by a component
reference be a simple ASN.1 type.
3.1.1. Component Type Substitutions
ASN.1 type notation has a number of constructs for referencing other
defined types, and constructs that are irrelevant for matching
purposes. These constructs are not represented in a component
reference in any way and substitutions of the component type are
performed to eliminate them from further consideration. These
substitutions automatically occur prior to each ComponentId, whether
constructing or interpreting a component reference, but do not occur
after the last ComponentId, except as allowed by Section 3.2.
Legg Standards Track [Page 7]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
If the ASN.1 type is an ASN.1 type reference then the component type
is taken to be the actual definition on the right hand side of the
type assignment for the referenced type.
If the ASN.1 type is a tagged type then the component type is taken
to be the type without the tag.
If the ASN.1 type is a constrained type (see X.680 [13] and X.682
[15] for the details of ASN.1 constraint notation) then the component
type is taken to be the type without the constraint.
If the ASN.1 type is an ObjectClassFieldType (Clause 14 of X.681
[14]) that denotes a specific ASN.1 type (e.g., MATCHING-RULE.&id
denotes the OBJECT IDENTIFIER type) then the component type is taken
to be the denoted type. Section 3.1.6 describes the case where the
ObjectClassFieldType denotes an open type.
If the ASN.1 type is a selection type other than one used in the list
of components for a SET or SEQUENCE type then the component type is
taken to be the selected alternative type from the named CHOICE.
If the ASN.1 type is a TypeFromObject (Clause 15 of X.681 [14]) then
the component type is taken to be the denoted type.
If the ASN.1 type is a ValueSetFromObjects (Clause 15 of X.681 [14])
then the component type is taken to be the governing type of the
denoted values.
3.1.2. Referencing SET, SEQUENCE and CHOICE Components
If the ASN.1 type is a SET or SEQUENCE type then the
form of ComponentId may be used to identify the component type within
that SET or SEQUENCE having that identifier. If
references an OPTIONAL component type and that component is not
present in a particular value then there are no corresponding
component values. If references a DEFAULT component
type and useDefaultValues is TRUE (the default setting for
useDefaultValues) and that component is not present in a particular
value then the component value is taken to be the default value. If
references a DEFAULT component type and useDefaultValues
is FALSE and that component is not present in a particular value then
there are no corresponding component values.
If the ASN.1 type is a CHOICE type then the form of
ComponentId may be used to identify the alternative type within that
CHOICE having that identifier. If references an
alternative other than the one used in a particular value then there
are no corresponding component values.
Legg Standards Track [Page 8]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
The COMPONENTS OF notation in Clause 24 of X.680 [13] augments the
defined list of components in a SET or SEQUENCE type by including all
the components of another defined SET or SEQUENCE type respectively.
These included components are referenced directly by identifier as
though they were defined in-line in the SET or SEQUENCE type
containing the COMPONENTS OF notation.
The SelectionType (Clause 29 of X.680 [13]), when used in the list of
components for a SET or SEQUENCE type, includes a single component
from a defined CHOICE type. This included component is referenced
directly by identifier as though it was defined in-line in the SET or
SEQUENCE type.
The REAL type is treated as though it is the SEQUENCE type defined in
Clause 20.5 of X.680 [13].
The EMBEDDED PDV type is treated as though it is the SEQUENCE type
defined in Clause 33.5 of X.680 [13].
The EXTERNAL type is treated as though it is the SEQUENCE type
defined in Clause 8.18.1 of X.690 [17].
The unrestricted CHARACTER STRING type is treated as though it is the
SEQUENCE type defined in Clause 40.5 of X.680 [13].
The INSTANCE OF type is treated as though it is the SEQUENCE type
defined in Annex C of X.681 [14].
The form MUST NOT be used on any other ASN.1 type.
3.1.3. Referencing SET OF and SEQUENCE OF Components
If the ASN.1 type is a SET OF or SEQUENCE OF type then the
, , and forms of ComponentId
may be used.
The form of ComponentId may be used to identify one
instance (i.e., value) of the component type of the SET OF or
SEQUENCE OF type (e.g., if Foo ::= SET OF Bar, then Bar is the
component type), where the instances are numbered from one upwards.
If references a higher numbered instance than the
last instance in a particular value of the SET OF or SEQUENCE OF type
then there is no corresponding component value.
The form of ComponentId may be used to identify one
instance of the component type of the SET OF or SEQUENCE OF type,
where "-1" is the last instance, "-2" is the second last instance,
Legg Standards Track [Page 9]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
and so on. If references a lower numbered instance than
the first instance in a particular value of the SET OF or SEQUENCE OF
type then there is no corresponding component value.
The form of ComponentId identifies a notional count of the
number of instances of the component type in a value of the SET OF or
SEQUENCE OF type. This count is not explicitly represented but for
matching purposes it has an assumed ASN.1 type of INTEGER (0..MAX).
A ComponentId of the form, if used, MUST be the last
ComponentId in a component reference.
The form of ComponentId may be used to simultaneously identify
all instances of the component type of the SET OF or SEQUENCE OF
type. It is through the form that a component reference can
identify more than one component value. However, if a particular
value of the SET OF or SEQUENCE OF type is an empty list, then there
are no corresponding component values.
Where multiple component values are identified, the remaining
ComponentIds in the component reference, if any, can identify zero,
one or more subcomponent values for each of the higher level
component values.
The corresponding ASN.1 type for the , ,
and forms of ComponentId is the component type of the SET OF or
SEQUENCE OF type.
The , , and forms MUST NOT be
used on ASN.1 types other than SET OF or SEQUENCE OF.
3.1.4. Referencing Components of Parameterized Types
A component reference cannot be formed for a parameterized type
unless the type has been used with actual parameters, in which case
the type is treated as though the DummyReferences [16] have been
substituted with the actual parameters.
3.1.5. Component Referencing Example
Consider the following ASN.1 type definitions.
ExampleType ::= SEQUENCE {
part1 [0] INTEGER,
part2 [1] ExampleSet,
part3 [2] SET OF OBJECT IDENTIFIER,
part4 [3] ExampleChoice }
Legg Standards Track [Page 10]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
ExampleSet ::= SET {
option PrintableString,
setting BOOLEAN }
ExampleChoice ::= CHOICE {
eeny-meeny BIT STRING,
miney-mo OCTET STRING }
Following are component references constructed with respect to the
type ExampleType.
The component reference "part1" identifies a component of a value of
ExampleType having the ASN.1 tagged type [0] INTEGER.
The component reference "part2" identifies a component of a value of
ExampleType having the ASN.1 type of [1] ExampleSet
The component reference "part2.option" identifies a component of a
value of ExampleType having the ASN.1 type of PrintableString. A
ComponentAssertion could also be applied to a value of ASN.1 type
ExampleSet, in which case the component reference "option" would
identify the same kind of information.
The component reference "part3" identifies a component of a value of
ExampleType having the ASN.1 type of [2] SET OF OBJECT IDENTIFIER.
The component reference "part3.2" identifies the second instance of
the part3 SET OF. The instance has the ASN.1 type of OBJECT
IDENTIFIER.
The component reference "part3.0" identifies the count of the number
of instances in the part3 SET OF. The count has the corresponding
ASN.1 type of INTEGER (0..MAX).
The component reference "part3.*" identifies all the instances in the
part3 SET OF. Each instance has the ASN.1 type of OBJECT IDENTIFIER.
The component reference "part4" identifies a component of a value of
ExampleType having the ASN.1 type of [3] ExampleChoice.
The component reference "part4.miney-mo" identifies a component of a
value of ExampleType having the ASN.1 type of OCTET STRING.
Legg Standards Track [Page 11]
RFC 3687 LDAP and X.500 Component Matching Rules February 2004
3.1.6. Referencing Components of Open Types
If a sequence of ComponentIds identifies an ObjectClassFieldType
denoting an open type (e.g., ATTRIBUTE.&Type denotes an open type)
then the ASN.1 type of the component varies. An open type is
typically constrained by some other component(s) in an outer
enclosing type, either formally through the use of a component
relation constraint [15], or informally in the accompanying text, so
the actual ASN.1 type of a value of the open type will generally be
known. The constraint will also limit the range of permissible
types. The