|
Message-ID: <20220326165217.GA10836@thinkstation.cmpxchg8b.net> 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.