Cryptology ePrint Archive: Report 2015/695

Cliptography: Clipping the Power of Kleptographic Attacks

Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou

Abstract: Kleptography, originally introduced 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 primitive by embedding a ``backdoor'' into the system. Remarkably, crippling subliminal theft is possible even if the subverted cryptosystem produces output indistinguishable from a secure ``reference implementation.'' After a long hiatus, interest in such issues was rekindled by the dramatic revelations of Edward Snowden, demonstrating that such deliberate attacks have been deployed and presumably used for massive surveillance. Notably, Bellare, Paterson, and Rogaway [Crypto '14] initiated a formal study of attacks on symmetric key encryption algorithms.

Motivated by the original examples of subverting key generation algorithms in the kleptography papers from Young and Yung [Crypto '96, Eurocrypt '97], we initiate the study of cryptography in the setting where \emph{all} algorithms are subject to kleptographic attacks---we call this {\bf cliptography}. As a first step, we formally study the fundamental primitives of one-way function and trapdoor one-way function in this ``complete subversion'' model. We describe a general, rigorous immunization strategy to clip the power of kleptographic subversions; concretely, we propose a general framework for sanitizing (trapdoor) one-way function index generation algorithms by hashing the function index, and prove that such a procedure indeed destroys the connection between a subverted function generation procedure and any possible backdoor. Along the way, we propose a split program model for practical deployment.

We then examine two standard applications of (trapdoor) one way functions in this complete subversion model. First, we consider construction of ``higher level'' primitives via black-box reductions. In particular, we show how to use our trapdoor one-way function to defend against key generation sabotage, and showcase a digital signature scheme that preserves existential unforgeability when {\em 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 our ``unforgeable'' one-way function, yields a backdoor-free PRG. Second, we generalize our immunizing technique to one way functions, and propose a new public immunization strategy to randomize the public parameters of a (backdoored) PRG. This notably contrasts with previous results of Dodis, Ganesh, Golovnev, Juels, and Ristenpart~[Eurocrypt '15], which require an honestly generated random key.

Thus, we develop fundamental cryptographic primitives with meaningful security guarantees in a quite adversarial setting, where one cannot rely on private randomness and all associated algorithms, including key and index generation, are under attack.

Category / Keywords: foundations / kleptography, massive surveiliance, cliptogrpahy

Date: received 10 Jul 2015, last revised 16 Aug 2015

Contact author: acr at cse uconn edu; qtang84@gmail com; motiyung@gmail com; hszhou@vcu edu