Symbolon: Enabling Flexible Multi-device-based User Authentication

Hardware tokens are increasingly used to support second-factor and passwordless authentication schemes. While these devices improve security over weaker factors like passwords, they suffer from a number of security and practical issues. We present the design and implementation of Symbolon, a system that allows users to authenticate to an online service in a secure and flexible manner by using multiple personal devices (e.g., their smartphone and smart watch) together, in place of a password. The core idea behind Symbolon is to let users authenticate only if they carry a sufficient number of their personal devices and give explicit consent. We use threshold cryptography at the client side to protect against strong adversaries while overcoming the limitations of multi-factor authentication in terms of flexibility. Symbolon is compatible with FIDO servers, but improves the client-side experience compared to FIDO in terms of security, privacy, and user control. We design Symbolon such that the user can (i) authenticate using a flexible selection of devices, which we call 'authenticators'; (ii) define fine-grained threshold policies that enforce user consent without involving or modifying online services; and (iii) add or revoke authenticators without needing to generate new cryptographic keys or manually (un)register them with online services. Finally, we present a detailed design and analyse the security, privacy and practical properties of Symbolon; this includes a formal proof using ProVerif to show the required security properties are satisfied.