To whom am I speaking? Remote booting in a hostile world

We consider the problem of booting a workstation across a network. We allow "maintenance" (that is, change without notice by untrusted parties such as adversaries and system managers) to be freely performed upon the network, the workstation, and the remote boot service itself. We assume that humans are unable to recognise long sequences of independent bits such as cryptographic keys or checksums reliably, but can remember passwords which have been sufficiently poorly chosen to succumb to guessing attacks. We also assume that a part of the workstation hardware (including a small amount of ROM) can be physically protected from modification, but that the workstation cannot protect the integrity of any mutable data, including cryptographic keys (which must change if a secret is compromised.)Nevertheless, we are able to provide strong guarantees that the code loaded by the remote boot is correct, if the boot protocol says it is. The removal of maintenance and other attacks upon system integrity then becomes desirable in order to improve performance, rather than as a pre-requisite for ensuring correct behaviour. Our approach makes essential use of a hash function which is deliberately chosen so as to be rich in collisions, in contrast with prevailing practice.