Abstract
A password-based mechanism is the most widely used method of authentication in distributed environments. However, because people are used to choosing easy-to-remember passwords, so-called ""weak-passwords,"" dictionary attacks on them can succeed. The techniques used to prevent dictionary attacks lead to a heavy computational load. Indeed, forcing people to use well-chosen passwords, so-called ""strong passwords,"" with the assistance of tamper-resistant hardware devices can be regarded as another fine authentication solution. In this paper, we examine a recent solution, the SAS protocol, and demonstrate that it is vulnerable to replay and denial of service attacks. We also propose an Optimal Strong-Password Authentication (OSPA) protocol that is secure against stolen-verifier, replay, and denial of service attacks, and minimizes computation, storage, and transmission overheads.