Abstract: To establish secure network communications, a common practice requires that users authenticate one another and establish a temporary session key based on their passwords. Since users often use passwords that are easy to remember, attackers can correctly guess the passwords simply by searching through a relatively small space of "weak" passwords. In this paper, we present a new set of efficient protocols that can establish secure communications while protecting passwords from any feasible guessing and replay attacks. Our protocols avoid the use of timestamps altogether and minimize the use of nonces (random numbers). We examine some common attacks to existing protocols, and show how our protocols can be secure against such attacks. Our protocols apply to both secure peer-to-peer and multicast communications.