On timing side channels in “constant-time implementations”
摘要
Cryptographic software following sound, modern practices and adhering to recommendations for writing constant-time code (e.g., RFC 7748) may yet leak secret data via the most naïve kind of timing side channels when a “secure” implementation in a high-level language gets compiled down to assembly instructions. This paper shows that it is not only aggressive optimization done by smart compilers that leads to such vulnerabilities, as previously often thought, but also inherent limitations of the target CPU architecture that the compiler must work around, coupled with dangerous recommendations for instruction idioms found in the architecture documentation. The popular customizable IP core, Xtensa, is identified to be affected by the problem, and its particular vulnerability is studied and exploited. Key-recovery attacks are conducted against Xtensa-based ESP32 chips running ephemeral-static X25519 implementations found in wolfSSL and CycloneCRYPTO, both advertised as resistant against timing attacks and using two unrelated implementation strategies. The attacks are four orders of magnitude more effective than a similar attack against a related vulnerability in the MSVC compiler known in the literature. A resolution of the compiler bug responsible for the vulnerability is proposed. Finally, an optimized implementation of X25519 (Ed25519) and X448 (Ed448) field arithmetic for Xtensa, leveraging a DSP extension to the core instruction set, is proposed.