Paper 2024/536

Public-Algorithm Substitution Attacks: Subverting Hashing and Verification

Mihir Bellare, University of California San Diego
Doreen Riepel, CISPA Helmholtz Center for Information Security
Laura Shea, University of California San Diego
Abstract

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 (Public-Algorithm Substitution Attack), the big-brother adversary replaces the public algorithm 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 -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 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
A minor revision of an IACR publication in PKC 2025
Keywords
subversionalgorithm substitution attackshash functionssignaturesproof systemscertificates
Contact author(s)
mbellare @ ucsd edu
riepel @ cispa de
lmshea @ ucsd edu
History
2025-03-15: last of 5 revisions
2024-04-06: received
See all versions
Short URL
https://ia.cr/2024/536
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/536,
      author = {Mihir Bellare and Doreen Riepel and Laura Shea},
      title = {Public-Algorithm Substitution Attacks: Subverting Hashing and Verification},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/536},
      year = {2024},
      url = {https://eprint.iacr.org/2024/536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.