Public-Algorithm Substitution Attacks: Subverting Hashing and Verification

Summary

Algorithm Substitution Attacks (ASAs) have traditionally targeted secretly-keyed algorithms (for example, symmetric encryption or signing) with the goal of undetectably exfiltrating the underlying key. We initiate work in a new direction, namely ASAs on algorithms that are public, meaning contain no secret-key material. Examples are hash functions, and verification algorithms of signature schemes or non-interactive arguments. In what we call a PA-SA (PublicAlgorithm Substitution Attack), the big-brother adversary replaces the public algorithm f with a subverted algorithm, while retaining a backdoor to the latter. Since there is no secret key to exfiltrate, one has to ask what a PA-SA aims to do. We answer this with definitions that 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, formalizing strong definitions for the three goals, and then give 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. Our constructions serve to help defenders and developers identify potential attacks by illustrating how they might be built.