Bug 727624 (CVE-2011-2895) - CVE-2011-2895 BSD compress LZW decoder buffer overflow
Summary: CVE-2011-2895 BSD compress LZW decoder buffer overflow
Keywords:
Status: CLOSED ERRATA
Alias: CVE-2011-2895
Product: Security Response
Classification: Other
Component: vulnerability
Version: unspecified
Hardware: All
OS: Linux
high
high
Target Milestone: ---
Assignee: Red Hat Product Security
QA Contact:
URL:
Whiteboard:
Depends On: 725760 728442 728443 728444 728445 728447 729317 752934 833925
Blocks: 714279
TreeView+ depends on / blocked
 
Reported: 2011-08-02 16:00 UTC by Tomas Hoger
Modified: 2019-09-29 12:46 UTC (History)
5 users (show)

Fixed In Version:
Clone Of:
Environment:
Last Closed: 2015-08-21 22:37:49 UTC
Embargoed:


Attachments (Terms of Use)
4.3BSD compress.c (40.60 KB, text/plain)
2011-08-02 18:14 UTC, Tomas Hoger
no flags Details


Links
System ID Private Priority Status Summary Last Updated
Red Hat Product Errata RHSA-2011:1154 0 normal SHIPPED_LIVE Important: libXfont security update 2011-08-11 21:36:10 UTC
Red Hat Product Errata RHSA-2011:1155 0 normal SHIPPED_LIVE Important: xorg-x11 security update 2011-08-11 21:56:34 UTC
Red Hat Product Errata RHSA-2011:1161 0 normal SHIPPED_LIVE Moderate: freetype security update 2011-08-15 17:49:07 UTC
Red Hat Product Errata RHSA-2011:1834 0 normal SHIPPED_LIVE Important: libXfont security update 2011-12-19 22:51:02 UTC

Description Tomas Hoger 2011-08-02 16:00:47 UTC
BSD compress implemented an LZW compressor and decompressor.  This decompressor implementation did not correctly handle compressed streams that contain code words that were not yet added to the decompression table.  LZW decompression has a special case (a KwKwK string) when code word may match the first free entry in the decompression table.  The implementation used in BSD compress allow code words not only matching, but also exceeding the first free entry.

It seems this compress implementation first appeared in BSD around 1985, and was later used in various other code base, such as ncompress and gzip.  Other components that contain affected code will be listed below.  Following page list the version of the code as was used in 4.3BSD:

http://minnie.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-Reno/src/usr.bin/compress/compress.c

Relevant code appears in the decompress() routine:

	/*
	 * Special case for KwKwK string.
	 */
	if ( code >= free_ent ) {
            *stackp++ = finchar;
	    code = oldcode;
	}

This allows creating a loop in the decompression table, which leads to an "infinite" loop:

	/*
	 * Generate output characters in reverse order
	 */
#ifdef SIGNED_COMPARE_SLOW
	while ( ((unsigned long)code) >= ((unsigned long)256) ) {
#else
	while ( code >= 256 ) {
#endif
	    *stackp++ = tab_suffixof(code);
	    code = tab_prefixof(code);
	}

where tab_prefixof is:

  unsigned short codetab [HSIZE];
  #define codetabof(i)	codetab[i]
  #define tab_prefixof(i)	codetabof(i)

This overflows de_stack "buffer" (part of the htab[]):

  count_int htab [HSIZE];
  # define tab_suffixof(i)	((char_type *)(htab))[i]
  # define de_stack		((char_type *)&tab_suffixof(1<<BITS))

Depending on the relative htab[] and codetab[] positions, de_stack overflow may overwrite codetab[] entries, which may break infinite loop and let program continue its execution with possibly corrupted memory.

Comment 1 Tomas Hoger 2011-08-02 18:13:21 UTC
Following projects embed this BSD compress code and have fixed this issue already, either by aborting compression when code > free_ent is encountered, or by protecting against de_stack overflow in the while loop.

ncompress - code > free_ent check
http://ncompress.git.sourceforge.net/git/gitweb.cgi?p=ncompress/ncompress;a=blob;f=compress.c;h=c16e1239#l1167

gzip - code > free_ent check
http://git.savannah.gnu.org/gitweb/?p=gzip.git;a=blob;f=unlzw.c;h=63f941c6#l297

libarchive - code > free_ent check
http://code.google.com/p/libarchive/source/browse/trunk/libarchive/archive_read_support_filter_compress.c?r=3195#375

busybox's libarchive - code > free_ent check
http://git.busybox.net/busybox/tree/archival/libarchive/decompress_uncompress.c?id=833d4e7f#n220

OpenBSD compress - stack overflow check
http://www.openbsd.org/cgi-bin/cvsweb/src/usr.bin/compress/zopen.c#rev1.17
It seems this fix never made it to other BSDs as FreeBSD or NetBSD.

The version from NetBSD was used in older freetype versions for some time:
http://git.savannah.gnu.org/cgit/freetype/freetype2.git/log/src/lzw/zopen.c
http://git.savannah.gnu.org/cgit/freetype/freetype2.git/tree/src/lzw/zopen.c?id=a1c990a6#n251
freetype version in Red Hat Enterprise Linux 4 (2.1.9) contains the code and is affected by this issue.

libXfont contains affected version of the code too:
http://cgit.freedesktop.org/xorg/lib/libXfont/tree/src/fontfile/decompress.c?id=f29f1d68#n249
More details can be found in bug #725760.

Heirloom mailx / nail lzw.c should be based on FreeBSD code:
http://nail.cvs.sourceforge.net/viewvc/nail/nail/lzw.c?revision=1.4&view=markup#l511
The code is used to compress and decompress imap cache file and spam filter database, and is not used to decompress untrusted inputs.

Comment 2 Tomas Hoger 2011-08-02 18:14:52 UTC
Created attachment 516375 [details]
4.3BSD compress.c

Local copy of the file from:
http://minnie.tuhs.org/cgi-bin/utree.pl?file=4.3BSD-Reno/src/usr.bin/compress/compress.c

Comment 5 Tomas Hoger 2011-08-04 11:37:51 UTC
(In reply to comment #1)
> busybox's libarchive - code > free_ent check
> http://git.busybox.net/busybox/tree/archival/libarchive/decompress_uncompress.c?id=833d4e7f#n220

It seems I was wrong about busybox.  Different code path is used for the first code word.  I'll need to work on additional reproducers to test both code paths.

Comment 8 Tomas Hoger 2011-08-04 18:25:13 UTC
(In reply to comment #5)
> It seems I was wrong about busybox.  Different code path is used for the first
> code word.  I'll need to work on additional reproducers to test both code
> paths.

This problem was previously fixed in ncompress as CVE-2006-1168, see bug #201919.  busybox code based on ncompress.

Comment 12 Tomas Hoger 2011-08-10 18:14:01 UTC
Making this public.

Comment 14 errata-xmlrpc 2011-08-11 21:36:18 UTC
This issue has been addressed in libXfont packages in following products:

  Red Hat Enterprise Linux 5
  Red Hat Enterprise Linux 6

Via RHSA-2011:1154 https://rhn.redhat.com/errata/RHSA-2011-1154.html

Comment 15 errata-xmlrpc 2011-08-11 21:56:44 UTC
This issue has been addressed in xorg-x11 packages in following products:

  Red Hat Enterprise Linux 4

Via RHSA-2011:1155 https://rhn.redhat.com/errata/RHSA-2011-1155.html

Comment 16 errata-xmlrpc 2011-08-15 17:49:13 UTC
This issue has been addressed in freetype packages in following products:

  Red Hat Enterprise Linux 4

Via RHSA-2011:1161 https://rhn.redhat.com/errata/RHSA-2011-1161.html

Comment 17 errata-xmlrpc 2011-12-19 17:52:22 UTC
This issue has been addressed in following products:

  Red Hat Enterprise Linux 5.6.Z - Server Only

Via RHSA-2011:1834 https://rhn.redhat.com/errata/RHSA-2011-1834.html


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