Checking Passwords on Leaky Computers: A Side Channel Analysis of Chrome's Password Leak Detect Protocol

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 sidechannel attacks that violate its security properties. Specifically, we demonstrate attacks against Chrome's use of the memoryhard 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. * Work partially done while affiliated with the University of Michigan † Work partially done while affiliated with the University of Adelaide breaches. This in turn led to an increase of credential stuffing attacks, where attackers try using leaked credentials from one service to breach accounts on other services. Prior works have demonstrated that even post compromise, 6.9% of credentials remain valid due to reuse, often for years [50] . However, the wide availability of datasets of breached credentials also has the potential to enable browsers and password managers to actively alert users when their specific credentials are present in the dataset, protecting their account from the risk of compromise. Indeed, most browsers have launched some type of password alerting service, automatically checking all credentials entered for prior vulnerabilities. Their inclusion in a browser's default configuration, however, raises significant privacy concerns from users, as passwords have to be shared with a credential checking service. This prompted Google to incorporate a Private Set Intersection (PSI) protocol as part of Chrome's Password Leak Detection mechanisms [50], removing the need to share users' passwords or the server's list of compromised credentials. Another emerging threat to modern systems is the risk of side-channel attacks. With a plethora of microarchitectural attacks on cryptographic implementations, both from native code [2