151. On the Security of a Universal Cryptocomputer: the Chosen Instruction Attack
- Author
-
Peter Schartner and Stefan Rass
- Subjects
Plaintext-aware encryption ,Theoretical computer science ,General Computer Science ,Computer science ,Cryptography ,02 engineering and technology ,security ,Encryption ,computer.software_genre ,Computer security ,Disk encryption hardware ,Watermarking attack ,Multiple encryption ,side-channel attack ,Ciphertext ,0202 electrical engineering, electronic engineering, information engineering ,General Materials Science ,applied cryptography ,Private function evaluation ,business.industry ,General Engineering ,Homomorphic encryption ,Client-side encryption ,020206 networking & telecommunications ,Disk encryption theory ,Deterministic encryption ,Ciphertext indistinguishability ,Disk encryption ,Symmetric-key algorithm ,Probabilistic encryption ,56-bit encryption ,40-bit encryption ,020201 artificial intelligence & image processing ,Link encryption ,Attribute-based encryption ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,On-the-fly encryption ,business ,Ciphertext-only attack ,computer ,lcsh:TK1-9971 - Abstract
The ultimate goal of private function evaluation is the complete outsourcing of processing tasks to distrusted platforms (such as clouds), so that arbitrary functions can be evaluated without any leakage of secret information. Several successful concepts have been proposed in the past, the most striking one having been fully homomorphic encryption besides the well-known garbled circuits and multiparty computation. In this paper, we look at an idealized model of outsourced computation, which we call a cryptocomputer . This is a (theoretical) machine that works exactly like a real-life computer in the sense of understanding a standard assembly language, but retaining all its internal signals, registers, and memory encrypted at all times. The encryption is assumed under a key that is unknown to the attacker, and taken as secure (in any cryptographically meaningful way), so that no leakage of information from any ciphertext can be expected from programs with reasonable (polynomial) time complexity. Unfortunately, such a cryptocomputer is necessarily insecure, irrespectively of how the encryption looks like. In particular, we explicitly do not assume any specific form of security (chosen-ciphertext or other) or (a)symmetry of encryption; our attack works only on ciphertexts and makes no assumptions whatsoever on the encryption. We prove insecurity of the cryptocomputer by taking the encryption as a black box, and show how to decipher every signal in the computer by pure virtue of submitting proper instructions for execution. Our attack falls into the general category of side-channel attacks, however unlike other related attacks, does neither exploit physical nor any logical characteristics of the underlying platform (besides the execution flow being observable). Somewhat surprisingly, it turns out that although the problem that we consider is cryptographic, it seemingly has no cryptographic solution and apparently calls for an interdisciplinary approach from new directions.
- Published
- 2016