ZipChannel: Cache Side-Channel Vulnerabilities in Compression Algorithms

While cache side-channel attacks have been known for over a decade, attacks and defenses have been mostly limited to cryptographic algorithms. In this work, we analyze the security of compression algorithms and their susceptibility to cache side-channels. We design TaintChannel, a tool that automatically detects cache side-channel vulnerabilities and apply the tool to compression software to conduct a study of vulnerabilities in popular compression algorithms—LZ77, LZ78, BWT—and their mainstream implementations. We discover that the implementation of all of these algorithms leak some or all of their input data via cache side-channels. This is concerning, as compression algorithms are widely used in software that operates on sensitive data (e.g., HTTPS). We demonstrate the practicality of these vulnerabilities via two end-to-end attacks on Bzip2. These attacks work in two different threat models and use different attack techniques. Our first attack targets compression within an SGX enclave using the Prime+Probe cache attack technique and extracts the entire input while it is being compressed with an accuracy greater than 99%. Because existing cache attack techniques fall short in targeting applications with larger memory footprint such as compression software, we develop new attack techniques for larger buffers. Our second attack works in the threat model when one application attacks a different application. It allows the attacker to identify which file is being compressed out of multiple options.