Cryptology ePrint Archive: Report 2015/808

Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks

Mihir Bellare and Joseph Jaeger and Daniel Kane

Abstract: We present new algorithm-substitution attacks (ASAs) on symmetric encryption that improve over prior ones in two ways. First, while prior attacks only broke a sub-class of randomized schemes having a property called coin injectivity, our attacks break ALL randomized schemes. Second, while prior attacks are stateful, ours are stateless, achieving a notion of strong undetectability that we formalize. Together this shows that ASAs are an even more dangerous and powerful mass surveillance method than previously thought. Our work serves to increase awareness about what is possible with ASAs and to spur the search for deterrents and counter-measures.

Category / Keywords: secret-key cryptography / mass surveillance, algorithm substitution attacks, kleptography, symmetric encryption

Original Publication (with major differences): 22nd ACM Conference on Computer and Communications Security (CCS), 2015
DOI: 10.1145/2810103.2813681

Date: received 13 Aug 2015, last revised 19 Aug 2015

Contact author: mihir at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20150819:151717 (All versions of this report)

Short URL: ia.cr/2015/808

Discussion forum: Show discussion | Start new discussion