1CVE: CVE-2018-25032 2Upstream-Status: Backport 3Signed-off-by: Ross Burton <ross.burton@arm.com> 4 5From 5c44459c3b28a9bd3283aaceab7c615f8020c531 Mon Sep 17 00:00:00 2001 6From: Mark Adler <madler@alumni.caltech.edu> 7Date: Tue, 17 Apr 2018 22:09:22 -0700 8Subject: [PATCH] Fix a bug that can crash deflate on some input when using 9 Z_FIXED. 10 11This bug was reported by Danilo Ramos of Eideticom, Inc. It has 12lain in wait 13 years before being found! The bug was introduced 13in zlib 1.2.2.2, with the addition of the Z_FIXED option. That 14option forces the use of fixed Huffman codes. For rare inputs with 15a large number of distant matches, the pending buffer into which 16the compressed data is written can overwrite the distance symbol 17table which it overlays. That results in corrupted output due to 18invalid distances, and can result in out-of-bound accesses, 19crashing the application. 20 21The fix here combines the distance buffer and literal/length 22buffers into a single symbol buffer. Now three bytes of pending 23buffer space are opened up for each literal or length/distance 24pair consumed, instead of the previous two bytes. This assures 25that the pending buffer cannot overwrite the symbol table, since 26the maximum fixed code compressed length/distance is 31 bits, and 27since there are four bytes of pending space for every three bytes 28of symbol space. 29--- 30 deflate.c | 74 ++++++++++++++++++++++++++++++++++++++++--------------- 31 deflate.h | 25 +++++++++---------- 32 trees.c | 50 +++++++++++-------------------------- 33 3 files changed, 79 insertions(+), 70 deletions(-) 34 35diff --git a/deflate.c b/deflate.c 36index 425babc00..19cba873a 100644 37--- a/deflate.c 38+++ b/deflate.c 39@@ -255,11 +255,6 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 40 int wrap = 1; 41 static const char my_version[] = ZLIB_VERSION; 42 43- ushf *overlay; 44- /* We overlay pending_buf and d_buf+l_buf. This works since the average 45- * output size for (length,distance) codes is <= 24 bits. 46- */ 47- 48 if (version == Z_NULL || version[0] != my_version[0] || 49 stream_size != sizeof(z_stream)) { 50 return Z_VERSION_ERROR; 51@@ -329,9 +324,47 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 52 53 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 54 55- overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 56- s->pending_buf = (uchf *) overlay; 57- s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 58+ /* We overlay pending_buf and sym_buf. This works since the average size 59+ * for length/distance pairs over any compressed block is assured to be 31 60+ * bits or less. 61+ * 62+ * Analysis: The longest fixed codes are a length code of 8 bits plus 5 63+ * extra bits, for lengths 131 to 257. The longest fixed distance codes are 64+ * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest 65+ * possible fixed-codes length/distance pair is then 31 bits total. 66+ * 67+ * sym_buf starts one-fourth of the way into pending_buf. So there are 68+ * three bytes in sym_buf for every four bytes in pending_buf. Each symbol 69+ * in sym_buf is three bytes -- two for the distance and one for the 70+ * literal/length. As each symbol is consumed, the pointer to the next 71+ * sym_buf value to read moves forward three bytes. From that symbol, up to 72+ * 31 bits are written to pending_buf. The closest the written pending_buf 73+ * bits gets to the next sym_buf symbol to read is just before the last 74+ * code is written. At that time, 31*(n-2) bits have been written, just 75+ * after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at 76+ * 8*n bits into pending_buf. (Note that the symbol buffer fills when n-1 77+ * symbols are written.) The closest the writing gets to what is unread is 78+ * then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and 79+ * can range from 128 to 32768. 80+ * 81+ * Therefore, at a minimum, there are 142 bits of space between what is 82+ * written and what is read in the overlain buffers, so the symbols cannot 83+ * be overwritten by the compressed data. That space is actually 139 bits, 84+ * due to the three-bit fixed-code block header. 85+ * 86+ * That covers the case where either Z_FIXED is specified, forcing fixed 87+ * codes, or when the use of fixed codes is chosen, because that choice 88+ * results in a smaller compressed block than dynamic codes. That latter 89+ * condition then assures that the above analysis also covers all dynamic 90+ * blocks. A dynamic-code block will only be chosen to be emitted if it has 91+ * fewer bits than a fixed-code block would for the same set of symbols. 92+ * Therefore its average symbol length is assured to be less than 31. So 93+ * the compressed data for a dynamic block also cannot overwrite the 94+ * symbols from which it is being constructed. 95+ */ 96+ 97+ s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4); 98+ s->pending_buf_size = (ulg)s->lit_bufsize * 4; 99 100 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 101 s->pending_buf == Z_NULL) { 102@@ -340,8 +373,12 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 103 deflateEnd (strm); 104 return Z_MEM_ERROR; 105 } 106- s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 107- s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 108+ s->sym_buf = s->pending_buf + s->lit_bufsize; 109+ s->sym_end = (s->lit_bufsize - 1) * 3; 110+ /* We avoid equality with lit_bufsize*3 because of wraparound at 64K 111+ * on 16 bit machines and because stored blocks are restricted to 112+ * 64K-1 bytes. 113+ */ 114 115 s->level = level; 116 s->strategy = strategy; 117@@ -552,7 +589,7 @@ int ZEXPORT deflatePrime (strm, bits, value) 118 119 if (deflateStateCheck(strm)) return Z_STREAM_ERROR; 120 s = strm->state; 121- if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) 122+ if (s->sym_buf < s->pending_out + ((Buf_size + 7) >> 3)) 123 return Z_BUF_ERROR; 124 do { 125 put = Buf_size - s->bi_valid; 126@@ -1113,7 +1150,6 @@ int ZEXPORT deflateCopy (dest, source) 127 #else 128 deflate_state *ds; 129 deflate_state *ss; 130- ushf *overlay; 131 132 133 if (deflateStateCheck(source) || dest == Z_NULL) { 134@@ -1133,8 +1169,7 @@ int ZEXPORT deflateCopy (dest, source) 135 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 136 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 137 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 138- overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 139- ds->pending_buf = (uchf *) overlay; 140+ ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4); 141 142 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 143 ds->pending_buf == Z_NULL) { 144@@ -1148,8 +1183,7 @@ int ZEXPORT deflateCopy (dest, source) 145 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 146 147 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 148- ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 149- ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 150+ ds->sym_buf = ds->pending_buf + ds->lit_bufsize; 151 152 ds->l_desc.dyn_tree = ds->dyn_ltree; 153 ds->d_desc.dyn_tree = ds->dyn_dtree; 154@@ -1925,7 +1959,7 @@ local block_state deflate_fast(s, flush) 155 FLUSH_BLOCK(s, 1); 156 return finish_done; 157 } 158- if (s->last_lit) 159+ if (s->sym_next) 160 FLUSH_BLOCK(s, 0); 161 return block_done; 162 } 163@@ -2056,7 +2090,7 @@ local block_state deflate_slow(s, flush) 164 FLUSH_BLOCK(s, 1); 165 return finish_done; 166 } 167- if (s->last_lit) 168+ if (s->sym_next) 169 FLUSH_BLOCK(s, 0); 170 return block_done; 171 } 172@@ -2131,7 +2165,7 @@ local block_state deflate_rle(s, flush) 173 FLUSH_BLOCK(s, 1); 174 return finish_done; 175 } 176- if (s->last_lit) 177+ if (s->sym_next) 178 FLUSH_BLOCK(s, 0); 179 return block_done; 180 } 181@@ -2170,7 +2204,7 @@ local block_state deflate_huff(s, flush) 182 FLUSH_BLOCK(s, 1); 183 return finish_done; 184 } 185- if (s->last_lit) 186+ if (s->sym_next) 187 FLUSH_BLOCK(s, 0); 188 return block_done; 189 } 190diff --git a/deflate.h b/deflate.h 191index 23ecdd312..d4cf1a98b 100644 192--- a/deflate.h 193+++ b/deflate.h 194@@ -217,7 +217,7 @@ typedef struct internal_state { 195 /* Depth of each subtree used as tie breaker for trees of equal frequency 196 */ 197 198- uchf *l_buf; /* buffer for literals or lengths */ 199+ uchf *sym_buf; /* buffer for distances and literals/lengths */ 200 201 uInt lit_bufsize; 202 /* Size of match buffer for literals/lengths. There are 4 reasons for 203@@ -239,13 +239,8 @@ typedef struct internal_state { 204 * - I can't count above 4 205 */ 206 207- uInt last_lit; /* running index in l_buf */ 208- 209- ushf *d_buf; 210- /* Buffer for distances. To simplify the code, d_buf and l_buf have 211- * the same number of elements. To use different lengths, an extra flag 212- * array would be necessary. 213- */ 214+ uInt sym_next; /* running index in sym_buf */ 215+ uInt sym_end; /* symbol table full when sym_next reaches this */ 216 217 ulg opt_len; /* bit length of current block with optimal trees */ 218 ulg static_len; /* bit length of current block with static trees */ 219@@ -325,20 +320,22 @@ void ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf, 220 221 # define _tr_tally_lit(s, c, flush) \ 222 { uch cc = (c); \ 223- s->d_buf[s->last_lit] = 0; \ 224- s->l_buf[s->last_lit++] = cc; \ 225+ s->sym_buf[s->sym_next++] = 0; \ 226+ s->sym_buf[s->sym_next++] = 0; \ 227+ s->sym_buf[s->sym_next++] = cc; \ 228 s->dyn_ltree[cc].Freq++; \ 229- flush = (s->last_lit == s->lit_bufsize-1); \ 230+ flush = (s->sym_next == s->sym_end); \ 231 } 232 # define _tr_tally_dist(s, distance, length, flush) \ 233 { uch len = (uch)(length); \ 234 ush dist = (ush)(distance); \ 235- s->d_buf[s->last_lit] = dist; \ 236- s->l_buf[s->last_lit++] = len; \ 237+ s->sym_buf[s->sym_next++] = dist; \ 238+ s->sym_buf[s->sym_next++] = dist >> 8; \ 239+ s->sym_buf[s->sym_next++] = len; \ 240 dist--; \ 241 s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 242 s->dyn_dtree[d_code(dist)].Freq++; \ 243- flush = (s->last_lit == s->lit_bufsize-1); \ 244+ flush = (s->sym_next == s->sym_end); \ 245 } 246 #else 247 # define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 248diff --git a/trees.c b/trees.c 249index 4f4a65011..decaeb7c3 100644 250--- a/trees.c 251+++ b/trees.c 252@@ -416,7 +416,7 @@ local void init_block(s) 253 254 s->dyn_ltree[END_BLOCK].Freq = 1; 255 s->opt_len = s->static_len = 0L; 256- s->last_lit = s->matches = 0; 257+ s->sym_next = s->matches = 0; 258 } 259 260 #define SMALLEST 1 261@@ -948,7 +948,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) 262 263 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 264 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 265- s->last_lit)); 266+ s->sym_next / 3)); 267 268 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 269 270@@ -1017,8 +1017,9 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc) 271 unsigned dist; /* distance of matched string */ 272 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 273 { 274- s->d_buf[s->last_lit] = (ush)dist; 275- s->l_buf[s->last_lit++] = (uch)lc; 276+ s->sym_buf[s->sym_next++] = dist; 277+ s->sym_buf[s->sym_next++] = dist >> 8; 278+ s->sym_buf[s->sym_next++] = lc; 279 if (dist == 0) { 280 /* lc is the unmatched char */ 281 s->dyn_ltree[lc].Freq++; 282@@ -1033,30 +1034,7 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc) 283 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 284 s->dyn_dtree[d_code(dist)].Freq++; 285 } 286- 287-#ifdef TRUNCATE_BLOCK 288- /* Try to guess if it is profitable to stop the current block here */ 289- if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { 290- /* Compute an upper bound for the compressed length */ 291- ulg out_length = (ulg)s->last_lit*8L; 292- ulg in_length = (ulg)((long)s->strstart - s->block_start); 293- int dcode; 294- for (dcode = 0; dcode < D_CODES; dcode++) { 295- out_length += (ulg)s->dyn_dtree[dcode].Freq * 296- (5L+extra_dbits[dcode]); 297- } 298- out_length >>= 3; 299- Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 300- s->last_lit, in_length, out_length, 301- 100L - out_length*100L/in_length)); 302- if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 303- } 304-#endif 305- return (s->last_lit == s->lit_bufsize-1); 306- /* We avoid equality with lit_bufsize because of wraparound at 64K 307- * on 16 bit machines and because stored blocks are restricted to 308- * 64K-1 bytes. 309- */ 310+ return (s->sym_next == s->sym_end); 311 } 312 313 /* =========================================================================== 314@@ -1069,13 +1047,14 @@ local void compress_block(s, ltree, dtree) 315 { 316 unsigned dist; /* distance of matched string */ 317 int lc; /* match length or unmatched char (if dist == 0) */ 318- unsigned lx = 0; /* running index in l_buf */ 319+ unsigned sx = 0; /* running index in sym_buf */ 320 unsigned code; /* the code to send */ 321 int extra; /* number of extra bits to send */ 322 323- if (s->last_lit != 0) do { 324- dist = s->d_buf[lx]; 325- lc = s->l_buf[lx++]; 326+ if (s->sym_next != 0) do { 327+ dist = s->sym_buf[sx++] & 0xff; 328+ dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8; 329+ lc = s->sym_buf[sx++]; 330 if (dist == 0) { 331 send_code(s, lc, ltree); /* send a literal byte */ 332 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 333@@ -1100,11 +1079,10 @@ local void compress_block(s, ltree, dtree) 334 } 335 } /* literal or match pair ? */ 336 337- /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 338- Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 339- "pendingBuf overflow"); 340+ /* Check that the overlay between pending_buf and sym_buf is ok: */ 341+ Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow"); 342 343- } while (lx < s->last_lit); 344+ } while (sx < s->sym_next); 345 346 send_code(s, END_BLOCK, ltree); 347 } 348