Paper 2020/418

Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing

Krzysztof Pietrzak

Abstract

Currently several projects (including DP-3T, east and west coast PACT, Covid watch) aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are very similar, and in their most basic from basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, their IDs of the last 14 days are published so other users can check if they have stored them locally and thus were close to an infected person. Vaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex \emph{interactive} schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. In this note propose a simple \emph{non-interactive} variant of the basic protocol that \begin{itemize} \item (security) Provably prevents replay and relay attacks. \item (privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened. \item (efficiency) The broadcasted message can fit into 128 bits and uses simple crypto (commitments and secret key authentication). \end{itemize} Towards this end we introduce the concept of ``delayed authentication", which basically is a message authentication code where verification can be done in two steps, where the first doesn't require the key, and the second doesn't require the message.