[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 26 Mar 2022 09:52:17 -0700
From: Tavis Ormandy <taviso@...il.com>
To: oss-security@...ts.openwall.com
Subject: Re: zlib memory corruption on deflate (i.e. compress)
On Fri, Mar 25, 2022 at 08:59:35AM -0500, John Helmert III wrote:
>
> CVE-2018-25032 appears to have been assigned for it now.
>
Thanks, I've made some progress working on the bug. I've got a nice
clean repro for Z_FIXED strategy. To hit the bug, you need to force
lots of worst-case (distance, length) pairs.
Zlib keeps a rolling hash of every 3 bytes of input, then uses this to
find previous matches and then see how long they are. Here is a good
explainer:
https://www.euccas.me/zlib/#zlib_hash_chain
The longest possible back-reference is 31 bits, starting at
(distance=16385, length=131).
The trick I found to force those is to use a de Bruijn sequence with
alphabet length cbrt(2^windowBits) and word length 3 (3 because that's
MIN_MATCH in zlib). Now there is a match of arbitrary length at every
single offset that can't be RLE'd away. So you generate one
2^windowsBits block of this sequence, then repeat the same sequence but
shuffle the subwords (lyndon words? I might be using the wrong
terminology).
I've attached a minimal C compressor, and an input that triggers the
bug. It should trigger ASAN and (if it doesn't crash) produces garbage
output that doesn't inflate into a matching input.
(Let me know if you want my C code to generate the input)
Repro:
$ gcc deflate.c -o deflate libz.a
$ deflate < CVE-2018-25032.txt
trees.c:1091:20: runtime error: index 734 out of bounds for type 'uch [512]'
trees.c:1091:20: runtime error: load of address 0x7f862280c27e with insufficient space for an object of type 'const uch'
0x7f862280c27e: note: pointer points here
19 19 19 19 19 19 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a 1a
^
=================================================================
==8534==ERROR: AddressSanitizer: global-buffer-overflow on address 0x7f862280c1ac at pc 0x7f86227f1b86 bp 0x7ffff6711bd0 sp 0x7ffff6711bc0
READ of size 1 at 0x7f862280c1ac thread T0
#0 0x7f86227f1b85 in compress_block zlib/zlib-1.2.11-orig/trees.c:1091
#1 0x7f86227ecdb2 in _tr_flush_block zlib/zlib-1.2.11-orig/trees.c:979
#2 0x7f86227cf310 in deflate_slow zlib/zlib-1.2.11-orig/deflate.c:2011
#3 0x7f86227b9b90 in deflate zlib/zlib-1.2.11-orig/deflate.c:1003
#4 0x7f86227a8849 in main (/home/taviso/deflate+0x95849)
#5 0x7f86211540b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b2)
#6 0x7f86227a848d in _start (/home/taviso/deflate+0x9548d)
0x7f862280c1ac is located 12 bytes to the right of global variable '_dist_code' defined in 'trees.h:73:25' (0x7f862280bfa0) of size 512
0x7f862280c1ac is located 20 bytes to the left of global variable '_length_code' defined in 'trees.h:102:25' (0x7f862280c1c0) of size 256
SUMMARY: AddressSanitizer: global-buffer-overflow trees.c:1091 in compress_block
If it doesn't crash, You can use the zpipe utility to verify that the
generated compressed data is garbage.
One question remains - does this *only* affect Z_FIXED, or also
Z_DEFAULT_STRATEGY? It seems plausible this also affects
Z_DEFAULT_STRATEGY, because of this condition:
https://github.com/madler/zlib/blob/master/trees.c#L976
} else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
That is, if the optimal and static trees are the same size, then zlib
*chooses* the Z_FIXED strategy anyway. I don't know if this is
practically possible yet, I'm investigating but if someone smarter than
me already knows the answer please let me know!
IMHO, this is a pretty bad bug - but if it is impossible to reach with
Z_DEFAULT_STRATEGY, then at least there's no need to panic, as Z_FIXED
is usually only used in special circumstances...
If it possible, well... uh-oh.
Tavis.
--
_o) $ lynx lock.cmpxchg8b.com
/\\ _o) _o) $ finger taviso@....org
_\_V _( ) _( ) @taviso
View attachment "CVE-2018-25032.txt" of type "text/plain" (32768 bytes)
View attachment "deflate.c" of type "text/x-csrc" (828 bytes)
Powered by blists - more mailing lists
Please check out the
Open Source Software Security Wiki, which is counterpart to this
mailing list.
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
