0
$\begingroup$

Imagine a hypothetical system as follows:

  • A distributed algorithm running on a Local Area Network (LAN) that allows real-time addition and removal of processors.
  • The addition of a processor is considered trustless until proven otherwise (guilty until proven innocent).
  • Each processor in the system is given some process instructions, and a data stream to run said process instructions on over time.
  • An intruder (Eve) can add or remove hardware at any point, listen into any communications link between processors, and modify any signals coming from a compromised processor.

How to protect the system from Eve, without sacrificing too much computational power?

The biggest mystery to me is the hot-swappable processors, as communications between processors can be safeguarded with a myriad of well-known standard encryption methods. However, the security issue seems to go right down to "don't even let the processor know what its processing". Is there a way of encrypting both the process instructions and the data, whilst being able to perform useful computation still? If so, what are such processes called? Where can I learn more about them? Thanks in advance.

- EDIT - In the interest of clarity:

  • A process instruction is what is performed on a processor.
  • The task to be completed is a distributed algorithm. Aka, it is to be performed across multiple processors (all processors + LAN collectively), but those processors should not know what it is that they are trying to do so as to prevent Eve from knowing.
  • Processors are trusted to execute instructions given. However, it is assumed that Eve can replace the processor with one that leaks information regarding both data and process instructions.
  • Validation of process instructions received by a processor can occur. However, Eve can replace unprotected code without issue, so such validations may be skipped under such circumstances.

EDIT 2 - Answering fgrieu's questions:

A) The question's title asks if one can "encrypt a process" when the (updated) question does not define a process per se.

  • The "encrypt a process" is a sort of tl;dr of the question, summarising to the core aspect of the problem from my perspective.

B) "Process instructions" is defined as "what is performed on a processor"; is that a processor's instructions, data, or both?

  • Both a processor's instructions and the data being processed.

C) What should encryption protect: the processor's instructions, or/and some other data?

  • Both a processor's instructions and the data being processed.

D) In academic cryptography, encryption aims at confidentiality only; is integrity immaterial? More generally, what are Eve's goals?

  • Eve's primary goal is to determine the processor instructions (of which the data can be used to infer these instructions as well).
  • Eve's secondary goal is manipulate the program to perform self-destructive tasks.

E) Are processors trusted to hold a secret (key, or data they manipulate) and only use it per instructions they execute?

  • No. If a processor has been compromised, then it is expected that any and all information that processor receives and computes will be passed to Eve.
  • If both data and processor instructions are securely encrypted, then processors can be trusted due to an inability to decrypt said information.

F) Are processors trusted to not execute instructions given by Eve (perhaps, by checking a digital signature of instructions given to them before executing these?), in particular instructions that make use of a secret/private key they hold?

  • No. Any compromised processor is assumed to perform any function Eve has installed on them.
$\endgroup$
  • 1
    $\begingroup$ "Don't even let the processor know what it's processing" is homomorphic encryption. Homomorphic encryption however adds significant overhead. Simple identification / authentication of processors seems a more realistic option. $\endgroup$ – Maarten Bodewes Oct 20 '18 at 23:20
  • $\begingroup$ @fgrieu Thanks for the critique. I will update the question to better address the issues and make things clearer. $\endgroup$ – user3303504 Oct 21 '18 at 8:36
  • $\begingroup$ @MaartenBodewes Homomorphic encryption looks interesting, thanks =) Regarding identification and authentication of processors, if Eve can create a duplicate of a processor, except it leaks information, then it will become impossible to determine which processors are imposters or not. $\endgroup$ – user3303504 Oct 21 '18 at 9:12
  • $\begingroup$ @fgrieu see above for further clarity. Thank you for helping me to better express the question in a manner more useful for the community. $\endgroup$ – user3303504 Oct 21 '18 at 17:21
0
$\begingroup$

The conventional ways to tackle similar problems involve trusted processors. That is, trusting that non-compromised processors

  • Can keep secret the data they manipulate (including instructions, keys)
  • Work without error, neither miss-executing instructions, nor correctly executing instructions which have been incorrectly designed.
  • Authenticate ingoing data (including instructions) as coming from non-adversaries and non-compromised processors. This is performed with Message Authentication Codes or Digital Signatures.
  • Can exchange data in encrypted form.
  • Initially contain at least an appropriate secret adversaries do not know, a set of authentic instructions, and perhaps a unique identifier.

Note: from an academic standpoint, authentication and encryption are separate functions: the later aims at confidentiality only. However authenticated encryption can provide data confidentiality and integrity, and a fragment of the question makes senses only for encrypted implying integrity too:

if both data and processor instructions are securely encrypted, then processors can be trusted due to an inability to decrypt said information.

With the above assumptions, it is at least theoretically possible, with conventional networking and distributed computing techniques, to come out with instructions that will perform a computation in a distributed manner, and resist all adversarial attempts to produce an incorrect result that pass an authentication. Adversaries, and compromised processors (without the appropriate secrets) can't produce anything that non-compromised processors and users will accept. In theory, the worse an adversary can do is remove enough processors and suppress enough messages that no result will ever come out. It might even be possible to prove that a correct result will eventually come out if enough non-compromised processors (and their communication links) remain. In practice that is uneasy (in particular errors tend to creep in all but tiny list of instructions).

Ensuring confidentiality of instructions and data is even harder, including in theory. In particular, encryption of everything manipulated is not enough, because traffic analysis (measuring time of transmission and length of encrypted data exchanged) has the potential to leak what is performed, including data.

Despite these difficulties, modern distributed computing systems use trusted processors and achieve some level of security. One important technique that helps is layered security, where the practically inevitable security failure of a processor or set of instructions (due to bugs) is isolated as much as possible. That's a reason to use asymmetric cryptography (which aims to insure that compromise of a processor does not compromise the keys of other devices), and operating systems which attempt to isolate processes (with a useful level of success).


If on the other hand we make lesser hypothesis on the processors, we are moving into poorly charted territory.

As pointed in comment, potentially homomorphic encryption can ensure that non-trusted processors perform some computation but can't leak what they compute. It is also theoretically possible to ensure that if a rogue processor manages to alter the computation, the result fails an integrity check, as with trusted processors.

However homomorphic encryption tends to come at extremely high computational overhead, even without integrity thrown in. Making it feasible at all for simple common tasks is a research topic, and has been for long enough that many IT architects are tired. And I don't know if distributing homomorphically encrypted computation with some quantified level of tolerance to adversarial fault is even a research topic yet.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.