International Association
for Cryptologic Research

Message authentication (MA) in the Short Authenticated String (SAS) model, defined by Vaudenay [28], 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 communi- cating over insecure network to establsh 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 chan- nels 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 [28,26,20] showed light-weight SAS-MA schemes, using only symmetric-key crypto and 3 communication flows, which is opti- mal [28]. In [21] this was extended to group SAS-(M)MA, for (mutual) message authentication among any number of parties, using two simulta- neous flows. We show a new two simultaneous flows SAS-(M)MA proto- col, 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 = gsk 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.