entropy-auth 2026.7.31

//! LDAP search filter (RFC 4511 §4.5.1): BER decode into a [`Filter`] AST +
//! evaluation against an entry's attributes.
//!
//! Matching uses case-insensitive equality/substrings (the common default for
//! directory string attributes); ordering (`>=`/`<=`) is a case-insensitive
//! lexicographic compare. Extensible/approx matching and attribute-specific
//! matching rules are out of scope ([`Filter::Unsupported`], which never
//! matches).
#![allow(clippy::doc_markdown)]

use super::ber::{BerError, Children, parse_tlv};

/// Filter CHOICE context tags (RFC 4511 §4.5.1).
const TAG_AND: u8 = 0xa0;
const TAG_OR: u8 = 0xa1;
const TAG_NOT: u8 = 0xa2;
const TAG_EQUALITY: u8 = 0xa3;
const TAG_SUBSTRINGS: u8 = 0xa4;
const TAG_GE: u8 = 0xa5;
const TAG_LE: u8 = 0xa6;
const TAG_PRESENT: u8 = 0x87;

/// A parsed LDAP search filter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Filter {
    /// Conjunction — all sub-filters must match.
    And(Vec<Filter>),
    /// Disjunction — any sub-filter matches.
    Or(Vec<Filter>),
    /// Negation.
    Not(Box<Filter>),
    /// `(attribute=value)`.
    Equality {
        /// The attribute description.
        attribute: String,
        /// The asserted value.
        value: String,
    },
    /// `(attribute=*)` — the attribute is present.
    Present(String),
    /// `(attribute=initial*any*final)`.
    Substrings {
        /// The attribute description.
        attribute: String,
        /// The leading substring, if any.
        initial: Option<String>,
        /// Zero or more interior substrings, in order.
        any: Vec<String>,
        /// The trailing substring, if any.
        last: Option<String>,
    },
    /// `(attribute>=value)`.
    GreaterOrEqual {
        /// The attribute description.
        attribute: String,
        /// The asserted value.
        value: String,
    },
    /// `(attribute<=value)`.
    LessOrEqual {
        /// The attribute description.
        attribute: String,
        /// The asserted value.
        value: String,
    },
    /// A filter type this implementation does not evaluate (never matches).
    /// A filter choice this codec does not evaluate.
    ///
    /// No longer constructed by [`decode_filter`], which rejects an unknown
    /// choice outright: `Not(Unsupported)` inverted a non-match into a match,
    /// so a negated unsupported filter returned every entry. Retained for
    /// API compatibility and matched as `false` should one ever be built.
    Unsupported,
}

fn octet_str(content: &[u8]) -> String {
    String::from_utf8_lossy(content).into_owned()
}

/// Maximum filter nesting depth. RFC 4511 sets no hard limit, but real
/// directories cap nesting well below this. Bounding it is a security control,
/// not a compatibility choice: the filter is decoded (and later evaluated)
/// recursively, and the LDAP server decodes it *before* the bind check, so an
/// unauthenticated peer could otherwise send a deeply-nested filter that
/// overflows the thread stack — an uncatchable abort of the whole process.
const MAX_FILTER_DEPTH: usize = 32;

/// Maximum total number of filter nodes (leaves + connectives). Depth alone is
/// not enough: a shallow filter can still carry a huge number of siblings (an
/// `And`/`Or` with tens of thousands of leaves, or a long `SEQUENCE OF`), and
/// the decoded AST is later evaluated against *every* directory entry, so an
/// unauthenticated peer could otherwise amplify one ~1 MB request into O(nodes
/// × users) work. Bounding the node count caps that cost.
const MAX_FILTER_NODES: usize = 4096;

/// Decode a filter from its BER `(tag, content)`.
///
/// # Errors
///
/// [`BerError`] on malformed nesting, a truncated assertion, nesting deeper
/// than [`MAX_FILTER_DEPTH`], or more than [`MAX_FILTER_NODES`] total nodes.
pub fn decode_filter(tag: u8, content: &[u8]) -> Result<Filter, BerError> {
    let mut budget = MAX_FILTER_NODES;
    decode_filter_at(tag, content, 0, &mut budget)
}

fn decode_filter_at(
    tag: u8,
    content: &[u8],
    depth: usize,
    budget: &mut usize,
) -> Result<Filter, BerError> {
    if depth > MAX_FILTER_DEPTH {
        return Err(BerError("filter nesting too deep"));
    }
    // SECURITY: charge one unit of the total-node budget per decoded node;
    // reject once it is exhausted (see MAX_FILTER_NODES).
    *budget = budget
        .checked_sub(1)
        .ok_or(BerError("filter has too many nodes"))?;
    match tag {
        TAG_AND => Ok(Filter::And(decode_set(content, depth, budget)?)),
        TAG_OR => Ok(Filter::Or(decode_set(content, depth, budget)?)),
        TAG_NOT => {
            let (t, c, _) = parse_tlv(content)?;
            Ok(Filter::Not(Box::new(decode_filter_at(
                t,
                c,
                depth + 1,
                budget,
            )?)))
        }
        TAG_EQUALITY | TAG_GE | TAG_LE => {
            let (attribute, value) = decode_ava(content)?;
            Ok(match tag {
                TAG_EQUALITY => Filter::Equality { attribute, value },
                TAG_GE => Filter::GreaterOrEqual { attribute, value },
                _ => Filter::LessOrEqual { attribute, value },
            })
        }
        TAG_PRESENT => Ok(Filter::Present(octet_str(content))),
        TAG_SUBSTRINGS => decode_substrings(content),
        // SECURITY: reject rather than decode to a placeholder. `Filter::Not`
        // inverts the `false` an Unsupported node returns into `true`, so
        // negating a filter choice the server cannot evaluate matched EVERY
        // entry instead of none — fail-open on the read path. The server now
        // answers unwillingToPerform for an unsupported choice.
        _ => Err(BerError("unsupported filter type")),
    }
}

fn decode_set(content: &[u8], depth: usize, budget: &mut usize) -> Result<Vec<Filter>, BerError> {
    let mut filters = Vec::new();
    for child in Children::new(content) {
        let (t, c) = child?;
        filters.push(decode_filter_at(t, c, depth + 1, budget)?);
    }
    Ok(filters)
}

/// AttributeValueAssertion: `SEQUENCE { desc OCTET STRING, value OCTET STRING }`
/// — but the two octet strings are the raw content here (context-tagged
/// constructed body), so read them directly.
fn decode_ava(content: &[u8]) -> Result<(String, String), BerError> {
    let (_t1, attr, rest) = parse_tlv(content)?;
    let (_t2, val, _) = parse_tlv(rest)?;
    Ok((octet_str(attr), octet_str(val)))
}

fn decode_substrings(content: &[u8]) -> Result<Filter, BerError> {
    // SubstringFilter ::= SEQUENCE { type, substrings SEQUENCE OF CHOICE }.
    let (_t, attr, rest) = parse_tlv(content)?;
    let (_seq_tag, parts, _) = parse_tlv(rest)?;
    let mut initial = None;
    let mut any = Vec::new();
    let mut last = None;
    for child in Children::new(parts) {
        let (t, c) = child?;
        match t {
            0x80 => initial = Some(octet_str(c)),
            0x81 => any.push(octet_str(c)),
            0x82 => last = Some(octet_str(c)),
            _ => {}
        }
    }
    Ok(Filter::Substrings {
        attribute: octet_str(attr),
        initial,
        any,
        last,
    })
}

impl Filter {
    /// Evaluate the filter against an entry, where `get` returns an attribute's
    /// values (case-insensitive attribute name lookup is the caller's job).
    #[must_use]
    pub fn matches<F>(&self, get: &F) -> bool
    where
        F: Fn(&str) -> Vec<String>,
    {
        match self {
            Filter::And(fs) => fs.iter().all(|f| f.matches(get)),
            Filter::Or(fs) => fs.iter().any(|f| f.matches(get)),
            Filter::Not(f) => !f.matches(get),
            Filter::Present(attr) => !get(attr).is_empty(),
            Filter::Equality { attribute, value } => {
                let v = value.to_lowercase();
                get(attribute).iter().any(|a| a.to_lowercase() == v)
            }
            Filter::GreaterOrEqual { attribute, value } => {
                let v = value.to_lowercase();
                get(attribute).iter().any(|a| a.to_lowercase() >= v)
            }
            Filter::LessOrEqual { attribute, value } => {
                let v = value.to_lowercase();
                get(attribute).iter().any(|a| a.to_lowercase() <= v)
            }
            Filter::Substrings {
                attribute,
                initial,
                any,
                last,
            } => get(attribute).iter().any(|a| {
                let a = a.to_lowercase();
                let mut cursor = 0;
                // Advance `cursor` by the *lowercased* substring's byte length —
                // Unicode case folding is not length-preserving (e.g. 'İ' → 2→3
                // bytes), so advancing by the original length could land mid-char
                // and panic on the next slice.
                if let Some(i) = initial {
                    let i = i.to_lowercase();
                    if !a.starts_with(&i) {
                        return false;
                    }
                    cursor = i.len();
                }
                for part in any {
                    let part = part.to_lowercase();
                    match a[cursor..].find(&part) {
                        Some(idx) => cursor += idx + part.len(),
                        None => return false,
                    }
                }
                if let Some(f) = last {
                    if !a[cursor..].ends_with(&f.to_lowercase()) {
                        return false;
                    }
                }
                true
            }),
            Filter::Unsupported => false,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::super::ber::{encode_octet_string, tlv};
    use super::*;

    fn ava(tag: u8, attr: &str, value: &str) -> Vec<u8> {
        let content = [
            encode_octet_string(attr.as_bytes()),
            encode_octet_string(value.as_bytes()),
        ]
        .concat();
        tlv(tag, &content)
    }

    fn getter(pairs: &'static [(&'static str, &'static str)]) -> impl Fn(&str) -> Vec<String> {
        move |name: &str| {
            pairs
                .iter()
                .filter(|(k, _)| k.eq_ignore_ascii_case(name))
                .map(|(_, v)| (*v).to_string())
                .collect()
        }
    }

    #[test]
    fn equality_and_present() {
        let eq = ava(TAG_EQUALITY, "uid", "bjensen");
        let (t, c, _) = parse_tlv(&eq).unwrap();
        let f = decode_filter(t, c).unwrap();
        assert_eq!(
            f,
            Filter::Equality {
                attribute: "uid".into(),
                value: "bjensen".into()
            }
        );
        let g = getter(&[("uid", "BJensen")]);
        assert!(f.matches(&g)); // case-insensitive
        assert!(
            !Filter::Equality {
                attribute: "uid".into(),
                value: "nope".into()
            }
            .matches(&g)
        );
        assert!(Filter::Present("uid".into()).matches(&g));
        assert!(!Filter::Present("mail".into()).matches(&g));
    }

    #[test]
    fn and_or_not() {
        let inner = [
            ava(TAG_EQUALITY, "uid", "bob"),
            ava(TAG_EQUALITY, "ou", "eng"),
        ]
        .concat();
        let and = tlv(TAG_AND, &inner);
        let (t, c, _) = parse_tlv(&and).unwrap();
        let f = decode_filter(t, c).unwrap();
        let g = getter(&[("uid", "bob"), ("ou", "eng")]);
        assert!(f.matches(&g));
        let g2 = getter(&[("uid", "bob"), ("ou", "sales")]);
        assert!(!f.matches(&g2));
    }

    #[test]
    fn substrings() {
        // (cn=a*b*c)
        let parts = [tlv(0x80, b"a"), tlv(0x81, b"b"), tlv(0x82, b"c")].concat();
        let content = [encode_octet_string(b"cn"), tlv(0x30, &parts)].concat();
        let sub = tlv(TAG_SUBSTRINGS, &content);
        let (t, c, _) = parse_tlv(&sub).unwrap();
        let f = decode_filter(t, c).unwrap();
        assert!(f.matches(&getter(&[("cn", "aXbYc")])));
        assert!(!f.matches(&getter(&[("cn", "aXc")]))); // missing 'b'
        assert!(!f.matches(&getter(&[("cn", "Xbc")]))); // wrong initial
    }

    #[test]
    fn substrings_non_ascii_no_panic() {
        // 'İ' (U+0130) lowercases to "i̇" (3 bytes) — advancing the cursor by the
        // original 2-byte length would slice mid-char and panic. initial+last
        // forces a post-initial slice.
        let f = Filter::Substrings {
            attribute: "cn".into(),
            initial: Some("İ".into()),
            any: Vec::new(),
            last: Some("x".into()),
        };
        assert!(f.matches(&getter(&[("cn", "İx")])));
        assert!(!f.matches(&getter(&[("cn", "İy")])));
    }

    #[test]
    fn rejects_over_deep_nesting() {
        // A chain of NOT wrappers deeper than MAX_FILTER_DEPTH must be rejected
        // rather than recursing (and overflowing the stack).
        let mut buf = ava(TAG_EQUALITY, "uid", "x");
        for _ in 0..(MAX_FILTER_DEPTH + 5) {
            buf = tlv(TAG_NOT, &buf);
        }
        let (t, c, _) = parse_tlv(&buf).unwrap();
        assert!(decode_filter(t, c).is_err());
    }

    #[test]
    fn rejects_too_many_nodes() {
        // A shallow (depth-2) filter that nonetheless carries more leaf nodes
        // than MAX_FILTER_NODES must be rejected before it can be evaluated
        // against every entry.
        let leaves: Vec<u8> = (0..=MAX_FILTER_NODES)
            .flat_map(|_| ava(TAG_EQUALITY, "uid", "x"))
            .collect();
        let and = tlv(TAG_AND, &leaves);
        let (t, c, _) = parse_tlv(&and).unwrap();
        assert!(decode_filter(t, c).is_err());
    }

    #[test]
    fn accepts_node_count_within_limit() {
        // The `And` connective plus (MAX_FILTER_NODES - 1) leaves is exactly at
        // the budget and must decode successfully.
        let leaves: Vec<u8> = (0..MAX_FILTER_NODES - 1)
            .flat_map(|_| ava(TAG_EQUALITY, "uid", "x"))
            .collect();
        let and = tlv(TAG_AND, &leaves);
        let (t, c, _) = parse_tlv(&and).unwrap();
        assert!(decode_filter(t, c).is_ok());
    }

    #[test]
    fn accepts_nesting_within_limit() {
        let mut buf = ava(TAG_EQUALITY, "uid", "x");
        for _ in 0..(MAX_FILTER_DEPTH - 1) {
            buf = tlv(TAG_NOT, &buf);
        }
        let (t, c, _) = parse_tlv(&buf).unwrap();
        assert!(decode_filter(t, c).is_ok());
    }
}