debreach: Selective Dictionary Compression to Prevent BREACH and CRIME

Abstract

Compression side-channel attacks like CRIME and BREACH have made compression a liability even though it is a powerful tool for improving efficiency. We present debreach, a step towards a general and robust mitigation for these attacks. A modified DEFLATE compressor with output that is fully backwards-compatible with existing decompressors, debreach has the ability to mitigate compression side-channels by excluding from compression sensitive data (e.g., security tokens, emails) identified either by explicit byte ranges or through string matching. In terms of usability, security, and efficiency, we find that string matching is well-suited to the task of protecting security tokens, but we also find that existing approaches to token security work equally as well. On the other hand, we find explicit byte ranges are well-suited to protect arbitrary content, whereas existing approaches lack in either efficiency or generality. When compared to the widely-used and insecure zlib in realistic scenarios, explicit byte ranges reduce throughput in networked connections by 16-24% on popular website's data, though this still results in a 106-269% improvement over not compressing depending on the available bandwidth. While the reduction is significant, we show that debreach can still improve throughput on connections between 112-208 Mb/s. We end with a discussion of practical use cases for debreach along with suggestions for their implementation and potential improvements to the algorithm.