Authenticating spontaneous interactions between devices and usersis challenging for several reasons: the wireless (and therefore invisible)nature of device communication, the heterogeneous nature of devicesand lack of appropriate user interfaces in mobile devices, and therequirement for unobtrusive user interaction. The most promisingapproach that has been proposed in literature involves the exploitationof so-called auxiliary channels for authentication to bridge thegap between usability and security. This concept has spawned theindependent development of various authentication methods and researchprototypes, that, unfortunately, remain hard to compare and interchangeand are rarely available to potential application developers. Wepresent a novel, unified cryptographic authentication protocol framework(UACAP) to unify these approaches and analyze its security properties.This protocol and a selection of auxiliary channels aimed at authenticationof mobile devices has been implemented and released in an open sourceubiquitous authentication toolkit (OpenUAT). We also present an initialuser study evaluating four of these channels.