Request for patch review (brotli)
Hi fellow LTS folks,
I am working on the update for brotli as it relates to CVE-2020-8927.
The upstream Git project contains a commit [0] which fixes the issue
along with several other issues in the same commit. However, there does
not appear to be any available information regarding the specifics of
the vulnerability nor is there a PoC that can be used to validate the
fix. There also appears to be no prior iteration of the PR which
contains the changes in separate commits.
That said, I have done my best to exclude the parts of the upstream
commit that do not appear related to CVE-2020-8927 and then to backport
the remainder to brotli as it exists in stretch. I would like it if
someone else could review the attached patch, comparing it to the
upstream commit, and provide feedback on the completeness of the patch.
Please make sure to follow-up with a reply to the list before reviewing
so that there is not duplicate work on this.
Regards,
-Roberto
[0] https://github.com/google/brotli/commit/223d80cfbec8fd346e32906c732c8ede21f0cea6
--
Roberto C. Sánchez
http://people.connexer.com/~roberto
http://www.connexer.com
>From 223d80cfbec8fd346e32906c732c8ede21f0cea6 Mon Sep 17 00:00:00 2001
From: Eugene Kliuchnikov <eustas.ru@gmail.com>
Date: Wed, 26 Aug 2020 12:32:27 +0200
Subject: [PATCH] Update (#826)
* IMPORTANT: decoder: fix potential overflow when input chunk is >2GiB
[rcs: backport; also note that the upstream PR has many additional changes which were excluded from backporting]
---
common/constants.c | 15 +++++++++++++++
common/constants.h | 18 ++++++++++++++++++
dec/bit_reader.c | 11 +++++++++++
dec/bit_reader.h | 19 +++++++------------
dec/decode.c | 9 +++++----
dec/prefix.h | 18 ------------------
setup.py | 1 +
7 files changed, 57 insertions(+), 34 deletions(-)
--- a/dec/bit_reader.c
+++ b/dec/bit_reader.c
@@ -15,6 +15,17 @@
extern "C" {
#endif
+const uint32_t kBrotliBitMask[33] = { 0x0000,
+ 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
+ 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
+ 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
+ 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
+ 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
+ 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
+ 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
+ 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
+};
+
void BrotliInitBitReader(BrotliBitReader* const br) {
br->val_ = 0;
br->bit_pos_ = sizeof(br->val_) << 3;
--- a/dec/bit_reader.h
+++ b/dec/bit_reader.h
@@ -11,6 +11,7 @@
#include <string.h> /* memcpy */
+#include "../common/constants.h"
#include "../common/types.h"
#include "./port.h"
@@ -26,16 +27,7 @@
typedef uint32_t reg_t;
#endif
-static const uint32_t kBitMask[33] = { 0x0000,
- 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
- 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
- 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
- 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
- 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
- 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
- 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
- 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
-};
+ATTRIBUTE_VISIBILITY_HIDDEN extern const uint32_t kBrotliBitMask[33];
static BROTLI_INLINE uint32_t BitMask(uint32_t n) {
if (IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
@@ -43,7 +35,7 @@
"Unsigned Bit Field Extract" UBFX instruction on ARM. */
return ~((0xffffffffU) << n);
} else {
- return kBitMask[n];
+ return kBrotliBitMask[n];
}
}
@@ -92,8 +84,11 @@
}
/* Returns amount of unread bytes the bit reader still has buffered from the
- BrotliInput, including whole bytes in br->val_. */
+ BrotliInput, including whole bytes in br->val_. Result is capped with
+ maximal ring-buffer size (larger number won't be utilized anyway). */
static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
+ static const size_t kCap = (size_t)1 << 30;
+ if (br->avail_in > kCap) return kCap;
return br->avail_in + (BrotliGetAvailableBits(br) >> 3);
}
--- /dev/null
+++ b/common/constants.c
@@ -0,0 +1,15 @@
+/* Copyright 2013 Google Inc. All Rights Reserved.
+
+ Distributed under MIT license.
+ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+#include "./constants.h"
+
+const BrotliPrefixCodeRange
+ _kBrotliPrefixCodeRanges[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = {
+ {1, 2}, {5, 2}, {9, 2}, {13, 2}, {17, 3}, {25, 3},
+ {33, 3}, {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4},
+ {113, 5}, {145, 5}, {177, 5}, {209, 5}, {241, 6}, {305, 6},
+ {369, 7}, {497, 8}, {753, 9}, {1265, 10}, {2289, 11}, {4337, 12},
+ {8433, 13}, {16625, 24}};
--- a/common/constants.h
+++ b/common/constants.h
@@ -7,6 +7,9 @@
#ifndef BROTLI_COMMON_CONSTANTS_H_
#define BROTLI_COMMON_CONSTANTS_H_
+#include "./port.h"
+#include "./types.h"
+
/* Specification: 7.3. Encoding of the context map */
#define BROTLI_CONTEXT_MAP_MAX_RLE 16
@@ -37,6 +40,10 @@
BROTLI_MAX_NDIRECT + \
(24 << (BROTLI_MAX_NPOSTFIX + 1)))
+
+/* Specification: 4. Encoding of Literal Insertion Lengths and Copy Lengths */
+#define BROTLI_NUM_INS_COPY_CODES 24
+
/* 7.1. Context modes and context ID lookup for literals */
/* "context IDs for literals are in the range of 0..63" */
#define BROTLI_LITERAL_CONTEXT_BITS 6
@@ -44,4 +51,15 @@
/* 7.2. Context ID for distances */
#define BROTLI_DISTANCE_CONTEXT_BITS 2
+/* Represents the range of values belonging to a prefix code:
+ [offset, offset + 2^nbits) */
+typedef struct {
+ uint16_t offset;
+ uint8_t nbits;
+} BrotliPrefixCodeRange;
+
+/* "Soft-private", it is exported, but not "advertised" as API. */
+extern const BrotliPrefixCodeRange
+ _kBrotliPrefixCodeRanges[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
+
#endif /* BROTLI_COMMON_CONSTANTS_H_ */
--- a/dec/decode.c
+++ b/dec/decode.c
@@ -801,8 +801,8 @@
uint32_t code;
uint32_t nbits;
code = ReadSymbol(table, br);
- nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */
- return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits);
+ nbits = _kBrotliPrefixCodeRanges[code].nbits; /* nbits == 2..24 */
+ return _kBrotliPrefixCodeRanges[code].offset + BrotliReadBits(br, nbits);
}
/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
@@ -820,13 +820,14 @@
}
{
uint32_t bits;
- uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */
+ uint32_t nbits = _kBrotliPrefixCodeRanges[index].nbits;
+ uint32_t offset = _kBrotliPrefixCodeRanges[index].offset;
if (!BrotliSafeReadBits(br, nbits, &bits)) {
s->block_length_index = index;
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX;
return BROTLI_FALSE;
}
- *result = kBlockLengthPrefixCode[index].offset + bits;
+ *result = offset + bits;
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
return BROTLI_TRUE;
}
--- a/dec/prefix.h
+++ b/dec/prefix.h
@@ -14,24 +14,6 @@
#include "../common/constants.h"
#include "../common/types.h"
-/* Represents the range of values belonging to a prefix code: */
-/* [offset, offset + 2^nbits) */
-struct PrefixCodeRange {
- uint16_t offset;
- uint8_t nbits;
-};
-
-static const struct PrefixCodeRange
- kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = {
- { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2},
- { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3},
- { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4},
- { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5},
- { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8},
- { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12},
- {8433, 13}, {16625, 24}
-};
-
typedef struct CmdLutElement {
uint8_t insert_len_extra_bits;
uint8_t copy_len_extra_bits;
--- a/setup.py
+++ b/setup.py
@@ -121,6 +121,7 @@
brotli = Extension("brotli",
sources=[
"python/brotlimodule.cc",
+ "common/constants.c",
"common/dictionary.c",
"dec/bit_reader.c",
"dec/decode.c",
Reply to: