6

I was thinking. And I was searching the Internet. I want to check if there is more than I found. I considered asking on crypto.se. But the question might involve hardware and out of the box thinking.

If I have a threat model where

  • the adversary

    • wants to corrupt computation or steal information
    • does not want to be noticed at all (or at least until I made sensitive computation)
    • knows the software I use
    • does lie about and modify higher hardware such as CPUs before handing it out
    • can not access the hardware directly later
  • I

    • want to compute correctly and secretly (or and at least prevent theft of sensitive information)
    • want to exchange information with the outside
    • have access to mathematically verified software (and additionally have access to clean hardware for Bootstrapping only)
    • can check lower hardware such as wires for manipulation and can repair or rewire
    • can not check higher hardware for manipulation

In brackets (...) are some weakened requirements.

Thoughts:

I saw fully homomorphic encryption (FHE). It does arbitrary computation but encrypted. Wikipedia knows two open source projects that do that. They do not seem to be mature and tested. But I think FHE could do correct and secret computation. Authenticated output is also possible. But I can not check it by hand each time. If I want human-readable information the graphic card can manipulate everything.

I think that I could give two computers the same input. Then make them simulate the same program. And compare the output with some simple electronics. They can not talk to each other like this. That could work if they tried to do a wrong thing independently. Like if China and the USA do not share access to corrupted hardware. You buy one from each. They would not give access to half of the national hardware to the enemy. But they are intelligent and could use a key based approach. They could share the single key. Then your corrupted hardware does the wrong thing at the same time. It is not detected.

I think that I could make many computers do different little computations. And check the groups for correctness. But only keep the computation I wanted. They can not know what the others saw. They can not coordinate the moment to do the wrong thing. But there are problems. Real time is a good coordinator. I could compute, scramble and check. Greater patterns with rare events are good coordinators. I could use steganography. But it will not be good if there is no proof. But I think denying coordination and checking could work.

Questions:

An other thing is the verifiable electronics. I asked as a spin-off "How can a IC (or transistors or diodes) design make it difficult for a malicious manufacturer to subvert it undetected?" on Electronics. Unfortunately it was put on hold and will be closed as off-topic. It was not possible for me to make it fit “electronics design within the scope defined in the help center”. I did get a useful hint in this Kafkaesque story from user jbord39.

“It is called designed for trust, or DFT. Typically ring oscillators or heat transducers are used to verify that no malicious hardware has been squeezed into your filler space (since doing so will necessarily either increase power or increase nodal capacitance).”

I will update after I looked at it.

Anyways I do not see a way at the moment. Are there are working systems? I do not find any. Or there might be research? Or you have thought of a different way?

  • If your adversary has those goals and is also modifying your hardware then no software based solution is going to help you. You have to modify or create your own hardware that you know can keep a secret. – Numeron Dec 5 '16 at 23:23
  • @Numeron - I would not be so absolute. FHE is possible. Other things could also be. Also I can partly restrict the hardware. Read my thoughts if you are interested. – Gabriel Schulz Dec 5 '16 at 23:28
  • and what if your FHE is done on a bugged CPU, which you say may be the case? The CPU does all the thinking in a computer including the encryption and decryption so .... what then? – Numeron Dec 5 '16 at 23:32
  • @Numeron - If I understood correctly: It is not possible to steal the secret or authenticate as the program or influence the program. It can only stop execution. – Gabriel Schulz Dec 5 '16 at 23:39
  • Understood what correctly? Did you read that somewhere? The program runs on the CPU so anything the program does the CPU must be able to do in order to run the program... Maybe then a simpler example then might be bugged monitors/display screens that take regular screenshots. No amount of encryption inside a computer is going to help you there, because any data you want to see at any point your adversary will also see. – Numeron Dec 5 '16 at 23:53
2

This answer is a practical take on it. I'll not theorize about encryption, but will take a round trip to earlier attempts at secretive computation.

Whilst I do agree with Numeron that at some point you will need to transform the cyphertext into a plaintext to read its contents, and at that point there is nothing that can can protect you from hardware; The idea of running computations that cannot be tracked by hardware is neither new nor it actually requires encryption.

If we assume that FHE works and can perform any computation (which is a far fetched assumption for today), then you can build a computer that can receive a cyphertext, perform computations on it, and return another cyphertext. And all is fine. But one important point there, is that you must have a client that will provide that server with the cyphertext and will receive the returned cyphertext. That client must have hardware that you trust (i.e. that is not under the control of the adversary in any way), since it will need to encrypt and decrypt the cyphertext at some point.

If you want to dive deeper into the hardware remember that the X11 architecture is a client-server architecture. And, moreover (i.e. deeper), an IRQ number that will serve a piece of data over the system bus can be understood as a client-server architecture. In other words, at some point you need to have a client that you trust, there is no escape from that.

Now, funny enough, FHE is not needed to achieve secretive computation. More than 15 years ago a bunch of guys from Indiana University thought of Parasitic Computing. The idea is that you can perform computations on unsuspecting machines by injecting clever values into the TCP header checksum field (other methods are possible too). A machine's answer (e.g. bad checksum) will give you the result of the computing.

But why parasitic computing is secretive, since all computation happens in plain text over the network? Because the reassembly of the computations (if big enough and on a decent sized network) is comparable to encryption brute-forcing.

And it didn't stop there. We had similar ideas for parasitic storage.

So yeah, those links above are just proof of concept systems. Yet, quite doable. The only thing that the parasitic computing do not meet is the requirement:

have access to mathematically verified software (and additionally have access to clean hardware for Bootstrapping only)

Since bootstrapping a network does not really make sense.

(Extra note: figuring out if the X11 protocol could be used for parasitic computing, or even other protocols, is an interesting research idea.)

  • I read the two papers. Abusing the evaluation and feedback that you get for an input is an interesting idea. But Parasitic Computing with TCP headers is not secretive. Your ISP sees the same that you see. But there is not necessarily a smart "ISP" in every hardware. Also I win nothing with obscurity. "The adversary knows the software I use" and for that he does modify hardware. I can be open about the computation that I demand. But telling each one not too much is useful. It is necessary for "denying coordination" and then "checking could work". Thank you for your answer. – Gabriel Schulz Dec 7 '16 at 3:23
0

Relating to IC subversion, there is this excellent paper "Stealthy Dopant-Level Hardware Trojans" which presents two practical attacks on complex ICs. One of those attacks is a "side channel" leak: when running AES, the power consumption of the device depends on the key material. Power side-channel attacks are effective when the adversary can get hold of the device but not physically break into it without destroying it, such as attacks against smartcards.

Physically larger, simpler gates like 74-series logic are harder to undetectably trojan. "The Photon" on EE.SE has a point about this making it harder to hide other things - but you still have to perform destructive analysis of the chips in order to see it. It all depends on what level of analysis the modified part is expected to be subjected to. If you're building something out of individual discrete transistors in TO-92 plastic packages, without opening the package there could be anything hidden in there. Entire microcontrollers. Small radio transmitters.

As mentioned on the other thread, there is already a real problem with counterfeit and cloned parts coming from disreputable manufacturers. There's this little saga of electronic warfare: FTDI parts are cloned, but have slightly different behavior in software. So FTDI release drivers that break the cloned parts. Then users who thought they were buying genuine parts but have been conned find their circuits stop working.

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.