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