A robust and secure password (or key) change method between a user and an authentication server in a distributed communication network is disclosed. The protocol requires the exchange of only two messages between the user desiring the key change and the server, the user's request including, at least partly encrypted, an identification of the sending user, old and new keys, and two nonces, at least one including a time indication. The authentication server's response includes a possibly encrypted accept/reject indication and the regularly encrypted request from the user.