Evaluating the LZO integer-overflow bug

In June, a security researcher disclosed an integer-overflow bug in the Lempel–Ziv–Oberhumer (LZO) compression algorithm—a bug that has persisted in the wild for roughly two decades, and is reproduced in multiple LZO implementations as well as in the related LZ4 algorithm. LZ4's author then accused the researcher of irresponsible disclosure and of over-hyping the issue for the sake of publicity. The two have subsequently argued back and forth about the proper assessment of the bug's severity, but wherever history eventually comes down on that particular question, the case holds lessons on a number of fronts for software developers.

Don A. Bailey published a June 26 blog post explaining the bug, which he had discovered during a code audit. In essence, Markus Oberhumer's original LZO code included a simple integer overflow in the code block that handles uncompressed "Literal Runs" in a compressed LZO file. The overflowed variable is later used as a size parameter, which an attacker can use to overflow a pointer and potentially gain access to a protected area of system memory. Importantly, as Bailey sees it, the original LZO reference code has essentially been copied verbatim into a wide variety of later LZO implementations, including OpenVPN, MPlayer2, Libav, FFmpeg, Btrfs, squashfs, Android systems, and the Linux kernel. Furthermore, the LZ4 algorithm developed by Yann Collet also reuses Oberhumer's reference code (including the bug), and LZ4 is also used in a variety of places, including the ZFS filesystem.

Bailey's original post not only described the bug in detail, but it went on to offer an assessment of the severity of the bug for real-world attacks. The Libav and FFmpeg versions of LZO are susceptible to remote code execution, he said, as are LZ4 implementations (although in the LZ4 case, such exploits are only practical on 32-bit architectures). On the other hand, denial-of-service attacks—while arguably less serious—are plausible on all LZO and LZ4 implementations. All of the possible attacks rely on specially crafted data payloads.

Collet fired back with a blog post of his own, the same day, calling Bailey's post "totally irresponsible" and an attempt "to create a flashy headline" by claiming that the bug is far more serious that it actually is. In reality, Collet said, the conditions required to exploit the bug in LZ4 are so peculiar that there is "no real-world risk", and that none of the known LZ4 implementations can be targeted. On June 28, Collet retracted some of his criticisms of Bailey's disclosure methodology but continued to argue that no known program met the conditions required to exploit the bug.

What followed was an at times heated back-and-forth between the two, both about the severity of the bug and about how it was disclosed. Collet noted that the underlying issue had been reported by someone else more than a year earlier and was deemed low-priority, mostly because the hypothetical attack would require that LZ4 be called with blocks of extremely large size (8MB or larger) and because a 64-bit system would require an implausibly large amount of memory to overflow the buffer. Bailey contended that there are plenty of 32-bit systems in the wild today (including most ARM devices) and that disinterest in future-proofing 64-bit implementations was short-sighted.

On July 1, Bailey posted a follow-up showing that LZ4 could be exploited with 2.47 MB of data. Collet again accused Bailey of irresponsible disclosure for publishing this follow-up without notifying the LZ4 project privately ahead of time.

As a practical matter, an update for LZ4 that fixes all of the issues cited by Bailey is already available, r119. The LZO reference implementation has also been updated with a fix, in version 2.08. Fixes have also been published for the affected downstream projects.

Assessing the real-world severity of the bug is, to a large degree, a matter on which reasonable people may never fully agree. It certainly requires separating the issue from Collet and Bailey's argument over disclosure practices—an argument that is not technical in nature. Bailey has written two posts that describe real-world attacks against LZ4 in the wild; one hinges on the fact that, while "real" users might never use LZ4 with exceptionally large block sizes, higher-level libraries often pass data down to algorithms like LZ4 without doing sanity checks. The second shows Bailey exploiting Firefox 30.0's video-playback code.

Lost in all of the debate about how plausible an attack is against LZ4, though, is a separate point raised in Bailey's original blog post. Oberhumer's reference code for LZO is the original source of the integer overflow, and because that reference code is believed to be highly optimized for decompression speed (which is, after all, one of LZO's key selling points), many developers copied it—flaws and all—into their own projects. Algorithms, Bailey said, become treated like "blessed" code, with other developers assuming their correctness and not giving them the same level of scrutiny that they might to other third-party work.

The potential harm of a long-standing bug or even a back-door in reference code is therefore magnified. Where the subject matter is regarded as highly specialized, things become even trickier. One can see echoes of this concern in the recent "too few independent implementations" issue that was cited as an objection to including Daniel J. Bernstein's Curve25519 cryptographic function in the W3C WebCrypto API. The odds may not be particularly high that Bernstein's code contains an exploitable bug, but the fact that so many developers implicitly trust its correctness is a cause for caution.

And cryptography is far from the only subject matter where widespread code reuse is commonplace. It is frequently found where low-level and highly-optimized functions are required. For example, virtually all—if not literally all—free-software raw photo software is built on top of Dave Coffin's dcraw decoder, which is released as ANSI C code typically copied into downstream projects.

However difficult it may be to craft a real-world exploit for LZO or LZ4, a key lesson is that the bug was replicated to a variety of downstream projects in part because the original reference code was not subjected to sufficient scrutiny sooner. A code audit did eventually uncover the flaw, but had that audit taken place years earlier, there would likely be far less outcry over the issue today.

Note: you can avoid this step in the future by logging into your LWN account.