International Association
for Cryptologic Research

The recent Hertzbleed disclosure demonstrates how remote-timing analysis can reveal secret information previously only accessible to local-power analysis. At worst, this constitutes a fundamental break in the constant-time programming principles and the many deployed programs that rely on them. But all hope is not lost. Hertzbleed relies on a coarse-grained, noisy channel that is difficult to exploit. Indeed, the Hertzbleed paper required a bespoke cryptanalysis to attack a specific cryptosystem (SIKE). Thus, it remains unclear if Hertzbleed represents a threat to the broader security ecosystem. In this paper, we demonstrate that Hertzbleed's effects affect cryptosystems beyond SIKE. We demonstrate how latent gadgets in other cryptosystem implementations---specifically ``constant-time'' ECDSA and Classic McEliece---can be combined with existing cryptanalysis to bootstrap Hertzbleed attacks on those cryptosystems.

The scale and frequency of password database compromises has led to widespread and persistent credential stuffing attacks, in which attackers attempt to use credentials leaked from one service to compromise accounts with other services. In response, browser vendors have integrated password leakage detection tools, which automatically check the user’s credentials against a list of compromised accounts upon each login, warning the user to change their password if a match is found. In particular, Google Chrome uses a centralized leakage detection service designed by Thomas et al. (USENIX Security ’19) that aims to both preserve the user’s privacy and hide the server’s list of compromised credentials. In this paper, we show that Chrome’s implementation of this protocol is vulnerable to several microarchitectural side- channel attacks that violate its security properties. Specifically, we demonstrate attacks against Chrome’s use of the memory-hard hash function scrypt, its hash-to-elliptic curve function, and its modular inversion algorithm. While prior work discussed the theoretical possibility of side-channel attacks on scrypt, we develop new techniques that enable this attack in practice, allowing an attacker to recover the user’s password with a single guess when using a dictionary attack. For modular inversion, we present a novel cryptanalysis of the Binary Extended Euclidian Algorithm (BEEA) that extracts its inputs given a single, noisy trace, thereby allowing a malicious server to learn information about a client’s password. This paper was presented at USENIX Security 2023, and the full version can be found at https://www.usenix.org/system/files/usenixsecurity23-kwong.pdf

In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure—that is, it should be possible to extract the client’s data from any prover that passes a verification check. In this paper, we give the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski.Our first scheme, built from BLS signatures and secure in the random oracle model, features a proof-of-retrievability protocol in which the client’s query and server’s response are both extremely short. This scheme allows public verifiability: anyone can act as a verifier, not just the file owner. Our second scheme, which builds on pseudorandom functions (PRFs) and is secure in the standard model, allows only private verification. It features a proof-of-retrievability protocol with an even shorter server’s response than our first scheme, but the client’s query is long. Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.