Paper 2024/536

Public-Algorithm Substitution Attacks: Subverting Hashing and Verification

Abstract

In the domain of algorithm substitution attacks (ASAs), we initiate work in a new direction, namely to consider such attacks on algorithms that are public, meaning contain no secret-key material. Examples are hash functions, and verification algorithms of signature schemes and non-interactive arguments. In what we call a PA-SA (Public-Algorithm Substitution Attack), the big-brother adversary replaces the public algorithm $f$ with a subverted algorithm, while retaining a backdoor to the latter. We consider big-brother's goal for the PA-SA to be three-fold: it desires utility (it can break an $f$-using scheme or application), undetectability (outsiders can't detect the substitution) and exclusivity (nobody other than big-brother can exploit the substitution). We start with a general setting in which $f$ is arbitrary, giving strong definitions for the three goals, and then a construction of a PA-SA that we prove meets them. We use this to derive, as applications, PA-SAs on hash functions, signature verification and verification of non-interactive arguments, exhibiting new and effective ways to subvert these. As a further application of the first two, we give a PA-SA on X.509 TLS certificates. While ASAs have been traditionally confined to exfiltrating secret keys, our work shows that they are possible and effective at subverting public functions where there are no keys to exfiltrate. Our constructions serve to help defenders and developers identify potential attacks by illustrating how they might be built.