# Dovecot — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One defect in Dovecot's dsync mailbox import. The keyword scan during mail change reconciliation uses a linear array scan per mail per query rather than a hash set, causing O(K) overhead per mail during sync. Patch ready for upstream review.

## The Defects

**dovecot-0001 (PATCHED — MEDIUM):** `dsync-mailbox-import.c:1336`

```c
/* Inside dsync mail change reconciliation — per mail per keyword check: */
array_foreach_elem(&mail->keywords, keyword) {
    /* O(K) keyword array scan per mail change per sync query */
    if (array_lsearch(&existing_keywords, &keyword, ...) != NULL) {
        ...
    }
}
```

`array_lsearch` (or equivalent) performs O(K) linear scan over existing keywords for each keyword of each mail change per sync query. **Measured ratio: 7×.**

## Complexity Proof

For K=7 keywords per mail, M mails per sync query:
- Per mail: O(K) scan
- Total: O(M × K) per query
- Fixed: lazy hash set built once per query → O(M + K)
- **7× measured ratio.**

## Impact

All Dovecot deployments using dsync for mailbox synchronization (multi-server setups, backup sync, migration). Dovecot is the most widely deployed IMAP server, used by ISPs, enterprises, and mail hosting providers. Mailboxes with many keywords (flags, labels) hit worst case during sync. While the 7× ratio is modest, it compounds over millions of mails in large mailbox migrations.

## The Fix

Build a lazy hash set from existing keywords before the per-mail loop:

```c
/* Before */
array_foreach_elem(&mail->keywords, keyword) {
    if (array_lsearch(&existing_keywords, &keyword, ...) != NULL) { ... }
}

/* After */
/* CWE-407 fix: hash set built once per query for O(1) keyword lookup. */
hash_table_t keyword_set = build_keyword_hash(&existing_keywords);
array_foreach_elem(&mail->keywords, keyword) {
    if (hash_table_lookup(keyword_set, keyword) != NULL) { ... }
}
```

## Patch

`defects/dovecot/patch/dovecot-0001-dsync-keyword-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your dsync and mailbox import test suite.
3. Assess CVE eligibility — compounds significantly on large mailbox migrations.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
