Note that non-repudiation is about convincing a third party (a judge): Alice signs a message and sends it to Bob, so that non only Bob is convinced that the message really comes from Alice and was not altered, but Bob can show it to Charlie and Charlie will be convinced, too. Here, you only have a client and a server, no third party, so "non-repudiation" is not relevant here. This more looks like an authentication problem.
The first answer is that it is not possible on the following grounds: the machine being fully compromised, the attacker could read its entire contents. The attacker may then run a clone of the machine in a virtual machine and let that clone talk with the server. The clone will report that all is well, while the attacker pillages the genuine system. From a cryptographer's point of view, a difference which can be made between two entities, from the outside (e.g. a genuine watchdog, and a fake one), only if they cannot compute the same things, and ability to compute equates to knowledge: the watchdog can compute an answer to the server that the attacker cannot fake only if the watchdog knows some secret data that the attacker does not, and, by construction, this does not happen.
The second answer is that it might be feasible but it requires that the conditions are right. If we look at the problem closely, we see that the attacker's goal is to talk with the server, emitting messages that the compromised machine cannot produce. This means that the watchdog can work reliably only if the compromise is destructive. For instance, suppose that:
- The client under supervision uses a set of system files (the operating system with its kernel and libraries and utilities).
- Under normal conditions, these files are not entirely known to the attacker (he may have copies of some or most of them, but not all).
- But the server knows all the files, exactly.
- A successful compromise necessarily "damages" at least one file (that's the tricky point) and the modified contents cannot be recovered afterwards by the attacker.
Under these conditions, then you can use the following:
- Make an archive of all the system files, in alphabetical order. The archive format must include the file names and contents and be deterministic: if you make the archive twice, you get twice the same output file, exact to the last bit. The archive file is not stored on disk or in RAM; it is hashed on-the-fly with SHA-256.
- Let K be the SHA-256 output. At regular intervals, the client talks to the server; the server sends a random challenge C, and the client responds with HMAC/SHA-256, computed over C and using K as key.
- The server uses his knowledge of the client files to recompute K and verify the HMAC output.
The challenge-response protocol with HMAC prevents replay attacks. MitM do not apply either. We really are in information-theoretic grounds here, not "normal crypto".
Unfortunately, it is very hard to ensure the conditions above. Secrecy of the device contents is almost impossible to achieve when the device is a consumer product (the attacker can buy other device instances, open them and look at all the contents), and most compromises are not destructive, at least as far as system files are involved: buffer overflows and similar vulnerabilities lead to RAM-only exploits, with no change whatsoever to system files.
Therefore what I expose here is more a theoretical concept than anything practical. However, this ought to help understand the issue: to prevent hidden alterations, the watchdog must own a "secret" which will not be revealed through a full compromise, which is kind of paradoxical and requires a bit of cheating with preposterous conditions.
