Internet Bug Bounty: Regexes with large repetitions on empty sub-expressions take a very long time to parse

Rust’s regex crate guarantees a linear time complexity with regex length for compilation of untrusted regexes. However, existing mitigations for known malicious regexes are based on memory usage and, as such, do not mitigate repetitions of empty sub-expressions. For example, the following payload triggers such an issue:

(?:){4294967295}

This will cause the regex compiler to attempt to create 4294967295 instances of an empty sub-expression, which will ultimately allocate zero bytes and therefore bypass existing memory-based mitigations. This can be further weaponised to create an exponential time complexity with regex length by using repetitions of repetitions, e.g.:

(?:){64}{64}{64}{64}{64}{64}

This payload would cause the regex compiler to attempt to create 64^6 instances of an empty sub-expression.

Impact

An attacker can induce a CPU time-based denial of service with effectively infinite CPU time, which would cause the service to become entirely unavailable.