Can a device prove the identity of its own code?

Question

Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed the software when you weren't looking. An example might be a voting machine for a non-crypto scheme, or verifying that a motherboard is running the factory's firmware.

Is there any sort of data or verification protocol that can be used to prove which version of the software is being run, that doesn't require physically disassembling the hardware, and is resilient against even an attacker who knows about it and who specifically designs their variant software to try to spoof it?

If nothing about the hardware (and its capacity) is known ahead of time, then AFAIK this is impossible because the attacker can just virtualise the entire "correct" software and return whatever it produces. (Although please correct me if this isn't true) Since that's not a very interesting scenario, instead assume

• Both the verifier and the attacker have complete access to the "correct" software in machine code form.
• The machine's memory capacity is fixed and known ahead of time by both verifier and attacker. (Or more generally, the machine's hardware configuration is known, and the attacker has not modified it except via software reprogramming)
• If a handshake is involved, the verifier can be a trusted computer of arbitary capacity, not necessarily a human. (And so any computations the verifier has to do can be complicated so long as they're efficient.)
• If the system's "correct" software has to be prepared in some unusual but efficiently doable way beforehand for the scheme to work, assume that has happened by the verification step.
• Solutions that can be implemented in pure software are prefered, but solutions involving "small" hardware changes would also be acceptable. (Assume that simply replacing the program memory with ROM wasn't an option for whatever reason)

(As an example of what I'm looking for, one possible solution for this problem that occured to me was to construct the software image as normal, then pad it with random data up to the capacity of the machine's program memory. To verify, the verifier then provides the system a random number, the machine then computes the hash of that number prepended to the entire contents of its program memory (which it can't spoof because there's nowhere to store the "correct" copy to reproduce for this step) and gives that to the verifier. The verifier can then verify the hash the machine has given it against its own calculation. I haven't thought very hard about the implications of this scheme though, or how to attack it, so I think I'm missing some flaw in it. I'd also like to see if it's possible to achieve the same outcome without relying on there being a reasonably small capacity to fill.)

Answer 1

No, a device can't "prove the identity of its own code" assuming no hardware modification, if we want this secure and achieved automatically from arbitrary software image made available in machine form representing what's supposed to be the executable code, at least when said image is in part adversarially built (and arguably neither if it is built per common practice).

Whatever remotely gives demonstration of what code is running must be inherently trusted; it can not attest of its own integrity, as thought in the question.

The question's "As an example.." method has a weakness: some of the data hashed can be selectively rebuilt during the hash, rather than really present. The code for the modified hashing part would hash content of actual memory for the bulk of the software image, but synthesized data in the two zones (A) where itself is and (B) where some of the genuine hashing code was supposed to be (actually modified, e.g. by at least a JMP to modified hashing code in A). At runtime, A and B are never actually hashed/checked. A contains the modified hash code and data necessary to reconstruct what's synthesized when apparently hashing A or B; that data includes a copy of the original B, and a compressed form of what A contains in the arbitrary software image made available in machine form (it is impossible to automatically detect that it is not actually functional code/data).

The above argument assumes that the arbitrary software image made available in machine form was prepared specially to make the insertion of the modified hash code easy, using zone A of software that has no real functional value and instead is a placeholder for something adversarially prepared. However, the attack might often be possible assuming only that the software image contains a zone of sufficiently compressible data or code. I'm willing to accept that the attack could not be carried if the entire software image was initially crafted by a non-attacker taking care to code densely; but that goes against modern software construction practice.

---

The OP is explicitly targeting integrity of the software of voting machines. An example is this one, which (with different software) is still used in France in several cities (Le Havre, Brest..). The entire software is in a socketted EPROM. The integrity of the software is "demonstrated" by the software computing and displaying a CRC of itself on the display. That's of course a complete joke against an adversarial attack (and using a hash would not help much, for the code displaying the hash can be replaced by code displaying the appropriate constant).

The method proposed by the question (where the value displayed depends on a manual entry) would seem, on the face of it, to mitigate the attack where a modified software displays the hard-coded CRC or hash of the software it mimics. However, for the reasons I explain, that's not cryptographically strong against a skilled adversary. And worse, the challenges fed for remote attestation could be used as a side channel to control the rigging of the votes.

---

That interesting "yes" answer achieves its goal by adding a Trusted Platform Module (a secure CPU with a private key capable of signing, a certificate, and trusted code), and most importantly assuming integrity of trusted boot code of the main CPU, the CRTM. My reasoning above assumed non-integrity of all software, only integrity of hardware.

Integrity of trusted boot code makes a qualitative difference. That boot code can verify the integrity of the rest of the code by verifying a digital signature, with the public key (or the root of a chain of certificates) in the trusted boot code. That's in wide use (e.g. in Point of Sales terminals since the 1990s) and is a reasonably effective measure against unauthorized code modification. This alone is however not achieving what the question asks: that method can't remotely attest that any software is running; it only insures that only authorized software could run. And it remains quite vulnerable to modification/tampering, by debug mechanism allowing code injection (JTAG port, extra memory dynamically brought into the addressable space by a paging mechanism), and exploitation of software vulnerability bringing hostile code e.g. by buffer overflow (mitigation to the later are possible with Harvard architecture separating code and data, security rings, virtual machines, code proofs..).

To add attestation, the standard and working method is adding a capability to sign with a private key. A simple conceptual model is that the trusted boot code includes a Virtual Machine (e.g. JavaCard), verifies (by checking code signature as above) what code can run in that VM, and remotely attests of what it launched there together with a challenge to prevent replay (preferably by cryptographically signing or MACing, which requires a secret somewhere); it may even dynamically peek at what's in the VM and attest about it. Interpretation in a VM is not essential; principles for hardware equivalents running at native speed are known since 1960's mainframes. The TPM-locked PC can be viewed as a refinement of that, allowing remote attestation of what is running, under hypothesis reasonable on a consumer PC, including that some code responsible of the attestation is not altered.

Answer 2

Yes, with caveats^*, this is possible without modifying hardware assuming the device has a TPM. The verification technique is called remote attestation. A TPM can be used in this way to verify software's state, even if write protection is not possible. When a system first boots up, a read-only component of the BIOS called the CRTM (protected by hardware) sends a hash of the BIOS to the TPM, where it is stored in a register called a PCR. The BIOS then hashes the option ROMs (expansion ROMs) and MBR and the hashes are stored in another PCR. This chain of trust continues upward until the bootloader and kernel have been hashed. The TPM now will either unseal itself, or stay sealed based on whether or not all of its PCRs contain the expected hash values. If they do, the TPM knows that the system (down to the BIOS) has not been tampered with, and it unseals a secret value. This value cannot be spoofed, and it proves that everything up to the kernel has been verified sufficiently. Once the kernel is verified, various other technologies such as IMA can be used to further extend the chain of trust and verify the individual executables on the system.

The TPM itself cannot be spoofed or virtualized because it contains an Endoresment Key, or EK, defined by the Trusted Computing Group (TCG). This key is inserted at manufacture time for only certified devices and verifies that the TPM is genuine. Like the web PKI model, this relies on the secrecy of the signing key and the honesty and security of the groups which do the signing. This of course means that it is not perfect, but obtaining a rogue EK is not trivial.

A TPM provides the following guarantees:

• The state of firmware and software on the system can be verified in a chain of trust.

• Verification relies on the security of the hardware, not the software.

• The administrator will be able to verify the authenticity of the TPM itself.

• Boot configuration options that affect software will be verified.

I strongly recommend you read the paper I linked which explains all this and more.

_{* There are caveats. Obtaining a rogue EK will defeat this protection if an attacker can run a simulated TPM. This is possible for a nation state or a similarly advanced threat actor, but is non-trivial otherwise. Additionally, it must be implemented correctly according to the standards, which mandate, among other things, a hardware-protected read-only CRTM. If the implementation is incorrect, all bets are off.}

---

The other "no" answer considers the CRTM to be part of software, and thus untrusted according to the scope of OP's question. However, the CRTM is protected by hardware in the same way the CPU's internal logic is protected by hardware. It requires tampering with the hardware, not the software, to modify the CRTM or TPM. As such, the integrity of the CRTM can be assumed to be equivalent to the integrity of any other hardware component of the system. Relying on the CRTM does not imply relying on the integrity of any software on the system. From the linked paper:

A root of trust for measurement is a hardware device (or some functionality provided by hardware) that can reliably prepare certain measurements on the software state of a device. A root of trust for reporting is a hardware device (or some functionality provided by hardware) that can reliably attest to the result of a measurement. A root of trust for storage is a hardware device (or some functionality provided by hardware) that ensures that certain data such as cryptographic keys will be stored in a way that will always preserve their secrecy.

This is explicitly at odds with the "no" answer's claim that the CRTM counts as software and thus must be considered untrusted. This is how a hardware-based chain-of-trust operates.

Please see MARK One and AEM for real-life implementations of this.

Answer 3

No. I'd like to reword the original question that makes the correct answer blindingly obvious.

Can a voting machine be hacked?

The context.

Let's upgrade to the latest machines in the market (you may have used one of these):-

These feature Windows OS, Windows Server and Windows SQL Server software. Perhaps .Net or Visual C++ for the GUI. It's not some little DIY GRUB thing and a bit of assembler. It's literally millions and millions of lines of code running off hard disks, with networking and remote collation/audit/diagnostics across the Internet. Some have WiFi. They're probably remotely up-gradable too. And gigabytes of RAM, not ROM. Security through obscurity will feature heavily as that's a common safety blanket.

Why should they be secure?

There is little financial incentive to rigorously secure these machines due to a combination of DMCA, voter fraud and IP legislation, market dominance and lobbying power. So lets look at a device that has massive incentive to not be hacked - a Play Station. Hacking directly lowers the profitability, yet PS4 has now been hacked.

Trusted Platform Modules are useless.

Simply legally or illegally obtaining a TPM key breaks any security guarantees that might have been stated. Notwithstanding, you can't even hash large scale software. Cryptographic hashing of a plain text works, but software evolves and changes as it's used. You cannot simply hash a production SQL Server installation (including the database files, transaction logs and blobs) and expect a consistent digest. Remote updates would be tricky too. As would the Registry.

And not all code is even program byte code. T-SQL is held within a schema and can be easily changed so that Hillary wins. There's a reason why no one uses them.

Most importantly...

It's impossible, as what the question asks is can there be an un-hackable computer? Could a Windows based voting machine be impervious to all hacks, but all other worldly computers not? Some what unlikely. Don't forget that one of the fundamental definitions of a computer is as a general purpose computing engine. It's not a hammer, but even a hammer can be used on screws.