remote DoS via CPU exhaustion in anon FTP server glob expansion

[Russ Cox <rsc () swtch com>]

Essentially all Unix shells and many popular programming languages use
an exponential-time algorithm to decide whether a glob pattern matches
a particular file name. For example, on my Linux system, matching
a*a*a*a*a*a*a*a*b unsuccessfully against a file name consisting of 100
a's takes half an hour using Java 8 and 15 minutes using BSD libc's
glob(3) function.

If an attacker can control the pattern used against even moderately
sized file names (40 characters would be fine), a single failed
pattern match against a single file name can easily consume
hours of CPU.

This can happen in anonymous FTP servers, creating a possible remote
DoS attack.

Affected:
- tnftpd, a fork of the NetBSD ftpd, as shipped with macOS 10.12.4 and earlier
- Pure-FTPd 1.0.36

Possibly affected:
- standard ftpd on BSD-based systems

Not affected:
- netkit ftpd 0.17, if run on Linux
- ProFTPD 1.3.5
- vsftpd 3.0.2

On the language side, C on BSD and macOS systems, Java, Perl, and Tcl
implement glob pattern-matching with an exponential-time algorithm.
Code passing untrusted glob patterns to those implementations would
also be affected. Because BSD libc is affected, I expect that most of
the standard *BSD ftpd implementations are affected as well, but I have
not tested them.

C on Linux systems (using GNU glibc), Go, Ruby, and Rust implement
glob pattern-matching with a linear-time algorithm. Code passing
untrusted glob patterns to those implementations should be unaffected.

This problem is not CVE-2001-1501, nor CVE-2010-2632, nor
CVE-2015-5917, all of which are about patterns matching many files.
In this case, the pattern matches no files.

The closest previous report is CVE-2005-0256 (CPU problems caused by
repeated adjacent stars), which is a special case of the underlying
general problem here.

Due to the widespread but limited ("only" CPU exhaustion) nature of
the problem, I have not attempted any embargoed prenotification.
I will forward this note directly to product-security () apple com and
bugs () pureftpd org. I filled out the "DWF Open Source Request Form v2"
for a CVE number for the generic problem, and I will reply here when
I receive the number.

In addition to fixing the matching algorithms, I would suggest that
all FTP implementations impose CPU time limits on individual FTP
sessions to guard against future problems and consider removing glob
support entirely. I would also suggest that affected sites consider
not running anonymous FTP servers.

More details at https://research.swtch.com/glob.

Russ Cox
rsc () swtch com