Detecting failed attacks on human-interactive security protocols

One of the main challenges in pervasive computing is how we can establish secure communication over an untrusted high-bandwidth network without any initial knowledge or a Public Key Infrastructure. An approach studied by a number of researchers is building security though involving humans in a low-bandwidth "empirical" out-of-band channel where the transmitted information is authentic and cannot be faked or modified. A survey of such protocols can be found in a paper by Nguyen and myself.  Many protocols discussed there achieve the optimal amount of authentication for a given amount of human work.  However it might still be attractive to attack them if a failed attack might be misdiagnosed as a communication failure and therefore remain undetected.

In this paper we show how to transform protocols of this type to make such misdiagnosis essentially impossible.