From 2e2e784de0605081af7c5c9d04a014af69888c2c Mon Sep 17 00:00:00 2001 From: Tom Rini Date: Tue, 10 May 2022 14:36:59 -0400 Subject: zlib: Port fix for CVE-2018-25032 to U-Boot While our copy of zlib is missing upstream commit 263b1a05b04e ("Allow deflatePrime() to insert bits in the middle of a stream.") we do have Z_FIXED support, and so the majority of the code changes in 5c44459c3b28 ("Fix a bug that can crash deflate on some input when using Z_FIXED.") apply here directly and cleanly. As this has been assigned a CVE, lets go and apply these changes. Link: https://github.com/madler/zlib/commit/5c44459c3b28a9bd3283aaceab7c615f8020c531 Reported-by: "Gan, Yau Wai" Signed-off-by: Tom Rini --- lib/zlib/deflate.c | 64 +++++++++++++++++++++++++++++++++++++++++------------- lib/zlib/deflate.h | 25 ++++++++++----------- lib/zlib/trees.c | 50 ++++++++++++------------------------------ 3 files changed, 74 insertions(+), 65 deletions(-) (limited to 'lib') diff --git a/lib/zlib/deflate.c b/lib/zlib/deflate.c index 63473359e45..4549f4dc12a 100644 --- a/lib/zlib/deflate.c +++ b/lib/zlib/deflate.c @@ -223,11 +223,6 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, int wrap = 1; static const char my_version[] = ZLIB_VERSION; - ushf *overlay; - /* We overlay pending_buf and d_buf+l_buf. This works since the average - * output size for (length,distance) codes is <= 24 bits. - */ - if (version == Z_NULL || version[0] != my_version[0] || stream_size != sizeof(z_stream)) { return Z_VERSION_ERROR; @@ -287,9 +282,47 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ - overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); - s->pending_buf = (uchf *) overlay; - s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); + /* We overlay pending_buf and sym_buf. This works since the average size + * for length/distance pairs over any compressed block is assured to be 31 + * bits or less. + * + * Analysis: The longest fixed codes are a length code of 8 bits plus 5 + * extra bits, for lengths 131 to 257. The longest fixed distance codes are + * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest + * possible fixed-codes length/distance pair is then 31 bits total. + * + * sym_buf starts one-fourth of the way into pending_buf. So there are + * three bytes in sym_buf for every four bytes in pending_buf. Each symbol + * in sym_buf is three bytes -- two for the distance and one for the + * literal/length. As each symbol is consumed, the pointer to the next + * sym_buf value to read moves forward three bytes. From that symbol, up to + * 31 bits are written to pending_buf. The closest the written pending_buf + * bits gets to the next sym_buf symbol to read is just before the last + * code is written. At that time, 31*(n-2) bits have been written, just + * after 24*(n-2) bits have been consumed from sym_buf. sym_buf starts at + * 8*n bits into pending_buf. (Note that the symbol buffer fills when n-1 + * symbols are written.) The closest the writing gets to what is unread is + * then n+14 bits. Here n is lit_bufsize, which is 16384 by default, and + * can range from 128 to 32768. + * + * Therefore, at a minimum, there are 142 bits of space between what is + * written and what is read in the overlain buffers, so the symbols cannot + * be overwritten by the compressed data. That space is actually 139 bits, + * due to the three-bit fixed-code block header. + * + * That covers the case where either Z_FIXED is specified, forcing fixed + * codes, or when the use of fixed codes is chosen, because that choice + * results in a smaller compressed block than dynamic codes. That latter + * condition then assures that the above analysis also covers all dynamic + * blocks. A dynamic-code block will only be chosen to be emitted if it has + * fewer bits than a fixed-code block would for the same set of symbols. + * Therefore its average symbol length is assured to be less than 31. So + * the compressed data for a dynamic block also cannot overwrite the + * symbols from which it is being constructed. + */ + + s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 4); + s->pending_buf_size = (ulg)s->lit_bufsize * 4; if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || s->pending_buf == Z_NULL) { @@ -298,8 +331,12 @@ int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, deflateEnd (strm); return Z_MEM_ERROR; } - s->d_buf = overlay + s->lit_bufsize/sizeof(ush); - s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; + s->sym_buf = s->pending_buf + s->lit_bufsize; + s->sym_end = (s->lit_bufsize - 1) * 3; + /* We avoid equality with lit_bufsize*3 because of wraparound at 64K + * on 16 bit machines and because stored blocks are restricted to + * 64K-1 bytes. + */ s->level = level; s->strategy = strategy; @@ -935,7 +972,6 @@ int ZEXPORT deflateCopy (dest, source) #else deflate_state *ds; deflate_state *ss; - ushf *overlay; if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { @@ -955,8 +991,7 @@ int ZEXPORT deflateCopy (dest, source) ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); - overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); - ds->pending_buf = (uchf *) overlay; + ds->pending_buf = (uchf *) ZALLOC(dest, ds->lit_bufsize, 4); if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || ds->pending_buf == Z_NULL) { @@ -970,8 +1005,7 @@ int ZEXPORT deflateCopy (dest, source) zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); - ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); - ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; + ds->sym_buf = ds->pending_buf + ds->lit_bufsize; ds->l_desc.dyn_tree = ds->dyn_ltree; ds->d_desc.dyn_tree = ds->dyn_dtree; diff --git a/lib/zlib/deflate.h b/lib/zlib/deflate.h index cbf0d1ea5d9..4c53b94af0b 100644 --- a/lib/zlib/deflate.h +++ b/lib/zlib/deflate.h @@ -211,7 +211,7 @@ typedef struct internal_state { /* Depth of each subtree used as tie breaker for trees of equal frequency */ - uchf *l_buf; /* buffer for literals or lengths */ + uchf *sym_buf; /* buffer for distances and literals/lengths */ uInt lit_bufsize; /* Size of match buffer for literals/lengths. There are 4 reasons for @@ -233,13 +233,8 @@ typedef struct internal_state { * - I can't count above 4 */ - uInt last_lit; /* running index in l_buf */ - - ushf *d_buf; - /* Buffer for distances. To simplify the code, d_buf and l_buf have - * the same number of elements. To use different lengths, an extra flag - * array would be necessary. - */ + uInt sym_next; /* running index in sym_buf */ + uInt sym_end; /* symbol table full when sym_next reaches this */ ulg opt_len; /* bit length of current block with optimal trees */ ulg static_len; /* bit length of current block with static trees */ @@ -318,20 +313,22 @@ void ZLIB_INTERNAL _tr_stored_block OF((deflate_state *s, charf *buf, # define _tr_tally_lit(s, c, flush) \ { uch cc = (c); \ - s->d_buf[s->last_lit] = 0; \ - s->l_buf[s->last_lit++] = cc; \ + s->sym_buf[s->sym_next++] = 0; \ + s->sym_buf[s->sym_next++] = 0; \ + s->sym_buf[s->sym_next++] = cc; \ s->dyn_ltree[cc].Freq++; \ - flush = (s->last_lit == s->lit_bufsize-1); \ + flush = (s->sym_next == s->sym_end); \ } # define _tr_tally_dist(s, distance, length, flush) \ { uch len = (length); \ ush dist = (distance); \ - s->d_buf[s->last_lit] = dist; \ - s->l_buf[s->last_lit++] = len; \ + s->sym_buf[s->sym_next++] = dist; \ + s->sym_buf[s->sym_next++] = dist >> 8; \ + s->sym_buf[s->sym_next++] = len; \ dist--; \ s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ s->dyn_dtree[d_code(dist)].Freq++; \ - flush = (s->last_lit == s->lit_bufsize-1); \ + flush = (s->sym_next == s->sym_end); \ } #else # define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) diff --git a/lib/zlib/trees.c b/lib/zlib/trees.c index 700c62f6d7b..970bc5dbc64 100644 --- a/lib/zlib/trees.c +++ b/lib/zlib/trees.c @@ -425,7 +425,7 @@ local void init_block(s) s->dyn_ltree[END_BLOCK].Freq = 1; s->opt_len = s->static_len = 0L; - s->last_lit = s->matches = 0; + s->sym_next = s->matches = 0; } #define SMALLEST 1 @@ -962,7 +962,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, - s->last_lit)); + s->sym_next / 3)); if (static_lenb <= opt_lenb) opt_lenb = static_lenb; @@ -1029,8 +1029,9 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc) unsigned dist; /* distance of matched string */ unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ { - s->d_buf[s->last_lit] = (ush)dist; - s->l_buf[s->last_lit++] = (uch)lc; + s->sym_buf[s->sym_next++] = dist; + s->sym_buf[s->sym_next++] = dist >> 8; + s->sym_buf[s->sym_next++] = lc; if (dist == 0) { /* lc is the unmatched char */ s->dyn_ltree[lc].Freq++; @@ -1045,30 +1046,7 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc) s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; s->dyn_dtree[d_code(dist)].Freq++; } - -#ifdef TRUNCATE_BLOCK - /* Try to guess if it is profitable to stop the current block here */ - if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { - /* Compute an upper bound for the compressed length */ - ulg out_length = (ulg)s->last_lit*8L; - ulg in_length = (ulg)((long)s->strstart - s->block_start); - int dcode; - for (dcode = 0; dcode < D_CODES; dcode++) { - out_length += (ulg)s->dyn_dtree[dcode].Freq * - (5L+extra_dbits[dcode]); - } - out_length >>= 3; - Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", - s->last_lit, in_length, out_length, - 100L - out_length*100L/in_length)); - if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; - } -#endif - return (s->last_lit == s->lit_bufsize-1); - /* We avoid equality with lit_bufsize because of wraparound at 64K - * on 16 bit machines and because stored blocks are restricted to - * 64K-1 bytes. - */ + return (s->sym_next == s->sym_end); } /* =========================================================================== @@ -1081,13 +1059,14 @@ local void compress_block(s, ltree, dtree) { unsigned dist; /* distance of matched string */ int lc; /* match length or unmatched char (if dist == 0) */ - unsigned lx = 0; /* running index in l_buf */ + unsigned sx = 0; /* running index in sym_buf */ unsigned code; /* the code to send */ int extra; /* number of extra bits to send */ - if (s->last_lit != 0) do { - dist = s->d_buf[lx]; - lc = s->l_buf[lx++]; + if (s->sym_next != 0) do { + dist = s->sym_buf[sx++] & 0xff; + dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8; + lc = s->sym_buf[sx++]; if (dist == 0) { send_code(s, lc, ltree); /* send a literal byte */ Tracecv(isgraph(lc), (stderr," '%c' ", lc)); @@ -1112,11 +1091,10 @@ local void compress_block(s, ltree, dtree) } } /* literal or match pair ? */ - /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ - Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, - "pendingBuf overflow"); + /* Check that the overlay between pending_buf and sym_buf is ok: */ + Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow"); - } while (lx < s->last_lit); + } while (sx < s->sym_next); send_code(s, END_BLOCK, ltree); s->last_eob_len = ltree[END_BLOCK].Len; -- cgit v1.2.3 From 26f981f295d00351b6f0c69b5317b254b2361cc0 Mon Sep 17 00:00:00 2001 From: Rasmus Villemoes Date: Thu, 19 May 2022 11:10:43 +0200 Subject: fdtdec: drop needlessly convoluted CONFIG_PHANDLE_CHECK_SEQ Asking if the alias we found actually points at the device tree node we passed in (in the guise of its offset from blob) can be done simply by asking if the fdt_path_offset() of the alias' path is identical to offset. In fact, the current method suffers from the possibility of false negatives: dtc does not necessarily emit a phandle property for a node just because it is referenced in /aliases; it only emits a phandle property for a node if it is referenced in somewhere. So if both the node we passed in and the alias node we're considering don't have phandles, fdt_get_phandle() returns 0 for both. Since the proper check is so simple, there's no reason to hide that behind a config option (and if one really wanted that, it should be called something else because there's no need to involve phandle in the check). Signed-off-by: Rasmus Villemoes Acked-by: Aswath Govindraju --- lib/Kconfig | 7 ------- lib/fdtdec.c | 7 ++----- 2 files changed, 2 insertions(+), 12 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index acc0ac081a4..884569f9b15 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -958,11 +958,4 @@ config LMB_RESERVED_REGIONS Define the number of supported reserved regions in the library logical memory blocks. -config PHANDLE_CHECK_SEQ - bool "Enable phandle check while getting sequence number" - help - When there are multiple device tree nodes with same name, - enable this config option to distinguish them using - phandles in fdtdec_get_alias_seq() function. - endmenu diff --git a/lib/fdtdec.c b/lib/fdtdec.c index e20f6aad9c2..ffa78f97ca0 100644 --- a/lib/fdtdec.c +++ b/lib/fdtdec.c @@ -516,11 +516,8 @@ int fdtdec_get_alias_seq(const void *blob, const char *base, int offset, * Adding an extra check to distinguish DT nodes with * same name */ - if (IS_ENABLED(CONFIG_PHANDLE_CHECK_SEQ)) { - if (fdt_get_phandle(blob, offset) != - fdt_get_phandle(blob, fdt_path_offset(blob, prop))) - continue; - } + if (offset != fdt_path_offset(blob, prop)) + continue; val = trailing_strtol(name); if (val != -1) { -- cgit v1.2.3