DATA - Differential Address Trace Analysis: Finding Address-based Side-Channels in Binaries

Cryptographic implementations are a valuable target for address-based side-channel attacks and should, thus, be protected against them. Countermeasures, however, are often incorrectly deployed or completely omitted in practice. Moreover, existing tools that identify information leaks in programs either suffer from imprecise abstraction or only cover a subset of possible leaks. We systematically address these limitations and propose a new methodology to test software for information leaks. In this work, we present DATA, a differential address trace analysis framework that detects address-based sidechannel leaks in program binaries. This accounts for attacks exploiting caches, DRAM, branch prediction, controlled channels, and likewise. DATA works in three phases. First, the program under test is executed to record several address traces. These traces are analyzed using a novel algorithm that dynamically re-aligns traces to increase detection accuracy. Second, a generic leakage test filters differences caused by statistically independent program behavior, e.g., randomization, and reveals true information leaks. The third phase classifies these leaks according to the information that can be obtained from them. This provides further insight to security analysts about the risk they pose in practice. We use DATA to analyze OpenSSL and PyCrypto in a fully automated way. Among several expected leaks in symmetric ciphers, DATA also reveals known and previously unknown leaks in asymmetric primitives (RSA, DSA, ECDSA), and DATA identifies erroneous bug fixes of supposedly fixed constant-time vulnerabilities. Tool Approach Finest Covered vulnerabilities False positives False Output Source code Tool granularity CF leak Data leak Deterministic Non-deterministic negatives Leaks Key dependency required available CacheAudit [24] Static analysis Cache line Leakage bound no CacheAudit 2 [25] Static analysis Byte address Leakage bound no CacheD [80] Combined Cache line Leak origin no ctgrind [50] Dynamic Byte address Leak origin yes Stacco [84] Dynamic (trace-based) Byte address a Leak origin no MI-Tool [41] Dynamic (attack-based) Cache line S S Leak origin generic yes Zankl et al. [89] Dynamic (trace-based) Byte address S S Leak origin HW no DATA Dynamic (trace-based) Byte address S S Leak origin generic, HW, etc. no a Only the first control-flow leak is reliably identified. Reporting multiple leaks could cause false positives.