Cliptography: Clipping the Power of Kleptographic Attacks
Kleptography, introduced 20 years ago by Young and Yung [Crypto ’96], studies how to steal information securely and subliminally from cryptosystems. The basic framework considers the (in)security of malicious implementations of a standard cryptographic primitives by embedding a “backdoor” into the system. Remarkably, crippling subliminal attacks are possible even if the subverted cryptosystem produces output indistinguishable from a truly secure “reference implementation.” Bellare, Paterson, and Rogaway [Crypto ’14] recently initiated a formal study of attacks on symmetric key encryption algorithms, demonstrating a kleptographic attack that can be mounted in broad generality against randomized components of cryptographic systems. We enlarge the scope of current work on the problem by permitting adversarial subversion of (randomized) key generation; in particular, we initiate the study of cryptography in the full subversion model, where all relevant cryptographic primitives are subject to kleptographic attacks. We formally study one-way permutations and trapdoor one-way permutations in this “complete subversion” model, describing a general, rigorous immunization strategy to clip the power of kleptographic subversions. We augment this strategy with a “split program” model that can directly inform practical deployment. We then examine two standard applications of (trapdoor) one-way permutations in this complete subversion model. First, we consider construction of “higher level” primitives via black-box reductions. We showcase a digital signature scheme that preserves existential unforgeability when all algorithms (including key generation, which was not considered to be under attack before) are subject to kleptographic attacks. Additionally, we demonstrate that the classic Blum–Micali pseudorandom generator (PRG), using an “immunized” one-way permutation, yields a backdoor-free PRG. Second, we apply our general immunization strategy to directly yield a backdoor-free PRG. This notably amplifies previous results of Dodis, Ganesh, Golovnev, Juels, and Ristenpart [Eurocrypt ’15], which require an honestly generated random key. Alongside development of these secure primitives, we set down a hierarchy of kleptographic attack models which we use to organize past results and our new contributions; this taxonomy may be valuable for future work. ∗University of Connecticut, acr@cse.uconn.edu †Cornell University, qt44@cornell.edu ‡Google Inc.& Columbia University, moti@cs.columbia.edu §Virginia Commonwealth University, hszhou@vcu.edu