In 2004, Tsuji and Shimizu proposed a one-time password authentication protocol, named 2GR (Two-Gene-Relation password authentication protocol). The design goal of the 2GR protocol is to eliminate the stolen-verifier attack on SAS-2 (Simple And Secure password authentication protocol, ver.2) and the theft attack on ROSI (RObust and SImple password authentication protocol). Tsuji and Shimizu claimed that in the 2GR an attacker who has stolen the verifiers from the server cannot impersonate a legitimate user. This paper, however, will point out that the 2GR protocol is still vulnerable to an impersonation attack, in which any attacker can, without stealing the verifiers, masquerade as a legitimate user.

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.

We will propose a key-agreement-type three-party password-authenticated key exchange protocol. The proposed protocol is quite efficient and, among the same type of protocols, is the first to be formally proven to be secure. A three-party formal model for security proof is proposed based on [25] and [26]. We construct a simulator in this model to show that our proposed protocol is secure under reasonable and well-defined cryptographic primitives.