  Time-based one-time password (TOTP) systems in use today require storing
secrets on both the client and the server. As a result, an attack on the server
can expose all second factors for all users in the system. We present T/Key, a
time-based one-time password system that requires no secrets on the server. Our
work modernizes the classic S/Key system and addresses the challenges in making
such a system secure and practical. At the heart of our construction is a new
lower bound analyzing the hardness of inverting hash chains composed of
independent random functions, which formalizes the security of this widely used
primitive. Additionally, we develop a near-optimal algorithm for quickly
generating the required elements in a hash chain with little memory on the
client. We report on our implementation of T/Key as an Android application.
T/Key can be used as a replacement for current TOTP systems, and it remains
secure in the event of a server-side compromise. The cost, as with S/Key, is
that one-time passwords are longer than the standard six characters used in
TOTP.
