Can a device prove the identity of its own code?

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.)

• it's unclear if the verifier can just dump the rom and verify a checksum. – dandavis Apr 2 '17 at 19:42
• How do you stop the attacker lying in the dump? (e.g. "I'll hide my changes in the last page, hide a copy of the original dump routine in the second page, then patch the dump function to pretend everything is fine and the last two pages are empty.") – redroid Apr 2 '17 at 21:05
• with means that cannot by altered by the attacker. akin to cloning a hard drive and doing the forensics on the image, instead of trying to install some sort of tool on the machine in question. On an MCU, this might involve reading the eeprom chip itself in isolation with another device. the key is to to ask the patient how he feels, but to trust the lab results. – dandavis Apr 2 '17 at 21:08
• I meant to rule out reading the backing ROM via plugging it into another device when I said, "doesn't require physically disassembling the hardware." Unless you mean that the secondary dumper functionality is always there, which I guess does count, but I'm not sure how practically you could avoid a circularity problem because the attacker compromised the dumper. – redroid Apr 2 '17 at 21:11
• you don't (nessesarily) need to disassemble. consider the a module like the ESP8266-based NODEMCU; it exposes the pins connected to the internal "sd" interface. While normally nobody every uses those, they would allow independent verification of the memory contents, without the influence of any on-device config/code. i see no other way, since you can't trust the device itself. – dandavis Apr 2 '17 at 21:14

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.

• The question that I am answering assumes non-integrity of all software, only integrity of hardware. This is exactly what the TPM is for, protecting software given uncompromised hardware. The CRTM is part of hardware (that's why it's bootblock). This verification code can be present in e.g. the physical CPU (for fTPM). It's no more software than the CPU is. BTW, I think you may be misunderstanding SRTM and measured boot. There is no code that is responsible for the verification, or that code could be modified. It's all about the unsealing of a secret. – forest May 18 '18 at 6:07
• From the OP: Both the verifier and the attacker have complete access to the "correct" software in machine code form.. This is at odds with your bolded sentence. Same with "if a handshake is involved" in the OP, which is how STARK/MARK works. (btw I think you mean "Harvard", not "Harward") – forest May 18 '18 at 7:22
• @forest: I do not see how the question's Both the verifier and the attacker have complete access to the "correct" software in machine code form is at odds with "Whatever remotely gives demonstration of what code is running must be inherently trusted; it can not attest of its own integrity". In the question, "correct" software is what's supposed to run, not what actually runs after an attacker modified it. – fgrieu May 18 '18 at 8:05
• Is the issue simply that you consider the CRTM to be software and I consider it to be hardware? I fail to see why this is an issue at all because the TCG, the NSA, and MITRE all share this viewpoint (since they're the ones who defined the terminology). There are multiple answers on Security.SE which share the viewpoint as well, so I am a little confused why there is any disagreement here. Perhaps I should delete my answer and save it for the other SE site, since it's not being well-received here? – forest May 18 '18 at 8:14
• @forest If you believe what you write, do not delete. Your opinion is more valuable than the points. Now I know about TPMs. I didn't before. – Paul Uszak May 18 '18 at 20:38

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.

• I have no idea why you say TPMs are useless anymore than TLS is useless. This is factually untrue. "Simply" obtaining the EK is far from trivial. – forest May 17 '18 at 23:56
• @forest TPMs are useless for the reasons I stated, and that they do nothing to prevent hacking or executing spurious code. Are you suggesting they stop it? Can you explain how a TPM stops Registry mutation or a bad patch? Read wiki(TPM). Plus the FBI can obtain an EK key with one National Security Letter. Or does that not count? What's TLS got to do with this? – Paul Uszak May 18 '18 at 20:27
• Who said the TPM threat model involves preventing arbitrary code execution? – forest May 25 '18 at 6:45
• @forest Well I think that perhaps you've lost sight of the original question. It's not about TPM per se. I'm now convinced that TPM can secure an Arduino running the Blink program, but nothing more. The question relates to a voting machine and I've supplied you a picture of the current Windows + SQL Server + internet + WiFi enabled ones. Securing the boot process will have no effect on hacking it post boot. – Paul Uszak May 25 '18 at 11:36
• The question gave a voting machine as one example. "Proving the identity of its own code" != "proving that no code execution vulns have been exploited". – forest May 25 '18 at 13:20

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.

• Among other things that assumes the read-only component of the BIOS is actually what's run on boot, which seems quite antagonist with the question's "Assume that simply replacing the program memory with ROM wasn't an option". – fgrieu May 16 '18 at 9:18
• @fgrieu Remote attestation does not require putting the program in ROM. The CRTM itself is already present in ROM, and there is no need to modify it. OP need not put anything of his in ROM. – forest May 16 '18 at 12:47
• Apart from all of the other problems with this answer, obtaining an EK key is not hard for the determined. Either buy one from the guy who makes them at the factory, or if you're the FBI just ask for one as the TCG is within US jurisdiction. Or appeal to their greed as they have numerous US government contracts and will gladly fully cooperate to preserve them. – Paul Uszak May 17 '18 at 22:18
• I added a disclaimer that this answer only applies to a proper TPM implementation that follows the specifications correctly. I hope this is enough to appease the downvoters. – forest May 20 '18 at 12:15
• @forest Unfortunately not. You're still maintaining that a little piece of plastic in the box makes a modern computer voting machine un-hackable. – Paul Uszak Jul 24 '18 at 9:31