Paper 2025/1654

Security without Trusted Third Parties: VRF-based Authentication with Short Authenticated Strings

Abstract

Message authentication (MA) in the Short Authenticated String (SAS) model, defined by Vaudenay, allows for authenticating arbitrary messages sent over an insecure channel as long as the sender can also transmit to the receiver a short authenticated message, e.g. d = 20 bits. The flagship application of SAS-MA is Authenticated Key Exchange (AKE) in the SAS model (SAS-AKE), which allows parties communicating over insecure network to establish a secure channel without prior source of trust except an ability to exchange d-bit authenticated strings. SAS-AKE is applicable e.g. for device pairing, i.e. creating secure channels between devices capable of displaying d-bit values, e.g. encoded as decimal strings, verified by a human operator, or to secure messaging applications like Signal or WhatsApp, where such short values can be read off by participants who trust each others’ voices. A string of works showed light-weight SAS-MA schemes, using only symmetric-key crypto and 3 communication flows, which is optimal. This was extended to group SAS-(M)MA, for (mutual) message authentication among any number of parties, using two simultaneous flows. We show a new two simultaneous flows SAS-(M)MA protocol, based on Verifiable Random Functions (VRF), with a novel property that the first flow, which consists of exchanging VRF public keys, can be re-used in multiple SAS-MA instances. Moreover, instantiated with ECVRF, these keys have the same form $vk = g^{sk}$ as Diffie-Hellman keys exchanged in DH-based (A)KE protocols like X3DH. We show that X3DH keys can be re-used in our SAS-MA, implying SAS-AKE which adds a minimal overhead of a single flow to X3DH. Crucially, while X3DH is secure only if participants’ public keys are certified by a shared source of trust, e.g. a Public Key Infrastructure (PKI) or a trusted Key Distribution Center (KDC) ran by Signal or WhatsApp, if X3DH is amended by our SAS-AKE then the established channel is secure even if PKI or KDC is compromised, assuming trust in user-assisted authentication of short d-bit strings.