Matching Rules for Constructed Syntaxes

["Steven Legg" <[e-mail]>]

LDAPers and PKIXers,

The LDAP ACI model and PKIX both have to deal with attribute syntaxes
that are complex constructed types. Matching rules for those syntaxes
have recently been discussion topics so it seems like a good time to
describe some ideas for matching rules that have been kicking around
in the back of my head for a while. First I'll address the question of
an equality matching rule for ldapACI and then go on to describe some
generic matching rules for complex syntaxes that would be useful to
both LDAP access control and PKIX, among other things.

One approach for ldapACI is the X.500 solution where a DirectoryString
label has been made a component of the ACI and the
directoryStringFirstComponentMatch matching rule is used to decide the
equality of two ACIs. This satisfies some basic requirements to be
able to match ACIs but the equality of two ACI values doesn't really
say anything about them at the semantic level.

Back when I was with Telstra we defined a catch-all equality matching rule
that could do a comparison of two attribute values of any arbitrary
ASN.1 syntax. This rule, or something like it, could be used as the
equality matching rule for the ldapACI attribute. The X.500 style
definition is simply this:

asn1Match MATCHING-RULE ::= {
	ID			{ 1 3 32 0 1 13 0 } }

Since no assertion syntax is specified, the syntax is inherited at
run time from the attribute type to which the matching rule is applied.
So the assertion syntax would be LdapACI if asn1Match is used to match
against the ldapACI attribute.

I have a slight problem defining this matching rule in LDAP terms because
the string encoding for MatchingRuleDescription doesn't allow an absent
SYNTAX.

This matching rule evaluates to true if and only if the attribute value
and the assertion value have the same components with the same values.

If the syntax is a SEQUENCE or SET type then each component in
the assertion value must match each component of the attribute value.
Optional components must be either both present or both absent.

If the syntax is a SEQUENCE OF then the attribute value and the
assertion value must have the same instances (members)
in the same order.

If the syntax is a SET OF then the attribute value and the assertion
value must have the same instances (and the same duplicates),
but order doesn't matter.

If the syntax is a CHOICE then the attribute value and the assertion value
must use the same CHOICE alternative.

The rules apply recursively to nested constructed types.

The primitive types like OBJECT IDENTIFIER, BOOLEAN, INTEGER, etc
match as one would expect. The string types are just matched character
for character.


The asn1Match rule would be fine as the equality matching rule for the
ldapACI attribute and would have much the same effect as was intended
by the original use of caseIgnoreMatch and DirectoryString syntax.
However, where there is a complex constructed syntax there is usually
a desire to selectively match only some of the components, e.g. to
match ACIs with a specific subject, or with specific rights.
What usually happens is that a bunch of new matching rules are defined
to cover the anticipated needs. Just look at X.509 and PKI for examples.

Rather than going down this path I would like to suggest a generic
way of selectively matching components in arbitrary syntaxes.
The following matching rule is something I've often thought about
implementing but haven't as yet.

componentMatch MATCHING-RULE ::= {
	SYNTAX		ComponentAssertion
	ID			<to be supplied>
}

ComponentAssertion ::= SEQUENCE {
	component	[0] PrintableString,
	rule		[1] MATCHING-RULE.&id, -- MatchingRuleId
	value		[2] MATCHING-RULE.&AssertionType -- AssertionValue
}

The idea here is that the component field identifies which part of a
value of a constructed syntax is to be matched, the rule indicates how that
part is to be matched, and the value is what that part is matched against.

X.680, section 12 already describes a way to reference the components
of an arbitrary ASN.1 type but it hasn't got a BER encoding so I'm just
stuffing it as text into a PrintableString.

Basically the component referencing string is a series of "." separated
componentIds where a componentId is usually the ASN.1 identifier for
the component. The componentId can also be a positive number to reference
a particular instance in a SET OF or SEQUENCE OF, "*" to reference
all the instances in a SET OF or SEQUENCE OF, or the number zero,
which is a conceptual count of the number of instances.

An example should make this clearer. First, here is the ASN.1 definition
of the syntax of the objectClasses schema attribute (not to be confused
with the objectClass attribute), so that I have something reasonably
familiar to base examples on.

ObjectClassDescription ::= SEQUENCE {
	identifier		OBJECT-CLASS.&id,
	name			SET OF DirectoryString { ub-schema } OPTIONAL,
	description		DirectoryString { ub-schema } OPTIONAL,
	obsolete		BOOLEAN DEFAULT FALSE,
	information	[0]	ObjectClassInformation
}

ObjectClassInformation	::=	SEQUENCE {
	subclassOf		SET OF OBJECT-CLASS.&id OPTIONAL,
	kind			ObjectClassKind DEFAULT structural,
	mandatories	[3]	SET OF ATTRIBUTE.&id OPTIONAL,
	optionals	[4]	SET OF ATTRIBUTE.&id OPTIONAL
}

OBJECT-CLASS.&id and ATTRIBUTE.&id are equivalent to the OBJECT IDENTIFIER
ASN.1 type.

So for a given value with the ObjectClassDescription syntax (i.e. a
value of the objectClasses attribute) ...

"identifier" references the OID of the object class description,
"description" references the text description of the object class,
"name.*" references all of the object class's names,
"name.0" gives the number of names defined for the object class,
"name.1" references the first of those names,
"information" references the whole ObjectClassInformation nested SEQUENCE,
"information.kind" references the ObjectClassKind in the nested SEQUENCE,
"information.mandatories.*" references all the mandatory attribute types
	for the object class

... and so on.

Each referenced component has a specific ASN.1 type. For example,
"identifier" is of type OBJECT IDENTIFIER and "name.1" is of type
DirectoryString. The type of "information.mandatories" is
SET OF OBJECT IDENTIFIER but the corresponding type for
"information.mandatories.*" I'll take to be OBJECT IDENTIFIER
(the instance type of the SET OF). The ".0" instance counts I'll assume
to be INTEGER.

Now that I've got a way to reference components I need to say how they
are matched. I could specify a new bunch of rules for different kinds
of matching on different ASN.1 types but it is convenient to just use
existing attribute matching rules. Each matching rule has a notional
set of attribute syntaxes (typically one), defined as ASN.1 types, to
which it may be applied. When embedded in a ComponentAssertion these
matching rules apply to the same ASN.1 types, only in this context the
types aren't necessarily attribute syntaxes. So the "identifier"
component of an objectClasses attribute value could be matched with
objectIdentifierMatch. The "name.*" component (instances) could be
matched with caseIgnoreMatch, caseExactMatch, caseIgnoreOrderingMatch,
or even caseIgnoreSubstringMatch. Any component, regardless of its
ASN.1 type could be matched by the asn1Match rule. The assertion value
that goes with the chosen matching rule will be of the syntax required
by that rule.

Because constructed types can have CHOICEs and OPTIONAL fields it is
possible that the referenced component does not exist in an attribute value.
In these cases the matching rule would evaluate to false.


Now for a few example filters using the componentMatch matching rule.
I don't want to go to the trouble of defining complete ABNF right
now so I'm using a string encoding that is a mix of ASN.1 value notation,
which I trust is verbose enough to be sufficiently clear, and LDAP string
encodings for well known ASN.1 types. I've put in spacing and line breaks
only as an aid to readability. The example search filters are mostly
single extensible match filter items, though of course there is no
reason why componentMatch can't be used in more complicated search filters.

To find the object class definition for the object class called
foobar use the filter:

(objectClasses:componentMatch:={
	component "names.*",
	rule caseIgnoreMatch,
	value "foobar" })

An object class definition can have multiple names and the above filter
will match an objectClasses value if any one of the names is "foobar".

To find all obsolete object classes use:

(objectClasses:componentMatch:={
	component "obsolete",
	rule booleanMatch,
	value TRUE })

To find all subclasses of "person" use:

(objectClasses:componentMatch:={
	component "information.subclassOf.*",
	rule objectIdentifierMatch,
	value person })

To find the object class definition for 2.5.6.18 use:

(objectClasses:componentMatch:={
	component "identifier",
	rule objectIdentifierMatch,
	value 2.5.6.18 })

A match on the "identifier" component of objectClasses values
is equivalent to the objectIdentifierFirstComponentMatch matching
rule applied to this attribute type. The componentMatch matching rule
subsumes the objectIdentifierFirstComponentMatch, integerFirstComponentMatch
and directoryStringFirstComponentMatch matching rules.

To find all values of the ldapACI attribute that have my DN in the subject
field I could use (refer to draft-ietf-ldapext-acl-model-06.txt for the
ASN.1 type definition of the ldapACI syntax):

(ldapACI:componentMatch:={
	component "subject.dn",
	rule distinguishedNameMatch,
	value "cn=Steven Legg, o=Adacel, c=au" })

The subject component is a CHOICE of which "dn" is one of several
possibilities. Those values with a different choice won't match the
filter item.

To find all ACIs that apply to the commonName attribute:

(ldapACI:componentMatch:=
	{ component "attr.attributes.*", rule objectIdentifierMatch, value cn })


The componentMatch rule allows any one component in a constructed value
to be matched but there are often good reasons to want to match more than
one component in the same constructed value. This is particularly true
for the matching of certificates and related constructs in PKIX.
Most, if not all, of the desired functionality could be achieved
with the following matching rule whose assertion syntax is a filter
of component matches.

componentFilterMatch MATCHING-RULE ::= {
	SYNTAX		ComponentFilter
	ID			<to be supplied>
}

ComponentFilter ::= CHOICE {
	item		[0] ComponentAssertion,
	and			[1] SEQUENCE OF ComponentFilter,
	or			[2] SEQUENCE OF ComponentFilter,
	not			[3] ComponentFilter
}

The component filter is evaluated over a single attribute value rather
than a whole entry. Note that a matching rule like this gives us the same
capability for matching components of a constructed syntax that a regular
search filter would give us had the constructed syntax been exploded out
as a set of attributes of simpler syntaxes in a subordinate entry.

The observant will notice that componentMatch is a special case of
componentFilterMatch so we don't really need componentMatch.

Here are some example search filters using the componentFilterMatch
matching rule.

To find all object class definitions that reference the commonName
AND surname attributes as mandatory attributes use:

(objectClasses:componentFilterMatch:=and:{
		item:{ component "information.mandatories.*",
			rule objectIdentifierMatch, value cn },
		item:{ component "information.mandatories.*",
			rule objectIdentifierMatch, value sn } })

To find all object class definitions that reference the commonName
AND surname attributes as either mandatory OR optional attributes:

(objectClasses:componentFilterMatch:=and:{
	or:{
		item:{ component "information.mandatories.*",
			rule objectIdentifierMatch, value cn },
		item:{ component "information.optionals.*",
			rule objectIdentifierMatch, value cn }
	},
	or:{
		item:{ component "information.mandatories.*",
			rule objectIdentifierMatch, value sn },
		item:{ component "information.optionals.*",
			rule objectIdentifierMatch, value sn }
	}
})

The next example is inspired by Sean Mullan.

Sean Mullan wrote:
> What happens if you want to define a matching rule to only retrieve certs
> that contain a specific basic constraints value AND a certain issuer name?
In
> this case, you would define 2 matching rules and specify both of them in
> the valuesReturnFilter control. But then you would get all certs with the
> requested issuer name and any basic constraints value and all certs with
> any issuer name and the requested basic constraints value. That's not
> what you wanted. I think we may want to enhance the valuesReturnFilter
> control (through a flag, perhaps) to allow the user to apply all of the
> elements of the filter to each attribute value. Let's discuss this more
> offline, if you like.

Here is a component filter match on a specific value of basic constraints
AND a certain issuer name:

(userCertificate:componentFilterMatch:=and:{
	item:{ component "extensions.*", rule asn1Match,
		value { extnId 2.5.29.19, extnValue '3003020102'H } },
	item:{ component "issuer.rdnSequence", rule distinguishedNameMatch,
		value "cn=CA, o=Adacel, c=au" } })

2.5.29.19 is the OID for the basicConstraints extension. Unfortunately
the extension value (extnValue) is defined to be a DER encoding wrapped
in an OCTET STRING (ugh!).

In the above example it was particularly convenient to use the
asn1Match rule to match the whole extension, i.e.
{ extnId 2.5.29.19, extnValue '3003020102'H }, in one hit, instead
of writing a nested "and" filter of each of the components of
the extension. The asn1Match rule is essentially a short hand
for an "and" component filter specifying every component.


I can imagine situations where it would be useful to test not only if
a *specific* value of a particular component is present but whether *any*
value of a particular component is present. Hence the following
matching rule:

presentMatch MATCHING-RULE ::= {
	SYNTAX		NULL
	ID			<to be supplied>
}

When used on an attribute in a extensible match filter item it behaves
like the present case of a regular search filter. In a ComponentAssertion
it evaluates to true if and only if the referenced component exists.

To find object class definitions that have descriptions use:

(objectClasses:componentMatch:=
	{ component "description", rule presentMatch, NULL })

To find object class definitions that don't have descriptions use:

(objectClasses:componentFilterMatch:=
	not:item:{ component "description", rule presentMatch, NULL })

To find the object class definitions that are not marked as obsolete
(the "obsolete" component is absent, or is present and set to FALSE):

(objectClasses:componentFilterMatch:=or:{
	not:item:{ component "obsolete", rule presentMatch, NULL },
	item:{ component "obsolete", rule booleanMatch, FALSE } })


The DistinguishedName and RelativeDistinguishedName ASN.1 types are
also constructed types so the component matching rules could be
applied to them.

For convenience, here is the stripped down ASN.1 type for DNs.

DistinguishedName ::= SEQUENCE OF RelativeDistinguishedName

RelativeDistinguishedName ::= SET OF AttributeTypeAndValue

AttributeTypeAndValue ::= SEQUENCE {
	type		AttributeType, -- OBJECT IDENTIFIER
	value		AttributeValue -- ANY }

To find all seeAlso attributes (DN syntax) containing the RDN "o=Adacel"
use:

(seeAlso:componentMatch:=
	{ component "*", rule componentFilterMatch, value
		and:{
			item:{ component "0", rule integerMatch, value 1 },
			item:{ component "*", rule asn1Match, value
				{ type o, value "Adacel" } }
		}
	})

This assertion tests each RDN (referenced by the first "*") to see if
it has exactly one AVA (the count is given by "0") with attribute type
organization and value "Adacel".

Since RDNs appear all over the place it makes sense to define a
matching rule that can make RDN matching more concise.

rdnMatch MATCHING-RULE ::= {
	SYNTAX		RelativeDistinguishedName
	ID			<to be supplied>
}

The rdnMatch rule evaluates to true if the component value and assertion
value are the same RDN.

Now the above example to find all seeAlso attributes containing the
RDN "o=Adacel" becomes:

(seeAlso:componentMatch:={ component "*", rule rdnMatch, value "o=Adacel" })

The rdnMatch can be useful wherever DNs appear. To find all values of the
ldapACI attribute that have "o=Adacel" somewhere in the DN in the subject
field use:

(ldapACI:componentMatch:=
	{ component "subject.dn.*", rule rdnMatch, value "o=Adacel" })

To find all seeAlso values with "o=Adacel, c=au" as a "suffix"
(noting that the string encoding of LDAPDN puts the RDNs in
reverse order) use:

(seeAlso:componentFilterMatch:=and:{
	item:{ component "1", rule rdnMatch, value "c=au" },
	item:{ component "2", rule rdnMatch, value "o=Adacel" } })

There's a case for being able to specify a match against the last component,
or second last component, etc, but we'd have to invent a syntax for that.


Okay, so what do people think ? The value of componentFilterMatch and
friends is that they implicitly define a bunch of useful matching rule
semantics for a new attribute syntax the moment the ASN.1 type is
written down, and are automatically extended if the ASN.1 type is later
extended. We might never need to define another matching rule for a
constructed syntax. What would be missing though is a definition of
the string encoding, so having a predictable way of generating the
ABNF from the ASN.1 type would be particularly valuable. For the examples
above I didn't formally define the string encoding for ComponentAssertion
and ComponentFilter, themselves constructed types, but I was consistently
following a set of rules. Those rules would be my preferred solution
for algorithmically derived string encodings for new attribute and assertion
syntaxes.

Since the componentFilterMatch is generally useful, and can be applied
to any ASN.1 type, it makes more sense for me to write it up as a separate
Internet draft under the auspices of LDAPEXT, rather than incorporating
its definition into either the LDAP ACL model or the PKIX LDAP schema.
So is there support out there for me to go ahead and write this up as
an ID ? Will LDAP access control and PKIX make use of it ?

Regards,
Steven