IACR News item: 16 July 2015
Alexander Russell, Qiang Tang, Moti Yung, Hong-Sheng Zhou
ePrint Reportstudies how to steal information securely and subliminally from cryptosystems.
Secure cryptosystems can be broken if they are maliciously implemented
since the adversary may have some backdoors embedded in the implementation.
Although kleptographic attacks have been investigated about two decades ago,
for too long the possibility of kleptographic attacks have been dismissed and
been viewed only as a far-fetched theoretical concept.
This is dramatically changed when real-world examples were recently revealed
by Edward Snowden, demonstrating that such deliberate attacks
(directly inspired by the original work) exist and probably have been used for massive surveillance. In light of such possible failures of basic protective technology,
the security community started to seriously re-investigate this important issue: one notable example is the work of
Bellare, Paterson, and Rogaway [Crypto \'14], which initiated the formal studies 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 case that {\\em all} algorithms are subject to kleptographic attacks---we call it {\\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. And more interesting, we investigate the general immunization strategy to clip the power of kleptographic subversions; concretely, we propose a general framework for sanitizing the (trapdoor) one-way function generation algorithm by hashing the function index, and prove that such 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 the applications of (trapdoor) one way function secure in the complete subversion model in two ways. First we consider to build ``higher level\" primitives via black-box reductions. In particular, we consider 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.
Also 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 for one way functions, and
propose a new public immunization strategy to randomize the public parameters of a (backdoored) PRG. Since the previous result by Dodis, Ganesh, Golovnev, Juels, and Ristenpart~[Eurocrypt \'15] requires an honestly generated random key, construction of secure PRG in the complete subversion model was also open until our paper.
Additional news items may be found on the IACR news page.