Paper 2005/409

Intrusion-Resilient Authentication in the Limited Communication Model

David Cash, Yan Zong Ding, Wenke Lee, and Richard Lipton

Abstract

We describe a general technique for building authentication systems that resist compromises at the client side. We derive this resistance by storing key information on hardware fast enough for valid use but too slow for an intruder (e.g., a virus) to capture much of the key before being detected and removed. We give formal models for two types of protocols: user authentication and authenticated session-key generation. The first can be used for physical authentication tokens, e.g., used for gaining access to a building. The second can be used for conducting secure remote sessions on laptops that are occasionally infected by viruses. We present and analyze protocols for each of these tasks and describe how they can be implemented. With one example setting of parameters, in the case of user authentication, we are able to guarantee security for 6 months using a device storing 384MB, and in the key generation protocol, a 128GB drive guarantees that an adversary would need 700 days to compromise the key information. The model for intrusion resilience considered in this paper was first introduced by Dagon et al. \cite{DLL05} and motivated by the bounded storage model for cryptography \cite{Mau92}. Recently Dziembowski \cite{Dzi05} independently developed this model, and studied the same problems as the ones addressed in this paper. Our user authentication protocol is essentially the same as that of \cite{Dzi05}, while our authenticated session-key generation protocol builds on that of \cite{Dzi05}.