This service will be undergoing maintenance at 00:00 UTC, 2016-08-01. It is expected to last about 1 hours
Bug 605286 - lynx: crash when parsing overly long links
lynx: crash when parsing overly long links
Status: CLOSED WONTFIX
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
unspecified
All Linux
medium Severity medium
: ---
: ---
Assigned To: Red Hat Product Security
public=20150206,reported=20100613,sou...
: Security
Depends On:
Blocks: 1248116
  Show dependency treegraph
 
Reported: 2010-06-17 11:07 EDT by Vincent Danen
Modified: 2015-08-01 10:36 EDT (History)
7 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2015-08-01 10:36:01 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:


Attachments (Terms of Use)
upstream patch to correct the issue (1.93 KB, patch)
2010-06-17 19:16 EDT, Vincent Danen
no flags Details | Diff
fix for reported issue in 2.8.8rel (unreleased). (6.25 KB, patch)
2010-06-20 20:57 EDT, Thomas E. Dickey
no flags Details | Diff

  None (edit)
Description Vincent Danen 2010-06-17 11:07:15 EDT
A vulnerability was discovered in lynx that would cause the browser to crash when parsing overly long links.

This can be reproduced using:

perl -e 'print "<a href="http://", "\xc3"x1100000, "">link</a>\n"'

or without odd characters:

perl -e 'print "<a href="http://", "x"x5000000, "">link</a>\n"'

Adjust the multiplier to the amount of stack memory you have.

It also looks like there is an integer overflow that can be triggered
with:

perl -e 'print "<a href="http://", "\xc3"x239000000, "">link</a>\n"'

if you have enough memory. Though there's a memcpy following right
after, copying lots of data to mid of the allocated buffer.
Comment 2 Kamil Dudka 2010-06-17 13:04:11 EDT
That's the documented behavior of alloca(3):

    The alloca() function returns a pointer to the beginning of the allocated
    space.  If the allocation causes stack overflow, program behavior is
    undefined.

The whole problem can be reduced to the following minimal example:

#include <alloca.h>
#include <stdlib.h>

int main()
{
    long i;
    for (i = 1; i; i <<=1) {
        printf("0x%x\n", i);
        alloca(i);
    }
    return 0;
}

I propose to solve it like this:

sed -i 's|#define HAVE_ALLOCA 1|/* #undef HAVE_ALLOCA */|' lynx_cfg.h

On the other hand, it can introduce some memory leaks...
Comment 3 Kamil Dudka 2010-06-17 13:06:51 EDT
(In reply to comment #2)
> The whole problem can be reduced to the following minimal example:

Oops, a better one:

#include <alloca.h>
#include <stdio.h>

int main()
{
    long i;
    for (i = 1; i; i <<=1) {
        printf("0x%lx\n", i);
        alloca(i);
    }
    return 0;
}
Comment 6 Vincent Danen 2010-06-17 19:16:38 EDT
Created attachment 424977 [details]
upstream patch to correct the issue

Patch provided by upstream.  This sets the maximum URI size to 8192, using a limit-check to stop page loading.
Comment 7 Tomas Hoger 2010-06-18 02:34:27 EDT
(In reply to comment #2)
> That's the documented behavior of alloca(3):

Right, this alloca behaviour is documented quite well know and yet source of many issues.

> I propose to solve it like this:
> 
> sed -i 's|#define HAVE_ALLOCA 1|/* #undef HAVE_ALLOCA */|' lynx_cfg.h

We can probably use more confined fix that only applies to HTParse.c's LYalloca define.

> On the other hand, it can introduce some memory leaks...

Probably not in HTParse.c, that defines and uses LYfree to, which expands to empty block when using alloca (and free() call when using standard malloc()).

It's probably going to have a performance impact that the use of alloca was supposed to address.  Possible solution to that may be use of some threshold.  If requested size is under that limit, it's ok to use alloca, otherwise use malloc.  glibc uses that, search for __libc_use_alloca and __MAX_ALLOCA_CUTOFF (currently 65536).

(In reply to comment #6)
> Created an attachment (id=424977) [details]
> upstream patch to correct the issue
> 
> Patch provided by upstream.  This sets the maximum URI size to 8192, using a
> limit-check to stop page loading.    

It seems to leave integer overflow issue not addressed.
Comment 8 Thomas E. Dickey 2010-06-18 04:29:45 EDT
Regarding integer overflow, I suppose you mean something
like
    if (need > MAX_URI_SIZE ||
        (int) need < len1 ||
        (int) need < len2)

and
        if (need > MAX_URI_SIZE ||
            (int) need < (p - aName) ||
            (int) need < strlen(p)) {

For anything more sophisticated, I would expect it to be
necessary to filter out long strings earlier in parsing,
or to change datatypes, etc.  (I've been picking away at
that, but don't have a quick fix).
Comment 9 Thomas E. Dickey 2010-06-18 06:34:16 EDT
gcc reminded me that it should be using casts, e.g.,

    if (need > (size_t) max_uri_size ||
        (int) need < (int) len1 ||
        (int) need < (int) len2)

and

        if (need > (size_t) max_uri_size ||
            (int) need < (int) (p - aName) ||
            (int) need < (int) strlen(p)) {
Comment 10 Tomas Hoger 2010-06-18 07:00:29 EDT
I was more thinking of following "standard" checks:

  if (len1 > SIZE_MAX - MIN_PARSE - len2  ||
      len > (SIZE_MAX - len1 - len2) / 2) {

You can use lower limit than SIZE_MAX (such as MAX_URI_SIZE used in the patch) and do an extra check that len2 does not exceed it.

HTParseAnchor should not need integer overflow check assuming aName is properly terminated, as you can't need more than what's already used for aName.
Comment 11 Thomas E. Dickey 2010-06-18 17:09:35 EDT
Using SIZE_MAX as a limit won't help much with the stack overflow.
Comment 12 Thomas E. Dickey 2010-06-20 20:55:18 EDT
I'm working to close out my changes for lynx 2.8.8dev.4 (which
includes the configurable change), and to put out a 2.8.8rel.2
patch (with just the hardcoded change).  I'll attach a copy of
the latter, since it is likely to be useful for backporting.
Comment 13 Thomas E. Dickey 2010-06-20 20:57:04 EDT
Created attachment 425508 [details]
fix for reported issue in 2.8.8rel (unreleased).
Comment 14 Tomas Hoger 2010-06-21 03:02:10 EDT
(In reply to comment #11)
> Using SIZE_MAX as a limit won't help much with the stack overflow.    

Sure, I was more thinking of a solution as mentioned in comment #7 - have a check to avoid integer overflows and independent check to decide whether to use malloc or alloca to allocate memory.

Is MAX_URI_SIZE the right bound for need too?  Such limit transitively implies that len1 and len2 are both less than MAX_URI_SIZE/3.
Comment 15 Thomas E. Dickey 2010-06-21 04:12:35 EDT
MAX_URI_SIZE at 8kb is probably big enough.  The largest value
I found above that was a comment about a 16k limit on fragment
size.  But in the development version, I made it configurable.

Since it is a small value, then the patch in #13 should be
sufficient (for the hardcoded limit) since both len1 and
len2 are less than the limit as well.  Checking all three
values merely ensures that there would not be an overflow
due to one of the components of the expression.
Comment 16 Thomas E. Dickey 2010-06-21 06:58:37 EDT
I released a 2.8.7rel.2 and 2.8.8dev.4 this morning, will
see if additional refinement is needed...
Comment 18 Vincent Danen 2010-06-23 18:07:29 EDT
Using the public reproducer, I can't get Red Hat Enterprise Linux 3 to crash (2.8.5dev.7) but RHEL4 does crash (2.8.5dev.16) so it looks like something may have regressed somewhere between those two versions.

Perhaps it is in 2.8.5dev.13:

* improve performance of HTParse() for very long strings -LP

or in 2.8.5dev.10:

* in HTParse(), use single alloca instead of three malloc/free pairs -LP
Comment 19 Thomas E. Dickey 2010-06-23 18:35:48 EDT
The latter.  That's the first use of alloca() in that file.
It's been a while though: 2002-11-11 (2.8.5dev.10)
Comment 20 Vincent Danen 2010-06-23 18:55:08 EDT
Ok, good to know, thank you.

For all of these issues, there is no possibility of arbitrary code execution, correct?  Just a crash?  (I'm not familiar with alloca() at all, so I'm not sure if this is a straight termination when encountering the overflowed buffer, or if it possible to do something nastier here).
Comment 21 Thomas E. Dickey 2010-06-23 19:24:35 EDT
It might be possible.  Using valgrind, I see several (perhaps a
hundred) incorrect uses of memory before it dies.  The manpage
for alloca() states that its behavior on stack overflow is
undefined.  Two scenarios come to mind: stack overflow which
would produce an illegal address reference, and stack overflow
which gives a pointer to a not-large-enough buffer.  I'm not
seeing the former.  There's no stack guard, so the program can
write onto the return-address area of the stack ("above" the
data).  Presumably someone could design a url that does some
damage (noting that the bytes used are limited by the character
set conventions).
Comment 22 Thomas E. Dickey 2010-06-23 19:28:46 EDT
The point at which it dies is in fact right on the alloca() call.
But the incorrect uses of memory before that point all go away
when the alloca() use is repaired.
Comment 24 Tomas Hoger 2010-06-24 04:36:01 EDT
(In reply to comment #18)
> Using the public reproducer, I can't get Red Hat Enterprise Linux 3 to crash
> (2.8.5dev.7) but RHEL4 does crash (2.8.5dev.16) so it looks like something may
> have regressed somewhere between those two versions.

As Thomas pointed out, version in EL3 does not use alloca, which makes that vector not applicable to it.

Integer overflow issue as affecting EL4+ is not applicable to EL3 either, as it allocates less memory:

  len = strlen(aName) + strlen(relatedName) + 10;

This is non-issue on 32bits, it may be issue on 64bits.  It requires larger input file and more memory, and there may be other constraint elsewhere that may make integer overflow impossible on 64bits too.

(In reply to comment #20)
> For all of these issues, there is no possibility of arbitrary code execution,
> correct?  Just a crash?  (I'm not familiar with alloca() at all, so I'm not
> sure if this is a straight termination when encountering the overflowed
> buffer, or if it possible to do something nastier here).    

I don't remember any case where similar alloca problem was demonstrated to be likely to be used to execute code in cases where alloca is used as:

   dst = alloca(strlen(src));
   strcpy(dst, src);

To make alloca attack useful, you'll need to use it to "allocate" enough memory to bridge unmapped memory gap between heap and stack.  If alloca size is based on the length of some other data already in memory and you fill the buffer right after allocating it, you're quite likely to touch that unmapped memory and crash.

Bad alloca use can be exploited if attacker can control size without need to provide too much data and can make application to only write to first few bytes of the allocated buffer.
Comment 25 Josh Bressers 2010-06-29 11:24:16 EDT
It's even harder that actually. The function in question has to do the huge alloca, write some bits to an arbitrary location in memory, then return from the function. If the stack is too large, you can't make any function calls until the current frame returns fixing the stack pointer to something sane.

The strcpy call will fail not because it's touching memory, but because the current stack pointer is something silly.

I'd call this not a security flaw in the context of lynx. It's certainly a bug, but if you're a user, just don't go back to the page in question.
Comment 26 Tomas Hoger 2010-06-29 11:54:43 EDT
(In reply to comment #25)
> It's even harder that actually. The function in question has to do the huge
> alloca, write some bits to an arbitrary location in memory, then return from
> the function. If the stack is too large, you can't make any function calls
> until the current frame returns fixing the stack pointer to something sane.
> 
> The strcpy call will fail not because it's touching memory, but because the
> current stack pointer is something silly.

It does not have to fail.  alloca changes stack pointer.  If alloca size is sufficient, stack pointer may point to heap memory and hence new stack frame will be created on heap and more functions can still be called.
Comment 27 Kurt Seifried 2015-08-01 10:36:01 EDT
Statement:

This issue affects the versions of lynx as shipped with Red Hat Enterprise Linux 3, 4, 5 and 6. Red Hat Product Security has rated this issue as having Moderate security impact. A future update may address this issue. For additional information, refer to the Issue Severity Classification: https://access.redhat.com/security/updates/classification/.

Note You need to log in before you can comment on or make changes to this bug.