1package ldap
2
3import (
4 "bytes"
5 "errors"
6 "fmt"
7
8 ber "github.com/go-asn1-ber/asn1-ber"
9)
10
11const (
12 maxFilterDepth = 16
13 maxFilterNodes = 256
14 maxAssertionBytes = 1024
15 maxAssertionsBytes = 16384
16)
17
18var (
19 errMalformedFilter = errors.New("malformed filter")
20 errFilterLimit = errors.New("filter exceeds limits")
21)
22
23const (
24 filterAnd ber.Tag = 0
25 filterOr ber.Tag = 1
26 filterNot ber.Tag = 2
27 filterEquality ber.Tag = 3
28 filterSubstrings ber.Tag = 4
29 filterGreaterOrEqual ber.Tag = 5
30 filterLessOrEqual ber.Tag = 6
31 filterPresent ber.Tag = 7
32 filterApprox ber.Tag = 8
33 filterExtensible ber.Tag = 9
34)
35
36const (
37 substringInitial ber.Tag = 0
38 substringAny ber.Tag = 1
39 substringFinal ber.Tag = 2
40)
41
42const (
43 extensibleRule ber.Tag = 1
44 extensibleType ber.Tag = 2
45 extensibleValue ber.Tag = 3
46 extensibleDN ber.Tag = 4
47)
48
49type FilterExpr struct {
50 root *filterNode
51}
52
53type filterNode struct {
54 kind ber.Tag
55 children []*filterNode
56 attr string
57 rule *attrRule
58 value []byte
59 substrings []substring
60 matchingRule string
61 hasRule bool
62 dnAttributes bool
63}
64
65type substring struct {
66 kind ber.Tag
67 value []byte
68}
69
70func Copy(p *ber.Packet) (FilterExpr, error) {
71 var c copier
72 root, err := c.filter(p, 1)
73 if err != nil {
74 return FilterExpr{}, err
75 }
76 return FilterExpr{root: root}, nil
77}
78
79type copier struct {
80 nodes int
81 bytes int
82}
83
84func malformed(format string, args ...any) error {
85 return fmt.Errorf("%w: %s", errMalformedFilter, fmt.Sprintf(format, args...))
86}
87
88func limitExceeded(format string, args ...any) error {
89 return fmt.Errorf("%w: %s", errFilterLimit, fmt.Sprintf(format, args...))
90}
91
92func (c *copier) filter(p *ber.Packet, depth int) (*filterNode, error) {
93 if p == nil {
94 return nil, malformed("missing filter")
95 }
96 if depth > maxFilterDepth {
97 return nil, limitExceeded("depth exceeds %d", maxFilterDepth)
98 }
99 c.nodes++
100 if c.nodes > maxFilterNodes {
101 return nil, limitExceeded("more than %d nodes", maxFilterNodes)
102 }
103 if p.ClassType != ber.ClassContext {
104 return nil, malformed("filter class %#x is not context-specific", uint8(p.ClassType))
105 }
106 switch p.Tag {
107 case filterAnd, filterOr:
108 return c.set(p, depth)
109 case filterNot:
110 if err := isConstructed(p, "not"); err != nil {
111 return nil, err
112 }
113 if len(p.Children) != 1 {
114 return nil, malformed("not has %d children", len(p.Children))
115 }
116 child, err := c.filter(p.Children[0], depth+1)
117 if err != nil {
118 return nil, err
119 }
120 return &filterNode{kind: filterNot, children: []*filterNode{child}}, nil
121 case filterEquality, filterGreaterOrEqual, filterLessOrEqual, filterApprox:
122 return c.assertion(p)
123 case filterSubstrings:
124 return c.substrings(p)
125 case filterPresent:
126 content, err := primitiveContent(p, ber.ClassContext, filterPresent, "present")
127 if err != nil {
128 return nil, err
129 }
130 attr, err := attributeDescription(content)
131 if err != nil {
132 return nil, err
133 }
134 return &filterNode{kind: filterPresent, attr: attr, rule: lookupAttribute(attr)}, nil
135 case filterExtensible:
136 return c.extensible(p)
137 }
138 return nil, malformed("unknown filter tag %d", uint64(p.Tag))
139}
140
141func (c *copier) set(p *ber.Packet, depth int) (*filterNode, error) {
142 if err := isConstructed(p, "and/or"); err != nil {
143 return nil, err
144 }
145 if len(p.Children) == 0 {
146 return nil, malformed("empty and/or")
147 }
148 n := &filterNode{kind: p.Tag}
149 for _, child := range p.Children {
150 k, err := c.filter(child, depth+1)
151 if err != nil {
152 return nil, err
153 }
154 n.children = append(n.children, k)
155 }
156 return n, nil
157}
158
159func (c *copier) assertion(p *ber.Packet) (*filterNode, error) {
160 if err := isConstructed(p, "attribute value assertion"); err != nil {
161 return nil, err
162 }
163 if len(p.Children) != 2 {
164 return nil, malformed("attribute value assertion has %d children", len(p.Children))
165 }
166 attr, err := describedAttribute(p.Children[0])
167 if err != nil {
168 return nil, err
169 }
170 content, err := primitiveContent(p.Children[1], ber.ClassUniversal, ber.TagOctetString, "assertion value")
171 if err != nil {
172 return nil, err
173 }
174 value, err := c.value(content)
175 if err != nil {
176 return nil, err
177 }
178 return &filterNode{kind: p.Tag, attr: attr, rule: lookupAttribute(attr), value: value}, nil
179}
180
181func (c *copier) substrings(p *ber.Packet) (*filterNode, error) {
182 if err := isConstructed(p, "substrings"); err != nil {
183 return nil, err
184 }
185 if len(p.Children) != 2 {
186 return nil, malformed("substrings has %d children", len(p.Children))
187 }
188 attr, err := describedAttribute(p.Children[0])
189 if err != nil {
190 return nil, err
191 }
192 seq := p.Children[1]
193 if seq == nil || seq.ClassType != ber.ClassUniversal || seq.TagType != ber.TypeConstructed || seq.Tag != ber.TagSequence {
194 return nil, malformed("substrings components are not a SEQUENCE")
195 }
196 if len(seq.Children) == 0 {
197 return nil, malformed("substrings without components")
198 }
199 n := &filterNode{kind: filterSubstrings, attr: attr, rule: lookupAttribute(attr)}
200 last := len(seq.Children) - 1
201 for i, comp := range seq.Children {
202 if comp == nil || comp.ClassType != ber.ClassContext || comp.TagType != ber.TypePrimitive {
203 return nil, malformed("substrings component %d is not a context-specific primitive", i)
204 }
205 switch {
206 case comp.Tag == substringInitial && i != 0:
207 return nil, malformed("substrings initial at position %d", i)
208 case comp.Tag == substringFinal && i != last:
209 return nil, malformed("substrings final at position %d", i)
210 case comp.Tag > substringFinal:
211 return nil, malformed("unknown substrings component tag %d", uint64(comp.Tag))
212 }
213 content, err := primitiveContent(comp, ber.ClassContext, comp.Tag, "substrings component")
214 if err != nil {
215 return nil, err
216 }
217 if len(content) == 0 {
218 return nil, malformed("empty substrings component at position %d", i)
219 }
220 value, err := c.value(content)
221 if err != nil {
222 return nil, err
223 }
224 n.substrings = append(n.substrings, substring{kind: comp.Tag, value: value})
225 }
226 return n, nil
227}
228
229func (c *copier) extensible(p *ber.Packet) (*filterNode, error) {
230 if err := isConstructed(p, "extensibleMatch"); err != nil {
231 return nil, err
232 }
233 n := &filterNode{kind: filterExtensible}
234 hasValue := false
235 var previous ber.Tag
236 for i, field := range p.Children {
237 if field == nil {
238 return nil, malformed("extensibleMatch field %d missing", i)
239 }
240 if field.Tag < extensibleRule || field.Tag > extensibleDN || (i > 0 && field.Tag <= previous) {
241 return nil, malformed("extensibleMatch field tag %d out of order", uint64(field.Tag))
242 }
243 previous = field.Tag
244 content, err := primitiveContent(field, ber.ClassContext, field.Tag, "extensibleMatch field")
245 if err != nil {
246 return nil, err
247 }
248 switch field.Tag {
249 case extensibleRule:
250 n.matchingRule = string(content)
251 n.hasRule = true
252 case extensibleType:
253 attr, err := attributeDescription(content)
254 if err != nil {
255 return nil, err
256 }
257 n.attr = attr
258 case extensibleValue:
259 value, err := c.value(content)
260 if err != nil {
261 return nil, err
262 }
263 n.value = value
264 hasValue = true
265 case extensibleDN:
266 if len(content) != 1 {
267 return nil, malformed("extensibleMatch dnAttributes is %d bytes", len(content))
268 }
269 n.dnAttributes = content[0] != 0
270 }
271 }
272 if !hasValue {
273 return nil, malformed("extensibleMatch without matchValue")
274 }
275 if !n.hasRule && n.attr == "" {
276 return nil, malformed("extensibleMatch without matchingRule or type")
277 }
278 return n, nil
279}
280
281func (c *copier) value(content []byte) ([]byte, error) {
282 if len(content) > maxAssertionBytes {
283 return nil, limitExceeded("assertion value of %d bytes exceeds %d", len(content), maxAssertionBytes)
284 }
285 c.bytes += len(content)
286 if c.bytes > maxAssertionsBytes {
287 return nil, limitExceeded("assertion values exceed %d bytes", maxAssertionsBytes)
288 }
289 return bytes.Clone(content), nil
290}
291
292func isConstructed(p *ber.Packet, what string) error {
293 if p.TagType != ber.TypeConstructed {
294 return malformed("%s is not constructed", what)
295 }
296 return nil
297}
298
299func primitiveContent(p *ber.Packet, class ber.Class, tag ber.Tag, what string) ([]byte, error) {
300 if p == nil || p.ClassType != class || p.TagType != ber.TypePrimitive || p.Tag != tag {
301 return nil, malformed("%s has the wrong tag", what)
302 }
303 if len(p.Children) != 0 || p.Data == nil {
304 return nil, malformed("%s has no primitive content", what)
305 }
306 return p.Data.Bytes(), nil
307}
308
309func describedAttribute(p *ber.Packet) (string, error) {
310 content, err := primitiveContent(p, ber.ClassUniversal, ber.TagOctetString, "attribute description")
311 if err != nil {
312 return "", err
313 }
314 return attributeDescription(content)
315}
316
317func attributeDescription(b []byte) (string, error) {
318 parts := bytes.Split(b, []byte{';'})
319 if !validOID(parts[0]) {
320 return "", malformed("invalid attribute description")
321 }
322 for _, option := range parts[1:] {
323 if len(option) == 0 || !allKeychars(option) {
324 return "", malformed("invalid attribute description")
325 }
326 }
327 return string(b), nil
328}
329
330func validOID(b []byte) bool {
331 if len(b) == 0 {
332 return false
333 }
334 if isAlpha(b[0]) {
335 return allKeychars(b)
336 }
337 numbers := bytes.Split(b, []byte{'.'})
338 if len(numbers) < 2 {
339 return false
340 }
341 for _, number := range numbers {
342 if len(number) == 0 || (len(number) > 1 && number[0] == '0') {
343 return false
344 }
345 for _, d := range number {
346 if !isDigit(d) {
347 return false
348 }
349 }
350 }
351 return true
352}
353
354func allKeychars(b []byte) bool {
355 for _, ch := range b {
356 if !isAlpha(ch) && !isDigit(ch) && ch != '-' {
357 return false
358 }
359 }
360 return true
361}
362
363func isAlpha(ch byte) bool { return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') }
364
365func isDigit(ch byte) bool { return '0' <= ch && ch <= '9' }
366
367func (f FilterExpr) encode() *ber.Packet {
368 if f.root == nil {
369 return nil
370 }
371 return f.root.encode()
372}
373
374func (f FilterExpr) canonical() []byte {
375 p := f.encode()
376 if p == nil {
377 return nil
378 }
379 return p.Bytes()
380}
381
382func (n *filterNode) encode() *ber.Packet {
383 switch n.kind {
384 case filterAnd, filterOr, filterNot:
385 p := ber.Encode(ber.ClassContext, ber.TypeConstructed, n.kind, nil, "")
386 for _, child := range n.children {
387 p.AppendChild(child.encode())
388 }
389 return p
390 case filterEquality, filterGreaterOrEqual, filterLessOrEqual, filterApprox:
391 p := ber.Encode(ber.ClassContext, ber.TypeConstructed, n.kind, nil, "")
392 p.AppendChild(octetString(n.attr))
393 p.AppendChild(octetString(string(n.value)))
394 return p
395 case filterSubstrings:
396 seq := ber.Encode(ber.ClassUniversal, ber.TypeConstructed, ber.TagSequence, nil, "")
397 for _, s := range n.substrings {
398 seq.AppendChild(ber.NewString(ber.ClassContext, ber.TypePrimitive, s.kind, string(s.value), ""))
399 }
400 p := ber.Encode(ber.ClassContext, ber.TypeConstructed, filterSubstrings, nil, "")
401 p.AppendChild(octetString(n.attr))
402 p.AppendChild(seq)
403 return p
404 case filterPresent:
405 return ber.NewString(ber.ClassContext, ber.TypePrimitive, filterPresent, n.attr, "")
406 }
407 p := ber.Encode(ber.ClassContext, ber.TypeConstructed, filterExtensible, nil, "")
408 if n.hasRule {
409 p.AppendChild(ber.NewString(ber.ClassContext, ber.TypePrimitive, extensibleRule, n.matchingRule, ""))
410 }
411 if n.attr != "" {
412 p.AppendChild(ber.NewString(ber.ClassContext, ber.TypePrimitive, extensibleType, n.attr, ""))
413 }
414 p.AppendChild(ber.NewString(ber.ClassContext, ber.TypePrimitive, extensibleValue, string(n.value), ""))
415 if n.dnAttributes {
416 p.AppendChild(ber.NewLDAPBoolean(ber.ClassContext, ber.TypePrimitive, extensibleDN, true, ""))
417 }
418 return p
419}
420
421func octetString(s string) *ber.Packet {
422 return ber.NewString(ber.ClassUniversal, ber.TypePrimitive, ber.TagOctetString, s, "")
423}